Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.237.32.143] |
|
Страницы: (4) 1 2 [3] 4 все ( Перейти к последнему сообщению ) |
Сообщ.
#31
,
|
|
|
Здесь у тебя вроде все правильно, во всяком случае технически. У тебя переменным M N не присвоены значения, проверь чему они равны. Добавлено Смотои ниже, как у него используется adjacencyMatrix |
Сообщ.
#32
,
|
|
|
Используется, насколько я понял, как MxM. Ну тогда надо лишь комментарий поправить:
// adjacencyMatrix - матрица инцидентности размерами MxM Добавлено Блин, не понимаю, что (в Опере?)сломалось: в своём сообщении №33 смайлик рисовался. Поправил букву N на M и перестал рисоваться. Буковки пишутся. :wall: П.С. wall тоже, небось не нарисуется. |
Сообщ.
#33
,
|
|
|
Так вылета нет, я поправил. Теперь бы большую матрицу бы придумать, и проверку на максимальное количество добавить. Есть какой онлайн конструктор графов?
Добавлено #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) { 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() { SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); int i,j,M, N; // размеры матрицы инцидентности FILE *f=fopen("graph.txt","r"); fscanf(f,"%u",&M); fscanf(f,"%w",&N); // выделяем память под M строк для матрицы инцидентости int **incidenceMatrix = new int*[M]; 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]); } // adjacencyMatrix - матрица инцидентности размерами MxN // выделяем память для матрицы смежности bool **adjacencyMatrix = new bool*[M]; for (int row = 0; row < M; row++) { adjacencyMatrix[row] = new bool[M]; for (int column = 0; column < M; column++) adjacencyMatrix[row][column] = false; } // заполняем матрицу смежности значениями // проходимся по каждому столбцу for (int column = 0; column < N; column++) { // индексы откуда и куда int from = -1, to = -1; // ищем строку, где будет указана информация откуда (1) и куда (-1) for (int 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; } блин похоже не корректно выводит, можете погонять на разных наборах? Выводит что то, но что? |
Сообщ.
#34
,
|
|
|
Цитата tdmods @ fscanf(f,"%w",&N); Что такое "%w"? Здесь, наверное, "%d" должен быть. Да и для M тоже - они у тебя оба int объявлены |
Сообщ.
#35
,
|
|
|
Олег Месли ставлю %d, то вылет программы...
|
Сообщ.
#36
,
|
|
|
Цитата tdmods @ Олег Месли ставлю %d, то вылет программы... Сделай после fscanf(f,"%u",&M); fscanf(f,"%w",&N); - prinf("M=%d, N=%d\n", M, N); и посмотри, что там возвращается |
Сообщ.
#37
,
|
|
|
Олег М смысла в этом нет, так как туда он не доходит. Рушится в самом начале.
|
Сообщ.
#38
,
|
|
|
Вообще, судя по всему, тебе там надо делать fscanf("%d %d\n", &M, &N);
Добавлено Цитата tdmods @ Олег М смысла в этом нет, так как туда он не доходит. Рушится в самом начале. В каком начале? Поставь в каждой строчке в начале prinf("%d\n", __LINE__) и посмотри, которая последняя исполнится |
Сообщ.
#39
,
|
|
|
FILE *f=fopen("graph.txt","r");
fscanf(f,"%d %d\n", &M, &N); Тоже рушит программу сразу после старта, ничего не выводит, хотя попробую. И еще нужна матрица побольше, где взять ХЗ. |
Сообщ.
#40
,
|
|
|
Цитата tdmods @ Тоже рушит программу сразу после старта, ничего не выводит, хотя попробую. Нашёл строчку, которая последняя исполнилась? И покажи код |
Сообщ.
#41
,
|
|
|
Олег М
Вроде все таки перестало вылетать, такое чувство что из за того, что матрицу меняю вылет. #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; // размеры матрицы инцидентности SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","r"); fscanf(f,"%d %d\n", &M, &N); // выделяем память под M строк для матрицы инцидентости int **incidenceMatrix = new int*[M]; 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]); } // adjacencyMatrix - матрица инцидентности размерами MxN // выделяем память для матрицы смежности bool **adjacencyMatrix = new bool*[M]; for (int row = 0; row < M; row++) { adjacencyMatrix[row] = new bool[M]; for (int column = 0; column < M; column++) adjacencyMatrix[row][column] = false; } // заполняем матрицу смежности значениями // проходимся по каждому столбцу for (int column = 0; column < N; column++) { // индексы откуда и куда int from = -1, to = -1; // ищем строку, где будет указана информация откуда (1) и куда (-1) for (int 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; } Но теперь после обход в ширину ничего не выводит, а прежний код выводил. |
Сообщ.
#42
,
|
|
|
Цитата tdmods @ Вроде все таки перестало вылетать, такое чувство что из за того, что матрицу меняю вылет. Ты выведи на экран то что ты начитал из файлов - переменные M и N и матрицы incidenceMatrix и adjacencyMatrix. Это для начала. А то так долго можно гадать, что именно не работает. |
Сообщ.
#43
,
|
|
|
Олег М ни черта не ясно мне.
4321318 6553180 int i,j,M, N; // размеры матрицы инцидентности SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); FILE *f=fopen("graph.txt","r"); fscanf(f,"%d %d\n", &M, &N); printf("%d %d\n"); Выводить не ясно что. |
Сообщ.
#44
,
|
|
|
Цитата tdmods @ Олег М ни черта не ясно мне. 4321318 6553180 Ты там забыл добавить M, N в printf |
Сообщ.
#45
,
|
|
|
FILE *f=fopen("graph.txt","r");
fscanf(f,"%d %d\n", &M, &N); printf("%d %d\n", &M, &N); 6553180 6553176 Введите номер вершины, с которой будет начат обход графа в ширину: |