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

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

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

 

 

 

 

 
  Кафедра ПМИ

 

 

 

 

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

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

 

 

 

 

 

 

 

 

 

 

 

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

Группа: Пми-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. Создаём матрицу-дуг (матрица дуг – матрица размером количество вершин на количество вершин графа, где строчка – одна вершина, а ячейка из этой строчки равна 1, если из этой вершины есть дуга в вершину, с номером, совпадающим с номером столбца, и равна 0 в противном случае).
2. Создаём матрицу-путей (матрица путей – матрица размером количество вершин на количество вершин графа, где строчка – одна вершин, а ячейка из этой строчки равна 1, если из этой вершины есть путь в вершину, с номером, совпадающим с номером столбца, и равна 0 в противном случае).
1. все элементы Матрица-путей_i,i=1, Остальные элементы = 0;
2. запоминаем номер строчки, которую мы проверяем на пути (например l), а так же кладём её в стек.
3. перебираем элементы по строчке i в Матрице дуг, пока он не равен 1, и элемент Матрица_{l,столбец}, не равен 1, и пока не конец строки i,
4. если конец строки i, то берём элемент из стека. Если стек не пуст, то смотрим, что за элемент там лежит (приравниваем i этому элементу), но не забираем, иначе выход из определения путей для этой строки.
5. если не конец строки, то i приравниваем столбцу который мы нашли, помещаем номер этой вершины в стек, Матрица-путей_l,i=1;
3. Анализируем матрицу путей. Берём подмножество вершин, состоящее из i вершин (i от 1, до количества вершин минус 1) и проверяем его на доступность всех путей из этого подмножества. Анализ идёт, пока не найдено решение и не перебраны все варианты.
1. Перебор вариантов осуществляется по алгоритму:
1. Вариант из i заполняется номерами вершин по порядку с 1 до i-й вершины.
2. Проверяем подмножество на доступность всех путей из этого подмножества:
1. создаём строчку обнулённую размером количество вершин графа, а затем записываем в ячейки 1, если из подмножества доступна вершина, с порядковым номер = номеру столбца строчки.
3. Если количество вариантов закончилось, то начинаем анализ с подмножеством, состоящим из i + 1 вершин (Количество вариантов закончилось, если 1-й элемент варианта равен количество вершин минус i плюс 1
4. Создаём следующий вариант
1. q=i.
2. увеличиваем q-ое число в варианте на единицу.
3. делаем все все числа с q+1 до i-го равными q-ое+1, q-ое+2 и т.п.
4. если q-ое число больше, чем количество вершин + q минус i, то уменьшаем q на единицу и идём в действие №3.a,iv,2.
5. Проверяем подмножество на доступность всех путей из этого подмножества.
6. идём в действие №3.a.iii.
4. Если решение не найдено, то решение – все вершины.

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)      // если конец строки, то забираем элемент из стека