Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.224.32.86] |
|
Страницы: (4) [1] 2 3 ... Последняя » все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Ребята день добрый. Не знаю правильный ли я выбрал раздел, но напишу сюда.
Задание: используя метод поиска в ширину, найти и вывести путь в ориентированном графе между двумя вершинами. Номера начальной и конечной вершин ввести с клавиатуры. Граф задать в текстовом файле матрицей инциденций. В методичке дан лишь один пример, лишь под смежность. Работаю с Dev C++, так как он дан в методичке. Я во первых не могу понять, что нужно поправить в программе под данный тип матрицы. И собственно саму матрицу подобрать. #include <stdlib.h> #include <stdio.h> #include <conio.h> #include <Windows.h> #include <malloc.h> #define n 100 #include <locale.h> /*Структура вершины графа, представленного списком смежно- сти*/ typedef struct ListNode_ { int info; ListNode_ *next; } ListNode; bool flag [n]= {false}; ListNode *BEGIN[n]; /*Набор процедур, реализующих обход в ширину 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) { EnQuene (List->info); flag[List->info]=true; printf("%d-%d\n", cur+1,List->info+1); } List=List->next; } } } int main() { int i,j; FILE *f = fopen ("graph.txt" , "r"); 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; int end; SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); printf("Введите номер вершины, с которой будет начат обход графа в ширину:\n"); scanf("%d", &FST); printf("Введите номер вершины, на которой будет закончен обход графа в ширину:\n"); scanf("%d", &end); /*Подготовка массива flag к использованию для поиска в ширину*/ printf("\nОбход в ширину BFS\n"); for(i=0;i<n;i++) flag[i]=false; /*Реализация поиска в ширину*/ InitQuene(); BFS(FST-1, end); getch(); for(i=0;i<n;i++) { ListNode *cuz, *tmp; cuz=BEGIN[i]; while(cuz!=NULL) { tmp=cuz; cuz=cuz->next; free(tmp); } } return 0; } |
Сообщ.
#2
,
|
|
|
1.В функции DeQuene() явно что-то не так, ибо на одной строке память выделяете, а на следующей же забиваете на неё; забываете адрес.
2.Функцию IsEmptyQuene() можно сократить до "bool IsEmptyQuene() { return EndQuene==NULL; }" |
Сообщ.
#3
,
|
|
|
Славян код из методического пособия.... Как мне быть......
|
Сообщ.
#4
,
|
|
|
П.С. это вы так случайно попутали букву u на n в слове "очередь"=Queue, или сознательно исказили слово?..
|
Сообщ.
#5
,
|
|
|
Код из методического пособия, ничего не правил.
|
Сообщ.
#6
,
|
|
|
Собственно, если DeQuene() удаляет узел, то её код должен быть каким-то таким:
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; } |
Сообщ.
#7
,
|
|
|
Алгоритм мне подсказали, но я никогда не делал такое и вообще бы не додумался бы до преобразования матриц.
Как преобразовать, могу подсказать алгоритм: 1. Начнем перебирать столбцы, j=1..M 1.1. Начнем перебирать все элементы столбца, i=1..N 1.1.1. Если очередной элемент столбца равен 1 - зафиксируем начало ребра. Т.е. если a[i][j] = 1, то x = i; 1.1.2. Если очередной элемент столбца равен -1 - зафиксируем конец ребра, т.е. если a[i][j] = -1, то y = i; 1.2 Добавим ребро (x, y) в матрицу смежности, т.е. ADJ[x][y] = TRUE Здесь a - матрица инциденций, размером NxM ADJ - матрица смежности, размером NxN Кто нибудь поймет что нужно сделать? |
Сообщ.
#8
,
|
|
|
Цитата tdmods @ В методичке дан лишь один пример, лишь под смежность. В методичке ведь не сказано "делать по примеру", верно? Таким образом, есть постановка задачи, и есть требование к результату. Первым делом читаем матчасть. Далее прогаем: Если есть методика, отличная от указанной в вики, и именно она требуется к исполнению - пересматриваем все три пункта под нее. Да, методика (читай алгоритм решения) будет иная, но методология та же. |
Сообщ.
#9
,
|
|
|
#include <stdlib.h> #include <stdio.h> #include <conio.h> #include <Windows.h> #include <malloc.h> #include <locale.h> #include <fstream> #define n 100 using namespace std; /*Структура вершины графа, представленного списком смежности*/ typedef struct ListNode_ { int info; ListNode_ *next; } ListNode; bool flag [n]= {false}; ListNode *BEGIN[n]; /*Набор процедур, реализующих обход в ширину 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; int M, N; // размеры матрицы инцидентности std::ifstream ifs("graph.txt"); // размеры я бы указал в файле первыми двумя значениями ifs >> 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++) ifs >> 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; int end; SetConsoleTitleW(L"Lab2"); setlocale(LC_ALL, "russian"); printf("Введите номер вершины, с которой будет начат обход графа в ширину:\n"); scanf("%d", &FST); printf("Введите номер вершины, на которой будет закончен обход графа в ширину:\n"); scanf("%d", &end); /*Подготовка массива flag к использованию для поиска в ширину*/ printf("\nОбход в ширину BFS\n"); for(i=0;i<n;i++) flag[i]=false; /*Реализация поиска в ширину*/ InitQuene(); BFS(FST-1); getch(); for(i=0;i<n;i++) { ListNode *cuz, *tmp; cuz=BEGIN[i]; while(cuz!=NULL) { tmp=cuz; cuz=cuz->next; free(tmp); } } return 0; } Ребята подскажите мне пожалуйста вот что 'f' was not declared in this scope, как это поправить, на что нужно f заменить? |
Сообщ.
#10
,
|
|
|
Быть может нужно строку
std::ifstream ifs("graph.txt"); заменнить на FILE *f=fopen("graph.txt","rt"); ну и прочие строки с ifs поправить. |
Сообщ.
#11
,
|
|
|
Славян можете дать код как правильно поправить, чтобы все работало? Я только начинаю свою работу с C++ и многое мне в новинку.
|
Сообщ.
#12
,
|
|
|
У вас просто весьма странное поведение: я же написал, что в строке память выделяется, а потом сразу на неё (память) вы плюёте, а вы, тем не менее, всё равно оставили то место без изменения. Почему же так? Т.е. почему вы не правите ошибки или не отвечаете на своё видение ситуации?
Смысла в полном коде весьма мало; гораздо интереснее двигаться шагами, исправляя проблемы и находя какие-то пути их обхода. |
Сообщ.
#13
,
|
|
|
Славян поправил я это место, в итоге еще одна НОВАЯ ошибка, мне сейчас важнее со сменой указателя разобраться. Можете мне хотя бы направление дать?
|
Сообщ.
#14
,
|
|
|
Пока не сильно ясно про какую смену указателя речь. Не сложно же - вставляйте имеющийся код (не руками же набираете) и будем смотреть на проблемы! :yes:
Добавлено П.С. хм... что-то не догоняю, отчего yes в конце смайликом не рисуется?.. :-? Добавлено О, и эта эмоция (с вопросиком) тоже. Что-то где-то поломалось... |
Сообщ.
#15
,
|
|
|
Славян мне нужно:
1) либо на что то заменить "f" 2) либо убрать std; нужно чтобы программа заработала и выполняла задание выше.... |