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

{ 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. Результаты  работы программы

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