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

Деревья.Модули

09.12.2013, 00:16. Показов 1260. Ответов 12
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Типы данных и подпрограммы для поиска ближайшего (с наибольшей длинной пути относительно корня дерева) предка двух заданных ключами узлов n-нарного дерева. Кроме подпрограммы поиска предка реализовать подпрограммы для создания ориентированного n-нарного дерева из m узлов, удаления дерева, распечатка дерева на экране. Поскольку узлы идентифицируются значениями своих ключей, ключи должны быть уникальны.Определить в отдельном модуле. Очень нужна помощь. Заранее благодарен.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.12.2013, 00:16
Ответы с готовыми решениями:

Деревья принятия решения (Деревья классификации)
Доброго времени суток! Столкнулся с такой проблемой: требуется написать программу на Pascal для...

Деревья
есть такое задание: во входном файле задана инфиксная форма арифметического выражения , содержащая...

Деревья
Вопрос мой таков как из заданого бинарного дерева построить новое из его листьев? Вообще думала и...

деревья
помогите,пожалуйстааа...::gcray2: описать логическую функцию same(t),определяющую,есть ли в дереве...

12
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32816 / 21154 / 8147
Регистрация: 22.10.2011
Сообщений: 36,413
Записей в блоге: 8
12.12.2013, 14:35 2
Что у тебя уже есть по этой задаче? Чтобы не переписывать уже готовую часть кода, хотя бы создание n-ary tree и его отображение выложил бы.
0
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 33
12.12.2013, 20:48  [ТС] 3
хм есть процедура вывода дерева на экран

Добавлено через 1 минуту
остальное ток с бинарном более-менее понимаю как работать но не скучей указателей в n-арно. Помоги пожалуйста)
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32816 / 21154 / 8147
Регистрация: 22.10.2011
Сообщений: 36,413
Записей в блоге: 8
12.12.2013, 21:01 4
Тогда чуть позже, надо искать, где-то была у меня работа с n-арными деревьями, чтобы совсем с нуля не писать... Кстати,
Цитата Сообщение от need_help Посмотреть сообщение
а вот сама программа поиска это да
- непонятно. Сама процедура поиска сведется к занесению в массив (ну, или в список) всех Parent-ов на пути от первого узла к корню, и потом к проходу также к корню от второго узла с проверкой, присутствует ли уже в списке текущий Parent. Если присутствует - то он и будет общим родителем, максимально удаленным от корня.
0
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 33
12.12.2013, 21:39  [ТС] 5
Я вообще мало что в этом понимаю. Мы писали на занятии распечатку дерева ну и способы поиска бинарном дереве. А с указателями я ещё запутался начиная со списков. Так что тут я вообще профан.
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32816 / 21154 / 8147
Регистрация: 22.10.2011
Сообщений: 36,413
Записей в блоге: 8
13.12.2013, 03:22 6
В общем, нашел я свои исходники... Проверял на FPC (на PascalABC или PascalABC.NET, сразу говорю, портировать не буду, под Турбо-Паскалем должно работать, ничего особенного я тут не делал)

Модуль
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
unit n_ary;
 
interface
 
type
  my_string = string[30];
 
  the_key = integer;
  the_data = record
    s: my_string;
  end;
 
  PItem = ^TItem;
  TItem = record
    Data: the_data;
    key: the_key;
 
    next: PItem;
    children: PItem;
    parent : PItem; { *** }
  end;
 
procedure Add(var root: PItem; parent: PItem; value: the_data);
function FindByKey(root: PItem; k: the_key): PItem;
procedure Print(root: PItem; visual: boolean);
procedure DeleteTree(var root: PItem);
 
function NearestParent(a, b : PItem) : PItem;
 
 
implementation
 
procedure Add(var root: PItem; parent: PItem;
          value: the_data);
var new_item, p_child: PItem;
begin
  new(new_item);
  new_item^.next := nil; new_item^.children := nil;
  new_item^.key := 0;
 
  new_item^.Data := value;
  new_item^.parent := parent;
 
  if parent = nil then
  begin
 
    if root <> nil then writeln('error: duplicate data!')
    else root := new_item;
 
  end
  else
  begin
 
    p_child := parent^.children;
    if p_child = nil then parent^.children := new_item
    else
    begin
 
      while p_child^.next <> nil do p_child := p_child^.next;
      p_child^.next := new_item;
 
    end;
 
  end;
 
end;
 
function FindByKey(root: PItem; k: the_key): PItem;
var p, found: PItem;
begin
  found := nil;
  p := root;
 
  if p <> nil then
  begin
    while (found = nil) and (p <> nil) do
    begin
 
      if p^.key = k then found := p
      else found := FindByKey(p^.children, k);
 
      p := p^.next;
 
    end;
 
  end;
  FindByKey := found;
 
end;
 
var curr_index: integer;
 
procedure Printing(level: integer; root: PItem;
          visual: boolean);
var p: PItem;
begin
  p := root;
  while p <> nil do
  begin
    inc(curr_index); p^.key := curr_index;
 
    if visual then
      writeln(p^.key:4, '':succ(2*level), p^.data.s);
 
    Printing(level+1, p^.children, visual);
 
    p := p^.next;
  end;
end;
 
procedure Print(root: PItem; visual: boolean);
begin
  curr_index := 0;
  printing(0, root, visual);
end;
 
function DeletePartially(root: PItem; k: integer): PItem;
var p, found: PItem;
begin
 
  found := nil;
  if root <> nil then
  begin
 
    if (root^.next <> nil) and (root^.next^.key = k) then
    begin
      found := root^.next;
      root^.next := found^.next;
      found^.next := nil;
      DeletePartially := found;
      exit;
    end;
 
    if (root^.children <> nil) and (root^.children^.key = k) then
    begin
      found := root^.children;
      root^.children := found^.next;
      found^.next := nil;
      DeletePartially := found;
      exit;
    end;
 
    p := root^.children;
    while p <> nil do
    begin
      found := DeletePartially(p, k);
      if assigned(found) then break;
      p := p^.next;
    end;
 
  end;
  DeletePartially := found;
 
end;
 
procedure DeleteTree(var root: PItem);
var p, T: PItem;
begin
  p := root;
  while p <> nil do
  begin
    DeleteTree(p^.children);
 
    T := p;
    p := p^.next;
    dispose(T);
 
  end;
  root := nil
 
end;
 
 
procedure Delete(var root: PItem; k: the_key);
var deleting: PItem;
begin
 
  if root^.key = k then deletetree(root)
  else
  begin
    deleting := DeletePartially(root, k);
    DeleteTree(deleting);
  end;
 
end;
 
function NearestParent(a, b : PItem) : PItem;
var
  head, tail, p : PItem;
  found : boolean;
 
begin
  head := nil; tail := nil;
  repeat
    new(p);
    p^.next := nil;
    p^.children := a;
 
    if head = nil then head := p
    else tail^.next := p;
    tail := p;
 
    a := a^.parent;
  until a = nil;
 
  found := false;
  while (b <> nil) and not found do
  begin
 
    // found := false;
    p := head;
    while not found and (p <> nil) do
    begin
      found := p^.children = b;
      p := p^.next;
    end;
 
    if not found then b := b^.parent;
  end;
 
  while head <> nil do
  begin
    p := head;
    head := head^.next;
    dispose(p);
  end;
 
  NearestParent := b;
end;
 
end.


Основная программа
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
uses crt, n_ary;
 
var
  i: integer;
  p_ix, k1, k2: the_key;
  r: the_data;
  nearest, tree_root, new_root: PItem;
  f: text;
 
begin
  tree_root := nil;
  repeat
    write('parent index = '); readln(p_ix);
    if p_ix <> -1 then
    begin
      write('data = '); readln(r.s);
      Add(tree_root, FindByKey(tree_root, p_ix), r);
 
      Print(tree_root, true);
    end;
  until p_ix = -1;
 
  repeat
    write('first_key: '); readln(k1);
    if k1 <> -1 then
    begin
      write('second_key: '); readln(k2);
      write('nearest parent:');
      nearest := NearestParent(FindByKey(tree_root, k1),
                               FindByKey(tree_root, k2));
      if nearest = nil then writeln(' NULL ')
      else writeln(nearest^.data.s);
    end;
  until k1 = -1;
 
  deletetree(tree_root);
 
  readln;
end.


Вот для такого дерева:
Деревья.Модули


получены вот такие результаты (совершенно, кстати, правильные):

Bash
_
   1 a
   2   b
   3   c
   4   d
   5     f
   6     g
   7       h
   8       i
   9   e
parent index = -1
first_key: 7
second_key: 5
nearest parent:d
first_key: 5
second_key: 9
nearest parent:a
first_key: 7
second_key: 8
nearest parent:g
first_key: 4
second_key: 8
nearest parent:d
first_key: -1
1
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 33
13.12.2013, 23:56  [ТС] 7
Огромное спасибо.Если труда не составит могли бы откомментировать код. Хочется тоже самому разобраться в этих указателях.

Добавлено через 16 часов 42 минуты
Потому что начиная со списков у меня начились сильные проблемы.
0
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 33
15.12.2013, 13:33  [ТС] 8
эх...
0
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 33
23.12.2013, 14:21  [ТС] 9
Расскажите пожалуйста хоть что мы вообще вбиваем?И когда вбиваю ваши значения на этапе nearest parent:d возникает ошибка.

Добавлено через 2 часа 33 минуты
Ошибка с адресацией в строче a := a^.parent;
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32816 / 21154 / 8147
Регистрация: 22.10.2011
Сообщений: 36,413
Записей в блоге: 8
23.12.2013, 14:25 10
Цитата Сообщение от need_help Посмотреть сообщение
И когда вбиваю ваши значения на этапе nearest parent:d возникает ошибка.
Скриншот ошибки - в студию. Проверял много раз, никакой ошибки не возникает... Компилятор - FPC...
Цитата Сообщение от need_help Посмотреть сообщение
что мы вообще вбиваем?
Дерево мы вбиваем, неужели не понятно? Вот полный лог работы программы с моими комментариями:

Bash
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
Running "d:\programs\pascal\n_ary_tree.exe"
parent index = 1
data = a
   1 a
parent index = 1
data = b
   1 a
   2   b
parent index = 1
data = c
   1 a
   2   b
   3   c
parent index = 1
data = d
   1 a
   2   b
   3   c
   4   d
parent index = 1
data = e
   1 a
   2   b
   3   c
   4   d
   5   e
parent index = 4
data = f
   1 a
   2   b
   3   c
   4   d
   5     f
   6   e
parent index = 4
data = g
   1 a
   2   b
   3   c
   4   d
   5     f
   6     g
   7   e
parent index = 6
data = h
   1 a
   2   b
   3   c
   4   d
   5     f
   6     g
   7       h
   8   e
parent index = 6
data = i
   1 a
   2   b
   3   c
   4   d
   5     f
   6     g
   7       h
   8       i
   9   e
parent index = -1
first_key: 7
second_key: 5
nearest parent:d
first_key: 5
second_key: 9
nearest parent:a
first_key: 7
second_key: 8
nearest parent:g
first_key: 4
second_key: 8
nearest parent:d
first_key: -1
Строки 2-3 - вводим индекс и значение корня дерева. Потом, в строках 5-21 вводим 4 узла первого уровня (я там выше картинку прилеплял, посмотри на то дерево, которое я ввожу), поскольку у них у всех предок - корневой узел, то parent_index = 1. Дальше (строки 27-36) смотрим, какой индекс имеет узел со значением "D" (а он имеет индекс = 4, слева от значения написано), и к нему тоже добавляем 2 потомка, и так далее, пока все дерево не будет введено. В 65 строке parent_index = -1 для того, чтобы прекратить ввод исходных данных и перейти к поиску собственно ближайшего предка. Для этого вносим индексы двух узлов, для которых надо найти этого предка. В ответ программа показывает, какой узел является nearest parent-ом для двух заданных узлов... 78-я строка - вводим первый ключ = -1 для завершения работы программы.

Что именно не так в приведенном логе?
0
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 33
26.12.2013, 03:13  [ТС] 11
Огромное спасибо начинаю разбираться. А процедуру поиска предка описать можно?

Добавлено через 3 часа 56 минут
Cо всем разобрался кроме функции NearestParent.

Добавлено через 27 секунд
Откомментировали бы её пожалуйста

Добавлено через 3 часа 34 минуты
Понятно что пришлёт в процедуру указатели на "родителя" по его индексу. А что дальше непонятно. Помогите пожалуйста.

Добавлено через 3 часа 5 минут
Пожалуйста опишите функцию самого поиска предка Не понятно как работает. Видимо как-то смотрятся все предки одного узла и все предки второго(найденные функцией find) а потом как-то находится ближайщий. Как это делается?Или я вообще не правильно что-то понимаю.?
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32816 / 21154 / 8147
Регистрация: 22.10.2011
Сообщений: 36,413
Записей в блоге: 8
26.12.2013, 03:34 12
Цитата Сообщение от need_help Посмотреть сообщение
Пожалуйста опишите функцию самого поиска предка
Пожалуйста. Сначала все предки одного из узлов (до корня дерева) заносятся в список, а потом идем по предкам второго узла и проверяем наличие очередного предка в списке до тех пор, пока не встретим в списке какой-то из предков узла B... Очевидно, что это будет именно ближайший к A общий предок...

Вот, скажем, на примере того же дерева, которое представлено на картинке. Допустим, надо найти общего предка узлов F и I... Сначала заносим в список всех предков F до самого корня дерева:
<F, D, A>
, и теперь идем от I вверх, и смотрим, присутствует ли очередной предок в списке:
Изначальный узел: I, в списке отсутствует.
I^.Parent = G, в списке отсутствует.
G^.Parent = D. Есть в списке. Значит, он и будет ближайшим общим предком узлов F и I... Осталось просто удалить список, и вернуть результат...
0
0 / 0 / 0
Регистрация: 07.12.2013
Сообщений: 33
26.12.2013, 13:55  [ТС] 13
Огромное спасибо. Огромное.

Добавлено через 9 часов 15 минут
в общем-то я так и выше написал.С каждой строчкой я не разобрался конечноособенно двойное присваивание какое-то ну да ладно.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.12.2013, 13:55
Помогаю со студенческими работами здесь

Деревья
Дано упорядоченное дерево глубины N=4 , каждая внутренняя вершина которого имеет K (&lt; 10)...

Деревья
Помогите,плиз у меня задание Описать абстракный тип данных дерево и основные функции работы с ним...

Бинарные деревья.
Вопрос жизни и смерти...Есть задача: дано 2 файла в первом 150 атрибутов типа char, во втором 100...

Бинарные деревья
Всем привет. Не хотелось просить помощи, но снова придется.... Есть задание: 1 построить дерево...


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

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

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