VPF::Реализация графов. - Форум программистов

Joil

Дата 18.4.2008, 19:31 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 211
Регистрация: 24.1.2008

Репутация: нет
Всего: 8

Всем привет.
Нужно построить граф в паскале (заданный списком инцидентности) с помощью динамической структуры данных. Не могу понять, как?
Если кто знает, киньте в меня ссылкой...

И вообще если кто знает хор. ресурс (с примерами и объяснениями) по динамическим объектам (стеки, очереди, деревья, графы....) в паскале, будьте добры, подскажите....

Это сообщение отредактировал(а) Joil - 18.4.2008, 19:34

--------------------

Who had deceived thee so often as thyself? © Benjamin Franklin--------------------Always bear in mind that your own resolution to succeed is more important than any other. © Abraham Lincoln--------------------If you need it - do it, if you want it - take it! © ...

volvo877

Дата 18.4.2008, 20:21 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Вообще-то список инцидентности (по Липскому) - не совсем динамическая структура... Скажем так, наполовину - это статический массив динамических списков... Вот так задается граф:

Код


const
  n = 6; { Это - число вершин графа }

type
  plist = ^tlist;
  tlist = record
    index: integer;
    next: plist;
  end;

function get_list(n: integer): plist;
var
  p, first, last: plist;
  value, size, i: integer;
begin
  write('Число вершин, связанных с (',n,') = '); readln(size);

  first := nil; last := nil;
  for i := 1 to size do begin
    new(p);
    write('вершина №', i, ': '); readln(value);
    p^.next := nil; p^.index := value;

    if first = nil then first := p
    else last^.next := p;

    last := p;
  end;
  get_list := first;
end;

var
  inc_list: array[1 .. n] of plist; { собственно, массив списков }
  i: integer;

var
  p: plist;

begin
  for i := 1 to n do begin
    inc_list[i] := get_list(i); { Заносим в массив создаваемый список }
  end;

  { Для наглядности - распечатываем список инцидентности }
  for i := 1 to n do begin
    p := inc_list[i];
    while p <> nil do begin
      write(p^.index:5);
      p := p^.next;
    end;
    writeln;
  end;

  ...  { собственно, работа с графом }

end.

Можно, конечно, сделать и список списков, для этого придется добавить всего навсего одну процедуру... Если не получится - говори, я помогу...

Насчет остальных ДСД - посмотри у меня на сайте...

Это сообщение отредактировал(а) volvo877 - 18.4.2008, 20:22

Joil

Дата 6.6.2008, 17:26 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 211
Регистрация: 24.1.2008

Репутация: нет
Всего: 8

Блин, чет не получается у меня сделать, вернее я сделал, но чет не то!!!! volvo877 как список списков сделать!!!

Это сообщение отредактировал(а) Joil - 6.6.2008, 17:43

--------------------

volvo877

Дата 6.6.2008, 19:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Цитата(Joil @ 6.6.2008, 17:26

)

как список списков сделать

Я ж говорил, что надо добавить всего одну процедуру:

Код

const
  n = 6; { Это - число вершин графа }
type
  plist = ^tlist;
  tlist = record
    index: integer;
    next: plist;
  end;

  { а вот это - список списков (элемент данных - список вершин) }
  pdynlist = ^tdynlist;
  tdynlist = record
    info: plist;
    next: pdynlist;
  end;


function get_list(n: integer): plist;
var
  p, first, last: plist;
  value, size, i: integer;
begin
  write('Число вершин, связанных с (',n,') = '); readln(size);
  first := nil; last := nil;
  for i := 1 to size do begin
    new(p);
    write('Вершина №', i, ': '); readln(value);
    p^.next := nil; p^.index := value;
    if first = nil then first := p
    else last^.next := p;
    last := p;
  end;
  get_list := first;
end;

{ вот это - то, что было добавлено }
procedure append_list(var first, last: pdynlist;
          to_add: plist);
var p: pdynlist;
begin
  new(p);
  p^.info := to_add;
  p^.next := nil;

  if first = nil then first := p
  else last^.next := p;

  last := p;
end;


var
  ilist_first, ilist_last: pdynlist;
  i: integer;
var
  lst_lst: pdynlist;
  lst: plist;
begin
  ilist_first := nil; ilist_last := nil;
  for i := 1 to n do
    append_list(ilist_first, ilist_last, get_list(i));

  { Для наглядности - распечатываем список инцидентности }
  lst_lst := ilist_first;
  while lst_lst <> nil do begin

    lst := lst_lst^.info; { первый элемент списка вершин }
    while lst <> nil do begin
      write(lst^.index:5);
      lst := lst^.next;
    end;
    writeln;

    lst_lst := lst_lst^.next; { продвигаемся по списку списков дальше }
  end;

  ...  { работа с графом }
end.

Joil

Дата 6.6.2008, 23:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 211
Регистрация: 24.1.2008

Репутация: нет
Всего: 8

volvo877 спасибо (+1), щас посмотрю твой код!! А вообще я вот так сделал:

Код


uses crt;

type ListV = ^VInc;
              VInc = record
                       VIndex:integer;
                       VNext:ListV;
                     end;
     ListR = ^RInc;
              RInc = record
                       RIndex:ListV;
                       RNext:ListR;
                     end;

var QR:integer;
    i:integer;
    FirstR,NR:ListR;

function Index(var i:integer):ListV;
var QV:integer;
    j:integer;
    FirstV,NV:ListV;
begin
  write('--Введите количество вершин соединеных с вершиной ',i,': ');
  readln(QV);
  for j:=1 to QV do
    begin
      New(NV);
      NV^.VNext:=FirstV;
      Write('---Введите вершину ',j,': ');
      Readln(NV^.VIndex);
      FirstV:=NV;
    end;
end;

begin
  ClrScr;
  Write('-Введите количество вершин графа: ');
  ReadLn(QR);
  for i:=1 to QR do
    begin
      New(NR);
      NR^.RNext:=FirstR;
      NR^.RIndex:=Index(i);
      FirstR:=NR;
    end;
  ReadKey;
end.

Незнаю, правильно или нет!!! Если подскажешь, буду очень признателен!

Это сообщение отредактировал(а) Joil - 6.6.2008, 23:17

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »