Программирование на языке С

Содержание
Аннотация
Введение
1.Анализ технического задания
2.Программная реализация
3.Описание программы
4.Руководство программиста
5.Методика испытаний
6.Заключение
7.Список литературы
Приложения
Блок-схема алгоритма программы
Текст программы

pVisited[i]i<iNumaТекст программыФайл: main.c//Автор программы://Фамилия:_______________Имя:___________Отчество:__________________//Курс:________ Группа:___________//////Программа решает задачу о возможности познакомиться всем участникам олимпиады,//при условии, что двое участников олимпиады могут познакомиться//только через общего знакомого.////Программа на этапе задания опрашивает пользователя на предмет://1. Колическтва участников.//2. Кто с кем знаком.////На этапе выдачи результатов - программа сообщает о возможности (невозможности)//познакомиться всем участникам олимпиады//Используемые в программе переменные и указатели//Переменные://int iNum - количество участников олимпиады;//int i, j - счетчики циклов//int fl - флаг наличия 0 в массиве посещенных вершин//int iHead - переменная, указывающая на голову очереди//int iCount - переменная, указывающая на хвост очереди//int iCurrent - переменная, которая будет хранить текущую вершину//Указатели://int *pArrayGraf - указатель на матрицу смежности, описывающую граф знакомств//int *pQueue - указатель на массив учереди//int *pVisited - указатель на массив посещенных вершин.////#include<stdio.h>#include<stdlib.h>int main(){int iNum = 0; printf("Enter a number of people, arrived on the Olympic Games - "); scanf("%d", &iNum); printf("On the Olympic Games there arrived %d of people\n", iNum);//Создаем динамический массив размерностью iNum X iNum//в этом массиве будет храниться матрица смежности,//описывающая граф, показывающий связи между олимпийцами//создадим iNum строкint (*pArrayGraf)[iNum];// выделение памяти для массива iNum x iNumpArrayGraf = malloc(iNum*iNum*sizeof(int));if (!pArrayGraf) { printf("There is not enough memory.\n"); exit(1); } printf("Memory is allocated\n");int i = 0, j = 0;//Заполним выделенный масив нулямиfor(i = 0;i < iNum; i++) {for(j = 0; j < iNum; j++){ pArrayGraf[i][j] = 0; } }////Задание знакомых прибывших на олимпиаду (заполнение матрицы смежности)////Тестовый пример №1/* pArrayGraf[0][1] = 1; pArrayGraf[0][2] = 1; pArrayGraf[1][0] = 1;pArrayGraf[1][2] = 1; pArrayGraf[1][3] = 1; pArrayGraf[2][0] = 1; pArrayGraf[2][1] = 1; pArrayGraf[2][1] = 1; pArrayGraf[2][3] = 1; pArrayGraf[2][4] = 0; pArrayGraf[3][1] = 1; pArrayGraf[3][2] = 1; pArrayGraf[3][4] = 0; pArrayGraf[4][2] = 0; pArrayGraf[4][3] = 0; /* ////Тестовыйпример №2 pArrayGraf[0][1] = 1; pArrayGraf[0][2] = 1; pArrayGraf[0][3] = 1; pArrayGraf[1][0] = 1; pArrayGraf[2][0] = 1; pArrayGraf[2][4] = 1; pArrayGraf[2][5] = 1; pArrayGraf[3][0] = 1; pArrayGraf[3][6] = 0; pArrayGraf[4][2] = 1; pArrayGraf[5][2] = 1; pArrayGraf[6][3] = 0; */////Заданиеграфавручнуюfor(i = 0; i < iNum; i++)for(j = i + 1; j < iNum; j++) {if(i!=j) {int sw = 0; printf("The Olympian of %d is familiar with the Olympian of %d? (Yes - 1 / No - 0) - ", i+1, j+1); scanf("%d",&sw); printf("\n");switch(sw) {case 0: pArrayGraf[i][j] = 0; pArrayGraf[j][i] = 0;break;case 1: pArrayGraf[i][j] = 1; pArrayGraf[j][i] = 1;break;default: pArrayGraf[i][j] = 1; pArrayGraf[j][i] = 1;break; } } }//Вывод содержимого массива на экранfor(i = 0;i < iNum; i++) {for(j = 0; j < iNum; j++) { printf("%d ", pArrayGraf[i][j]);} printf("\n"); }//Матрицу, описывающую граф знакомств, мы получили//Теперь нам надо определить является ли граф, описанный этой матрице, связным//Если граф связный, то перезнакомить всех олимпийцев - возможно,//если не - то нельзя.//Для определения связности графа, воспользуемся известным алгоритмом поиска в ширину// Для этого:// 1. Определим массив, который будет выполнять роль очереди:int *pQueue = malloc(iNum*sizeof(int));// 2. Массивпосещенныхвершинint *pVisited = malloc(iNum*sizeof(int));for(i = 0; i < iNum; i++) { pQueue[i] = 0; pVisited[i] = 0; }// 3. Головаочереди:int iHead = 0;// 4. Хвосточереди:int iCount = 0;// 5. Текущий элемент:int iCurrent = 0;//Помещаем первую вершину графа в очередь pQueue[iCount] = 1;//Увеличиваем указатель на хвост очереди iCount++;//Помечаем первую вершину, как посещенную pVisited[0] = 1;//Начинаем цикл поиска связанных с вершиной 1 вершинdo {//В переменную извлекаем головной элемент очереди iCurrent = pQueue[iHead]-1;//Увеличиваем указатель на голову очереди iHead++;//Ищем связанные вершины (в матрице смежности на пересечении//связанных вершин ставится единица), т.о. если iCurrent == 1,//то связная у связной вершины на пересечении будет стоять единица.for(i = 0; i < iNum; i++){//Проверяем условие смежности вершин и то что вершина еще была не посещенаif ((pArrayGraf[iCurrent][i] == 1) && (!pVisited[i])){//если смежная вершина есть и она еще не посещалась,//то добавляем ее в очередь pQueue[iCount] = (i+1);//увеличиваем указатель на конец очереди iCount++;//помечаем, как посещенную pVisited[i] = 1; } } }//цикл заканчивается, когда очередь исчерпаетсяwhile(iCount != iHead);//печать содержимое матрицы посещений printf("\n");for(j = 0; j < iNum; j++) { printf("%d ", pVisited[j]); } printf("\n\n");//печать содержимое очередиfor(j = 0; j < iNum; j++) { printf("%d ", pQueue[j]); }int fl = 0;//проверка связности (если в матрице посещений есть 0, то граф не связан)for(j = 0; j < iNum; j++) {if ((pVisited[j] == 0) && (fl == 0)) { printf("\nParticipants of the Olympic Games can`t get acquainted with each other."); fl = 1; } }if (fl == 0) printf("\nParticipants of the Olympic Games can get acquainted with each other.");//освобождениепамяти free(pArrayGraf); free(pQueue);free(pVisited);return 0;}