Поиск вершины в графе между двумя заданными вершинами

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

1. ЗАДАНИЕ

2. ОПИСАНИЕ ПРИМЕНЕНИЯ

2.1 Постановка задачи

2.2 Обращение к программе

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

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

2.5 Сообщения

2.5.1 Информационные сообщения

2.5.2 Сообщения об ошибках

3. ОПИСАНИЕ ПРОГРАММЫ

3.1 Метод решения задачи

3.2 Структура программы

3.3 Описание модулей

3.3.1 main - главный модуль

3.3.2 vvod - ввод графа

3.3.3 vyvod - вывод матрицы смежности

3.3.4 messages - сообщения

3.3.5 poisk - поиск вершин

4. ПОДГОТОВКА К ОТЛАДКЕ ПРОГРАММЫ

4.1 План отладки

4.2 Проектирование тестов

4.2.1 Тесты черного ящика

4.2.2 Тесты белого ящика

4.3 Отладочные средства

4.4 Отладка программы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

1. Системный файлы проекта

2. Текст программы модуля main

3. Текст программы модуля vvod

4. Текст программы модуля vyvod

5. Текст программы модуля poisk

6. Текст программы модуля messages

7. Результаты тестирования программы

8. Трудоемкость курсовой работы

9. Дневник выполнения курсовой работы

1. ЗАДАНИЕ

Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными (различными) вершинами и отлична от них.

2. ОПИСАНИЕ ПРИМЕНЕНИЯ

2.1 Постановка задачи

Разработанная программа определяет вершину в заданном графе с количеством вершин n<=20.

В программе используются следующие определения. Граф - это пара (V, E), где V - конечное непустое множество вершин, а Е - множество неупорядоченных пар <u, v> вершин из V, называемых ребрами. Рассматривается класс графов без петель, т.е. ребер, в которых u=v.

Путь, соединяющий вершины u и v, - это последовательность вершин v0, v1, …, vk (k?0), такая, что v0=u, vk=u, и для любого i (0 ? i ? k) вершины vi и vi+1 соединены ребром.

Длина пути v0, v1, …, vk равна k (количеству ребер). Путь замкнут, если vk=v0. Путь называется простым, если все его вершины различны.

Из условия задачи, выделенная вершина - это такая вершина, которая отлична от всех других вершин, находящихся в графе.

Следовательно, искомая вершина не должна совпадать с заданными вершинами, и должна принадлежать всем путям, следующим из вершины A в вершину B.

Решаемая задача иллюстрируется рис. 2.1. и 2.2. На рисунке 2.1. показан граф, содержащий 5 вершин, и имеет две выделенные вершины A и B, между которыми существует вершина, принадлежащая всем путям между вершинами A и B. При наличии нескольких таких вершин, программа находит их все. Возможен также случай, когда в графе не найдется искомой вершины (рис. 2.2). Тогда выдается соответствующее сообщение.



Рис. 2.1. Граф, имеющий искомую точку Рис. 2.2. Граф, не имеющий искомую точку

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

2.2 Обращение к программе

Запуск программы производится непосредственно в операционной системе. Исполняемый файл программы имеет название MyProject.exe. Исходные данные вводятся с клавиатуры, а результаты выводятся на экран дисплея.

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

Входные данные представляют собой граф. Исходные данные вводятся с клавиатуры. Граф представляется в виде перечня ребер, перед которым указывается количество вершин. Каждое ребро задается парой номеров вершин. Вершины нумеруются от 0 до n-1, где n - количество вершин графа (n?20). Ребра можно задавать в произвольном порядке. Все числа разделяются пробелом и/или переводом строки (клавиша <Enter>).

При вводе данных с клавиатуры после ввода всех данных нажимается <Ctrl-Z> (обозначает конец файла) и <Enter>.

Например, граф, показанный на рис. 2.1, можно ввести с клавиатуры следующим образом:

5

0 1

0 2

0 3

1 3

2 3

3 4

<Ctrl-Z><Enter>

Другой вариант ввода:

5 0 1 0 2 0 3 1 3 2 3 3 4<Ctrl-Z><Enter>

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

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

Пример результатов обработки графа, показанного на рис. 2.1.:

Enter the number of points (from 2 till 50):

5

Enter the parts of graph:

0 1

0 2

0 3

1 3

2 3

3 4^Z

Matrix:

	0	1	2	3	4
0	0	1	1	1	0
1	1	0	0	1	0
2	1	0	0	1	0
3	1	1	1	0	1
4	0	0	0	1	0

Предполагается, что входной и выходной файлы не заданы, т. е. использованы клавиатура и экран.

2.5 Сообщения

Выходные данные программы могут содержать сообщения, перечисленные в разделах 2.5.1. и 2.5.2. В угловых скобках указаны названия вставляемых в сообщения величин.

2.5.1 Информационные сообщения

1. Введите количество вершин (от 2 до 50):<число вершин>

2. Введите ребра графа (конец <Ctrl-Z>): <перечень ребер>

3. Матрица смежности: <матрица>

4. Введите вершины A и B

5. Найденные вершины: <перечень найденных вершин>

6. Искомых вершин в графе не найдено.

2.5.2 Сообщения об ошибках

7. Ошибка! Количество вершин должно быть от 2 до 50.

8. Ошибка! Введено недопустимое значение.

9. Ошибка! Вершины A и B не должны совпадать.

10. Ошибка! Вершина A введена неправильно, попробуйте еще раз.

11. Ошибка! Вершина B введена неправильно, попробуйте еще раз.

12. Внимание! Обнаружены повторяющиеся ребра, программа будет игнорировать повторы.

3. ОПИСАНИЕ ПРОГРАММЫ

3.1 Метод решения задачи

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

Покажем кусок программы, содержащий алгоритм обхода графа в глубину:

Алгоритм 3.1. Обход графа в глубину

do

{ i=st[uk];

j=jp;

while (j<n && (gr[i][j]==0 || vp [j]==1)) j++;

if (j<n)

{ uk++;

st[uk]=j;

jp=0;

vp[j]=1;

if (j==B)

{ for (l=0;l<=uk;l++)

m[st[l]]++;

kolput++;

jp=st[uk]; vp[jp]=0;

jp++;

uk--;

}

}

else

{ jp=st[uk]; vp[jp]=0;

jp++;

uk--;

}

}

while (uk>=0);

3.2 Структура программы

Структура программы показана на рисунке 3.1.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 3.1. Модульная структура программы

Программа состоит из пяти модулей: main - главная программа, vvod - ввод графа, vyvod - вывод матрицы, poisk - поиск вершин, messages - сообщения.

Сопряжение модулей программы описаны в табл. 3.1. Все данные между модулями передаются только в виде параметров, глобальных переменных в программе нет.

Все модули транслировались отдельно. Их имена перечислены вместе с разработанной для данной программы библиотекой my.lib в файле проекта myprojec.prj. Модули vvod, vyvod, poisk, messages помещены в библиотеку объективных модулей my.lib и для их использования требуется включить в программу созданный в курсовой работе файл заголовков my.h командой:

#include “my.h”

Таблица 3.1.

Сопряжения модулей

Номер	Вход	Выход
1	Количество вершин, список ребер графа	-
2	Количество вершин, матрица смежности	-
3	Количество и номера вершин	Признак, найдены ли вершины
4	Номер сообщения	-

Тексты файла my.h и программ всех модулей в алфавитном порядке приведены в приложении, а их описания - в разделе 3.3.

3.3 Описание модулей

3.3.1. main - главный модуль

ОБРАЩЕНИЕ ИЗ MS-DOS: myprojec

ЗАГОЛОВОК: void main()

ФУНКЦИЯ: Ввод графа, построение матрицы смежности, ввод выделенных вершин, поиск вершин, вывод результата и сообщений об ошибках.

ВХОДНЫЕ ДАННЫЕ:

n - количество вершин

ВЫХОДНЫЕ ДАННЫЕ: Нет.

ЗНАЧЕНИЕ: Нет.

РАБОЧИЕ ДАННЫЕ:

i - переменная цикла;

j - переменная цикла;

n - количество вершин;

gr - матрица смежности;

A, B - выделенные вершины;

p - признак вершины;

flag - признак правильности ввода количества вершин;

АЛГОРИТМ: см. алгоритм 3.2.

Алгоритм 3.2. Алгоритм модуля main.

do

{ Вывод сообщения 1;

scanf("%d", &n); // Ввод количества вершин

flag=0;

if (n<2 || n>NMAX){ Вывод сообщения 3; flag=1;} // Если n введено правильно, то flag=1

}

while (flag==1);

vvod(n,gr); // Ввод графа

Вывод сообщения 2;

vyvod(n,gr); // Вывод матрицы смежности

Вывод сообщения 7;

do

{scanf ("%d",&A); // Ввод вершины A

scanf ("%d",&B) ; // Ввод вершины B

if (A<0 || A>=n) Вывод сообщения 8; // Если A превышает число n

if (B<0 || B>=n) Вывод сообщения 9; // Если B превышает число n

if (A==B) Вывод сообщения 10; // Если A=B

}

while (A<0 || A>=n || B<0 || B>= n || A==B);

p=poisk ( gr,n, A, B); // Поиск вершины

if (p==0) Вывод сообщения 11;

3.3.2 vvod - ввод графа

ЗАГОЛОВОК: int vvod(int n, int gr[NMAX][NMAX])

ФУНКЦИЯ: Ввод графа в виде перечня ребер и его преобразование в матрицу смежности gr. NMAX - максимальное количество вершин.

ВХОДНЫЕ ДАННЫЕ:

n - количество вершин

ВЫХОДНЫЕ ДАННЫЕ:

gr - матрица смежности

ЗНАЧЕНИЕ: Нет.

РАБОЧИЕ ДАННЫЕ:

i, j - номера вершин ребра;

f - признак проверки повторения ребер.

АЛГОРИТМ: см. алгоритм 3.3.

Алгоритм 3.3. Алгоритм модуля vvod.

for(i=0;i<n;i++)

for(j=0;j<n;j++)

gr[i][j]=0; // Обнуление матрицы смежности

Вывод сообщения 5;

while(scanf("%d %d", &i, &j)==2) // Ввод ребер графа

{ if (i==j)

Вывод сообщения 3;

else

if (i>=n||i<0||j>=n||j<0)

Вывод сообщения 3;

else

{ gr[i][j]=1; if (gr[j][i]==0) gr[j][i]=1; else f=1;}

}

if (f==1) Вывод сообщения 6; // если было повторение ребер

3.3.3 vyvod - вывод матрицы смежности

ЗАГОЛОВОК: void vyvod(int n, int gr[NMAX][NMAX])

ФУНКЦИЯ: Вывод матрицы смежности.

ВХОДНЫЕ ДАННЫЕ:

n - количество вершин;

gr - матрица смежности.

ВЫХОДНЫЕ ДАННЫЕ: Нет.

ЗНАЧЕНИЕ: Нет.

РАБОЧИЕ ДАННЫЕ:

i,j - номера вершин ребра.

АЛГОРИТМ: см. алгоритм 3.4.

Алгоритм 3.4. Алгоритм модуля vyvod.

for(i=0;i<n;i++)

{ for(j=0;j<n;j++) printf("%d ", gr[i][j]); printf("\n");} // Вывод матрицы смежности

3.3.4 messages - сообщения

ЗАГОЛОВОК: void message(int i)

ФУНКЦИЯ: Вывод сообщений.

ВХОДНЫЕ ДАННЫЕ:

i - номер сообщения.

ВЫХОДНЫЕ ДАННЫЕ: Нет.

ЗНАЧЕНИЕ: Нет.

РАБОЧИЕ ДАННЫЕ:

t - вектор, содержащий текст сообщения.

АЛГОРИТМ: см. алгоритм 3.5.

Алгоритм 3.5. Алгоритм модуля messages.

{ char *t[]={" ",

/*1*/ "\n Enter the number of points (2-50): \n",

/*2*/ "\n Matrix: \n",

/*3*/ "\n Error! Wrong number, try again \n",

/*4*/ "\n Error! Number of points must be from 2 till 50: \n",

/*5*/ "\n Enter the parts of graph (end Ctrl-Z): \n",

/*6*/ "\n Warning! Repeated edges of count are found out, the program will ignore them \n",

/*7*/ "\n Enter A & B: \n",

/*8*/ "\n Error! A is incorrect, try again: \n",

/*9*/ "\n Error! B is incorrect, try again: \n",

/*10*/ "\n Error! A not must be B (A ne ravno B) \n",

/*11*/ "the programm didn't found this points. \n",

/*12*/ "\n Found points: ",

};

printf("%s", t[i]); // Вывод сообщения

}

3.3.5 poisk - поиск вершин

ЗАГОЛОВОК: int poisk (int gr[NMAX][NMAX], int n, int A, int B)

ФУНКЦИЯ: Нахождение вершин заданного графа, которые принадлежат каждому пути между двумя выделенными (различными) вершинами, и отличных от них.

ВХОДНЫЕ ДАННЫЕ:

n - количество вершин;

gr - матрица смежности;

A, B - две выделенные вершины.

ВЫХОДНЫЕ ДАННЫЕ:

flag - признак существования такой вершины.

ЗНАЧЕНИЕ:

flag=0 - таких вершин нет;

flag=1 - такие вершины есть.

РАБОЧИЕ ДАННЫЕ:

st[NMAX+1] - стек;

i, j - переменные цикла;

jp - столбец с которой ведется поиск новой вершины;

l - переменная цикла;

vp[NMAX] - вектор посещений;

kolput - количество путей;

m[NMAX] - массив, который заносит путь в стек;

flag - признак вершины;

uk - указатель стека.

АЛГОРИТМ: см. алгоритм 3.6.

Алгоритм 3.6. Алгоритм модуля poisk.

{ kolput=0; flag=0; uk=0;

for(i=0;i<n;i++){vp[i]=0; m[i]=0;} // Обнуление вектора посещений и массива

st[0]=A; // Присваивание первому элементу стека числа A

vp[A]=1; // A-ый элемент посещен

i=0;

jp=0;

do

{ i=st[uk]; // Присваивание uk элемента стека строке i

j=jp; // Присваивание столбцу j номер столбца jp

while (j<n && (gr[i][j]==0 || vp [j]==1)) j++;

if (j<n)

{ uk++;

st[uk]=j; // Присваивание uk элементу стека числа j

jp=0;

vp[j]=1; // Отметили посещенной

if (j==B) // Если j равно конечной вершине B

{ for (l=0;l<=uk;l++)

m[st[l]]++; // Заносим стек в массив

kolput++; // Увеличиваем на 1 количество путей

jp=st[uk]; vp[jp]=0; // Возвращаемся

jp++;

uk--;

}

}

else

{ jp=st[uk]; vp[jp]=0;

jp++;

uk--;

}

}

while (uk>=0);

Вывод сообщения 12;

for(i=0;i<n;i++)

if (m[i]==kolput&& i!=A &&i!=B)

{ printf("%d ",i); flag=1;} // Вывод найденных вершин

return flag;

}

4. ПОДГОТОВКА К ОТЛАДКЕ ПРОГРАММЫ

4.1 План отладки

Особенности данной программы затрудняют применение для нее в чистом виде традиционной стратегии тестирования: возможно более быстрого подключения к программе модулей ввода/вывода и сложных модулей с их предварительной автономной отладкой. Дело в том, что наиболее сложный модуль poisk имеет довольно громоздкие входные и выходные данные. Для его автономной отладки эти данные пришлось бы передавать с помощью имитаторов и драйверов, близких по функции и сложности к модулям main, vvod и vyvod или совместно с ними.

Работа модулей main и vvod тесно переплетена: main сообщает об ошибках, обнаруженных модулем vvod. При автономной отладке каждого из них, особенно при вводе ошибочных данных, драйвер или имитатор практически должен дублировать работу другого модуля. Поэтому их удобно отлаживать совместно. Модуль vyvod прост и не требует автономной отладки.

Из приведенных соображений принят следующий план отладки:

1. Тестирование модуля vvod. Для проверки правильности ввода требуется модуль вывода матрицы смежности, который полезно использовать на всех этапах отладки.

2. Совместное тестирование модулей poisk, vyvod и main с модулем vvod (т.е. всей программы) на «правильных» тестах.

3. Тестирование всей программы для совместной отладки модулей main и vvod на «неправильных» тестах.

4.2 Проектирование тестов

4.2.1 Тесты черного ящика

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

Таблица 4.1.

Области входных/выходных данных тестов программы

Входное/выходное условие (значение)	«Правильные» классы эквивалентности	«Неправильные» классы эквивалентности
Количество вершин n	2…NMAX (1)	< 2 (2), > NMAX (3)
Количество вершин в ребре	2 (4)	< 2 (5), > 2 (6)
Номер вершины	0…n-1 (7)	< 0 (8), > n-1 (9), i==j (29)
Заданная вершина A	0…n-1 (10)	< 0 (11), > n-1 (12), A==B (13)
Заданная вершина B	0…n-1 (14)	< 0 (15), > n-1 (16), B==A (13)
Сообщения программы	1 (17), 2 (18), 3 (19), 4 (20), 5 (21), 6 (22)	7 (23), 8 (24), 9 (25), 10 (26), 11 (27), 12 (28)

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

Таблица 4.2.

Тесты черного ящика для отладки программы

№	Вход	Выход	Основные ситуации
1	n=1	Сообщения: 1, 7	2, 17, 23
2	n=6 Ребра: 0-1, 0-2, 0-3, 1-3, 2-3, 2-5, 3-4, 4-5 Вершины A и B: 0 4	Сообщения: 1, 2, 3, 4, 6	1, 4, 7, 10, 14, 17, 18, 19, 20, 22
3	n=5 Ребра: 0-1, 0-2, 0-3, 0-4, 0-5	Сообщения: 1, 2, 8	1, 4, 7, 9, 17, 18, 24
4	n=60	Сообщения: 1, 7	3, 17, 23
5	n=5 Ребра: 0-1, 0-2, 0-3, 1-0, 1-3, 2-0, 2-3, 3-0, 3-1, 3-2, 3-4 Вершины A и B: 0 4	Сообщения: 1, 2, 3, 4, 5, 12	1, 4, 7, 10, 14, 17, 18, 19, 20, 21, 28
6	n=5 Ребра: (-1)-0, 0-2, 0-3, 1-3, 2-3, 3-4	Сообщения: 1, 2, 8	1, 4, 8, 17, 18, 24
7	n=5 Ребра: 0-1, 0-2, 0-3, 1-3, 2-3, 3-4 Вершины A и B: -1 4	Сообщения: 1, 2, 3, 4, 10	1, 4, 7, 11, 14, 17, 18, 19, 20, 26
8	n=5 Ребра: 0-1, 0-2, 0-3, 1-3, 2-3, 3-4 Вершины A и B: 5 4	Сообщения: 1, 2, 3, 4, 10	1, 4, 7 , 12, 14, 17, 18, 19, 20, 26
9	n=5 Ребра: 0-1, 0-2, 0-3, 1-3, 2-3, 3-4 Вершины A и B: 4 4	Сообщения: 1, 2, 3, 4, 9	1, 4, 7, 13, 17, 18, 19, 20, 25
10	n=5 Ребра: 0-1, 0-2, 0-3, 1-3, 2-3, 3-4 Вершины A и B: 0 -1	Сообщения: 1, 2, 3, 4, 11	1, 4, 7, 10, 15, 17, 18, 19, 20, 27
11	n=5 Ребра: 0-1, 0-2, 0-3, 1-3, 2-3, 3-4 Вершины A и B: 0 5	Сообщения: 1, 2, 3, 4, 11	1, 4, 7, 10, 16, 17, 18, 19, 20, 27
12	n=5 Ребра: 0-1, 0-2, 0-3, 1-1, 1-3, 2-3, 3-4	Сообщения: 1, 2, 8	1, 4, 29, 17, 18, 24
13	n=5 Ребра: 0-(-1), 0-1, 0-2, 0-3, 1-3, 2-3, 3-4	Сообщения: 1, 2, 8	1, 4, 8, 17, 18, 24
14	n=5 Ребра: 4-0, 4-1, 4-2, 4-3, 5-4	Сообщения: 1, 2, 8	1, 4, 9, 17, 18, 24

Примечание: ребра записаны через тире для наглядности, входные данные не содержат тире.

4.2.2 Тесты белого ящика

Разработанные тесты проверены методами белого ящика по критериям охвата основных путей выполнения алгоритмов модулей. В программе имеются составные условия. Поэтому использован критерий комбинаторного покрытия условий (см. табл. 4.3).

Таблица 4.3.

Комбинаторное покрытие условий тестами черного ящика

Модуль	Элементарное условие	Номера тестов
		Истина	Ложь
main	n < 2	1	остальные
main	n > NMAX	4	остальные
main	A < 0	7	2, 5, 8, 9, 10, 11
main	A >= n	8	2, 5, 7, 9, 10, 11
main	B < 0	10	2, 5, 7, 8, 9, 11
main	B >= n	11	2, 5, 7, 8, 9, 10
main	A == B	9	2, 5, 7, 8, 10, 11
vvod	i < 0	6	2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14
vvod	j < 0	13	2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 14
vvod	i > n	14	2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13
vvod	j > n	3	2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
vvod	i < n	1, 4	остальные
vvod	j < n	1, 4	остальные
vvod	i == j	12	2, 3, 5, 6, 7, 8, 9, 10, 11, 13, 14
vivod	i < n	1, 4	остальные
vivod	j < n	1, 4	остальные
poisk	i < n	1, 4	остальные
poisk	j < n	1, 4	остальные

Тесты, приведенные в таблице 4.3., покрывают истинные значения всех условий, дополнительные тесты не требуются.

граф матрица программа тест

4.3 Отладочные средства

Перечень необходимых отладочных средств в соответствии с планом приведен в разделе 4.1. Несмотря на то, что планируются правильные входные данные, предусмотрено сообщение «Ошибка ввода» на случай, если ошибка все же появится в данных или неправильно сработает vvod.

4.4 Отладка программы

Программа отлажена по плану на всех предусмотренных в нем тестах. Результаты тестирования приведены в приложении 7.

Во время отладки были обнаружены и исправлены следующие ошибки.

1. В модуле main вместо сообщения о выводе матрицы, выводилось сообщение ввода вершин A и B.

2. В модуле main вместо n<2 || n>NMAX, было написано n<1 || n>NMAX.

3. В модуле messages были перепутаны сообщения «Ошибка! Введено недопустимое значение» и «Ошибка! Количество вершин должно быть от 2 до 50».

4. В модуле poisk в стеке вместо st[NMAX+1] было написано st[NMAX].

5. В модуле vyvod при выводе матрицы смежности были перепутаны i и j.

ЗАКЛЮЧЕНИЕ

Курсовая работа выполнена в соответствии с требованиями и в полном объеме.

СПИСОК ЛИТЕРАТУРЫ

1. Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикум на ЭВМ. - М.: Наука, 1986. - 272 с.

2. Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с.

3. Хохлов Д.Г. Основы технологии модульного программирования: Учебное пособие. - Казань: КГТУ (КАИ), 2003. - 62с.

4. Медведев В. И., Рохлин Ф. З., Хохлов Д. Г. Технология программирования: Учебное пособие. - Казань: КАИ, 1983. - 56 с.

Приложение 1. Системный файлы проекта

1. Файл myprojec.prj - перечень модулей и библиотек проекта (указывается как имя проекта системе Turbo-C):

main.cpp

messages.cpp

vvod.cpp

vyvod.cpp

poisk.cpp

my.lib

2. Файл my.h - определения для библиотеки my.lib

#include <stdio.h>

#include <conio.h>

#define NMAX 50 /* Максимальное количество вершин графа */

/* Прототипы для библиотечных функций */

void message(int i);

int vvod(int n, int gr[][NMAX]);

void vyvod(int n, int gr[NMAX][NMAX]);

int poisk (int gr[NMAX][NMAX], int n, int A, int B);

Приложение 2. Текст программы модуля main

/************************************************************/

/* Курсовая работа */

/* по алгоритмическим языкам и программированию */

/* Поиск вершины между двумя выделенными вершинами */

/* Группа 28203 Д.В. Щербакова */

/************************************************************/

#include "my.h"

void main()

{ clrscr();

int n; // Количество вершин графа

A, B, p; // Выделенные вершины и признак вершины

int gr[NMAX][NMAX]; // Матрица смежности

int i, j, flag=0; // Переменные цикла

do { message(1); // «Введите кол-во вершин…»

scanf("%d", &n); // Ввод количества вершин графа

flag=0; // Признак правильности ввода кол-ва вершин

if (n<2 || n>NMAX){ message(3); flag=1;} // Если n неправильное, «Недопустимое зн-ие...»

}

while (flag==1);

kol=vvod(n,gr); // Ввод ребер графа

message(2); // «Матрица смежности:»

vyvod(n,gr); // Вывод матрицы смежности

message(7); // «Введите A и B…»

do

{scanf ("%d",&A); // Ввод A

scanf ("%d",&B) ; // Ввод B

if (A<0 || A>=n) message(8); // Если A неверно, «A неверно…»

if (B<0 || B>=n) message(9); // Если B неверно, «B неверно…»

if (A==B) message(10); // Если A=B, «A не должно быть равно B»

}

while (A<0 || A>=n || B<0 || B>= n || A==B); // Выполнять ввод пока не будет правильно

p=poisk ( gr,n, A, B); // Поиск вершины

if (p==0) message(11); // Если признак вершины = 0, «нет вершин»

getch();

}

Приложение 3. Текст программы модуля vvod

/************************************************************/

/* Ввод перечня ребер в матрицу смежности */

/* Щербаков Д.В. */

/************************************************************/

#include "my.h"

void vvod(int n, int gr[NMAX][NMAX]) {

int i,j; // Переменные цикла

f=0; // Признак проверки повторения ребер

for(i=0;i<n;i++)

for(j=0;j<n;j++)

gr[i][j]=0; // Обнуление матрицы смежности

message(5); // «Введите ребра…»

while(scanf("%d %d", &i, &j)==2) // Ввод ребер графа

{ if (i==j) // Если i=j (введена петля)

message(3); // «Недопустимое значение…»

else

if (i>=n||i<0||j>=n||j<0) // Введена не существующая вершина

message(3); // «Недопустимое значение…»

else

{ gr[i][j]=1; if (gr[j][i]==0) gr[j][i]=1; else f=1;} /* если сущ-ет ребро i-j, то создаем и ребро j-i, иначе обнаружено повторение ребер */

}

if (f==1) message(6); // «Повторение ребер…»

}

Приложение 4. Текст программы модуля vyvod

/************************************************************/

/* Вывод матрицы смежности gr графа */

/* Щербаков Д.В. */

/***********************************************************/

#include "my.h"

void vyvod(int n, int gr[NMAX][NMAX])

{ int i,j; // Переменные цикла

for(i=0;i<n;i++)

{ for(j=0;j<n;j++) printf("%d ", gr[i][j]); printf("\n"); // Вывод матрицы смежности графа gr

}

}

Приложение 5. Текст программы модуля poisk

#include "my.h"

int poisk (int gr[NMAX][NMAX], int n, int A, int B)

{ int st[NMAX+1]; // Стек

int i, j; // Переменные цикла

int jp; // Столбец с которой ведется поиск новой вершины

int l; // Переменная цикла

int vp[NMAX]; // Вектор посещений

int kolput=0; // Обнуление количества путей

int m[NMAX]; // Массив, который заносит путь в стек

int flag=0; // Обнуление признака вершины

int uk=0; // Обнуление указателя стека

for(i=0;i<n;i++)

{vp[i]=0; m[i]=0;} // Обнуление массива и вектора посещений

st[0]=A; // Нулевой элемент стека равен вершине A

vp[A]=1; // Отмечаем A элемент посещенным

i=0;

jp=0;

do

{ i=st[uk]; // Присваивание uk элемента стека строке i

j=jp; // Присваивание столбцу j номер столбца jp

while (j<n && (gr[i][j]==0 || vp [j]==1)) j++;

if (j<n)

{uk++;

st[uk]=j; // Присваивание uk элементу стека числа j

jp=0;

vp[j]=1; // Отметили посещенной

if (j==B) // Если j равно конечной вершине B

{for (l=0;l<=uk;l++)

m[st[l]]++; // Заносим стек в массив

kolput++; // Увеличиваем на 1 количество путей

jp=st[uk]; vp[jp]=0; // Возвращаемся

jp++;

uk--;

}

}

else

{jp=st[uk]; vp[jp]=0;

jp++;

uk--;

}

}

while (uk>=0);

message(12);

for(i=0;i<n;i++)

if (m[i]==kolput&& i!=A &&i!=B)

{ printf("%d ",i); flag=1;} // Вывод найденных вершин

return flag;

}

Приложение 6. Текст программы модуля messages

/************************************************************/

/* Вывод i-го сообщения */

/* Щербаков Д.В. */

/*********************************************************/

#include "my.h"

void message(int i)

{ char *t[]={" ",

/*1*/ "\n Enter the number of points (2-50): \n",

/*2*/ "\n Matrix: \n",

/*3*/ "\n Error! Wrong number, try again \n",

/*4*/ "\n Error! Number of points must be from 2 till 50: \n",

/*5*/ "\n Enter the parts of graph (end Ctrl-Z): \n",

/*6*/ "\n Warning! Repeated edges of the count are found out, the programm will ignore them \n",

/*7*/ "\n Enter A & B: \n",

/*8*/ "\n Error! A is incorrect, try again: \n",

/*9*/ "\n Error! B is incorrect, try again: \n",

/*10*/ "\n Error! A not must be B (A ne ravno B) \n",

/*11*/ "the programm didn't found this points. \n",

/*12*/ "\n Found points: ",

};

printf("%s", t[i]);

}

Приложение 7. Результаты тестирования программы

1. Тестирование с правильными входными данными.

Тест 2

Введите количество вершин (от 2 до 50): 6

Введите ребра (конец ввода Ctrl-Z): 0 1, 0 2, 0 3, 1 3, 2 3, 2 5, 3 4, 4 5 ^Z

Введите вершины A и B: 0 4

Найденные вершины: таких вершин в графе нет.

Тест 5

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 0 1, 0 2, 0 3, 1 0, 1 3, 2 0, 2 3, 3 0, 3 1, 3 2, 3 4 ^Z

Внимание! Найдены повторные ребра, программа будет их игнорировать!

Введите вершины A и B: 0 4

Найденные вершины: 3

2. Тестирование с неправильными входными данными.

Тест 1

Введите количество вершин (от 2 до 50): 1

Ошибка! Количество вершин должно находиться в интервале от 2 до 50!

Тест 3

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 0 1, 0 2, 0 3, 0 4, 0 5 ^Z

Ошибка! Введено недопустимое значение!

Тест 4

Введите количество вершин (от 2 до 50): 60

Ошибка! Количество вершин должно находиться в интервале от 2 до 50!

Тест 6

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): -1 0, 0 1, 0 2, 0 3, 1 3, 2 3, 3 4 ^Z

Ошибка! Введено недопустимое значение!

Тест 7

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 0 1, 0 2, 0 3, 1 3, 2 3, 3 4 ^Z

Введите вершины A и B: -1 4

Ошибка! Недопустимое значение A, попробуйте еще раз!

Тест 8

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 0 1, 0 2, 0 3, 1 3, 2 3, 3 4 ^Z

Введите вершины A и B: 5 4

Ошибка! Недопустимое значение A, попробуйте еще раз!

Тест 9

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 0 1, 0 2, 0 3, 1 3, 2 3, 3 4 ^Z

Введите вершины A и B: 4 4

Ошибка! Вершина A не должна совпадать с вершиной B, попробуйте еще раз!

Тест 10

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 0 1, 0 2, 0 3, 1 3, 2 3, 3 4 ^Z

Введите вершины A и B: 0 -1

Ошибка! Недопустимое значение B, попробуйте еще раз!

Тест 11

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 0 1, 0 2, 0 3, 1 3, 2 3, 3 4 ^Z

Введите вершины A и B: 0 5

Ошибка! Недопустимое значение B, попробуйте еще раз!

Тест 12

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 0 1, 0 2, 0 3, 1 1, 1 3, 2 3, 3 4 ^Z

Ошибка! Введено недопустимое значение!

Тест 13

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 0 -1, 0 1, 0 2, 0 3, 1 3, 2 3, 3 4 ^Z

Ошибка! Введено недопустимое значение!

Тест 14

Введите количество вершин (от 2 до 50): 5

Введите ребра (конец ввода Ctrl-Z): 4 0, 4 1, 4 2, 4 3, 5 4 ^Z

Ошибка! Введено недопустимое значение!

Приложение 8. Трудоемкость курсовой работы

Общий объем программы (количество строк исходного текста) - 115

Количество модулей программы - 5

Объем модулей (количество строк)

main - главный модуль - 28

vvod - ввод графа - 19

vyvod - вывод матрицы смежности - 7

messages - сообщения - 18

poisk - поиск вершин - 43

Время (час) затраченное на работу - 52 ч

В том числе по этапам:

постановка и анализ задачи - 3 ч

проектирование - 14 ч

программирование - 7 ч

отладка - 19 ч

оформление - 9 ч

Приложение 9. Дневник выполнения курсовой работы

(сокращен)

Дата	Работа	Время ч, мин.	Отметка преподавателя
10.09	Получение задания	10'
11.09	Изучение задачи по литературе	4 ч
12.09	Анализ задачи	1 ч
17.09	Внешнее проектирование задания	1 ч
19.09	Проектирование тестов черного ящика	3 ч
20.09	Проектирование модулей main, vvod, vyvod	2 ч
1.10	Программирование модулей main, vvod, vyvod	3 ч
4.10	Проектирование модулей poisk	2 ч
6.10	Программирование модуля poisk	4 ч
11.10	Отладка (поиск ошибок)	2 ч
15.10	Отладка: все тесты прошли	10 ч
20.10	Оформление отчета	7 ч

Размещено на Allbest.ru