Поиск эйлерова пути в графе
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
а metka.
ВЫХОДНЫЕ ДАННЫЕ: количество помеченных вершин.
ЗНАЧЕНИЕ: нет.
РАБОЧИЕ ДАННЫЕ:
i - номер вершины;
result - количество помеченных вершин
АЛГОРИТМ: см. алгоритм 3.8., рис. 3.8.
Алгоритм 3.8 Алгоритм модуля marker
=0;(int i = 0; i < n; i++) if (massiv[i]==metka) result++; //подiет помеченных вершин
return result;//возврат количества помеченных вершин
.Подготовка к отладке программы
.1 План отладки
Работа практически всех модулей зависит от работы модуля VVOD, следовательно, его нужно отлаживать в первую очередь. Модуль VYVOD связан с модулем main: VYVOD выводит сообщения, возникающие при работе main, его нужно отлаживать параллельно. Правильность работы модуля poisk также тесно связан с главной программы, их работу необходимо синхронизировать. Работа модуля prov1 зависит от работы модуля marker, их нужно отлаживать вместе. А работа же модулей prov1 и prov2 может быть отлажена независимо от других модулей (за исключением нюанса, возникающего между prov1 и marker. Следовательно, получаем следующие этапы отладки:
)Тестирование модуля VVOD
)Тестирование модулей prov1 и marker
)Тестирование prov2
)Тестирование VYVOD и main
)Тестирование модулей poisk и main
)Тестирование всей программы
4.2 Проектирование тестов
4.2.1 Тесты черного ящика
Для проектирования тестов программы методами черного ящика с помощью эквивалентного разбиения входных и выходных данных на области эквивалентности составлен список ситуаций, каждая из которых должна создаваться хотя бы одним тестом. Тестовые ситуации приведены в табл. 4.1, в скобках указаны их номера.
Таблица 4.1 Области входных/выходных данных тестов программы
Входное/выходное условие (значение)Правильные классы эквивалентностиНеправильные классы эквивалентностиКоличество вершин n2 тАж NMAX (1)2 (9)Входной файлНе пустой (10)Пустой (11)
Для создания перечисленных тестовых ситуаций разработаны тесты, представленные в табл. 4.2. Входные и выходные данные тестов по возможности выбирались ближе к границам классов эквивалентности.
Таблица 4.2 Тесты черного ящика для отладки программы
НомерВходВыходОсновные ситуации15 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0Эйлеров путь: 012342(1), (4), (6), (8), (10)21 . . .Сообщение 5(2)325 тАжСообщение 5(3)4Сообщение 3(5)5Сообщение 4(11)64 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0Сообщение 2(9)73 0 1 0 1 0 0 0 0 0Сообщение 2(7)
4.2.2 Тесты белого ящика
Разработанные тесты проверены методами белого ящика по критериям охвата основных путей выполнения алгоритмов модулей. В программе имеются составные условия. Поэтому использован критерий комбинаторного покрытия условий.
Таблица 4.3 Комбинаторное покрытие условий тестами черного ящика
МодульЭлементарное условиеНомера тестовИстинаЛожьmainVVOD(&n,g)!=02.3.4.51.6.7prov1(n,g)==671.6prov2(n,g)==761g[res[i]][res[i+1]]==116k==no-116vvodf!=NULL1.2.3.5.6.74*n261.7poiskV==01*VYVODcase 52.31.4.5.6.7case 341.5.6.7case 451.6.7case 26.71* значение V всегда становится равным нулю, можно iитать, что это условие не бывает ложным
Из табл. 4.3 видно, что тесты черного ящика не обеспечивают истинное значение условия k%2!=0 в модуле prov2, т.е. остаток от деления на два степени вершины. Для покрытия истинного значения этого условия разработан тест , представленный в табл. 4.4.
Таблица 4.4 Тесты белого ящика
НомерВходВыходОсновные ситуации7n=3 0 1 1 1 0 1 1 1 00,1,2(1), (4), (6), (8), (10)
.3 Отладка программы
Программа отлажена по плану на всех предусмотренных в нем тестах.
Во время отладки были обнаружены следующие ошибки:
)В модуле prov1 в условии (g[v][j]==1)||(massiv[j]==1) нужно условие или заменит на и, программа в первом случае работает некорректно, по исправлении же условия стали выполняться.
)В модуле поиск при присвоении v верхнего значения стека, указатель стека следовало уменьшить на единицу, так как указатель ссылается на последующий свободный после последнего элемент.
СПИСОК ЛИТЕРАТУРЫ
1.Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практимуму на ЭВМ. М.:Наука, 1986.
2.Липский В. Комбинаторика для программистов. М.: Мир, 1988.
.Хохлов Д.Г. Основы технологии модульного программирования: Учебное пособие. Казань: Изд-во Казан. гос. техн. ун-та, 2005.
.Белецкий Я. Энциклопедия языка Си. М.: Мир, 1992.
.Хохлов Д.Г. структуры данных и комбинаторные алгоритмы: Учебное пособие. Казань: Изд-во Казан. гос. техн. ун-та, 2006. 102 с.
Приложение 1
Текст программы
#include
#include
#include
#define NMAX 20
prov2(int n,int g[][NMAX])
{i,j,t=0,k=0;(i=0;i<n;i++)
{for (j=0;j2) return 7;=0;
}0;
}
Poisk(int v, int n,int g[][NMAX], int *no, int res[NMAX])
{stack[NMAX]={0},ns=0,V=0,i,j;
[ns++]=v;(ns!=0)
{=0;=stack[ns-1];(i = 0; i < n; i++) V+=g[v][i];(V==0) ns--,res[(*no)++]=v;
{=0;(g[v][i]!=1) i++;[v][i]=0;[i][v]=0;[ns++]=i;
}
}
}
VVOD(int *n,int g[][NMAX])
{i,j;*f; ((f=fopen("","r"))!=NULL)
{(f,"%d",n);((*n20)) return 5;(feof(f)) return 4;(i=0;i<(*n);i++)(j=0;j<(*n);j++)(f,"%d",&g[i][j]);
}return 3;0;
}marker(int n, int massiv[], int metka)
{result=0;(int i = 0; i < n; i++) if (massiv[i]==metka) result++;result;
}
prov1(int n,int g[][NMAX])
{v=0;*massiv=(int*)malloc(sizeof(int)*n);(int i=0; i < n; i++) massiv[i]=1;[v]=2;(marker(n,massiv,2)!=0)
{(int i=0; i < n; i++) if (massiv[i]==2){ v=i; break;}(int i=0; i < n; i++) printf("%d\n",massiv[i]);("\n");[v]=3;(int j=0; j < n; j++) if ((g[v][j]==1)&&(massiv[j]==1)) massiv[j]=2;
}(int i=0; i < n; i++) if (massiv[i]==1) return 6;
0;
}
Vyvod(int pr)
{(pr)
{5: {printf("nedopustimoe k