Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Курсовая работа по “Структурам данных и алгоритмам”

Министерство Образования и науки Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра ПМИ

Курсовая работа по дисциплине

“Структуры данных и алгоритмы”

Факультет: ПМИ

Группа: Пми-51

Студент: Коновалов В.О.

Преподаватель: Шапошникова Т. А.

Новосибирск, 2006

1.Условие задачи

(№56 – Касьянов) Найти минимальное подмножество вершин заданного орграфа, от которых достижимы все остальные его вершины.

2.Анализ задачи

Дано: Входной файл “D:\input.txt”.

Представление данных: <Граф>

<Граф>:= <Список вершин> {<Список дуг>}

<Список вершин>:=<Название вершины> {<,> <Название вершины>}

<Список дуг>:=<Дуга> {<Дуга>}

<Название вершины>:=<Символ>{<Символ>}

<Символ>:=<a> || <b> || … || <z> || <0> || <1> || … || <9> || < > || <A> || <B> || … || <Z>

<Дуга>:=<\n> <Название вершины> <-> <Название вершины>

Результат: Выходной файл “D:\output.txt”.

Представление данных: <Подмножество вершин>

<Подмножество вершин>:=<Название вершины> <,>{<Название вершины> < >}

<Название вершины>:=<Символ>{<Символ>}

<Символ>:=<a> || <b> || … || <z> || <0> || <1> || … || <9> || < > || <A> || <B> || … || <Z>

Метод решения:

Создаём матрицу-дуг (матрица дуг – матрица размером количество вершин на количество вершин графа, где строчка – одна вершина, а ячейка из этой строчки равна 1, если из этой вершины есть дуга в вершину, с номером, совпадающим с номером столбца, и равна 0 в противном случае).
Создаём матрицу-путей (матрица путей – матрица размером количество вершин на количество вершин графа, где строчка – одна вершин, а ячейка из этой строчки равна 1, если из этой вершины есть путь в вершину, с номером, совпадающим с номером столбца, и равна 0 в противном случае).

все элементы Матрица-путей_i,i=1, Остальные элементы = 0;
запоминаем номер строчки, которую мы проверяем на пути (например l), а так же кладём её в стек.
перебираем элементы по строчке i в Матрице дуг, пока он не равен 1, и элемент Матрица_{l,столбец}, не равен 1, и пока не конец строки i,
если конец строки i, то берём элемент из стека. Если стек не пуст, то смотрим, что за элемент там лежит (приравниваем i этому элементу), но не забираем, иначе выход из определения путей для этой строки.
если не конец строки, то i приравниваем столбцу который мы нашли, помещаем номер этой вершины в стек, Матрица-путей_l,i=1;

Анализируем матрицу путей. Берём подмножество вершин, состоящее из i вершин (i от 1, до количества вершин минус 1) и проверяем его на доступность всех путей из этого подмножества. Анализ идёт, пока не найдено решение и не перебраны все варианты.

Перебор вариантов осуществляется по алгоритму:

Вариант из i заполняется номерами вершин по порядку с 1 до i-й вершины.
Проверяем подмножество на доступность всех путей из этого подмножества:

создаём строчку обнулённую размером количество вершин графа, а затем записываем в ячейки 1, если из подмножества доступна вершина, с порядковым номер = номеру столбца строчки.

Если количество вариантов закончилось, то начинаем анализ с подмножеством, состоящим из i + 1 вершин (Количество вариантов закончилось, если 1-й элемент варианта равен количество вершин минус i плюс 1
Создаём следующий вариант

q=i.
увеличиваем q-ое число в варианте на единицу.
делаем все все числа с q+1 до i-го равными q-ое+1, q-ое+2 и т.п.
если q-ое число больше, чем количество вершин + q минус i, то уменьшаем q на единицу и идём в действие №3.a,iv,2.

Проверяем подмножество на доступность всех путей из этого подмножества.
идём в действие №3.a.iii.

Если решение не найдено, то решение – все вершины.

3.Структура основных входных и выходных данных

Внешнее представление

Внутреннее представление

Входные данные

Заданы названия вершин. На следующей строке могут быть заданы, либо отсутствовать, дуги: от какой вершины какая дуга ведёт к какой вершине (название вершины - название вершины, переход на следующую строку либо конец файла)

Динамический список-списков list *head, с Названиями вершин, заданный структурой:

struct name { name *next;

char sim; };

struct list { list *next;

name *sim; };

После анализа дуг граф представляется двумерным массивом размером количество вершин на количество вершин, в котором строка представляет собой порядковый номер вершины, а элементы в ней либо 0, либо 1, если из вершины идёт дуга в вершину с порядковым номером = номеру столбца.

Выходные данные

Перечисление вершин, составляющих минимальное подмножество вершин, от которых достижимы все остальные его вершины.

Динамический список-списков list *head, с Названиями вершин, заданный структурой:

struct name { name *next;

char sim; };

struct list { list *next;

name *sim; };

Динамический массив buf с порядковыми номерами вершин.

Выходной файл: “D:\output,txt”. С записанными названиями вершин графа через <,>.

4.Алгоритм решения задачи

{

Создать пустой список-наименования-вершин;

Ввод вершин;

Создать обнулённую матрицу-дуг размером количество-вершин на количество-вершин;

Заполнить матрицу-дуг дугами;

Создать обнулённую матрицу-путей размером количество-вершин на количество-вершин;

Решение=0;

При количество вершин=1

Решение = Задача (количество вершин, матрица-путей );

Количество вершин = количество вершин+1;

Пока количество вершин < общего количества вершин -1 и не найдено решение;

Если Решение = 0, то Вывод всех вершин;

}

Алгоритм функции Задача (количество вершин, матрица-путей)

{

делать

Создать следующий вариант буфер-вариант-вершин.

Решение = Проверка (буфер-вариант-вершин, матрица путей);

пока не закончились варианты буфера и не найдено решение

Если Решение=1, то Вывод вершин, записанных в буфер-вариант вершин;

Вернуть Решение;

}

Алгоритм функции Проверка (буфер-вариант-вершин, матрица-путей)

{

Создать обнулённый одномерный массив размером количество вершин;

Если для вершины из буфера-вариат-вершин элемент равен 1, то делаем элемент массива равным 1.

Если в массиве хоть один элемент равен 0, то возвращаем 0, иначе 1.

}

Алгоритм функции создания буфер-вариант-вершин(изменяемая позиция, буфер-вариант вершин, количество вершин в графе, количество вершин в варианте)

{

Увеличиваем на единицу элемент под нужной позицией;

Заполняем все последующие элементы согласно методу решения.

Если элемент превысил вычисляемое по формуле максимальное значение (количество элементов + изменяемая позиция - количество вершин в варианте), то

Изменяемая позиция = изменяемая позиция – 1;

Запускаем функция создания буфер-вариант-вершин;

}

Примечание – всегда при первоначальном запуске функции изменяемая позиция равна количеству вершин в варианте

5. Структура программы

int InputVer(list *head,FILE *in) – функция ввода названий вершин графа в список; list *head – указатель на список; FILE *in – указатель на поток – входной файл.

return number – возвращает количество вершин в графе. Number [0;+ )

void InputDug(list *head,FILE *in,char **matrix1) – функция ввода дуг графа в матрицу matrix1 (матрица дуг); list *head – указатель на список с элементами – название вершины графа; FILE *in – указатель на поток – входной файл; char **matrix1 – указатель на двумерный массив определяющий граф. Элемент матрицы типа char { 0 ; 1 }.

int Search(list *head,name *beg) – функция поиска слова, находящегося посимвольно в списке (*beg – указатель на голову этого списка) в списке с элементами (*head – указатель на голову этого списка) – список с наименованием вершины графа посимвольно.

return place – возвращает номер позиции, на которой это слово находится в списке списков слов, если первая позиция – 0.

void InputSD(stack * & SD,int elem) – функция помещения элемента в стек. Видоизменённый стек возвращается не явно; stack * & SD – стек. int elem – помещаемый элемент. elem [0; + )

int TakeSD(stack * & SD) – функция взятия элемента из стека. Видоизменённый стек возвращается не явно. stack * & SD – стек.

return elem – возвращает элемент - элемент взятый из стека типа int. elem [0; + ).

char CleanSD(stack * SD) – функция проверки стека на пустоту. stack * SD – указатель на стек.

,возвращает 0, если стек пуст и 1, если стек не пуст.

void MatBuild(int i,char **matrix1,char **matrix2,int number) – функция определения доступных путей для вершины графа под номером i из матрицы-дуг. i [0; + ); char **matrix1 – указатель на матрицу-дуг; char **matrix2 – указатель на матрицу-путей. Элемент матрицы типа char { 0 ; 1 }; int number - количество вершин в графе. Number [0;+ )

char Program(int *buf,int number,int i,char **matrix2) – функция создания и заполнения массива доступных путей для элементов, номера которых берутся из массива buf; int *buf – указатель на массив-вариант-вершин. Его элементы – номера вершин графа типа int; int number - количество вершин в графе. Number [0;+ ); int i – количество элементов в массиве-вариант-вершин buf. i [0; + ); char **matrix2 – указатель на матрицу-путей. Элемент матрицы типа char { 0 ; 1 };

return resh - возвращает счётчик типа char, который равен 1, если все элементы массива-доступных-путей-для-подмножества равны 1 и равен 0, в противном случае. resh { 0 ; 1 }

void Perebor(int * & buf,int q,int number,int i) – функция изменяющая массив buf – массив-вариант-вершин на следующий вариант. Возвращает массив buf неявно. int *buf – указатель на массив-вариант-вершин. Его элементы – номера вершин графа типа int; int q – позиция в массиве buf, которую нужно изменить; int number - количество вершин в графе. Number [0;+ ); int i – количество элементов в массиве buf.

void Output(int *buf,FILE *out,list *head,int i) – функция вывода в файл имён вершин, которые записаны в массиве buf. int *buf – указатель на массив-вариант-вершин. Его элементы – номера вершин графа типа int; FILE *out - указатель на поток – исходящий файл”; list *head – указатель на список с элементами – наименование вершины графа; int i – количество элементов в массиве buf.

char Zadacha(char **matrix2,int i,int number,list *head,FILE *out) – функция анализа матрицы-путей. Берёт вариант взятия вершин из Графа из функции Perebor и проверяет этот вариант в функции Program. Если Program возвращает resh=1, то выводит этот вариант с помощью функции Output.

return resh - возвращает счётчик типа char, который равен 0, если решение не найдено и равен 1, если решение найдено. resh { 0 ; 1 }

6. Текст программы

#include<stdio.h>

#include<stdlib.h>

struct name { name *next; //определение структур

char sim; };

struct list { list *next;

name *sim; };

struct stack { char sim;

stack *next; };

typedef stack stack;

int InputVer (list *head, FILE *in) // функция ввода названий вершин графа в список

{ int number=0,i,k,t; list *p; name *m; char g;

p=head;

while (g!='\n' && !feof(in) ) // ввод названия вершин пока не конец файла и

{ p->next=new list; // не конец строки

p=p->next;

m=p->sim;

fscanf (in,"%c",&g); //ввод названия вершины посимвольно в

while (g!=',' && g!='\n' && !feof(in) ) // динамический список

{ m->next=new name;

m=m->next;

m->sim=g;

fscanf (in,"%c",&g);

}

m->next=NULL;

m=p->sim;

number++; //увеличиваем счётчик количества вершин графа

}

p->next=NULL;

return number; //возвращаем количество переменных графа

}

int Search (list *head, name *beg) // функция поиска слова, находящегося

{ char v=1,place=0; list *p; name *k,*q; // посимвольно в списке в списке с

p=head->next; // элементами – словами, находящимися

q=p->sim->next; // посимвольно в списке.

k=beg->next;

while (!id) // Пока не найдено идентичное слово

{ if (q->sim!=k->sim) //если буквы не равны, то счётчик порядкового номера

{ place++; // вершины увеличиваем на единицу и переходим к

p=p->next; // следующему слову в списке. Указатель, передвигающийся

q=p->sim->next; // по списку со словом, которое ищем, делаем указывающим на

k=beg->next; // начало списка

}

else //иначе, если конец обоих слов, то найдено идентичное слово.

{ if (q->next==NULL && k->next==NULL) id=1;

q=q->next; // Передвигаем указатели в словах на следующую букву

k=k->next;

}

return place; // возвращаем порядковый номер вершины

}

void InputDug (list *head, FILE *in, char **matrix1) // функция ввода дуг в матрицу-дуг

{ int i; char g,l,v,place1,place2; name *m,*beg;

while (!feof(in)) // считываем дугу, пока не конец файла

{ beg=new name;

m=beg;

fscanf (in,"%c",&g);

while (g!='-') // считываем начало дуги до

{ m->next=new name; // символа «-» в список посимвольно

m=m->next;

m->sim=g;

fscanf (in,"%c",&g);

}

m->next=NULL;

place1=Search(head,beg); // определяем порядковый номер вершины – начала дуги

beg=new name;

m=beg;

fscanf (in,"%c",&g);

while (g!='\n' && !feof(in) ) // считываем конец дуги до

{ m->next=new name; // до конца строки, либо до конца файла

m=m->next;

m->sim=g;

fscanf (in,"%c",&g);

}

m->next=NULL;

place2=Search(head,beg); // определяем порядковый номер вершины – начала дуги

matrix1[place1][place2]=1; // делаем элемент матрицы дуг в строчке = порядковый

} // номер начало дуги, в столбце = порядковый номер

} // конца дуги равным 1

void InputSD (stack * & SD, int elem) // функция помещения элемента в стек

{ stack *k;

k=SD; // запоминается указатель на голову стека в голове стека SD=new stack; // создаётся новая ячейка указатель next новой ячейки делаем

SD->next=k; // указывающим на следующий элемент стека

SD->sim=elem; // заполняем информационное поле головы стека

}

int TakeSD (stack * & SD) //функция взятия элемента из стека

{ stack *k; int elem;

elem=SD->sim; //берётся элемент

k=SD; // делается указатель на голову стека

SD=SD->next; // меняем голову стека

delete k; // удаляем старую голову

return elem; // возвращается взятый элемент

}

char CleanSD (stack * SD) // функция проверки стека на пустоту

{ if (SD==NULL) return 0; else //если стек пуст возвращаем 0, иначе 1

return 1;

}

void MatBuild (int i, char **matrix1,char **matrix2,int number) // функция определения

{ stack *SD=NULL; int j,l=i; char m=1,q; // доступных путей для вершины графа

matrix2[l][l]=1; // делаем диагональные элемент матрицы в проверяемой строчке = 1

InputSD(SD,i); //помещаем пор. номер проверяемой вершины в стек

while (m) // пока стек не пуст

{ j=0; q=1;

do //поиск неисследованного пути в строке, пока не найден или не конец строки

{ if (matrix1[i][j]) //если элемент в строке = 1, а в матрице-

{ if (!matrix2[l][j]) q=0; // путей это ещё нет, то выход из поиска пути

else j++; //иначе проверка следующей ячейке в строке

}

while (q && j!=number);

if(j==number) // если конец строки, то забираем элемент из стека

{ i=TakeSD(SD); // если стек не пуст, то смотрим элемент в его

if(CleanSD(SD)) i=SD->sim; else m=0;// голове и продолжаем поиск нового пути

} // с него, иначе выход из определения путей для вершины

else // иначе начинаем поиск дальнейшего пути, для новой вершины.

{ i=j; // Помещаем её номер в стек. Делаем элемент матрицы дуг с

InputSD(SD,i); // номером строки = изначально проверяема вершина,

matrix2[l][i]=1; // номером столбца = найденная вершина

}

char Program (int *buf, int number, int i, char **matrix2) // функция создания и заполнения

{ char resh=1; char *m; int j,l; // массива доступных путей подмножества

m=(char*)malloc(number*sizeof(char)); // для элементов из массива вариантов

for(j=0; j!=number ;j++) m[j]=0; // создание и обнуление массива под доступные пути

for(j=0; j!=i+1;j++) for(l=0; l!=number ;l++) if (matrix2[buf[j]][l]) m[l]=1; // заполнение

for(l=0; l!=number ;l++) if (m[l]==0) resh=0; // массива доступных путей: берётся return resh; // вершина из варианта и если в её ячейке есть 1, то

} // соответствующая ячейка массива доступных путей

// приравнивается 1, затем проверяется созданный

// массив. Если среди его элементов нет 0, то решение

// найдено.

// возвращаем 1, если решение найдено, иначе 0

void Perebor (int * & buf, int q, int number, int i) // функция изменяющая массив buf –

{ int t; // массив-вариант-вершин на следующий вариант

buf[q]++; // увеличиваем на единицу элемент под нужной позицией, заполняем for(t=q+1; t<i+1 ; t++) buf[t]=buf[q]+t-q; // все последующие элементу согласно методу

if (buf[q]>number+q-i-1) { q--; Perebor(buf,q,number,i); } // решения. Если элемент

} // превысил вычисляемое по формуле максимальное значение,

// то переключаем изменяемую позицию на предыдущую и

// запускаем функцию ещё раз

void Output (int *buf, FILE *out, list *head, int i) // функция вывода в файл имён

{ int j=0,v=0; list *p; name *q; // вершин, которые записаны в массиве buf

p=head->next; // делаем указатель на элемент, следующий после головы,

while(v!=i+1) // в списке с наименованиями вершин

{ if (buf[v]==j) // пока не закончились вершины в массиве-варианте

{ q=p->sim; // вершин делаем если порядковый номер вершины не

do // совпадает с номером вершины в массиве-варианте, то

{ q=q->next; // переходим на следующую вершину, иначе

fprintf (out,"%c",q->sim); // выводим наименование вершины, ставим

} // в конце запятую, переключаемся на

while(q->next!=NULL); // следующую вершину в массиве-варианте

fprintf (out,",");

v++;

}

j++;

p=p->next; // переключаемся на следующее наименование

}

char Zadacha (char **matrix2,int i, int number, list *head, FILE *out) // функция анализа

{ char resh=0; int j,q=i; int *buf; // матрицы-путей

buf=(int*)malloc((i+1)*sizeof(int)); //создание массива под вариант-вершин-решения

for(j=0;j!=i+1;j++) buf[j]=j; //заполнение массива-варианта первым вариантом

resh=Program(buf,number,i,matrix2); // проверка варианта

for(j=number-i-1; buf[0]!=j && !resh ;) // цикл проверок, пока первый элемент

{ Perebor(buf,q,number,i); // варианта не равен высчитанному по формуле и

q=i; // не найдено решение, берётся новый вариант.

resh=Program(buf,number,i,matrix2); // Изменяемая позиция переключается на

} // последнюю. Проверка варианта

if (resh) Output(buf,out,head,i); //если найдено решение, то выводим его

return resh; //возвращается счётчик = 1, если решение найдено и = 0, если нет

}

void main ()

{ FILE *in,*out; int number,i,q,t,j,* buf; char **matrix1,**matrix2,resh;

if((in=fopen("D:\input.txt","r"))==NULL)

{perror("Mistake"); exit(0);}

out=fopen("D:\output.txt","w");

list *head=new list;

number=InputVer(head,in); // ввод названий вершин и определение их количества

matrix1=(char**)malloc(number*sizeof(char*)); //создание массива под матрицу-дуг for(i=0; i!=number ;i++) matrix1[i]=(char*)malloc(number*sizeof(char)); // и его обнуление

for(i=0; i!=number ;i++) for(j=0; j!=number ;j++) matrix1[i][j]=0;

InputDug(head,in,matrix1); //определение элементов матрицы-дуг

fclose(in);

matrix2=(char**)malloc(number*sizeof(char*)); //создание массива под матрицу-путей

for(i=0; i!=number ;i++) matrix2[i]=(char*)malloc(number*sizeof(char)); // и его обнуление

for(i=0; i!=number ;i++) for(j=0; j!=number ;j++) matrix2[i][j]=0;

for(i=0; i!=number ;i++) MatBuild(i,matrix1,matrix2,number); //цикл определения элементов

resh=0; // матрицы-путей построчно

for(i=0; i!=number-1 && !resh ;i++) resh=Zadacha(matrix2,i,number,head,out); // цикл анализа if (!resh) // матрицы-путей, с изменяемым количеством вершин в подмножестве-

{ buf=(int*)malloc(number*sizeof(int)); // варианте. Продолжается, пока не найдено

for(j=0; j!=number ;j++) buf[j]=j; // решение или не перебраны все варианты количества

Output(buf,out,head,number-1); // вершин в подмножестве-варианте, кроме варианта – все

} // вершины. Если решение не найдено, то создаём вариант-вершин,

fclose(out); // состоящий из всех вершин, и выводим его.

}

7. Набор тестов

№	Дано	Графическое представление	Результат	Примечание
1	One		One,	Граф, состоящий из 1 вершины.
2	One,Two		One,Two	Граф, состоящий из 2 не связанных дугой вершин. Решение – все вершины.
3	One,Two,Three ,Four,Five		One,Two,Three, Four,Five,	Граф состоящий из произвольного количества вершин без дуг. Решение – все вершины.
4	One,Two\n One-Two		One,	Граф, состоящий из 2 вершин. Одна, связана с другой дугой.
5	One,Two\n One-Two\n Two-One		One,	Граф, состоящий из 2 обоюдно связанных между собой дугами вершин. Решение – 1ое найденное.
6	One,Two,Three ,Four,Five\n Four-Three\n Three-Two\n Five-One		Four,	Граф, состоящий из произвольного количества вершин с вершиной, из которой есть путь во все остальные.
7	One,Two,Three ,Four,Five\n One-Two\n Three-Four		One,Three,Five	Граф, состоящий из произвольного количества вершин, где решение – подмножество, с количеством вершин больше 1 и меньше общего количества.
8	One1,Two2,T ,Four L,Five\n One1-Two2\n T-Four L\n	Граф из предыдущего теста (изменены названия вершин)	One1,T,5	Проверка работоспособности Вершин с названиями: содержащими цифры и буквы состоящими из одного символа состоящими из цифры

8. Результаты работы программы

Программа работает верно, что подтверждено тестами.

Курсовая работа по “Структурам данных и алгоритмам” 📙 Курсовая → 🆔 114462