16. Указатели

Предыдущий раздел:

16.3. Динамическое выделение памяти

Следующий раздел:

Задание 16: Указатели

16.4. Рекурсивные структуры данных

Пусть описан тип-запись, и одним из полей этой записи является указатель. В этот указатель можно записать адрес, по которому данная запись располагается, либо, что более интересно адрес другой записи того же типа. Это позволяет при помощи указателей создать структуру данных, называемую связанным списком.

Пример описания такой структуры данных:

  type
    PListElement = ^TListElement;
    TListElement = record
      <Произвольные поля записи>
      NextElement: PListElement;
    end;

Здесь сначала описывается тип – указатель PListElement на запись типа TListElement. Затем идет описание самого типа записи, одно из полей которой имеет тип PListElement. Получается, что мы используем идентификатор TListElement еще до того, как его описали. Обычно такие вещи запрещено делать, но в данном случае, когда описывается ссылочный тип, из этого правила сделано исключение.

Если имеется запись этого типа, то можно с помощью указателя динамически создать еще один элемент этого типа. По указателю в этом новом элементе еще один элемент и т.д., сколько потребуется. Такая структура данных называется однонаправленным связанным списком. Ее схематическое изображение показано на рис. 1.

Рис. 1. Связанный список.

Пример 1: Пусть в виде однонаправленного связанного списка хранятся целые числа. Создать процедуры, которые:

    а) Создают список, динамически выделяя из кучи память под заданное число элементов N.
    б) Заполняют информационную часть элементов списка числами 1, 2, …, N.
    в) Печатают в столбик информационную часть списка.
    г) Уничтожают список, возвращая в кучу выделенную под него память.

Решение:

type
  PList = ^TList;
  TList = record
    x: integer; {Информационное поле}
    Next: PList; {Ссылка на следующий элемент списка}
  end;

procedure CreateList(var Head: PList; Num: integer);
{Процедура создает список, содержащий Len элементов, 
начинающийся с элемента Head}
var
  n: integer;
  H: PList;
begin
  if Num > 1 then
  begin
    New(Head);
    H := Head;
    {При работе с однонаправленными списками принципиально 
     важно не потерять ссылку на первый элемент. Поэтому 
     дальнейшие операции будем проводить не с Head, а со 
     вспомогательной переменной H}
    for n := 2 to Num do
    begin
      New(H^.Next);
      H := H^.Next;
    end;
    H^.Next := nil;
  end else
    Head := nil;
end;

procedure FreeList(var Head: PList);
{Процедура освобождающая память, выделенную под список с 
первым элементом Head}
var
  H: PList;
begin
  {Поскольку список все равно уничтожается, 
   можем спокойно изменять Head}
  while Head <> nil do
  begin
    H := Head;
    Head := Head^.Next;
    Dispose(H);
  end;
end;

procedure FillList(Head: PList);
{Процедура заполняет информационную часть элементов списка 
числами 1, 2, 3, …}
var
  n: integer;
begin
  n:=1;
  while Head <> nil do
  begin
    Head^.x := n;
    n := n+1;
    Head:=Head^.Next;
  end;
end;

procedure PrintList(Head: PList);
{Процедура печатает информационную часть элементов списка}
begin
  while Head <> nil do
  begin
    writeln(Head^.x);
    Head := Head^.Next;
  end;
end;

Программа, работающая с этими процедурами, может выглядеть, например, так:

var
  List: PList;
begin
  CreateList(List, 5); {Создаем список из 5-ти элементов}
  FillList(List); {В информационные части пишем числа 1, 2, 3, 4, 5}
  PrintList(List); {Печатаем информационные части элементов списка}
  ClearList(List); {Освобождаем память}
  readln;
end.

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

Например, у связанных списков легче производить операцию вставки и удаления элементов внутри структуры. У массива надо смещать все последующие элементы, в списках достаточно поменять указатель одного только предыдущего элемента.

С другой стороны, если надо получить доступ к элементу по его номеру, в массиве это делается сразу, в то время как в списке придется пройти все цепочку, начиная с головного элемента.

В рассмотренных однонаправленных списках, зная элемент, можно было найти все последующие элементы. Однако, если известна ссылка на один из средних элементов, то идущие перед ним найти не удастся. Если в нахождении предыдущих элементов есть нужда, то создаются двунаправленные списки, каждый элемент которых содержит два указателя – на предыдущий и последующий элементы.
Вообще говоря, каждый элемент подобной структуры может содержать сколько угодно указателей на элементы того же типа, что позволяет формировать не только списки, но также деревья и графы.

Следующий раздел:

Задание 16: Указатели

Предыдущий раздел:

16.3. Динамическое выделение памяти

Добавить комментарий