• Вступление
• Теория
• Новости сайта

[26.01.03] Новая статья: Процедуры и функции языка Паскаль

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

Как вы могли заметить односвязные списки имеют один большой недостаток, который препятствует их широкому применению: такой список нельзя просматривать в обратном направлении. Для этих целей используются списки с двойной связью. Такой список представляет из себя ту же структуру, только теперь добавляется указатель на предыдущий элемент. Т.е. вот так:

	+------+<---|  |---->+------+<---|  |---->+------+    
	| data |    |  |     | data |    |  |     | data |
	+------+    |  |     +------+    |  |     +------+
	| next |    |  |     | next |    |  |     | next |
	|  ---------+---     |  ---------+---     |  -------------> nil
	+------+    |        +------+    |        +------+     
        | prev |    |        | prev |    |        | prev |
nil<---------  |    |-------------  |    |-------------  |  
        +------+             +------+             +------+

type
  plist = ^tlist;
  tlist = record
          data : integer;
          next, prev : plist;
  end;

p2list = ^plist;

Для начала откажемся от глобальных переменных. Давайте представим, что мы будем писать функции и процедуры для кого другого, т.е. у нас не будет глобальных переменных - всё, что нам нужно мы будем получать из параметров. Начнём с добавления нового элемента в конец списка. Это очень просто :)

procedure AddToEnd (list : p2list; d : integer);
var
 prior : plist;
begin
     prior := nil;

{ перематываем список до конца }
     while list^ <> nil do
     begin
        prior := list^;
        list := @list^^.next
     end;

{ добавляем новый элемент }

     New (list^);

     with list^^ do
     begin
       data := d;
       next := nil;
       prev := prior
     end
end;

Теперь давайте разберём зачем мы здесь использовали @. Опять обратимся к определению указателя: указтель - это адрес. Значит в list у нас должен содержаться адрес указателя на tlist. Такой указтель у нас есть - list^^.next - указывает на tlist. Значит мы должны присвоить list адрес list^^.next, что мы благополучно и делаем. В остальном эта процедура ничем замечательным не обладает.

Итак элемент добавлен, после работы его надо удалить.

procedure DelFromEnd (list : p2list);
var
  old : plist;
begin
  if list^ = nil then
     exit; { список пуст, удалять нечего }

{ перемотка в конец }
  while list^^.next <> nil do
    list := @list^^.next;

{ list^ указывает на последний элемент }
  old := list^;

{ удаляем этот элемент логически ....}
  list^ := nil;
{ ... и физически - освобождаем память }
  Dispose (old)
end;

1. Преобразовать DelFromEnd в функцию, возвращающую значение false, если список пуст, тогда что бы его очистить можно создать пустой цикл, пока функцию не вернёт false
2. Воспользоваться специальной процедурой, текст которой приведён ниже.

procedure Clear (list : p2list);
var
  old : plist;
begin
  if list^ = nil then
    exit;

{ перемотка в начало }
  while list^^.prev <> nil do
     list^ := list^^.prev;

{ перемотка в конец с уничтожением текущего элемента }
  while list^ <> nil do
  begin
    old := list^;
    list^ := list^^.next;
    Dispose (old)
  end
end;

function FindData (list : p2list; data : integer): boolean;
var
  l : plist;
begin
  if  list^ = nil then
  begin
    FindData := false;
    exit
  end;

  while list^^.prev <> nil do
     list^ := list^^.prev;

  l := list^;

  while l <> nil do
  begin
    if l^.data = data then
    begin
       FindData := true;
       list^ := l;
       exit
    end;
    l := l^.next
  end;

  FindData := false
end;

procedure bla (c,d : integer);
begin 
  c := 2;
  d := 3
end;

var
 a, b : integer;
begin
  a := 0;
  b := 0;
  bla (a, b)
end.

type
   pint = ^integer;

procedure bla (c,d : pint);
begin 
  c^ := 2;
  d^ := 3
end;

var
 a, b : integer;
begin
  a := 0;
  b := 0;
  bla (@a, @b)
end.

Всё это конечно хорошо, но зачем тогда мы передаём в процедуры для работы со списком указатель на указатель, а не просто указатель! Тут всё дело в организации списка. Для односвязного списка мы использовали 2 указателя: начала и рабочий. Для двусвязного списка необходимость в указателе на начало отпадает, поэтому у нас будет один единственный указатель. С ним надо быть осторожнее! Не дай бог обратить его где-нибудь в nil! Односвязный список мы могли бы востановить по указателю начала. Поэтому например в функции поиска для перемотки используется дополнительная переменная. Однако я отвлёкся. Главная часть нашей программы будет выглядеть так:

var
  list : plist;  { это и есть наш список }
begin
   .....
   AddToListEnd (@list, d);
   .....

Но вернёмся к нашим баранам. Продолжим пополнять арсенал процедур и функций для работы со списком. Теперь, когда мы можем найти элемент в списке, то нужно с ним что-то делать. Например удалить или вставить новый после него. Начнём со вставки. Что бы вставить элемент нам надо соответствующим образом изменить указатели next у предшествующего и prev у следующего. Т.е. если вначале у нас был такой список:

   ...---->+------+<---|  |---->+------+    
           | data |    |  |     | data |
           +------+    |  |     +------+
           | next |    |  |     | next |
           |  ---------+---     |  ------------->....
           +------+    |        +------+ 
           | prev |    |        | prev |
   ...<---------  |    |-------------  |  
           +------+             +------+

   ...---->+------+             +------+    
           | data |             | data |
           +------+             +------+
           | next |             | next |
           |  ------|           |  ------------->...
           +------+ |           +------+ 
           | prev | |           | prev |
   ...<---------  | |     |----------  |  
           +------+ |     |     +------+
               ^    |    \ /        ^
               |    |->+------+     |
               |       | data |     |
               |       +------+     |
               |       | next |     |
               |       |  ----------|
               |       +------+
               |       | prev |
               |-----------   |
                       +------+

procedure Add (list : p2list; d : integer);
var
  l : plist;
begin
   if list^ = nil then
   begin
      AddToEnd (list, d);
      exit
   end;

   New (l);
   l^.data := d;
   l^.prev := list^;
   l^.next := list^^.next;
   list^^.next := l
end;

procedure AddToBegin (list : p2list; d : integer);
var
  l : plist;
begin
  if list^ = nil then
  begin
     AddToEnd (list, d);
     exit
  end;

  while list^^.prev <> nil do
      list := @list^^.prev;

  New (l);

  l^.data := d;
  l^.prev := nil;
  l^.next := list^;
  list^^.prev := l
end;

procedure DelFromBegin (list : p2list);
var
 old : plist;
begin
  if list^ = nil then
    exit;

  while list^^.prev <> nil do
     list^ := list^^.prev;

   old := list^;
   list^ := list^^.next;
   list^^.prev := nil;

   Dispose (old)
end;

var
  list : plist;  { это и есть наш список }
begin
   .....
   AddToListEnd (@list, d);
   .....

*123

321 *123

321 *123 456

321 *123 0 456

321 123 0 *456

procedure Display (list : plist);
var
  p : plist;
begin
  if list = nil then
     writeLn ('Список пуст')
  else
  begin
    p := list;

    while p^.prev <> nil do
       p := p^.prev;

    while p <> nil do
    begin
       if p = list then
         write ('*');
       write (p^.data, #32);
       p := p^.next
    end
  end
end;

Ну и наконец я привожу текст программы, работающей с двусвзяным списком. Как и в прошлый раз процедуры, которые я дал вам на домашнее рассмотрение не приведены.