Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.145.175.243] |
|
Страницы: (4) « Первая ... 2 3 [4] все ( Перейти к последнему сообщению ) |
Сообщ.
#46
,
|
|
|
& убери, в printf
|
Сообщ.
#47
,
|
|
|
Олег Мвывело 4 и 5 как и должно быть. Что дальше.
|
Сообщ.
#48
,
|
|
|
Уже лучше. Теперь выведи содержимое матриц
|
Сообщ.
#49
,
|
|
|
А как вывод то матрицы указать?
|
Сообщ.
#50
,
|
|
|
for (int row = 0; row < M; row++) { // для каждой строки выделяем память под N элементов incidenceMatrix[row] = new int[N]; // считываем значения for (int column = 0; column < N; column++) { fscanf(f, "%d", &incidenceMatrix[row][column]); printf("%d ", incidenceMatrix[row][column]) } printf("\n") } |
Сообщ.
#51
,
|
|
|
Олег М
#include <stdlib.h> #include <stdio.h> #include <conio.h> #include <Windows.h> #include <malloc.h> #include <locale.h> //#include <fstream> #define u 100 //using namespace std; /*Ñòðóêòóðà âåðøèíû ãðàôà, ïðåäñòàâëåííîãî ñïèñêîì ñìåæíîñòè*/ typedef struct ListNode_ { int info; ListNode_ *next; } ListNode; bool flag [u]= {false}; ListNode *BEGIN[u]; /*Íàáîð ïðîöåäóð, ðåàëèçóþùèõ îáõîä â øèðèíó BFS*/ struct QueneNode { int info; QueneNode *next; }; QueneNode *BeginQuene; QueneNode *EndQuene; void InitQuene() { BeginQuene=NULL; EndQuene=NULL; } void EnQuene(int x)//çàíåñåíèå â î÷åðåäü { QueneNode *p; p=(QueneNode *) malloc(sizeof(QueneNode)); p->info=x; p->next=NULL; if(BeginQuene==NULL) BeginQuene=p; else EndQuene->next=p; EndQuene=p; } int DeQuene() { int val; QueneNode *p; p=(QueneNode *) malloc(sizeof(QueneNode)); p=BeginQuene; val=BeginQuene->info; BeginQuene=p->next; if(BeginQuene==NULL) EndQuene=NULL; free(p); return val; } bool IsEmptyQuene() { if(EndQuene==NULL) return true; else return false; } void BFS(int cur) { EnQuene(cur); flag[cur] = true; while (IsEmptyQuene() != true) { cur = DeQuene(); ListNode *List = BEGIN[cur]; while (List != NULL) { if (flag[List->info] == false) { EnQuene(List->info); flag[List->info] = true; printf("%d-%d\n", cur + 1, List->info + 1); } List = List->next; } } } int main() { int i,j,M, N, column, row; // ðàçìåðû ìàòðèöû èíöèäåíòíîñòè SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","r"); fscanf(f,"%d %d\n", &M, &N); printf("%d %d\n", M, N); // âûäåëÿåì ïàìÿòü ïîä M ñòðîê äëÿ ìàòðèöû èíöèäåíòîñòè int **incidenceMatrix = new int*[M]; for (row = 0; row < M; row++) { // äëÿ êàæäîé ñòðîêè âûäåëÿåì ïàìÿòü ïîä N ýëåìåíòîâ incidenceMatrix[row] = new int[N]; // ñ÷èòûâàåì çíà÷åíèÿ for (column = 0; column < N; column++) { fscanf(f, "%d", &incidenceMatrix[row][column]); printf("%d ", incidenceMatrix[row][column]); } } // adjacencyMatrix - ìàòðèöà èíöèäåíòíîñòè ðàçìåðàìè MxN // âûäåëÿåì ïàìÿòü äëÿ ìàòðèöû ñìåæíîñòè bool **adjacencyMatrix = new bool*[M]; for (row = 0; row < M; row++) { adjacencyMatrix[row] = new bool[M]; for (column = 0; column < M; column++) { adjacencyMatrix[row][column] = false; printf("%d ", adjacencyMatrix[row][column]); } } // çàïîëíÿåì ìàòðèöó ñìåæíîñòè çíà÷åíèÿìè // ïðîõîäèìñÿ ïî êàæäîìó ñòîëáöó for (column = 0; column < N; column++) { // èíäåêñû îòêóäà è êóäà int from = -1, to = -1; // èùåì ñòðîêó, ãäå áóäåò óêàçàíà èíôîðìàöèÿ îòêóäà (1) è êóäà (-1) for (row = 0; row < M && (from == -1 || to == -1); row++) { if (incidenceMatrix[row][column] == 1) from = row; else if (incidenceMatrix[row][column] == -1) to = row; } // ïîìå÷àåì ïåðåõîä â ìàòðèöå ñìåæíîñòè adjacencyMatrix[from][to] = true; } for(i = 0 ; !feof(f); i++) { int n1; fscanf(f,"%d",&n1);/*ñ÷èòûâàåì êîëè÷åñòâî âåðøèí, ñìåæíûõ ñ i-é âåðøèíîé*/ for(j=0;j<n1;j++) { int a; fscanf(f,"%d",&a);/*ñ÷èòûâàåì íîìåð î÷åðåäíîé j-é âåðøèíû, ñìåæíîé ñ âåðøèíîé i */ ListNode *cuz= (ListNode*) malloc( sizeof(ListNode)); cuz->info=a-1;/*çàíîñèì â ïîëå info ñïèñêà çíà÷åíèå íîìåðà j-é ñìåæíîé âåðøèíû íà 1 ìåíüøå åå ðåàëüíîãî íîìåðà, òàê êàê â ìàññèâå âåðøèí íóìåðàöèÿ ýëåìåíòîâ íà÷èíàåòñÿ ñ 0, à íå ñ 1, êàê íóìåðóþòñÿ âåðøèíû ãðàôà */ cuz->next=BEGIN[i]; BEGIN[i]=cuz; } } fclose(f); int FST; printf("Ââåäèòå íîìåð âåðøèíû, ñ êîòîðîé áóäåò íà÷àò îáõîä ãðàôà â øèðèíó:\n"); scanf("%d", &FST); /*Ïîäãîòîâêà ìàññèâà flag ê èñïîëüçîâàíèþ äëÿ ïîèñêà â øèðèíó*/ printf("\nÎáõîä â øèðèíó BFS\n"); for(i=0;i<u;i++) flag[i]=false; /*Ðåàëèçàöèÿ ïîèñêà â øèðèíó*/ InitQuene(); BFS(FST-1); getch(); for(i=0;i<u;i++) { ListNode *cuz, *tmp; cuz=BEGIN[i]; while(cuz!=NULL) { tmp=cuz; cuz=cuz->next; free(tmp); } } return 0; } Похоже, что преобразование не проходит: видно лишь исходную матрицу, а смежность нет Добавлено 4 5 1 0 0 -1 0 -1 1 0 0 -1 0 0 1 1 1 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Введите номер вершины, с которой будет начат обход графа в ширину: Добавлено Похоже попутаны списки смежности и матрица смежности. Добавлено #include <stdlib.h> #include <stdio.h> #include <conio.h> #include <Windows.h> #include <malloc.h> #include <locale.h> //#include <fstream> #define u 100 //using namespace std; /*Ñòðóêòóðà âåðøèíû ãðàôà, ïðåäñòàâëåííîãî ñïèñêîì ñìåæíîñòè*/ typedef struct ListNode_ { int info; ListNode_ *next; } ListNode; bool flag [u]= {false}; ListNode *BEGIN[u]; /*Íàáîð ïðîöåäóð, ðåàëèçóþùèõ îáõîä â øèðèíó BFS*/ struct QueneNode { int info; QueneNode *next; }; QueneNode *BeginQuene; QueneNode *EndQuene; void InitQuene() { BeginQuene=NULL; EndQuene=NULL; } void EnQuene(int x)//çàíåñåíèå â î÷åðåäü { QueneNode *p; p=(QueneNode *) malloc(sizeof(QueneNode)); p->info=x; p->next=NULL; if(BeginQuene==NULL) BeginQuene=p; else EndQuene->next=p; EndQuene=p; } int DeQuene() { int val; QueneNode *p; p=(QueneNode *) malloc(sizeof(QueneNode)); p=BeginQuene; val=BeginQuene->info; BeginQuene=p->next; if(BeginQuene==NULL) EndQuene=NULL; free(p); return val; } bool IsEmptyQuene() { if(EndQuene==NULL) return true; else return false; } void BFS(int cur, int end) { EnQuene(cur); flag[cur] = true; while (IsEmptyQuene() != true) { cur = DeQuene(); ListNode *List = BEGIN[cur]; while (List != NULL) { if (flag[List->info] == false && cur < end) { EnQuene(List->info); flag[List->info] = true; printf("%d-%d\n", cur + 1, List->info + 1); } List = List->next; } } } int main() { int i,j,M, N, column, row; // ðàçìåðû ìàòðèöû èíöèäåíòíîñòè SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","rt"); fscanf(f,"%d %d\n", &M, &N); //printf("%d %d\n", M, N); // âûäåëÿåì ïàìÿòü ïîä M ñòðîê äëÿ ìàòðèöû èíöèäåíòîñòè int **incidenceMatrix = new int*[M]; for (row = 0; row < M; row++) { // äëÿ êàæäîé ñòðîêè âûäåëÿåì ïàìÿòü ïîä N ýëåìåíòîâ incidenceMatrix[row] = new int[N]; // ñ÷èòûâàåì çíà÷åíèÿ for (column = 0; column < N; column++) fscanf(f, "%d", &incidenceMatrix[row][column]); //printf("%d ", incidenceMatrix[row][column]); } // adjacencyMatrix - ìàòðèöà èíöèäåíòíîñòè ðàçìåðàìè MxN // âûäåëÿåì ïàìÿòü äëÿ ìàòðèöû ñìåæíîñòè bool **adjacencyMatrix = new bool*[M]; for (row = 0; row < M; row++) { adjacencyMatrix[row] = new bool[M]; for (column = 0; column < M; column++) adjacencyMatrix[row][column] = false; } // çàïîëíÿåì ìàòðèöó ñìåæíîñòè çíà÷åíèÿìè // ïðîõîäèìñÿ ïî êàæäîìó ñòîëáöó for (column = 0; column < N; column++) { // èíäåêñû îòêóäà è êóäà int from = -1, to = -1; // èùåì ñòðîêó, ãäå áóäåò óêàçàíà èíôîðìàöèÿ îòêóäà (1) è êóäà (-1) for (row = 0; row < M && (from == -1 || to == -1); row++) { if (incidenceMatrix[row][column] == 1) from = row; else if (incidenceMatrix[row][column] == -1) to = row; } // ïîìå÷àåì ïåðåõîä â ìàòðèöå ñìåæíîñòè adjacencyMatrix[from][to] = true; } for(i = 0 ; !feof(f); i++) { int n1; fscanf(f,"%d",&n1);/*ñ÷èòûâàåì êîëè÷åñòâî âåðøèí, ñìåæíûõ ñ i-é âåðøèíîé*/ for(j=0;j<n1;j++) { int a; fscanf(f,"%d",&a);/*ñ÷èòûâàåì íîìåð î÷åðåäíîé j-é âåðøèíû, ñìåæíîé ñ âåðøèíîé i */ ListNode *cuz= (ListNode*) malloc( sizeof(ListNode)); cuz->info=a-1;/*çàíîñèì â ïîëå info ñïèñêà çíà÷åíèå íîìåðà j-é ñìåæíîé âåðøèíû íà 1 ìåíüøå åå ðåàëüíîãî íîìåðà, òàê êàê â ìàññèâå âåðøèí íóìåðàöèÿ ýëåìåíòîâ íà÷èíàåòñÿ ñ 0, à íå ñ 1, êàê íóìåðóþòñÿ âåðøèíû ãðàôà */ cuz->next=BEGIN[i]; BEGIN[i]=cuz; } } fclose(f); int FST; printf("Ââåäèòå íîìåð âåðøèíû, ñ êîòîðîé áóäåò íà÷àò îáõîä ãðàôà â øèðèíó:\n"); scanf("%d", &FST); int End; printf("Ââåäèòå íîìåð âåðøèíû, íà êîòîðîé áóäåò çàâåðøåí îáõîä ãðàôà â øèðèíó:\n"); scanf("%d", &End); /*Ïîäãîòîâêà ìàññèâà flag ê èñïîëüçîâàíèþ äëÿ ïîèñêà â øèðèíó*/ printf("\nÎáõîä â øèðèíó BFS\n"); for(i=0;i<u;i++) flag[i]=false; /*Ðåàëèçàöèÿ ïîèñêà â øèðèíó*/ InitQuene(); BFS(FST-1,End); getch(); for(i=0;i<u;i++) { ListNode *cuz, *tmp; cuz=BEGIN[i]; while(cuz!=NULL) { tmp=cuz; cuz=cuz->next; free(tmp); } } return 0; } Добавил проверку на каком элементе закончить. |
Сообщ.
#52
,
|
|
|
Цитата tdmods @ for(i = 0 ; !feof(f); i++) { int n1; fscanf(f,"%d",&n1);/*ñ÷èòûâàåì êîëè÷åñòâî âåðøèí, ñìåæíûõ ñ i-é âåðøèíîé*/ for(j=0;j<n1;j++) А это что? Ты ж вроде уже весь файл вычитал в матрицу. |
Сообщ.
#53
,
|
|
|
Олег Мсчитывает количество смежных вершин
Добавлено Блин а оно же тут из файла пишется... вот и |
Сообщ.
#54
,
|
|
|
Цитата tdmods @ Что-то вас не поймёшь: то исправляете эту ошибку, то снова её пишете. Как же в итоге? p=(QueneNode *) malloc(sizeof(QueneNode)); p=BeginQuene; |
Сообщ.
#55
,
|
|
|
#include <stdlib.h> #include <stdio.h> #include <conio.h> #include <Windows.h> #include <malloc.h> #include <locale.h> //#include <fstream> #define u 100 //using namespace std; /*Структура вершины графа, представленного списком смежности*/ typedef struct ListNode_ { int info; ListNode_ *next; } ListNode; bool flag [u]= {false}; ListNode *BEGIN[u]; /*Набор процедур, реализующих обход в ширину BFS*/ struct QueneNode { int info; QueneNode *next; }; QueneNode *BeginQuene; QueneNode *EndQuene; void InitQuene() { BeginQuene=NULL; EndQuene=NULL; } void EnQuene(int x)//занесение в очередь { QueneNode *p; p=(QueneNode *) malloc(sizeof(QueneNode)); p->info=x; p->next=NULL; if(BeginQuene==NULL) BeginQuene=p; else EndQuene->next=p; EndQuene=p; } int DeQuene() { int val; QueneNode *p; if( !BeginQuene ) return -666; // пусто, нечего удалять p = BeginQuene; val = BeginQuene->info; BeginQuene = p->next; if( BeginQuene==NULL ) EndQuene = NULL; free( p ); return val; } bool IsEmptyQuene() { if(EndQuene==NULL) return true; else return false; } void BFS(int cur, int end) { EnQuene(cur); flag[cur] = true; while (IsEmptyQuene() != true) { cur = DeQuene(); ListNode *List = BEGIN[cur]; while (List != NULL) { if (flag[List->info] == false && cur < end) { EnQuene(List->info); flag[List->info] = true; printf("%d-%d\n", cur + 1, List->info + 1); } List = List->next; } } } int main() { int i,j,M, N, column, row; // размеры матрицы инцидентности SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","rt"); fscanf(f,"%d %d\n", &M, &N); //printf("%d %d\n", M, N); // выделяем память под M строк для матрицы инцидентости int **incidenceMatrix = new int*[M]; for (row = 0; row < M; row++) { // для каждой строки выделяем память под N элементов incidenceMatrix[row] = new int[N]; // считываем значения for (column = 0; column < N; column++) fscanf(f, "%d", &incidenceMatrix[row][column]); //printf("%d ", incidenceMatrix[row][column]); } // adjacencyMatrix - матрица инцидентности размерами MxN // выделяем память для матрицы смежности bool **adjacencyMatrix = new bool*[M]; for (row = 0; row < M; row++) { adjacencyMatrix[row] = new bool[M]; for (column = 0; column < M; column++) adjacencyMatrix[row][column] = false; } // заполняем матрицу смежности значениями // проходимся по каждому столбцу for (column = 0; column < N; column++) { // индексы откуда и куда int from = -1, to = -1; // ищем строку, где будет указана информация откуда (1) и куда (-1) for (row = 0; row < M && (from == -1 || to == -1); row++) { if (incidenceMatrix[row][column] == 1) from = row; else if (incidenceMatrix[row][column] == -1) to = row; } // помечаем переход в матрице смежности adjacencyMatrix[from][to] = true; } for(i = 0 ; !feof(f); i++) { int n1; for(j=0;j<4;j++) { int a; fscanf(f,"%d",&a);/*считываем номер очередной j-й вершины, смежной с вершиной i */ ListNode *cuz= (ListNode*) malloc( sizeof(ListNode)); cuz->info=a-1;/*заносим в поле info списка значение номера j-й смежной вершины на 1 меньше ее реального номера, так как в массиве вершин нумерация элементов начинается с 0, а не с 1, как нумеруются вершины графа */ cuz->next=BEGIN[i]; BEGIN[i]=cuz; } } fclose(f); int FST; printf("Введите номер вершины, с которой будет начат обход графа в ширину:\n"); scanf("%d", &FST); int End; printf("Введите номер вершины, на которой будет завершен обход графа в ширину:\n"); scanf("%d", &End); /*Подготовка массива flag к использованию для поиска в ширину*/ printf("\nОбход в ширину BFS\n"); for(i=0;i<u;i++) flag[i]=false; /*Реализация поиска в ширину*/ InitQuene(); BFS(FST-1,End); getch(); for(i=0;i<u;i++) { ListNode *cuz, *tmp; cuz=BEGIN[i]; while(cuz!=NULL) { tmp=cuz; cuz=cuz->next; free(tmp); } } return 0; } |
Сообщ.
#56
,
|
|
|
А ты зачем adjacencyMatrix строил, если нигде её потом не используешь? Насколько я понимаю, именно по ней путь и ищется
|
Сообщ.
#57
,
|
|
|
Олег М вот и ответ. Как ее вписать?
Добавлено for(i = 0 ;i< adjacencyMatrix [row]; i++) { int n1; fscanf(f,"%d",&n1);/*????????? ?????????? ??????, ??????? ? i-? ????????*/ for(j=0;j<n1;j++) { int a; fscanf(f,"%d",&a);/*ñ÷èòûâàåì íîìåð î÷åðåäíîé j-é âåðøèíû, ñìåæíîé ñ âåðøèíîé i */ ListNode *cuz= (ListNode*) malloc( sizeof(ListNode)); cuz->info=a-1;/*çàíîñèì â ïîëå info ñïèñêà çíà÷åíèå íîìåðà j-é ñìåæíîé âåðøèíû íà 1 ìåíüøå åå ðåàëüíîãî íîìåðà, òàê êàê â ìàññèâå âåðøèí íóìåðàöèÿ ýëåìåíòîâ íà÷èíàåòñÿ ñ 0, à íå ñ 1, êàê íóìåðóþòñÿ âåðøèíû ãðàôà */ cuz->next=BEGIN[i]; BEGIN[i]=cuz; } } Как я понял нужно править вот этот кусок. Как? |
Сообщ.
#58
,
|
|
|
"Беглым взглядом вижу, что преобразование Вы закончили. Теперь, используя эту матрицу нужно решать. Как дальше делать - также как и со старой, только меняется порядок вершин. Если раньше все были в списке смежные. То теперь для конкретной вершины cur нужно просмотреть все смежные, to, и если есть ребро cur->to, то добавляем to в очередь и т.д."
Как это реализовать? |