Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Граф и ссылки
Автор: looogle 17.03.2012 2:29
Есть такой код. Универсальный способ обхода древовидного графа. С ним я разобрался. А вот как задать граф я не понимаю.
Граф:
type ukazatel = ^tree;
tree = record
data:integer;
left:ukazatel;
right:ukazatel;
end;
var p, root:ukazatel;
k, i:integer;
procedure treego(p: ukazatel; k:integer);
begin
P^.data := k;
if p^.left<>nil then treego(p^.left, k+1);
if p^.right<>nil then treego(p^.right, k+1);
write('Done!');
end;
begin
new(root);
treego(root, 1);
end.
Пожалуйста, помогите.
Автор: Krjuger 17.03.2012 17:36
Щас ты строишь полное дерево,где у каждого предка существует всегда 2 потомка.Как вариант, начинаешь дополнять условия
if p^.left<>nilнапример
if p^.left<>nil and p^.data<> 5 then ......тогда у 5 круга не будет создан левый потомок.... Я точно не могу сказать, но так вроде занумеровать нельзя,так что либо вводить еще одно поле отображающее дату,а k использовать как номер в дереве, либо менять само заполнение сделав функцию, преобразующую к к нужному значению.
Или это был лишь пример того,как ты думаешь, как должно формироваться дерево?
Автор: IUnknown 17.03.2012 22:56
Цитата
А вот как задать граф я не понимаю.
Больше похоже на дерево, а не на граф.Я в таких случаях пользуюсь приемом, подсмотренным в TurboVision в свое время (у них подобным образом организуются меню любой вложенности - одним вызовом):
type ukazatel = ^tree;
tree = record
data:integer;
left:ukazatel;
right:ukazatel;
end;
procedure walk(p: ukazatel; level:integer);
begin
writeln('':2*level, p^.data);
if p^.left<>nil then walk(p^.left, level+1);
if p^.right<>nil then walk(p^.right, level+1);
end;
function it(value : integer; L, R : ukazatel) : ukazatel;
var p : ukazatel;
begin
new(p);
with p^ do
begin
data := value;
left := L;
right := R;
end;
it := p;
end;
var
root : ukazatel;
begin
root := it(2,
it(7,
it(2, nil, nil),
it(6,
it(5, nil, nil),
it(11, nil, nil)
)
),
it(5,
nil,
it(9,
it(4, nil, nil),
nil
)
)
);
walk(root, 0); { <--- Выводим, что получилось}
{ Не забудь удалить структуру }
end.
Автор: looogle 20.03.2012 0:43
Цитата(Krjuger @ 17.03.2012 14:36) 
Щас ты строишь полное дерево,где у каждого предка существует всегда 2 потомка.Как вариант, начинаешь дополнять условия
if p^.left<>nilнапример
if p^.left<>nil and p^.data<> 5 then ......тогда у 5 круга не будет создан левый потомок.... Я точно не могу сказать, но так вроде занумеровать нельзя,так что либо вводить еще одно поле отображающее дату,а k использовать как номер в дереве, либо менять само заполнение сделав функцию, преобразующую к к нужному значению.
Или это был лишь пример того,как ты думаешь, как должно формироваться дерево?
Изначально граф не задан, поэтому обходить он его не будет. Там стоит условие
if p^.left<>nil
чтобы ходить по графу, а
P^.data := k;
просто как пример.
Мне надо было узнать, как именно задавать граф. Иначе алгоритм просто не будет работать.
Добавлено через 2 мин.
Цитата(IUnknown @ 17.03.2012 19:56)
Больше похоже на дерево, а не на граф.
Я в таких случаях пользуюсь приемом, подсмотренным в TurboVision в свое время (у них подобным образом организуются меню любой вложенности - одним вызовом):
type ukazatel = ^tree;
tree = record
data:integer;
left:ukazatel;
right:ukazatel;
end;
procedure walk(p: ukazatel; level:integer);
begin
writeln('':2*level, p^.data);
if p^.left<>nil then walk(p^.left, level+1);
if p^.right<>nil then walk(p^.right, level+1);
end;
function it(value : integer; L, R : ukazatel) : ukazatel;
var p : ukazatel;
begin
new(p);
with p^ do
begin
data := value;
left := L;
right := R;
end;
it := p;
end;
var
root : ukazatel;
begin
root := it(2,
it(7,
it(2, nil, nil),
it(6,
it(5, nil, nil),
it(11, nil, nil)
)
),
it(5,
nil,
it(9,
it(4, nil, nil),
nil
)
)
);
walk(root, 0); { <--- Выводим, что получилось}
{ Не забудь удалить структуру }
end.
Да, именно то, что надо! Спасибо.
А в root записывается голова или хвост?
Автор: IUnknown 20.03.2012 1:24
У дерева не очень принято называть этот элемент "голова" или "хвост". Обычно у деревьев бывает "корень", из которого все и растёт. Вот тут как раз и есть Root (в переводе - корень)
Автор: looogle 20.03.2012 1:37
Цитата(IUnknown @ 19.03.2012 22:24)
У дерева не очень принято называть этот элемент "голова" или "хвост". Обычно у деревьев бывает "корень", из которого все и растёт. Вот тут как раз и есть Root (в переводе - корень)
Да-да. Это я и имел ввиду. Спасибо.
Вот конечный код, если интересно.
P.S. Что значит удалить структуру?
uses GraphABC;
type
ukazatel = ^tree;
tree = record
x: integer;
y: integer;
left: ukazatel;
right: ukazatel;
data:integer;
end;
procedure walk(p: ukazatel; x,y,level,xp,yp: integer);
var s:string;
begin
if p^.left <> nil then walk(p^.left, x-(150 div level), y+30, level+1, x, y);
if p^.right <> nil then walk(p^.right, x+(150 div level), y+30, level+1, x, y);
MoveTo(x,y);
LineTo(xp,yp);
s:=IntToStr(p^.data);
p^.x := x;
p^.y := y;
Circle(x,y,13);
TextOut(x-5,y-5,s);
end;
function it(datav:integer; L, R: ukazatel): ukazatel;
var
p: ukazatel;
begin
new(p);
with p^ do
begin
left := L;
right := R;
data := datav;
end;
it := p;
end;
var
root: ukazatel;
begin
root := it(2,
it(7,
it(2, nil, nil),
it(6,
it(5, nil, nil),
it(11, nil, nil)
)
),
it(5,
nil,
it(9,
it(4, it(22, it(55, nil, nil), nil), nil),
nil
)
)
);
walk(root, 250, 250, 1, 250, 250);
end.
Автор: TarasBer 20.03.2012 13:30
Удалсть структуру - это значит удалить память, занимаемую её, то есть сделать Dispose для всех узлов-указателей, составляющих её.