0 / 0 / 0
Регистрация: 09.07.2017
Сообщений: 4
1

Переориентирование орграфа

09.07.2017, 18:30. Показов 1087. Ответов 7

Author24 — интернет-сервис помощи студентам
У меня есть задание.

Разработать алгоритм и программу на языке Паскаль для преобразования ориентированного графа: каждая дуга заменяется на обратно направленную дугу. Граф в программе представлен в списковой форме. Для проверки работы программы исходный граф представляется текстовым файлом вида {книга[тетрадь, листок], библиотека[листок, шкаф, стол], и т.д.}, где каждое слово – это имя вершины графа, а в квадратных скобках указывается список имен вершин, в который направлены дуги из данной вершины. После обращения дуг списковое представление результирующего графа также преобразуется в текстовый файл, построенный по тем же правилам.

Текст разработанной программы должен быть снабжен подробными комментариями.



Необходимо, чтобы процесс инвертирования включал в себя только списки смежности, т.е. список -> инвертированный список.

Нельзя использовать какие либо модули.

Я распарсил файл, создал списки смежности, которые хранятся в динамическом массиве. Вывести уже переориентированные списки смежности в файл тоже не проблема. Но вот сама подпрограмм для этого у меня не выходит. Проблема заключается, скорее всего, в том, что когда мы идем по списку InvList, чтобы добраться до последнего элемента и в конец записать новый, то сам список ломается. Помогите с процедурой Change, пожалуйста.

Файл G1: v1[v3, v2], v2[v3, v1], v3[v1, v2].

Pascal
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
type List = ^node;
    node = record
      name:string;
      next:list;
    end;
    dyn_arr = array of list;
 
var L1:list;  x:string; G:text; j,n,i:integer;listV: dyn_arr;   InvList: dyn_arr;
 
procedure CreateList( var f:text);
var i,k:integer; p,l,g:list; s:string; u:integer;
begin
  k:=0; i:=1; read(f,x);
  while x[i]<>#46 do
    begin
      new(l); l^.name:= '';
      listV[k]:= l;
      while x[i]<>'[' do
      begin
        l^.name:= l^.name+x[i];
        i:=i+1;
      end;
      inc(i);
      p:= l;
      while x[i]<>#93 do
      begin
        new(g);
        g^.name:='';
        u:=u+1;
        while (x[i]<>#44) and (x[i]<>#93) do
        begin
          g^.name:= g^.name+x[i];
          inc(i);
        end;
        p^.next:= g; p:=g; p^.next:= nil;
        if x[i]=#44 then i:=i+2;
      end;
      if x[i+1]<>#46 then i:=i+2;
      k:= k+1;
      i:=i+1;
    end;
end;
procedure CHECK(u:integer);
begin
        writeln('Check',u);
end;
procedure Out(ff:list);
begin
        if ff<>nil then begin
          write(ff^.name);
          Out(ff^.next);
        end;
 
end;
 
procedure Change(i:integer);
var p,q,l,tt,g:list; k,j:integer;
begin
    g:=listV[i];  new(l); check(1); l^.name:=g^.name; check(2); j:=0;
    while (g^.next<>nil) do
    begin
        new(p); p^.name:=g^.next^.name;
        if InvList[j]=nil then
        begin
          InvList[j]:=p;
          p^.next:=l;          
          g:=g^.next;
        end
        else begin
        op:=0; 
    while (InvList[op]^.name<>p^.name) and (InvList[op]<>nil) do
               op:= op+1;    
        if InvList[op]^.name=p^.name then
          while InvList[op]<>nil do
          begin   
            if InvList[op]^.next= nil then
            begin
              new(q);
              q^.name:= l^.name;
              InvList[op]^.next:= q;     
            end;
            InvList[op]:= InvList[op]^.next;
          end
        else begin
          InvList[op]:=p;
          p^.next:=l;
    end;
    end;
          j:= j+1;  
  end;    
end;
begin
 
    writeln('Enter the number of vertices to create a dynamic array');
    readln(n);
  SetLength(InvList, n);
  SetLength(listV, n);
  assign(G,'G1.txt');
  reset(G);
 
  CreateList(G);
  close(g);
      for i:=0 to N-1 do begin
        writeln;
        InvList[i]:= nil;
      end;
  for i:=0 to N-1 do
  Change(i);
   for i:=0 to N-1 do begin
        Out(invlist[i]);
    writeln;
   end;
 
        readln();
end.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.07.2017, 18:30
Ответы с готовыми решениями:

Разложение орграфа
Привет всем!!Задание по дискретней математике,Нам задали Составить программу, находящую разложение...

Диаметр орграфа
Здравствуйте, помогите пожайлуйста. Нужно в маткаде реализовать нахождение диаметра орграфа. ...

Центр орграфа, классы
помогите с конструктором и деструктором) Дан файл, первой строкой в файле является размерность...

Поиск источника орграфа
Источник орграфа - вершина из которой достижимы все другие вершины. Как её можно найти? Есть такая...

7
Модератор
Эксперт по электронике
8475 / 4334 / 1642
Регистрация: 01.02.2015
Сообщений: 13,455
Записей в блоге: 8
09.07.2017, 18:48 2
А обязательно внутреннее хранение орграфа в виде списка?
Может быть сделать его в виде матрицы смежности и из неё заполнять файл?

Т.е. при чтении входного файла появляются две структуры - 1) список названий вершин, 2) матрица смежности.
Потом при выводе в файл производить чтение не по строкам, а по столбцам и вместо номера выводить название вершины.

Можно и из списка (списка списков). Но тогда, на основе одного списка смежности формировать абсолютно новый список (новую переменную).
1
0 / 0 / 0
Регистрация: 09.07.2017
Сообщений: 4
09.07.2017, 18:58  [ТС] 3
Да, использование списков смежности обязательно. Так же необходимо именно список перевести в список

Добавлено через 1 минуту
Цитата Сообщение от ФедосеевПавел Посмотреть сообщение
Можно и из списка (списка списков). Но тогда, на основе одного списка смежности формировать абсолютно новый список (новую переменную).
А можно подробнее?
0
Модератор
Эксперт по электронике
8475 / 4334 / 1642
Регистрация: 01.02.2015
Сообщений: 13,455
Записей в блоге: 8
09.07.2017, 19:38 4
Вот есть переменная listV. На её основе заполняете InvList.
0
0 / 0 / 0
Регистрация: 09.07.2017
Сообщений: 4
09.07.2017, 19:53  [ТС] 5
Цитата Сообщение от ФедосеевПавел Посмотреть сообщение
Вот есть переменная listV. На её основе заполняете InvList.
Ну я так и делаю. Для первой вершины все хорошо. Если у меня задан граф v1[v3, v2], v2[v3, v4]..., то у меня создается InvList[0]: v3 v1, InvList[1]: v2 v1, но вот когда я перехожу на следующую вершину (v2), то мне же надо не новый элемент InvList[2] создать, а дополнить InvList[0], так как его голова это вершина v3, и когда я начинаю идти по списку InvList[0], чтобы найти последний элемент и после него приписать вершину v2, то этот список InvList[0] ломается. Вот что я и спрашиваю, как мне дойти до последнего элемента списка InvList[0] или любого другого так, чтобы его не сломать?
Ломается он, как мне кажется вот на этой строке:
Цитата Сообщение от moonSIDE Посмотреть сообщение
82 InvList[op]:= InvList[op]^.next;
0
Модератор
Эксперт по электронике
8475 / 4334 / 1642
Регистрация: 01.02.2015
Сообщений: 13,455
Записей в блоге: 8
09.07.2017, 20:32 6
Все проблемы от плохой структуры программы. Вместо того, чтобы выделить процедуры работы со списками и вызывать их по мере необходимости, вы городите мегакод.

Программа должна:
1. for NewTo:=0 to n do - цикл по "старому" списку вершин. NewTo - вершина, на которую будут направлены связи в новом графе
2. __while (listVptr<>nil) do
3. ____NewFrom:=listVptr.name
4. ____InsertVertex(InvList, NewFrom, NewTo) - это самодельная процедура, в которой проверяется наличие вершины NewFrom в массиве InvList, при необходимости её создание, добавление вершины NewTo в список смежности.

Вот и весь алгоритм. В InsertVertex будет работа со списками.
1
0 / 0 / 0
Регистрация: 09.07.2017
Сообщений: 4
09.07.2017, 21:46  [ТС] 7
Но в 97 строке вылезает ошибка:
No heap dump by heaptrc unit
Exitcode = 216

Добавлено через 13 минут
Цитата Сообщение от moonSIDE Посмотреть сообщение
Но в 97 строке вылезает ошибка:
No heap dump by heaptrc unit
Exitcode = 216
Переделал. Теперь без ошибок, но g как-то не так двигается.
Pascal
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
function CheckIn(p: list):integer;
var f: Boolean;
begin
    f:= true;
    for i:=0 to N-1 do
        begin
                if InvList[i]<>nil then
                begin
                if p^.name = InvList[i]^.name then
                begin
                       CheckIn:= i;
                       f:= false;
                    end
                    else
                    if f then CheckIn:=-1;
                end
                else
                if f then CheckIn:=-1;
        end;
end;
procedure ChangeLast(var q:list; p: list);
begin
    if q=nil then
    begin
        new(q);
        q^.name:=p^.name;
        q^.next:=nil;
    end
    else
    ChangeLast(q^.next, p);
end;
procedure AddToNil(q, p:list);
var i: integer;
begin
        i:=0;
    while InvList[i]<>nil do i:= i+1;
    InvList[i]:= q;
    q^.next:= p;
    p^.next:=nil;
end;
0
Модератор
Эксперт по электронике
8475 / 4334 / 1642
Регистрация: 01.02.2015
Сообщений: 13,455
Записей в блоге: 8
09.07.2017, 22:29 8
Надеюсь, что не собью вас с мысли.
Это только заготовка для начала работы со списками
Pascal
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
program ReverseGraph;
 
type
  {----------------------------------}
  {список смежности для одной вершины}
  {указатель на список}
  PListAdj = ^TListAdj;
  {элемент списка}
  TListAdj = record
    fId: integer;
    fTo: PListAdj;
  end;
  {----------------------------------}
  {описание вершины}
  TVertex = record
    fName: string;
    fId: integer;
    fList: PListAdj;
  end;
  {----------------------------------}
  {списки смежности (список вершин со списками смежности)}
  {указатель на список}
  PList = ^TList;
  {элемент списка}
  TList = record
    fVertex: TVertex;
    fTo: PList;
  end;
 
  {================================================================}
  {процедуры для работы со списком смежности для одной вершины}
  {Процедура добавления нового элемента в конец односвязного списка}
  procedure AddToListAdj(var ARoot: PListAdj; AId: integer);
  var
    tmp: PListAdj;
  begin
    if ARoot = nil then
    begin
      new(ARoot);
      tmp := ARoot;
    end
    else
    begin
      tmp := ARoot;
      while tmp^.fTo <> nil do
        tmp := tmp^.fTo;
      new(tmp^.fTo);
      tmp := tmp^.fTo;
    end;
    tmp^.fTo := nil;
    tmp^.fId := AId;
  end;
 
  {процедура освобождения памяти списка}
  procedure FreeListAdj(var ARoot: PListAdj);
  var
    tmp: PListAdj;
  begin
    while ARoot <> nil do
    begin
      tmp := ARoot;
      ARoot := Aroot^.fTo;
      dispose(tmp);
    end;
  end;
 
  {================================================================}
  {процедуры для работы со списками смежностей (списком списков)}
  {Процедура добавления нового элемента в конец односвязного списка}
  procedure AddToList(var ARoot: PList; AVertex: TVertex);
  var
    tmp: PList;
  begin
    if ARoot = nil then
    begin
      new(ARoot);
      tmp := ARoot;
    end
    else
    begin
      tmp := ARoot;
      while tmp^.fTo <> nil do
        tmp := tmp^.fTo;
      new(tmp^.fTo);
      tmp := tmp^.fTo;
    end;
    tmp^.fTo := nil;
    tmp^.fVertex := AVertex;
  end;
 
  {процедура освобождения памяти списка}
  procedure FreeList(var ARoot: PList);
  var
    tmp: PList;
  begin
    while ARoot <> nil do
    begin
      tmp := ARoot;
      ARoot := Aroot^.fTo;
      dispose(tmp);
    end;
  end;
 
  {процедура поиска вершины в списке смежности (списке списков)
  поиск считается успешным, если совпало или имя вершины или её номер}
  function FindList(ARoot: PList; AVertex: TVertex): PList;
  begin
    while (ARoot <> nil) do
    begin
      if (ARoot^.fVertex.fName = AVertex.fName) or
        (ARoot^.fVertex.fId = AVertex.fId) then
        break;
      Aroot := ARoot^.fTo;
    end;
    FindList := ARoot;
  end;
 
  {================================================================}
  {чтение списка из файла}
  procedure ReadListFromFile(var ARoot: PList; const AFileName: string);
  begin
    Assign(f, AFileName);
    reset(f);
 
    Close(f);
  end;
 
begin
end.
Идея в том, чтобы сделать единый способ заполнения списков смежности как из файла, так и из другого списка при обработке.

Как только это будет готово, можно простыми вызовами процедур вызывать построение нового списка.
1
09.07.2017, 22:29
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.07.2017, 22:29
Помогаю со студенческими работами здесь

Матрица смежности для орграфа
Добрый день Задача: Изобразить ориентированный граф из четырёх вершин по тому же числу (943116),...

Компоненты сильной связности орграфа
#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;string&gt; #include &lt;algorithm&gt; using namespace...

Достроение до сильно связного орграфа
Народ, мне не нужен ваш код, мне нужна только идея решения. Задача такая: Количество вершин в...

Постройте матрицу смежности орграфа
Задача 11. Орграф G1(V,E): V={a, b, c, d, e, f}, задан как алгебраическая система. a) Для...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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