Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.97/30: Рейтинг темы: голосов - 30, средняя оценка - 4.97
0 / 0 / 1
Регистрация: 16.09.2011
Сообщений: 24
1

Граф на C

16.09.2011, 11:13. Показов 5967. Ответов 19
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем доброго времени суток. В общем присутплю сразу к проблеме. Задали курсовую:даётся сеть двусторонних автомобильных дорог, вывести маршрут из города А в город Б, А и Б естественно задаёт пользователь, сам граф, то есть матрица берётся из файла.
Пишу на Visual Studio, программа выдаёт ошибку при построении, вот собстенно сам код:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include "stdafx.h"
 #include "stdio.h"
 #include "conio.h"
 #include "stdlib.h"
 #include "string.h"
 #define TownMax 20
 
 int ReadMatr(int *matr[TownMax][TownMax])
 { int i;
 FILE *fp;
 if((fp=fopen("matr.txt", "r"))==NULL) 
 {
 printf("Ошибка при открытии файла.\n");
 exit(1);
 }
 //fread(matr[TownMax][TownMax], sizeof(int), TownMax, fp);
 for(i=0;i<TownMax;i++)
 {
 scanf("%d",matr[TownMax][TownMax]);
 } 
 printf("%d",matr[TownMax]);
 fclose(fp);
 return 0;
 }
 
 void GetWays (int begin, int end, int *matr[TownMax][TownMax])
 {
 int Visited[TownMax];
 Visited[begin] = 1;
 int Way[TownMax];
 int i,j,schet=0,t;
 int put[TownMax][TownMax];
 
 for (i=1; i<=begin;i++) 
 {
 if ((matr[begin][i]!=0) && (Visited[i]==0)) 
 {
 Way[TownMax]=i; schet++;
 }
 if (Way[1]==begin && Way[schet]==end)
 {
 for (i=0; i<schet;i++)
 put[TownMax][TownMax]=Way[i];j++;
 
 }
 for(t=0;t<schet;t++)
 printf("%d",Way[TownMax]);
 
 }
 }
 
 int main()
 { int begin,end;
 int matr[TownMax];
 int k,p;
 puts("Введите начальную и конечную точку маршрута");
 k=ReadMatr (*matr);
 scanf("%d%d",&begin,&end);
 p=GetWays (begin,end,*matr);
 }
 Комментарий модератора 
Используйте теги форматирования кода
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.09.2011, 11:13
Ответы с готовыми решениями:

Граф задан цепными списками. Построить его реберный граф
Дорогие форумчане, прошу помочь с написанием данной программы: Граф задан с помощью цепных...

Как преобразовать неориентированный граф в ориентированный граф из матричной записи
Есть ли какой нибудь алгоритм преобразования Неориентированный графа в ориентированный граф из...

Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством пересечений
Ориентированный граф задан матрицей смежности. Нарисовать граф с наименьшим количеством...

Реализовать граф от 1 до 10: граф связный; -число от 1 до 10, могут повторяться
Реализовать граф от 1 до 10: граф связный; -число от 1 до 10, могут повторяться. Добавить рандом...

19
194 / 193 / 15
Регистрация: 12.12.2010
Сообщений: 270
16.09.2011, 11:26 2
а ошибку какую выдает и в каком месте кода?
0
0 / 0 / 1
Регистрация: 16.09.2011
Сообщений: 24
16.09.2011, 12:27  [ТС] 3
Сейчас построение успешно проходит, но завершается прога с кодом 1, т.е. не может найти matr.txt для открытия, но он лежит в папке самого проекта, может в Visual Studio 2010 он в другом месте должен лежать???

Добавлено через 14 минут
Сейчас код выглядит так:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include "string.h"
#define TownMax 20
 
int ReadMatr()
{   int i,j;
int matr[TownMax][TownMax]={0};
  FILE *fp;
  if((fp=fopen("D:\matr.txt", "r"))==NULL) 
  {
    printf("Ошибка при открытии файла.\n");
    exit(1);
  }
    //fread(matr[TownMax][TownMax], sizeof(int), TownMax, fp);
  for(i=0;i<TownMax,j<TownMax;i++)
    {
        scanf("%d",matr[TownMax][TownMax]);
        if (i==TownMax) j++;
    }   
    printf("%d",matr[TownMax]);
    fclose(fp);
    return 0;
}
 
void GetWays (int begin, int end, int matr[TownMax][TownMax])
    {
        int Visited[TownMax]={0};
         Visited[begin] = 1;
         int Way[TownMax]={0};
         int i,j=0,schet=0;
         int put[TownMax][TownMax];
 
   for (i=1; i<=begin;i++) 
   {
    if ((matr[begin][i]!=0) && (Visited[i]==0)) 
     {
        Way[TownMax]=i; schet++;
     }
    if (Way[1]==begin && Way[schet]==end)
    {
        for (i=0; i<schet;i++)
            put[TownMax][TownMax]=Way[i];j++;
 
    }
    printf("%d",Way[TownMax]);
 
   }
    }
 
    int main(int matr[TownMax][TownMax])
    {   int begin,end;
        puts("Введите начальную и конечную точку маршрута");
        ReadMatr();
        scanf("%d%d",&begin,&end);
        GetWays (begin,end,matr);
        
    }
0
194 / 193 / 15
Регистрация: 12.12.2010
Сообщений: 270
16.09.2011, 12:33 4
не может найти matr.txt для открытия, но он лежит в папке самого проекта, может в Visual Studio 2010 он в другом месте должен лежать???
ну видимо он должен был лежать в той папке где собирается EXE файл.
0
0 / 0 / 1
Регистрация: 16.09.2011
Сообщений: 24
16.09.2011, 12:40  [ТС] 5
Цитата Сообщение от zalogic Посмотреть сообщение
ну видимо он должен был лежать в той папке где собирается EXE файл.
Он у меня и лежит в папке Debug, или exe где-то в другом месте создаётся?
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
16.09.2011, 13:18 6
K16FORWARD, положи его в папку, из которой запускается исполняемый файл. Ну или задай абсолютный путь
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
16.09.2011, 13:20 7
Цитата Сообщение от K16FORWARD Посмотреть сообщение
C
1
fp=fopen("D:\matr.txt", "r"))
надо либо так:
C
1
fp=fopen("D:\\matr.txt", "r"))
либо так:
C
1
fp=fopen("D:/matr.txt", "r"))
1
0 / 0 / 1
Регистрация: 16.09.2011
Сообщений: 24
16.09.2011, 14:50  [ТС] 8
Цитата Сообщение от Nameless One Посмотреть сообщение
надо либо так:
C
1
fp=fopen("D:\\matr.txt", "r"))
либо так:
C
1
fp=fopen("D:/matr.txt", "r"))
Спасибо, теперь файл открывает, но ругается на функцию Readmatr, из-за того что я её криво написал в виду неумения, можно ли после открытия файла использовать функцию scanf чтобы из файла в массив данные перешли?

Добавлено через 19 минут
Переписал строку
C
1
scanf("%d",matr[TownMax][TownMax]);
вот таким образом:
C
1
fscanf(fp,"%d",matr[TownMax][TownMax]);
при запуске пишет "Ошибка прав доступа для записи"

Добавлено через 15 минут
Ошибка:
Необработанное исключение в "0x691c936c (msvcr90d.dll)" в "p2e1.exe": 0xC0000005: Нарушение прав доступа при записи "0x80000000".
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
16.09.2011, 19:07 9
Цитата Сообщение от K16FORWARD Посмотреть сообщение
вот таким образом:
C
1
fscanf(fp,"%d",matr[TownMax][TownMax]);
при запуске пишет "Ошибка прав доступа для записи"
ну, по крайней мере одна очевидная ошибка:
C
1
fscanf(fp, "%d", &matr[TownMax][TownMax]);
нужно передавать не саму переменную, а адрес переменной, чтобы по этому адресу можно было записать (функцией fscanf) данные.
Подробнее см. man 3 scanf (или другую доступную документацию). Ну или гуглить по теме "Указатели" и для чего они на самом деле нужны в языках С/С++.
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
16.09.2011, 19:24 10
Кстати, в цикле (строки 18-22) у тебя scanf (fscanf) читает (или должен читать) данные из файла для каждой итерации в один и тот же элемент двумерного массива (matr). Мне лично это кажется очень подозрительным.
Какой у тебя формат файла? Что там задано? Матрица смежности?
0
0 / 0 / 1
Регистрация: 16.09.2011
Сообщений: 24
16.09.2011, 22:10  [ТС] 11
Да, у меня в файле матрица смежности
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
17.09.2011, 02:59 12
C
1
2
3
for(i = 0; i < TownMax; ++i)
  for(j = 0; j < TownMax; ++j)
    fscanf(fp, "%d", &matr[i][j]);
И да, измени прототип функции ReadMatr на такой:
C
1
void ReadMatr(int matr[TownMax][TownMax])
1
Заблокирован
17.09.2011, 04:25 13
C++
1
2
#include "stdafx.h" 
#include "conio.h"
прости за оффтоп. вижу и напрягаюсь
1
0 / 0 / 1
Регистрация: 16.09.2011
Сообщений: 24
18.09.2011, 08:49  [ТС] 14
Цикл поменял, прототип изменил, чёто сразу не подумал цикл в цикле использовать) матрица правильно считывается(трассировкой проверил). Теперь проблема с нахождением пути, не подскажете где можно найти готовые алгоритмы нахождения всех путей в неориентированном графе из точки А в точку Б?
0
0 / 0 / 1
Регистрация: 16.09.2011
Сообщений: 24
22.09.2011, 13:51  [ТС] 15
У меня сейчас получился вот такой код программы и немного исправленная функция поиска путей, компилируется без ошибок, но работает неправильно, укажите плз на ошибки)
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include "string.h"
#define TownMax 6
 
    void ReadMatr(int matr[TownMax][TownMax])
{   int i=0,j=0;
  FILE *fp;
  if((fp=fopen("D:\\matr.txt", "r"))==NULL) 
  {
    printf("File not found\n");
    exit(1);
  }
  for(i = 0; i < TownMax; ++i)
  for(j = 0; j < TownMax; ++j)
    fscanf(fp, "%d", &matr[i][j]);
    fclose(fp);
}
    
void GetWays (int begin, int end, int matr[TownMax][TownMax])
    {
        int Visited[TownMax]={0};
         Visited[begin] = 1;
         int Way[TownMax]={0};
         int i,j=0,schet=0;
 
   for (i=1; i<=TownMax;i++)
             {
    if ((matr[begin][i]!=0) && (Visited[i]==0)) 
             {
                Way[TownMax]=i; schet++;
                Visited[i]=1;
             }
    if (Way[1]==begin && Way[schet]==end)
             {  
                for (i=0; i<schet;i++)
                printf("Путь:%d",Way[TownMax]);
             }
 
         }
     }
 
    int main()
    {   int begin,end;
        int matr[TownMax][TownMax]={0};
            puts("Gets begin and end points");
                ReadMatr(matr);
            scanf("%d%d",&begin,&end);
                GetWays (begin,end,matr);
                    getch();
    }
0
Заблокирован
22.09.2011, 18:14 16
ты бы указал что не так работает. ну вот пример кода, который не компилируется
ошибка в строке 8. так инициализировать массив нельзя

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
 
const int ARR_SIZE = 6;
 
int main(){
    int  i, k;
    int arr[ARR_SIZE][ARR_SIZE] = {0};
 
    /*for(i = 0; i < ARR_SIZE; ++i){
        for(k = 0; k < ARR_SIZE; ++k){
            arr[i][k] = 0;
        }
    }*/
 
    for(i = 0; i < ARR_SIZE; ++i){
        for(k = 0; k < ARR_SIZE; ++k)
            printf(" %d", arr[i][k]);
        printf("\n");
    }
    return 0;
}
результат работы без инициализации с исправленной строкой
C
1
int arr[ARR_SIZE][ARR_SIZE]
результат
Код
$ ./system 
 12960916 750006397 129100401 5904336 6364454 -163754450
 -1215842828 6 12974360 0 0 1
 2206 -1215842768 -1215843648 134513295 5906416 134513132
 1 12972020 -1075251872 12974800 -1075251920 12892537
 -1075251936 134513132 -1075251948 12974708 0 -1215842768
 1 0 1 12974360 29 -1075252052

результат работы кода
C
1
2
3
4
5
    int arr[ARR_SIZE][ARR_SIZE];
 
    for(i = 0; i < ARR_SIZE; ++i)
        for(k = 0; k < ARR_SIZE; ++k)
            arr[i][k] = 0;
результат
Код
$ ./system 
 0 0 0 0 0 0
 0 0 0 0 0 0
 0 0 0 0 0 0
 0 0 0 0 0 0
 0 0 0 0 0 0
 0 0 0 0 0 0


Добавлено через 1 час 19 минут
Я кстати вообще поражаюсь как компилятор мог скомпилировать такое. Даже боюсь представить чем это может быть чревато.
C
1
int matr[TownMax][TownMax]={0}; //инициализировать чужую область память нулем
0
0 / 0 / 1
Регистрация: 16.09.2011
Сообщений: 24
22.09.2011, 19:55  [ТС] 17
Так спокойно все инициализируется, я явно присваиваю первому элементу 0, остальные обнуляются неявно.
А почему вы считаете что я инициализировал ЧУЖУЮ область?
просто я пользуюсь обнулением как в цикле так и способом {0}, в обоих случаях обнуление проходит, делал трассировку на Visual Studio 2010
0
Заблокирован
22.09.2011, 20:30 18
потому что массиву принадлежат элементы с 0 по (TownMax - 1) включительно. элемента массива
matr[TownMax][TownMax] не существует, это уже выход за пределы массива... что-то там обсуждалось на эту тему на очень низком уровне с функцией Crush() для Си. Попробуйте код и убедитесь.
C
1
printf(" %d", matr[TownMax][TownMax])
я явно присваиваю первому элементу 0, остальные обнуляются неявно.
это делается так
C
1
matr[0][0] = 0;
а что там неявно обнуляется, напрямую зависит от реализации компилятора. Вы же видите в моем посте выше что ничего подобного нет. По крайней мере я знаю точно что в с++ переменные автоматически должны инициализироваться нулями (кто не верит дам ссылку на страницу в книге Страуструппа), но и этого не происходит потому что видимо в стандарте такого жесткого правила нет. А в Си тем более. В любом случае Вы так и не показали что же работает неправильно.

Добавлено через 16 минут
код
C
1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include <stdlib.h>
 
const int ARR_SIZE = 16;
 
int main(){
    int  i, k;
    int arr[ARR_SIZE][ARR_SIZE] = {0};
    return 0;
}
естественный ответ:
variable-sized object may not be initialize
все ясно на этапе компиляции.
0
0 / 0 / 1
Регистрация: 16.09.2011
Сообщений: 24
23.09.2011, 12:15  [ТС] 19
Да, вы правы, сейчас тоже не понимаю как компилятор это пропустил, как и то что я присвоил
C
1
Way[TownMax]=i
Хотя он при выполнении доходя до того места ругается на это. Дело собственно не в этом, я просто не знаю какой алгоритм применить, просмотрел все стандартные, но ни один не предназначен для поиска ВСЕХ путей в неориентированном графе из точки А в точку Б, какой алгоритм модифицировать посоветуете?
0
Заблокирован
23.09.2011, 15:38 20
Цитата Сообщение от K16FORWARD Посмотреть сообщение
какой алгоритм модифицировать посоветуете?
Т.Ч. Ху, М.Т.Шинг "Комбинаторные алгоритмы", Кнута надо посмотреть, у него 100% должны быть подобные решения.
З.Ы. при скачивании обращайте внимание на размер. Первая книга часто идет как просто оглавление и список литературы.
0
23.09.2011, 15:38
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.09.2011, 15:38
Помогаю со студенческими работами здесь

Дан список, содержащий смешанный граф. Выбрать из него однонаправленные ветви и занести в результирующий граф
Помогите, пожалуйста решить эту зайку. Очень прошу...

Считать граф из файла (граф задан матрицей) представить его в виде списка и записать список заново в файл
помогите очень срочно надо. считать граф из файла (граф задан матрицей) представить его в виде...

Граф в С
Не могли бы помочь.. как можно построить граф в С ? или где модно прочесть про то как создать файл...

Граф
Добрый вечер! Друзья, помогите с реализацией программы: Дано дерево (граф). Найти диметр и вершины,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru