| ← Июнь 2017 → | ||||||
|
1
|
2
|
3
|
||||
|---|---|---|---|---|---|---|
|
6
|
7
|
8
|
11
|
|||
|
12
|
13
|
14
|
15
|
16
|
17
|
|
|
19
|
20
|
22
|
23
|
24
|
25
|
|
|
26
|
27
|
28
|
29
|
30
|
||
За последние 60 дней ни разу не выходила
Сайт рассылки:
http://prog.rusfaq.ru/C
Открыта:
14-03-2002
Статистика
0 за неделю
RFpro.ru: Программирование на C / C++
| РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты в разделе
∙ С / С++
Здравствуйте! Прошу помощи в следующем вопросе:
Дата отправки: 30.05.2017, 19:53 Консультирует Лысков Игорь Витальевич (Старший модератор): Здравствуйте, pNod! Код :: выделить код #include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode
{
int count; //количество соседей текущего узла
int idx; //индекс по соседям (для поиска)
int* node; //массив номеров узлов соседей (как в файле)
}ListNode;
typedef struct EDGE
{
int a;
int b;
}EDGE;
//Определим некоторые переменные в глобальной памяти
// (для удобства, чтобы не передавать параметрами)
ListNode* list = NULL; //адрес массива узлов графа
int edgesFullCnt; //количество ребер графа
EDGE* edgesPath = NULL; //адрес массива ребер пути
//поиск ребра в массиве предыдущего пути
//параметры: номера узлов ребра и длина найденного пути
bool CmpEdge(int a1, int b1, int edgesPathCnt)
{
int i, a2, b2, temp;
//отсортируем, чтобы было a1 < b1
if (a1 > b1)
{
temp = a1;
a1 = b1;
b1 = temp;
}
//сравним ребро со всеми ребрами уже найденного пути
for (i=0; i<edgesPathCnt; i++)
{
//получаем очередное ребро, как пару номеров вершин
//отсортируем, чтобы было a2 < b2
a2 = edgesPath[i].a;
b2 = edgesPath[i].b;
if (a2 > b2)
{
temp = a2;
a2 = b2;
b2 = temp;
}
//проверяем на совпадение
if ((a1 == a2) && (b1 == b2))
return true; //ребро найдено
}
return false; //не найдено
}
//поиск пути
//параметры:
//номер узла и длина текущего пути
//возвращается длина найденного пути
int SearchPath(int node, int edgesPathCnt)
{
int idxNode = node-1; //индекс узла в массиве узлов графа list
//цикл по всем соседям текущего узла
for(list[idxNode].idx = 0; list[idxNode].idx<list[idxNode].count; list[idxNode].idx++)
{
//есть ли ребро от текущего узла до соседа в текущем пути
if (CmpEdge(node, list[idxNode].node[list[idxNode].idx], edgesPathCnt))
continue; //есть - смотрим следующего соседа
//нет - добавим ребро в текущий путь
//в поле "а" текущий узел
edgesPath[edgesPathCnt].a = node;
//одновременно увеличиваем длину найденного пути
edgesPath[edgesPathCnt++].b = list[idxNode].node[list[idxNode].idx];
//если найден еще не весь путь
if (edgesPathCnt != edgesFullCnt)
//продолжаем искать путь с соседа
edgesPathCnt = SearchPath(list[idxNode].node[list[idxNode].idx], edgesPathCnt);
//если полный путь найден, то выходим, возвращая длину найденного пути
if (edgesPathCnt == edgesFullCnt)
return edgesPathCnt;
//иначе исследуем следующего соседа
}
return edgesPathCnt-1; //прошли всех соседей, полный путь не нашли,
//вернем путь на 1 короче, т.е. исключим себя
//чтобы предок продолжил поиск со следующего соседа
}
int main()
{
int cnt = 0; //количество узлов
int i, j, k, First;
int edgesPathCnt; //длина найденного пути
FILE * f = fopen("graph.txt", "r");
if (f)
{
for(i=0; ; i++)
{
if (EOF == fscanf(f, "%d", &k)) //количество соседей узла
break; //читаем, пока читается
//перевыделяем память под массив структур-узлов, каждый раз на 1 больше
list = (ListNode*)realloc(list, (cnt+1)*sizeof(ListNode));
list[cnt].count = k; //сохраним количество соседей для узла
//количество ребер равно половине сумме количеств соседей всех узлов
edgesFullCnt += k; //накопим эту сумму
//выделяем память под массив соседей всех узлов
list[cnt].node = (int*)malloc(k * sizeof(int));
for(j = 0; j < k; j++)
fscanf(f, "%d", &list[cnt].node[j]); //считываем соседей
cnt++; //считаем узлы
}
edgesFullCnt /= 2; //количество ребер
//выделим память под искомый путь
edgesPath = (EDGE*)malloc(edgesFullCnt*sizeof(EDGE)); //путь
printf("Enter node number: ");
scanf("%d", &First);
if ((First>0) && (First<=cnt)) //проверим на корректность начального номера
{
//ищем путь, параметры: номер первого узла и длину найденного пути = 0
//получим длину найденного пути
edgesPathCnt = SearchPath(First, 0);
if(edgesPathCnt == edgesFullCnt) //нашли полный путь?
{
//выведем
printf("Full path found: ");
for(i=0; i<edgesPathCnt; i++)
printf("%d ", edgesPath[i].a); //в поле "а" последовательность проходимых узлов
printf("%d\n", edgesPath[i-1].b); //выведем поле "b" последнего узла, как последний узел
}
else
printf("Full path not found!\n");
}
else
printf("Node number error!\n");
}
else
printf("File error!\n");
//освободим память
if (list)
{
for(i=0; i<cnt; i++)
free(list[i].node);
free(list);
}
if(edgesPath)
free(edgesPath);
return 0;
}
Список смежности Код :: выделить код 3 2 4 5 3 1 4 5 2 4 5 4 1 2 3 5 4 1 2 3 4
Оценить выпуск | Задать вопрос экспертам
главная страница
|
стать участником
|
получить консультацию
|
| В избранное | ||
