Лабораторная работа №3 Неор.граф поиск в глубину

2

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Лабораторная работа №3

по дисциплине

«Структуры и алгоритмы»

на тему:

«Программирование алгоритмов реализации и обработки графов»

Студент

Ельшаева Н.А.

^подпись, дата

^фамилия, инициалы

Группа

АС-09-1

Принял

Журавлева М.Г.

^ученая степень, звание

^подпись, дата

^фамилия, инициалы

Липецк 2010

1. Задание

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

Обход в глубину, неориентированный граф

2. Листинг программы

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <locale.h>

#include <windows.h>

struct graph

{

int key;

int depth;

};

graph *add(graph *mas,int kolvo)

{

int key,p=-1;

printf("\nВведите ключ узла: ");

scanf("%d",&key);

for(int i=0;i<kolvo;i++)

if(mas[i].depth==0)

{

p=i;

break;

}

if(p+1)

{

mas[p].key=key;

mas[p].depth=1;

return mas;

}

else

return NULL;

}

void output(bool **table,graph *mas,int kolvo)

{

printf("\n ");

for(int i=0;i<kolvo;i++)

printf("%d ",i);

for(int i=0;i<kolvo;i++)

{

printf("\n%d| ",i);

for(int j=0;j<kolvo;j++)

printf("%d ",table[i][j]);

}

printf("\n");

for(int i=0;i<kolvo;i++)

if(mas[i].depth)

printf("(%d\%d:%d)",i,mas[i].key,mas[i].depth);

}

bool prov(bool **table,graph *mas,int kolvo,int p)

{

for(int i=0;i<kolvo;i++)

if(table[p][i]==true)

return true;

return false;

}

bool **bond(graph *mas,bool **table,int kolvo)

{

int k1,k2,p1=-1,p2=-1;

printf("\nВведите значения двух узлов: ");

scanf("%d %d",&k1,&k2);

for(int i=0;i<kolvo;i++)

{

if(mas[i].key==k1)

p1=i;

if(mas[i].key==k2)

p2=i;

}

if((p1+1)&&(p2+1)&&(p1!=p2))

{

if(!prov(table,mas,kolvo,p2))

mas[p2].depth=mas[p1].depth+1;

else if(!prov(table,mas,kolvo,p1))

mas[p1].depth=mas[p2].depth+1;

if(!table[p1][p2])

{

table[p1][p2]=true;

table[p2][p1]=true;

}

}

else

{

printf("\nОдин или оба элемента не существуют, или вы ввели одинаковые значения");

getch();

}

return table;

}

int *round(graph *mas,int *mas1,bool **table,int kolvo,int p)

{

mas1[p]=1;

printf("\n%d",mas[p].key);

for(int i=0;i<kolvo;i++)

if(table[p][i] && mas[i].depth==mas[p].depth+1 && !mas1[i])

mas1=round(mas,mas1,table,kolvo,i);

return mas1;

}

void inf(graph *mas,bool **table,int kolvo)

{

int key,p;

printf("\nО каком узле вы хотите просмотреть информацию?");

scanf("%d",&key);

for(int i=0;i<kolvo;i++)

if(mas[i].key==key)

p=i;

printf("\nУзел с этим ключом имеет глубину %d",mas[p].depth);

for(int i=0;i<kolvo;i++)

if(table[p][i])

printf("\nЭтот узел связан с узлом %d",mas[i].key);

getch();

}

void menu()

{

int kolvo;

int key=-1;

char p;

printf("\nСколько элементов будет в графе? ");

scanf("%d",&kolvo);

int *mas1=(int*)malloc(kolvo*sizeof(int));

graph *dop,*mas=(graph*)malloc(kolvo*sizeof(graph));

bool **table=(bool**)malloc(kolvo*sizeof(bool*));

for(int i=0;i<kolvo;i++)

{

mas[i].depth=0;

mas1[i]=0;

table[i]=(bool*)malloc(kolvo*sizeof(bool));

for(int j=0;j<kolvo;j++)

table[i][j]=false;

}

while(true)

{

system("cls");

printf("Что хотите сделать?\n1.Добавить узел\n2.Вывести таблицу графа\n3.Создать связь между узлами\n4.Вывести информация о ключе\n5.Обход\n6.Выход");

p=getch();

switch(p)

{

case '1':

if(dop=add(mas,kolvo))

{

mas=dop;

printf("\nОперация произведена успешно!");

}

else

{

printf("\nОперация завершилась неудачей, возможно количество элементов достигло максимума");

getch();

}

break;

case '2':

output(table,mas,kolvo);

getch();

break;

case '3':

table=bond(mas,table,kolvo);

break;

case '4':

inf(mas,table,kolvo);

break;

case '5':

key=-1;

for(int i=0;i<kolvo;i++)

if((mas[i].key+1) && mas[i].depth==1)

{

key=i;

break;

}

if(key+1)

round(mas,mas1,table,kolvo,key);

else

printf("\nНе найдено ни одного элемента");

getch();

break;

case '6':

exit(1);

break;

}

}

}

void main()

{

setlocale(LC_ALL,"Rus");

menu();

}

3. Контрольный пример

4. Блок-схема

5. Вывод

При выполнении данной лабораторной работы я получила навыки программирования графов.

6. Список использованной литературы

1. Шилдт Г. Искусство программирования на C++. БХВ.2005

2. Шилдт Г. C++ Руководство для начинающих. Вильямс.2005

3. Страуструп Б. Язык программирования С++. Специальное издание, 3-изд. Бином.2004