Форум «Всё о Паскале» > Граф и ссылки

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 для всех узлов-указателей, составляющих её.