void proga() – эта функция содержит в себе все выше перечисленные, поэтому она создает первые элементы 1-ой и 2-ой очередей и добавляет в них новые элементы. Также эта функция выводит на экран полученные очереди, то есть выводит на экран все элементы двух очередей, после чего функция производит сравнение: входит ли 1-я очередь во 2-ю, и выводит результат на экран.

3. ИСПОЛЬЗОВАНИЕ ДИНАМИЧЕСКИХ СТРУКТУР ПРИ РАБОТЕ С ГРАФАМИ

3.1. Способы представления графов

Для представления графа можно использовать матрицу смежности, матрицу инцидентности либо представить его списком дуг.

Основные способы представления (задания) графов:

1) перечисление множеств V (вершин) и E (ребер), задающих граф. G = (V, E);

2) матричные способы описания;

Пусть G = (V, E), |V| = p, а |E| = q, тогда:

a) матрица смежности – квадратная матрица

, где

b) матрица инцидентности – прямоугольная матрица

3) список дуг:

Пример: задан граф G = (V, E), где V = {v1, v2, v3, v4}, E = {v1v2, v2,v3, v1v3, v1v4, v3,v4} = {e1, e2, e3, e4, e5}. Рисунок 3.1.

Рисунок 3.1. – Пример построения графа

В данной программе граф представлен списком дуг, в котором каждая вершина содержит информацию о смежном ей ребре, а каждое ребро содержит информацию о тех вершинах, которые ей смежные. Этот способ более экономичен в плане использования памяти.

head: NULL

Рисунок 3.2. – Пример связности ребер графа

3.2. Операции над графами

При связанном хранении каждая вершина графа представляет собой структуру graf, состоящую из двух элементов: v1,v2 - предназначены для хранения вершин графа, next - для указателя на структуру, содержащую следующую вершину графа. На первые элементы графа указывает указатель head. Для всех операций над графом используется описание:

typedef struct graf

{ int v1,v2;

struct graf* next;

} Graf;

Graf *g, *head, *temp;

Для реализации операций могут использоваться следующие фрагменты программ:

1) определить первый элемент в линейном списке (рисунок 3.1):

printf("v1=");

scanf("%d",&head->v1);

head->next=0;

NULL

head NULL

Рисунок 3.3– Создание первого элемента в графе

2) вставить дополнительный элемент после указанного узла (рисунок 3.2):

printf("v=");

scanf("%d",&g->v1);

g->next=head;

head=g;

…. .

head NULL

Рисунок 3.4– Вставка дополнительного элемента

3) печать всех элементов списка:

printf("Ребра графа: \n");

g=head;

i=0;

while(g! =NULL) {

i++;

printf("РЕБРО%d: v1=%d v2=%d\n", i,g->v1,g->v2);

g=g->next; }

4) удаление ребра:

Удалить ребро означает разрушить связь между вершинами, которые являются для данного графа концевыми.

5) удаление вершины:

if((head->v1==i) ||(head->v2==i))

head=head->next;

else{

temp=head;

g=head->next;

while(g) {

if((g->v1==i) ||(g->v2==i)) {

temp->next=g->next;

free(g);

break; }

temp=g;

g=g->next; }}

Удалить вершину означает разрушить связь со смежными ей вершинами и создать новую связь уже без этой вершины. Схема удаления вершины графа, следующей за узлом, на который указывает р находится на рисунке 3.3.

Рисунок 3.5– Схема удаления вершины графа

3.3. Описание программной реализации

Данная программа реализована при помощи всего двух функций, которые в полной мере выполняют поставленную перед программой задачу. Задачей является поиск висячих вершин в графе и удаление одной из них, которую укажет пользователь.

Висячей вершиной графа называется такая вершина, степень которой равна единице, то есть вершина, которая имеет всего лишь одно смежное ей ребро. Граф, содержащий висячую вершину изображен на рисунке 3.4.

3 2

4 5

Рисунок 3.6– Изображение графа, содержащего висячую вершину

Степени вершин в данном графе таковы: 11, 23, 32, 42, 52, из этого следует, что изолированной вершиной является вершина под номером 1.

Список ребер до удаления висячей вершины в этом графе будет иметь вид: ребо1: 1-2, ребро2: 2-3, ребро3: 3-4, ребро4: 4-5 и ребро5: 5-2.

После удаления единственной висячей список ребер примет вид: ребро1: 2-3, ребро2: 3-4, ребро3: 4-5 и ребро4: 5-2.

Каждая функция данной программы полностью выполняет поставленную перед ней задачу. Первая функция klavа создает первую вершину графа и предлагает пользователю дополнить граф другими вершинами. Функция реализована таким способом, что пользователь вводит вершины попарно, то есть вводит вершины одного ребра. Вторая функция raschet производит поиск висячих вершин графа и, если они имеются, предлагает пользователю выбрать одну из них для ее удаления и удаления смежного ей ребра. В завершение программы на экран пользователю выводится обновленный список ребер введенного графа.

3.3.1. Описание процедур и функций языка

void *malloc(size_t size) – данная функция используется для выделения памяти из кучи в байтах. Для таких информационных структур, таких как деревья и списки выделение памяти происходит таким же способом

void free(void *block) – данная функция очищает память, которая была выделена такими функциями как calloc, malloc или realloc.

3.3.2. Описание созданных функций для работы с динамической памятью, графами

Создание и поддержание динамических структур данных требует динамического распределения памяти: возможности в процессе выполнения программы увеличивать область памяти для хранения новых узлов и освобождать ресурсы памяти, в которых уже нет необходимости. Пределы динамического выделения памяти ограничены только объемом доступной физической памяти или доступной виртуальной памяти в системах с виртуальной памятью. Впрочем, часто эти пределы намного меньше из-за того, что свободная память делится при совместном доступе к ней многих пользователей.

void klava() – данная функция является универсальной, так как изначально она создает первый элемент (первую вершину графа), после чего пользователю предлагается дополнить граф новыми элементами (вершинами). Функция использует стандартную функцию для выделения памяти языка С: malloc.

void raschet() – функция, которая производит ряд проверок в полученном графе на наличие висячих вершин, после чего пользователю предлагается сделать выбор какую из висячих вершин нужно удалить, если таковые имеются. В конечном итоге на экран выводится список ребер графа после удаления висячей вершины.

ВЫВОДЫ

Желание каждого программиста быть востребованным ставит перед ним определенную цель: идти в одну ногу со временем. С каждым годом это делать становиться все сложнее и сложнее, так как за определенные промежутки времени темпы развития компьютерных технологий постоянно увеличиваются. Задача, которую ставит перед собой программист при разработке нового продукта остается неизменной уже на протяжении долгого времени: получение максимального результата при минимуме затрат времени и средств. Выполнение данной задачи становится возможной только при постоянном самосовершенствовании и самообразовании программиста.

Задание, выданное на летнюю практику, поставило определенные задачи:

1) Научится создавать связные структуры данных, используя указатели;

2) научится создавать и манипулировать динамическими структурами данных, такими как связные списки, очереди и стеки;

3) понять работу различных приложений со связными структурами данных.

Решение выданного задания было реализовано с помощью языка программирования С.

С обладает множеством преимуществ. Он является современным языком программирования, включающим в себя управляющие структуры, наличие которых в языке считается желательным с точки зрения теории и практики программирования. Этот язык построен так, что позволяет естественным образом применять планирование сверху – вниз, структурный подход к программированию, модульное проектирование программ. В результате на С получаются более надежные и “прозрачные программы”.

Вот почему именно язык С был выбран автором для реализации данной задачи.

Структуры – это составные типы данных, построенные с использованием других типов. Классы в С++ являются естественным продолжением структуры struct в С. Вот почему детальное изучение этого раздела является таким необходимым для дальнейшего изучения других языков программирования. Так как прежде чем рассматривать специфику разработки классов на С++ нужно более глубоко разобраться со структурами в С.

Приложение А

ЛИСТИНГ ПРОГРАММЫ

Задание №1:

#include<stdio. h>

#include<conio. h>

#include<alloc. h>

#include<string. h>

#include<stdlib. h>

// ------------<Структура>---------

typedef struct sp

{

char inf [100] ;

struct sp *next;

} sp;

sp *g,*head,*teil;

// -----------</Структура>---------

void titl()

{

clrscr();

gotoxy(20,1);

printf("МИHИСТЕРСТВО ОБРАЗОВАHИЯ И HАУКИ УКРАИHЫ");

gotoxy(12,2);

printf("Донецкий государственный институт искусственного интеллекта");

gotoxy(27,8);

printf("Здание на летнюю практику #1");

gotoxy(35,9);

printf("по дисциплине: ");

gotoxy(17,10);

printf("\"Основы программирования и алгоритмические языки. \"");

gotoxy(50,15);

printf("Выполнил: ");

gotoxy(50,16);