Структура данных и алгоритмы на языке Pascal

Очереди, стеки, связанные списки и деревья

Программы состоят из алгоритмов и структур данных. Хорошие программы используют преимущества их обоих. Выбор и разработка структуры данных столь же важна, как и разработка процедуры, которая манипулирует ими. Организация информации и методы доступа к ней обычно определяются характером стоящей перед программистом задачи. Поэтому каждый программист должен иметь в своем "багаже" соответствующие методы представления и поиска данных, которые можно применить в каждой конкретной ситуации.
В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как "char", "integer", "real". На следующем уровне находятся массивы, представляющие собой наборы базовых типов данных. Затем идут записи, представляющие собой группы типов данных, доступ к которым осуществляется по одному из данных, а на последнем уровне, когда уже не рассматриваются физические аспекты представления данных, внимание обращается на порядок, в котором данные хранятся и в котором делается их поиск. По существу физические данные связаны с "машиной данных", которая управляет способом доступа к информации в вашей программе. Имеется четыре такие "машины":
  • очередь;
  • стек;
  • связанный список;
  • двоичное дерево.
Каждый метод используется при решении определенного класса задач. Каждый метод по существу является неким "устройством", которое обеспечивает для заданной информации определенный способ хранения и при запросе выполняет определенные операции поиска данных. В каждом из этих методов используется две операции: добавить элемент и найти элемент /под элементом понимается некоторая информационная единица/.

ОЧЕРЕДИ

Очередь представляет собой линейный список данных, доступ к которому осуществляется по принципу "первый вошел, первый вышел" /иногда сокращенно его называют методом доступа FIFO/. Элемент, который был первым поставлен в очередь, будет первым получен при поиске. Элемент, поставленный в очередь вторым, при поиске будет получен также вторым и т.д. Этот способ является единственным при постановке элементов в очередь и при поиске элементов в очереди. Применение очереди не позволяет делать прямой доступ к любому конкретному элементу.
В повседневной жизни очереди встречаются часто. Например, очередь в банке или очередь в кафетериях с быстрым обслуживанием являются очередью в указанном выше смысле /исключая те случае, когда человек пытается добиться обслуживания вне очереди!/. Для того, чтобы лучше понять работу очереди, рассмотрим две процедуры: постановка в очередь и выборка из очереди. При выполнении процедуры постановки в очередь элемент помещается в конец очереди. При выполнении процедуры выборки из очереди из нее удаляется первый элемент, который является результатом выполнения данной процедуры. Работа очереди проиллюстрирована на рис.1. Следует помнить, что при выборке из очереди из нее действительно удаляется один элемент. Если этот элемент нигде не будет сохранен, то в последствии к нему нельзя будет осуществить доступ.
Операция                           Содержимое очереди

1 Qstore(A)                         A

1 Qstore(B)                         A B

1 Qstore(C)                         A B C

2 Qretrieve returns A               B C

1 Qstore(D)                         B C D

2 Qretrieve returns B               C D

2 Qretrieve returns C               D
Рис.1. Работа очереди: 1 - постановка в очередь; 2 - выборка из очереди элемента А, В, С.
Очереди в программировании используются во многих случаях, например, при моделировании (обсуждается ниже в соответствующей главе), при планировании работ (метод ПЕРТ или графики Гатта), при буферизации ввода-вывода.
В качестве примера рассмотрим простую программу планирования предписаний, которая позволяет обращаться к нескольким предписаниям. При каждом обращении предписание удаляется из списка и на экран выводится следующее предписание. Для простоты в программе используется массив символьных строк для управления событиями. Описание предписания ограничивается 80 символами и число предписаний не должно превышать 100. Прежде всего в этой программе планирования должны быть предусмотрены процедура постановки в очередь и процедура выборки из очереди. Эти процедуры приводятся ниже и даются необходимые описания глобальных переменных и типов данных.
const
  MAX_EVENT = 100;

type
  EvtType = string[80];
  var
    event: array[1..MAX_EVENT] of EvtType;
    spos, rpos: integer;

  {добавить в очередь}
  procedure Qstore(q:EvtType);
  begin
    if spos=MAX_EVENT then
      WriteLn('List full')
    else
    begin
      event[spos]:=q;
      spos:=spos+1;
    end;
end; {конец процедуры постановки в очередь}

{ выборка объекта из очереди }
function Qretrieve:EvtType;
begin
  if rpos=spos then
  begin
    WriteLn('No appointments scheduled.');
    Qretrieve := ' ';
  end else
  begin
    rpos:=rpos+1;
    Qretrieve := event[rpos-1];
  end;
end; { конец процедуры выборки из очереди }
В работе этих функций используются три глобальные переменные: "spos", которая содержит индекс следующего свободного элемента; "rpos", которая содержит индекс следующего выбираемого элемента и "event", которая представляет собой массив символьных строк с описанием предписаний. Переменные "spos" и "rpos" должны быть установлены в нулевое значение до первого обращения к процедурам постановки в очередь и выборки из очереди.
В этой программе процедура постановки в очередь помещает новые события в конец списка и делает проверку заполнения списка. Функция выборки из очереди выбирает события из очереди при необходимости их обработки. Когда планируется новое событие, переменная "spos" увеличивается на единицу, а когда событие завершается, то увеличивается на единицу переменная "rpos". Фактически переменная "rpos" преследует переменную "spos" в проходах по очереди. Этот процесс иллюстрируется на рис.2. Если значение указателя свободного места совпадает со значением указателя выбираемого элемента, то это означает, что в очереди нет событий. Следует помнить, что хотя функция выборки элемента из очереди в действительности не нарушает информацию в очереди, повторный доступ к ней невозможен и фактически она исчезает.
Ниже приводится целиком программа, осуществляющая простое планирование предписаниями. Вы можете усовершенствовать эту программу по собственному желанию.

Циклическая очередь







Рис.2. Указатель поиска преследует указатель свободного места в очереди:
1 - очередь в исходном положении;
2 - указатель свободного места в очереди;
3 - указатель следующего выбираемого элемента;
4 - процедура постановки в очередь;
5 - функция выборки из очереди.
{ простое  планирование предписаниями }
procram MiniScheduler;

uses Grt;

const
  MAX_EVENT = 100;
type
  EvtType = string[80];

var
  event: array[1..MAX_EVENT] of EvtType;
  spos, rpos, t: integer;
  ch:char;
  done:boolean;

{ добавить в очередь }
procedure Qstore(q:EvtType);
begin
  if spos=MAX_EVENT then
    WriteLn('List full')
  else
  begin
    event[spos] := q;
    spos := spos+1;
  end;
end; { конец процедуры постановки в очередь }

{ выборка объекта из очереди }
function Qretrieve:EvtType;
begin
  if rpos=spos then
  begin
    WriteLn('No appointments scheduled.);
    Qretrieve := ' ';
  end else
    begin
      rpos := rpos+1;
      Qretrieve := event[rpos-1];
    end;
end; { конец функции выборки элемента  из  очереди }

{ ввести предписание в планировщик }

procedure Enter;
var
  s: string[80];

begin
  repeat
    Write('Enter appointment',spos+1, ':');
    ReadLn(s);
    WriteLn;
    if Length(s)<>0 then Qstore(s);
  until Length(s)=0;
end; { конец процедуры ввода }

{ вывести предписание }
procedure Review;
var
  t: integer;
begin
  for t:=rpos to spos-1 do WriteLn(t+1,':',event[t]);
end; { конец процедуры вывода }

{ активизировать предписание }
procedure Periorm;
var
  s:string[80];
begin
  s:=Qretrieve;  { получить следующее предписание }
  if Length(s)<>0 then WriteLn(s);
end; { конец процедуры   активизации   предписаний }

begin  { начало планировщика }
  for t:= 1 to MAX_EVENT do event[t]:=''; { инициализация событий}
  spos:=0; rpos:=0; done:=FALSE;

  repeat
    Write('Enter,Review, Pertorm,Quit: ');
    ch:= ReadKey;
    WriteLn;
    Case upcase(ch) of
      'E':Enter;
      'R':Review;
      'P':Perform;
      'Q':done:=TRUE;
    end;
  until done=TRUE;
end.
При чтении предыдущего раздела вы возможно подумали об улучшении программы планирования предписаниями. Вместо остановки программы по достижению предела массива, который используется под очередь, можно указатель постановки в очередь и указатель выборки из очереди вернуть на начало массива. В этом случае в очередь можно добавлять любое число элементов в то время как элементы будут также выбираться из очереди. Такая очередь называется циклической, поскольку теперь массив используется не как линейный список, а как циклический список.
Для создания циклической очереди в программе планирования предписаний требуется изменить подпрограммы постановки в очередь и выборки из очереди следующим образом:
procedure Qstore(q: EvtType);
begin
  { убедитесь,  что  имеется  свободное место в очереди }
  if ((spos+1=rpos) or ((spos=MAX_EVENT) AND (rpos=0))then
    WriteLn('List full')
  else
  begin
    event[spos] := q;
    spos := spos+1;
    if spos=MAX_EVENT then spos:=1; { возврат в начало }
  end;
end; { конец процедуры постановки в очередь }

function Qretrieve:EvtType;
begin
  if rpos=MAX_EVENT then rpos:=1; { возврат в начало }
  else rpos:=rpos+1;

  if rpos=spos then
  begin
    WriteLn('Queue empty');
    Qretrieve:=';';
  end else
    Qretrieve:=event[rpos-1];
end; { конец функции выборки из очереди }
В действительности очередь становится заполненной только в том случае, когда указатель свободного места совпадает с указателем выборки следующего элемента. В противном случае очередь будет иметь свободное место для нового элемента. Однако, это значит, что в начале программы индекс выборки должен устанавливаться не в нулевое значение, а на значение максимального числа событий. В противном случае первое обращение к процедуре постановки в очередь приведет к появлению сообщения о заполнении списка. Следует помнить, что очередь может содержать только на один элемент меньше, чем значение максимального числа событий, поскольку указатели выборки и постановки в очередь всегда должны отличаться хотя бы на единицу (в противном случае нельзя будет понять заполнена ли очередь или она пустая).
Наиболее широко циклические очереди применяются в операционных системах при буферизации информации, которая считывается или записывается на дисковые файлы или консоль. Другое широкое применение эти очереди нашли в решении задач реального времени, когда, например, пользователь может продолжать делать ввод с клавиатуры во время выполнения другой задачи. Так работают многие текстовые процессоры, когда изменяется формат параграфа или выравнивается строка. Имеется короткий промежуток времени, когда набранная на клавиатуре информация не выводится на экран до окончания другого процесса. Для достижения такого эффекта в программе должна предусматриваться постоянная проверка ввода с клавиатуры в ходе выполнения другого процесса. При вводе некоторого символа его значение должно быстро ставиться в очередь и процесс должен продолжаться. После завершения процесса набранные символы выбираются из очереди и обрабатываются обычным образом.
Для того, чтобы понять, как это можно сделать с помощью циклической очереди, рассмотрим следующую простую программу, состоящую из двух процессов. Первый процесс выполняет подсчет до 32 000. Второй процесс устанавливает символы в циклическую очередь по мере того как они вводятся с клавиатуры. При этом вводимые символы не будут выводиться на экран до тех пор, пока не будет введена точка с запятой. Вводимые символы не будут выводиться на экран, поскольку первый процесс будет иметь более высокий приоритет до тех пор, пока вы не введете точку с запятой или пока счетчик не достигнет максимального значения. Затем из очереди будут выбраны введенные символы и выведены на экран.
{ программа, иллюстрирующая применение циклической очереди }
program KeyBuffer;

uses Crt, Dos;

const
  MAX_EVENT = 10;

type
  EvtType = char;

var
  event: array[1..MAX_EVENT] of EvtType;
  spos, rpos, t: integer;
  ch: char;

{ поместить объект в очередь }
procedure Qstore(q:EvtType);
begin
2 { убедиться,  что в очереди имеется свободное место}
  if ((spos+1=rpos) or ((spos=MAX_EVENT) AND (rpos=0))then
    WriteLn('List full')
  else
  begin
    event[spos]:=q;
    spos:=spos+1;
    if spos=MAX_EVENT then spos:=1; { вернуться в начало очереди }
  end;
end; { конец процедуры  постановки в очередь }

{ выборка объекта из очереди }
function Qretrieve:EvtType;
begin
  if rpos=MAX_EVENT then rpos:=1; { вернуться в начало очереди }
  else rpos:=rpos+1;

  if rpos=spos then
  begin
    WriteLn('Queue empty');
    Qretrieve:=';';
  end else
  begin
    Qretrieve:= event[rpos-1];
  end;
end; { конец функции выборки объекта из очереди  }

begin  { буфер набранных  с  помощью клавиатуры символов }
  spos := 0;
  rpos := MAX_EVENT;
  { установить переменную "ch" на начальное значение, отличное от точки с запятой }

  ch:=' ';
  t := 1;
  repeat
    if KeyPressed then
    begin
      ch := ReadKey;
      Qstore(ch);
    end;
    t:=t+1;
    write(t); write(' ');
  until (t=32000) or (ch=';');

{ вывести  содержимое буфера введенных с клавиатуры символов }
  repeat
    ch:=Qretrieve;
    if ch<>';' then Write(ch);
  until ch = ';';
end.
Процедура "KeyPressed" делает обращение к программе операционной системы, которая возвращает значение "истина", если была нажата какая-либо клавиша, или значение "ложь", если клавиатура не использовалась.

СТЕКИ

Организация стека в определенном смысле противоположна организации очереди, поскольку здесь используется доступ по принципу "последней вошел, первый вышел" /такой метод доступа иногда называют методом LIFO/. Представим себе стопку тарелок. Нижняя тарелка из этой стопки будет использована последней, а верхняя тарелка /которая была установлена в стопку последней/ будет использована первой. Стеки широко используются в системном программном обеспечении, включая компиляторы и интерпретаторы.
Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализации стека необходимо создать две функции: "posh" /затолкнуть/, которая помещает элемент в вершину стека, и "pop" /вытолкнуть/, которая выбирает из вершины стека значение. Необходимо также предусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать массив или можно выделить область памяти, используя средство динамического распределения памяти, предусмотренное в языке Паскаль. Как и при работе с очередью при выборке значения из стека элемент будет потерян, если его не сохранить где-нибудь в памяти. Ниже приводится общая форма процедур установки в стек и выборки из стека.
const
  MAX = 100;

var
  stack:array[1..100] of integer;
  tos:integer; {points to top of stask}

{ помещение объекта в стек }
procedure Push(i:integer);
begin
  if tos>=MAX then WriteLn('Stask full')
  else
  begin
    stack[tos]:=i;
    tos:=tos+1;
  end;
end; { конец  процедуры  помещения объекта в стек}

{ выборка объекта из стека }
function Pop:integer;

begin
  tos:=tos-1;
  if tos<1 then
  begin
    WriteLn('Stack underflow');
    tos:=tos+1;
    Pop:=0;
  end
  else Pop := stack[tos];
end; { конец функции выборки объекта из стека }
Переменная "tos" содержит значение индекса для следующего помещаемого в стек элемента. При реализации этих процедур никогда нельзя забывать о проверке ситуаций переполнения стека и выборки из пустого стека. В приведенных процедурах нулевое значение указателя "tos" означает, что стек пуст, а значение этого указателя, равное или превышающее адрес последней ячейки памяти, где содержится стек, означает заполнение стека. Рис.3 иллюстрирует работу стека.
Операция                   Содержимое стека
Push(A)                    A
Push(B)                    B A
Push(C)                    C B A
Pop, выбирается С          В А
Push(F)                    F B A
Pop, выбирается F          B A
Pop, выбирается В          А
Рор, выбирается А          пусто
Рис.3. Работа стека.
Хорошим примером применения стека является калькулятор, который может выполнять четыре действия. Большинство калькуляторов используют стандартную форму выражений, которая носит название инфиксной формы. В общем виде ее можно представить в виде "операнд-оператор-операнд". Например, для прибавления 100 к 200 вы должны ввести число 100, набрать символ сложения, ввести число 200 и нажать клавишу со знаком равенства. Однако, некоторые калькуляторы применяют другую форму выражений, получившую название постфиксной формы. В этом случае оба операнда вводятся перед вводом оператора. Например, для добавления 100 к 200 при использовании постфиксной формы сначала вводится число 100, затем вводится число 200 и после этого нажимается клавиша со знаком плюс. Введенные операнды помещаются в стек. При вводе оператора из стека выбираются два операнда и результат помещается в стек. При использовании постфиксной формы очень сложные выражения могут легко вычисляться на калькуляторе.
Ниже показана программа для такого калькулятора.
{ калькулятор с четырьмя операциями, иллюстрирующий работу }
program four_function_calc;
const
  MAX = 100;
var
  stack:array [1..100] of integer;
  tos:integer; { указатель вершины стека }
  a, b:integer;
  s:string[80];

  { поместить объект в стек }
  procedure Push(i:integer);
  begin
    if tos >= MAX then Writeln('Stack full')
    else
    begin
      stack[tos] :=1;
      tos := tos+1;
    end;
  end;{Push}

  { выборка объекта из стека }
  function Pop:integer;
  begin
    tos := tos-1;
    if tos < 1 then
    begin
      Writeln('Stack underflow')
      tos := tos+1;
      Pop := 0;
    end
    else Pop := stack[tos];
  end;{ Pop }

  begin { калькулятор }
    tos := 1;
    Writeln('For Function Calculator');
    repeat
      Write(': '); { вывод приглашения }
      Readln(s);
      Val(s, a, b) { преобразование строки символов в целое число }

{ считается, что при успешном преобразовании пользователь ввел число, а 
   в противном случае пользователь ввел оператор}
    if (b=0) and ((Length(s)>1) or (s[1]<>'-')) then
    Push(a)
    else
      case s[1] of
        '+' begin
              a := Pop
              b := Pop
              Writeln(a+b);
              Push(a+b);
            end;
         '-' begin
              a := Pop
              b := Pop
              Writeln(b+a);
              Push(b+a);
            end;
        '*'  begin
               a := Pop
               b := Pop
               Writeln(a*b);
               Push(a*b);
             end;
          '/' begin
               a := Pop
               b := Pop
               if a=0 then Writeln('divide by zero');
               else
                 begin
                   Writeln(b div a);
                   Push(b div a);
                 end;
               end;
          '.' begin
               a := Pop
               Writeln(a);
               Push(a);
             end;
           end;
    until UpCase(s[1])='G'
end.
Для того, чтобы посмотреть, что находится в вершине стека, достаточно ввести точку. Хотя данная программа выполняет арифметические действия только с целыми числами, ее легко можно приспособить для чисел с плавающей запятой, изменяя тип данных стека и преобразуя оператор "div" в оператор деления для чисел с плавающей запятой /наклонная черта/.

СВЯЗАННЫЕ СПИСКИ

Очереди и стеки обладают двумя общими свойствами. Во-первых, доступ к находящимся в них данных подчиняется строгим правилам. Во-вторых, операции поиска имеют разрушительный характер. Если выбранный из стека или очереди элемент не будет где-нибудь сохранен, то он будет потерян. Кроме того, стеки и очереди для своей работы требуют наличия непрерывной области памяти /непрерывность должна обеспечиваться по крайней мере логически/.
В отличии от стека и очереди связанный список позволяет осуществлять доступ к любым элементам, поскольку каждая единица информации имеет указатель на следующий элемент данных в цепочке. Элементами связанного списка являются сложные структуры данных, тогда как стеки и очереди могут работать и с простыми и со сложными структурами данных. Операция поиска в связанном списке не приводит к удалению и уничтожению элемента. В данном случае следует предусмотреть дополнительно операцию удаления элемента из списка.
Связанные списки используются в двух основных случаях. Во-первых, при создании массивов, которые располагаются в оперативной памяти и размер которых заранее неизвестен. Если вы заранее знаете, какого размера память потребуется для решения вашей задачи, то вы можете использовать простой массив. Однако, если действительный размер списка вам неизвестен, то вы должны применить связанный список. Во-вторых, связанные списки используются в базах данных на дисках. Связанный список позволяет быстро выполнять вставку и удаление элемента данных без реорганизации всего дискового файла. По этим причинам связанные списки широко используются в программах по управлению базами данных.
Связанные списки могут иметь одиночные или двойные связи. Список с одной связью содержит элементы, каждый из которых имеет связь со следующим элементом данных. В списке с двойной связью каждый элемент имеет связь как со следующим элементом, так и с предыдущим элементом. Тип связанного списка выбирается в зависимости от решаемой задачи.

Связанные списки с одиночной связью

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



Рис.4. Расположение списка с одиночной связью в памяти:
1 - информация;
2 - указатель связи;
3 - нуль.

Имеется два способа построения списка с одиночной связью. В первом случае каждый новый элемент добавляется в начало или в конец списка. Во втором случае каждый элемент добавляется в свое место в списке /например, так, чтобы обеспечить упорядочность по возрастанию/.
Способ построения списка определяется процедурой постановки нового элемента в список. Ниже дается такая процедура для простого случая, когда элементы добавляются в конец списка. Необходимо определить запись, которая будет содержать информацию и указатели связи. В этом примере запись содержит адрес почтовой корреспонденции. Тип записи для каждого элемента в списке адресов определяется ниже:
AddrPointer = ^address;
address = record
  name:   string[30];
  street: string[40];
  city:   string[20];
    state: string[2];
    zip:   string[9];
    next:  AddrPointer;  { указатель на следующую запись  }
  end;
  DataItem = address;
var
  start.last: AddrPointer;
Ниже представлена функция добавления в список с одной связью, когда каждый новый элемент помещается в конец списка. Указатель записи типа "address" должен передаваться в качестве аргумента функции:
{ добавление  в  список с одной связью }
procedure SL_Store(i: AddrPointer);
Legin
  if last=nil then  { первый элемент списка } 2
  begin
    last := i;
    start := i;
    i^.next := nil;
  end else
  begin
    last^.next := i;
    i^.next := nil;
    last := i;
  end;
end;  { конец процедуры добавления элементов в список с одной связью }
Следует помнить, что до первого обращения к этой функции переменные "start" и "last" должны быть установлены на значение "nil".
Можно предусмотреть отдельную операцию по сортировке списка, созданного с помощью указанной функции добавления элементов в список с одной связью. Однако упорядочения легче добиться во время вставки путем установки каждого нового элемента в соответствующее место списка. Кроме того, если список уже является отсортированным, то имеет смысл сохранить его упорядоченность, вставляя каждый новый элемент в соответствующее место списка. Для этого делается последовательный просмотр списка до тех пор, пока не будет найдено нужное место. В это место вставляется новый адрес и делается соответствующее изменение связей.
При вставке элемента в список с одной связью может возникнуть одна из трех ситуаций. Во-первых, новый элемент может оказаться первым в списке. Во-вторых, он может встать между другими двумя элементами и в-третьих, он может оказаться последним элементом в списке. На рис.5 показано, как для каждого из этих случаев изменяются связи.
Если изменяется первый элемент списка, то везде в программе должна быть изменена точка входа в список. Для того, чтобы избежать этого, в качестве первого элемента нужно использовать фиктивный элемент. Этот фиктивный элемент должен иметь такое значение, которое обеспечивает ему первое место в списке. В этом случае точка входа в список не будет меняться. Однако, недостатком такого метода является необходимость расхода дополнительной памяти для фиктивного элемента и поэтому в показанном примере этот метод не используется.

1 Новый первый элемент
4 becomes
6 New Middle Item
4 becomes
7 New Last Item
4 becomes
Рис.5. Вставка элемента в список с одной связью: 1 - новый первый элемент; 2 - новый элемент; 3 - информационные поля; 4 - справа дается преобразованный список; 5 - нулевой указатель связи; 6 - новый средний элемент; 7 - новый последний элемент.
Приводимая ниже функция используется для вставки адресов почтовых корреспонденций в порядке возрастания фамилий /поле "name"/. В качестве результата функции выдается первый элемент списка. Входными аргументами этой функции являются указатели на начало и конец списка.
{ добавление элементов в список с одной связью с сохранением  упорядоченности }
function SLS_Store(info, start: AddrPointer;
                     var last: AddrPointer): AddrPointer;
var
  old, top: AddrPointer;
  done: boolean;
begin
  top := start;
  old := nil;
  done := FALSE;

  if start=nil then
  begin { первый элемент списка }
    info^.next:=nil;
    ast:=info;
    SLS_Store:=info;
  end else
  begin
    while (start<>nil) and (not done) do
      begin
        if start^.name < info^.name then
        begin
          old:=start;
          start:=start^.next;
        end else
        begin { вставка в середину }
          if old<>nil then

          begin
            old^.next:=info;
            info^.next:=start;
            SLS_Store:=top; { сохранить начало  }
            done:=TRUE;
          end else
          begin
            info^.next:=start; { новый первый элемент }
            SLS_Store:=info;
            done:=TRUE;
          end;
        end;
      end; {while}
      if not done then
      begin
        last^.next:=info; { вставка в конец }
        info^.next:=nil;
        last:=info;
        SLS_Store:=top;
      end;
    end;
  end;
{ конец процедуры упорядоченной вставки в список с одной связью}
Для связанного списка обычно не предусматривается отдельная функция, связанная с процессом поиска, при котором элементы выдаются в порядке их расположения в списке. Эта функция обычно программируется очень просто и оформляется вместе с другими функциями, например, поиском отдельного элемента, его удалением или выводом на экран. В качестве примера ниже приводится процедура вывода всех фамилий в списке адресов почтовых корреспонденций:
procedure Display(start: AddrPointer);
begin
  while start<>nil do begin
    WriteLn(start^.name);
    start:=start^.next;
  end;
end;  { конец процедуры вывода}
Здесь переменная "start" является указателем на первую запись в списке.
Поиск элемента в списке представляет собой простую процедуру прохода по цепочке. Процедуру поиска адресов по фамилиям можно составить следующим образом:
function Search(start:AddrPointer;name:str80):AddrPointer;
var
  done:boolean;
begin
  done := FALSE;
  while (start<>nil) and (not done) do
begin
  if name=start^.name then
  begin
    Search:=start;
    done:=TRUE;
  end else
    start:=start^.next;
  end;
  if start=nil then Search := nil; { нет в списке }
end; { конец процедуры поиска элемента }
Поскольку эта процедура поиска в результате выдает указатель на тот элемент списка, который соответствует искомой фамилии, переменная "Search" должна объявляться как указатель записи типа "address". Если требуемый элемент отсутствует в списке, то в результате выдается нулевой указатель.
Процедура удаления элемента из списка с одной связью программируется просто. Как при вставке элемента здесь может встретиться один из трех случаев: удаляется первый элемент, удаляется средний элемент и удаляется последний элемент. На рис.6 иллюстрируется каждая ситуация.
1 Deleting the First Item 2 becomes
6 Deleting a Middle Item 2 becomes
7 Deleting the Last Item 2 becomes
Рис.6. Удаление элемента из списка с одной связью: 1 - удаление первого элемента; 2 - левый список преобразуется в правый; 3 - информационные поля; 4 - удаленный элемент; 5 - связь с нулевым значением; 6 - удаление среднего элемента; 7 - удаление последнего элемента.
Приводимая ниже функция выполняет удаление заданного элемента из списка записей адресов:
function SL_Delete(start, item, prior_item: AddrPointer):AddrPointer;
begin
  if prior_item<>nil then
  prior_item^.next:=item^.next
  else start:= item^.next;
  SL_Delete:=start;
end;  { конец функции удаления элемента из списка с одной связью }
Приведенная функция передает указатель элемента, указатель элемента, стоящего перед удаленным, и указатель на начало списка. Если удаляется первый элемент, то указатель элемента, стоящего перед удаленным, будет иметь нулевое значение. Значением функции должен являться указатель на начало списка, поскольку может удалиться первый элемент и необходимо знать, где будет новый первый элемент списка.
Списки с одной связью имеют один большой недостаток, который препятствует их широкому применению: такой список нельзя просматривать в обратном направлении. Для этих целей используются списки с двойной связью.

Списки с двойной связью

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

Рис.7. Список с двойной связью: 1 - информационные поля; 2 - связь с нулевым значением.
Для списка с двойной связью предусматриваются три основные операции: вставка нового первого элемента, вставка нового среднего элемента и вставка нового последнего элемента. Эти операции проиллюстрированы на рис.8.
Список с двойной связью строится подобно списку с одной связью, причем в записи должно быть предусмотрено место для двух указателей. Для примера со списком почтовых корреспонденций запись адреса можно модифицировать следующим образом:
type
  str80 = string[80];
  AddrPointer = ^address;
  address = record
1 Inserling a New First Element
4 becomes
6 Inserling a New Middle Element
4 becomes
7 Inserling a New Last Element
4 becomes
Рис.8. Вставка элемента в список с двойной связью: 1 - вставка нового первого элемента; 2 - новый элемент; 3 - указатель с нулевым значением; 4 - левый список преобразуется в правый; 5 - информационные поля; 6 - вставка нового среднего элемента; 7 - вставка нового последнего элемента.
  name :  string[30];
  street: string[40];
  city:   string[20];
  state:  string[2];
  zip:    string[9];
  next:   AddrPointer; { указатель на следующую запись  }
  prior:  AddrPointer; { указатель на предыдущую запись }
  end;
  DataItem = address;
  DataArray = array [1..100] of AddrPointer;
Ниже приводится функция, которая позволяет строить список с двойной связью для записей адресов:
{добавление элементов в список с двойной связью }
procedure DL_Store(i: AddrPointer);
begin
  if last=nil then { первый элемент списка }
  begin
    last:=i;
    start:=i;
    i^.next:=nil;
    i^.prior:=nil;
  end
  else
  begin
    last^.next:=i;
    i^.next:=nil;
    i^.prior:=last;
    last:=i;
  end;
end; { конец функции добавления в список с двойной связью }
Эта функция помещает каждый новый элемент в конец списка. Следует иметь в виду, что перед первым обращением к функции переменные "start" и "last" должны устанавливаться в нулевое значение.
В ходе построения списка с двойной связью каждый новый элемент может /как и для списка с одной связью/ устанавливаться не в конец, а в соответствующее место, обеспечивая упорядочность элементов в списке. Ниже приводится функция, которая создает список с двойной связью, упорядоченый по возрастанию фамилий из записей адресов:
{упорядоченная установка элементов в список с двойной связью}
function DSL_Store(info, start: AddrPointer;
var last: AddrPointer): AddrPointer;
{ вставка элементов в соответствующее место с сохранением  порядка }
var
  old, top: AddrPointer;
  done: boolean;
begin
  top := start;
  old := nil;
  done := FALSE;

  if start = nil then begin { первый элемент списка }
    info^.next := nil;
    last := info;
    info^.prior :=nil;
    DCL_Store := info;
  end else
  begin
    while (start<>nil) and (not done) do
    begin
      if start^.name < info^.name then
      begin
        old := start;
        start := start^.next;
      end else
      begin { вставка в середину }
      if old <>nil then
      begin
        old^.next := info;
        info^.next := start;
        start^.prior := info;
        info^.prior := old;
        DSL_Store := top; { сохранение начала }
        done := TRUE;
      end else
      begin
        info^.next := start;{новый первый элемент }
        info^.prior := nil;
        DSL_Store := info;
        done := TRUE;
      end;
    end;
  end;  { конец цикла }
  if not done then begin
    last^.next := info;
    info^.next := nil;
    info^.prior := last;
    last := info;
    DSL_Store := top; { сохранение начала }
  end;
end;
end;  { конец функции DSL_Store }
Поскольку элемент может помещаться в самое начало списка, эта функция должна выдавать указатель на начало списка, чтобы в других частях программы учесть изменения начала списка. При поиске конкретного элемента списка, как и для списка с одиночной связью, делается последовательный проход по цепочке связей пока не будет найден требуемый элемент.
При удалении элемента из списка возникает одна из трех ситуаций: удаление первого элемента, удаление среднего элемента и удаление последнего элемента. Рис.9 иллюстрирует изменение связей для этих случаев.

1 Deleting the First Item
3 becomes
6 Deleting a Middle Item
3 becomes
7 Deleting the Last Item
3 becomes
Рис.9. Удаление элемента из списка с двойной связью: 1 - удаление первого элемента; 2 - информационные поля; 3 - левый список преобразуется в правый; 4 - удаленный элемент; 5 - указа- тель с нулевым значением; 6 - удаление среднего элемента; 7 - удаление последнего элемента.
Ниже приводится функция, которая выполняет удаление элемента типа "address" из списка с двойной связью:
{ удаление элемента из списка с двойной связью }
function DL_Delete(start: AddrPointer;
                  key: str80): AddrPointer;
var
  temp, temp2: AddrPointer;
  done: boolean;
begin
  if start^.name=key then begin { первый элемент списка}
    DL_Delete:=start^.next;
    if temp^.next <> nil then
    begin
      temp := start^.next;
      temp^.prior := nil;
    end;
    dispose(start);
  end else
  begin
    done := FALSE;
    temp := start^.next;
    temp2 := start;
    while (temp<>nil) and (not done) do
    begin
      if temp^.name=key then
      begin
        temp^.next:=temp^.next;


      if temp^.next<>nil then
        temp^.next^.prior:=temp2;
      done:=TRUE;
      dispose(temp);
    end else
    begin
      temp2:=temp;
      temp:=temp^.next;
    end;
  end;
  DL_Delete:=start; { начало не изменяется }
  if not done then WriteLn('not found');
 end;
end; { конец функции удаления элемента  из списка с двойной связью }
Этой функции передается на один указатель меньше, чем для соответствующей функции при использовании списка с одной связью. /Удаленный элемент уже имеет указатель на предыдущий элемент и указатель на следующий элемент/. Поскольку первый элемент в списке может измениться, функция возвращает указатель на начало списка.

Список адресов почтовых корреспонденций, построенный в виде списка с двумя связями

Ниже приведена простая программа для списка почтовых корреспонденций, построенного в виде списка с двойной связью. Здесь весь список содержится в оперативной памяти. Однако, программа может быть изменена для хранения списка на диске.
{простая  программа для списка адресов почтовых корреспонденций, 
 иллюстрирующая применение списков с двойной связью}
program mailing_list;

type
  str80 = string[80];
  AddrPointer = ^address;
  address = record
    name: string[30];
    street: string[40];
    city: string[20];
    state: string[2];
    zip: string[9];
    next: AddrPointer;  { указатель  на следующую запись }
    prior: AddrPointer; { указатель на предыдущую запись }
  end;

  DataItem = address;
  filtype = file of address;

var
  t, t2: integer;
  mlist: FilType;
  start, last: AddrPointer;
  done: boolean;

{ вызов меню }
function MenuSelect: char;
var
  ch: char;
    begin
      Writeln('1. Enter names');
      Writeln('2. Delete a name');
      Writeln('3. Display the list');
      Writeln('4. Search for a name');
      Writeln('5. Save the list');
      Writeln('6. Load the list');
      Writeln('7. Quit');
      repeat
        Writeln;
        Write('Enter your choice: ');
        Readln(ch);
        ch := UpCase(ch);
      until (ch>='1') and (ch<='7')
      MenuSelect := ch;
      end;{ конец выбора по меню }

{ упорядоченная установка элементов в список с двойной связью }
function DSL_Store(info, start: AddrPointer;
var last: AddrPointer): AddrPointer;
{ вставка элементов в соответствующее место с сохранением  порядка }
var
  old, top: AddrPointer;
  done: boolean;
begin
  top := start;
  old := nil;
  done := FALSE;

  if start = nil then begin { первый элемент списка }
    info^.next := nil;
    last := info;
    info^.prior :=nil;
    DSL_Store := info;
  end else
  begin
    while (start<>nil) and (not done) do
    begin
      if start^.name < info^.name then
      begin
        old := start;
        start := start^.next;
      end else
      begin { вставка в середину }
        if old <>nil then
        begin
          old^.next := info;
          info^.next := start;
          start^.prior := info;
          info^.prior := old;
          DSL_Store := top; { сохранение начала }
          done := TRUE;
        end else
        begin
          info^.next := start;{новый первый элемент }
          info^.prior := nil;
          DSL_Store := info;
          done := TRUE;
        end;
      end;
    end;  { конец цикла }
    if not done then begin
      last^.next := info;
      info^.next := nil;
      info^.prior := last;
      last := info;
      DSL_Store := top; { сохранение начала }
    end;
  end;
end;  { конец функции DSL_Store }

{ удалить элемент из списка с двойной связью }
function DL_Delete(start: AddrPointer
                            key: str[80]): AddrPointer
var
  temp, temp2: AddrPointer
  done: boolean;
begin
  if star^.name = key then begin { первый элемент  списка }
    DL_Delete := start^.next;
    if temp^.next <> nil then
    begin
      temp := start^.next;
      temp^.prior := nil;
    end;
    dispose(start);
  end else
  begin
    done := FALSE;
    temp := start^.next;
    temp2 := start;
    while (temp <> nil) and (not done) do
    begin
      if temp^.next <> nil then
      temp^.next^.prior := temp2
      done := TRUE
      dispose(temp);
    end else
    begin
      temp2 := temp;
      temp := temp^.next;
    end;
  end;
  DL_Delete := start; { начало не изменяется }
  if not done then Writeln('not found');
end;
end; { конец функции DL_Delete }

{ удаление адреса из списка }
procedure remove;
var
  name:str80;
begin
  Writeln('Enter name to delete: ');
  Readln(name);
  start := DL_Delete(start,name);
end;  { конец процедуры удаления адреса из списка }

procedure Enter;
var
  info: AddrPointer;
  done: boolean;
begin
  done := FALSE;
  repeat
    new(info)  { получить новую запись }
    Write('Enter name: ');
    Readln(info^.name);
    if Length(info^.name)=0 then done := TRUE
    else
    begin
      Write(Enter street: ');
      Readln(info.street);
      Write(Enter city: ');
      Readln(info.city);
      Write(Enter state: ');
      Readln(info.state);
      Write(Enter zip: ');
      Readln(info.zip);
      start := DSL_Store(info, start, last); { вставить  запись }
    end;
  until done;
end;  { конец ввода }

{ вывести список }
procedure Display(start:AddrPointer);
begin
  while start <> nil do begin
    Writeln(start^.name);
    Writeln(start^.street);
    Writeln(start^.city);
    Writeln(start^.state);
    Writeln(start^.zip);
    start := start^.next
    Writeln;
  end;
end;

{ найти элемент с адресом }
function Search(start: AddrPointer; name: str80):
                    AddrPointer;
var
  done: boolean;
begin
  done := FALSE
  while (start <> nil) and (not done) do begin
    if name = start^.name then begin
      search := start;
      done := TRUE;
    end else
    start := star^.next;
  end;
  if start = nil then search := nil; { нет в списке }
  end; { конец поиска }

{ найти адрес по фамилии }
procedure Find;
var
  loc: Addrpointer;
  name: str80;
begin
  Write('Enter name to find: ');
  Readln(name);
  loc := Search(start, name);
  if loc <> nil then
  begin
    Writeln(loc^.name);
    Writeln(loc^.street);
    Writeln(loc^.city);

    Writeln(loc^.state);
    Writeln(loc^.zip);
  end;
  else Writeln('not in list')
  Writeln;
end; { Find }

{ записать список на диск }
procedure Save(var f:FilType; start: AddrPointer):
begin
  Writeln('saving file');
  Rewrite(f);
  while start <> nil do begin
    write(f,start);
    start := start^.next;
  end;
end;
{ загрузить список с файла }
procedure Load(var f:FilType; start: AddrPointer):
                     AddrPointer;
var
  temp, temp2: AddrPointer
  first: boolean;
begin
  Writeln('load file');
  Reset(f);
  while start <> nil do begin  { освобождение памяти  при необходимости }
    temp := start^.next
    dispose(start);
    start := temp;
  end;

  start := nil; last := nil;
  if not eof(f) then begin
    New(temp);
    Read(i, temp^);
    temp^.next := nil;  temp^.prior:= nil;
    load := temp;  { указатель на начало списка }
  end;

  while not eof(f) do begin
    New(temp2);
    Read(i, temp2^);
    temp^.next := temp2; { построить список }
    temp2^.next := nil;
    temp^.prior := temp2;
    temp := temp2;
  end;
  last := temp2;
end; { конец загрузки }

begin
  start := nil; { сначала список пустой }
  last := nil;
  done := FALSE;

  Assign(mlist, 'mlistd.dat');
  repeat
    case MenuSelect of
      '1': Enter;
      '2': Remove;
      '3': Display(start);
      '4': Find;
      '5': Save(mlist, start);
      '6': start := Load(mlist, start);
      '7': done := TRUE;
    end;
  until done=TRUE;
end. { конец программы }

ДВОИЧНЫЕ ДЕРЕВЬЯ

В этом разделе рассматривается четвертая структура данных, которая называется двоичным деревом. Имеется много типов деревьев. Однако, двоичные деревья занимают особое положение. Если такие деревья упорядочить, то операции поиска, вставки и удаления будут выполняться очень быстро. Каждый элемент двоичного дерева имеет информационные поля, связь с левым элементом и связь с правым элементом. На рис.10 показано небольшое дерево.
При описании деревьев используется специальная терминология. Первый элемент дерева называется его корнем. Каждый элемент называют вершиной /или листом/ дерева, а часть дерева носит название поддерева. Вершина, которая не имеет поддеревьев, называется терминальной вершиной. Высота дерева равна числу уровней вершин в дереве. В дальнейшем при рассмотрении деревьев можно считать, что в памяти они располагаются так же, как на бумаге. Однако следует помнить, что деревья представляют собой лишь способ представления данных в памяти, а память в действительности имеет линейную форму.

Root Node 1
3 4
Left Subtree Right Subtree
6
Terminal Nodes
Рис.10. Пример двоичного дерева: 1 - корневая вершина; 2 - информационные поля; 3 - левое поддерево; 5 - указатель связи с нулевым значением; 6 - терминальные вершины.
Двоичное дерево представляет собой особую форму связанного списка. Доступ к элементам, их вставка и удаление могут выполняться в любом порядке. Кроме того, операция поиска не носит разрушительный характер. Хотя деревья легко представляются образно, для программирования они представляют достаточно непростую задачу.
Большинство функций над деревьями носят рекурсивный характер, поскольку дерево само по себе является рекурсивной структурой данных. /Т.е. каждое поддерево само является деревом/. Поэтому представленные в этом разделе программы являются, как правило, рекурсивными. Имеются нерекурсивные версии этих функций, однако разобраться в них значительно труднее.
Упорядоченность дерева зависит от порядка доступа к дереву. Процесс доступа к каждой вершине дерева называется обходом дерева.
Имеется три способа обхода дерева: во внутреннем порядке, в прямом порядке и в обратном порядке. При прохождении дерева во внутреннем порядке сначала посещается левое поддерево, затем корень и затем посещается правое дерево. При прохождении дерева в прямом порядке сначала посещается корень, затем левое поддерево и затем правое поддерево. При прохождении дерева в обратном порядке сначала посещается левое поддерево, затем правое поддерево и затем корень.
Порядок прохождения ds, выбранного в качестве примера дерева будет следующим:
при прохождении во внутреннем порядке:     a b c d e f g;
при прохождении в прямом порядке:          d b a c f e g;
при прохождении в обратном порядке:        a c b e g f d.  
 
Хотя дерево не обязательно должно быть упорядочено, в большинстве случаев оно должно быть таким. Упорядоченность дерева зависит от того, как вы будете проходить дерево. В приводимых ниже примерах используется внутренний порядок прохода по дереву. В отсортированном двоичном дереве левое поддерево содержит вершины, которые меньше или равны корню, а вершины правого поддерева больше или равны корню. Ниже приводится функция, которая выполняет построение отсортированного двоичного дерева:
type
  TreePointer = ^tree;
  tree = record
    data: char;
    left: TreePointer;
    right:TreePointer;
  end;

  { добавить элемент в двоичное дерево }
  function Stree(root,r:TreePointer;data:char);TreePointer;
  begin
    if r=nil then
    begin
      new(r); { получить новую вершину }
      r^.left:=nil;
      r^right:=nil;
      r^.data:=data;
      if data<root^.data then root^.left:=r
      else root^.right:=r;
      STree:=r;
    end else
    begin
      if datar^.data then STree:=STree(r, r^.left, data)
      else STree:=STree(r, r^.right, data);
    end;
  end; { конец функции добавления элемента в двоичное  дерево }
В этом алгоритме выполняется просто прохождение по связям дерева, двигаясь вправо или влево в зависимости от поля данных. При применении этой функции необходимо предусмотреть глобальную переменную для корня дерева. Вначале эта глобальная переменная должна быть установлена в нулевое значение. Указатель на корень будет установлен при первом обращении к указанной функции. Поскольку при последующих обращениях к этой функции нет необходимости делать новую установку корня, то используется фиктивная переменная. Если глобальной переменной будет "rt", то обращение к указанной функции может иметь следующий вид:
{call STree}
if rt=nil rt:=STree(rt, rt, info)
else dummy := STree(rt, rt, info);
При таком обращении к функции вставка и первого и последующих элементов будет выполняться корректно.
Указанная функция является рекурсивной, как и большинство других процедур с деревьями. Если этот алгоритм преобразовать, используя прямой метод перехода рекурсивных алгоритмов в циклиескую форму, то программа будет в несколько раз длинее. При обращении к функции задается указатель на корень и указатель на поддерево, а также помещаемые в дерево данные. Здесь в качкестве вставляемых в дерево данных используется символьное данное. Однако, в качестве такого данного можно использовать данное любого типа.
Для обхода дерева с использованием указанной функции и выдачи на печать поля данных каждой вершины можно использовать следующую функцию:
procedure InOrder(root:TreePointer);
begin
  if root>nil then
  begin
    InOrder(root^.left);
    Write(root^.data);
     InOrder(root^.right);
   end;
 end.
Эта функция делает обход дерева во внутреннем порядке и завершается при обнаружении терминального листа /указателя о нулевом завершении/. Ниже показаны функции для прохождения дерева в прямом и обратном порядке:
procedure PreOrder(root:TreePointer);
begin
  if root<>nil then
  begin
    write(root^.data);
    preorder(root^.left);
    preorder(root^.right);
  end;
 end.

procedure PostOrder(root:TreePointer);
begin
  if root<>nil then
  begin
    postorder(root^.left);
    postorder(root^.right);
    Write(root^.data);
  end;
end.
Вы можете составить короткую программу, которая строит упорядоченное двоичное дерево и, кроме того, печатает его на экране вашего компьютера. Для этого требуется выполнить лишь незначительные изменения в процедуре прохода дерева во внутреннем порядке. Ниже приводится программа, которая выдает вершины дерева во внутреннем порядке:
{ вывод на экран вершин дерева /слева направо/ }
programm DisplayTree;

uses Crt;

type
  TreePointer = ^tree
  tree = record
  data: char;
  left: TreePointer;
  right: TreePointer;
end;
var
  root, dummy: TreePointer;
  ch:char;

function STree(root, r:TreePointer; data: char):
                  TreePointer;
begin
  if r = nil then
  begin
    new(r); { получить новую вершину }
    r^.left := nil;
    r^.right := nil;
    r^.data := data;
    if data < root^.data then root^.left := r
    else root^.right := r;
    STree := r;
  end else
  begin
    if data<r^.data then STree := STree(r, r^.left, data)
    else STree := STree(r, r^.right, data)
  end;
end; { конец процедуры STree }

procedure PrintTree(r: TreePointer; n: integer);
var
  i:integer;
begin
  if r>nil then begin
    PrintTree(r.^left, n+1);
    for i := 1 to n do Write('   ');
   Writeln(r^.data);
    PrintTree(r^.right, n+1);
  end;
end; { конец процедуры PrintTree }

begin
  root := nil;
  repeat
    Write('enter a letter (Q to quit): ');
    ch := ReadKey; Writeln(ch);
    if root= nil then root := STree(root, root, ch)
    else dummy := STree(root, root, ch);
    ch := UpCase(ch);
  until ch ='Q';
  PrintTree(root, 0);
end;
В этой программе фактически делается сортировка полученной информации. В данном случае используется вариант сортировки вставкой. Для среднего случая сортировка вставкой имеет достаточно хорошие характеристики, однако быстрая сортировка все же является лучшим методом сортировки, так как она требует меньше оперативной памяти и выполняется быстрее. Однако, если дерево строится на основе использования других деревьев или если вам приходится поддерживать упорядоченное дерево, то новые элементы всегда будут вставляться с использованием функции STree.
Если вы воспользуетесь программой вывода на экран двоичного дерева, то возможно вы заметите, что некоторые деревья сбалансированы /т.е. все поддеревья имеют одинаковую или почти одинаковую высоту/, а другие сильно несбалансированы. Если вы введете дерево "abcd", то оно примет следующий вид:
a
 \
  \
   b
    \
     \
      c
       \
        \
         d
В этом случае левых поддеревьев не будет. Это дерево называется вырожденным, поскольку оно выродилось в линейный список. В общем случае, если используемые для построения дерева данные являются в достаточной мере случайными, дерево будет приближаться к сбалансированному. Однако, если информация уже упорядочена, то в результате будет получаться вырожденное дерево. /Имеется возможность переупорядочивать дерево, сохраняя при каждой вставке его балансировку. Однако такой алгоритм достаточно сложен и если он вас заинтересовал, то следует воспользоваться книгами по усовершенствованным методам составления алгоритмов программ/.
Функции поиска для двоичных деревьев составляются легко. Ниже приводится функция, результатом которой является указатель на вершину дерева, которая совпадает с ключом. В противном случае возвращается нулевое значение.
{ поиск элемента в дереве }
function Search(root:TreePointer;
              key:DataItem):TreePointer;

begin
  if root <> nil
  begin
    while (root^.data <> key) and (root <> nil) do
    begin
      if key < root^.data then root := root^.left
      else root := root^.right;
    end;
  end;
  Search := root;
end; { конец процедуры поиска элемента }
К сожалению, удаление вершины дерева выполняется не так просто, как поиск вершины. Удаленной вершиной может быть корень, левая вершина или правая вершина. Вершина может также иметь от нуля до двух поддеревьев. Необходимость изменения указателей приводит, например, к следующему рекурсивному алгоритму .
{ удаление элемента из дерева }
function DTree(root:TreePointer;key:char):TreePointer;
var
  temp,temp2:TreePointer;

begin
  if root^.data = key then
  begin
    if root^.left=root^.right tnen
    begin
      dispose(root)
      DTree := nil;
    end
    else  if root^.left=nil tnen
    begin
      temp := root^.right
      dispose(root)
      DTree := temp;
    end
    else  if root^.right=nil tnen
    begin
      temp := root^.left
      dispose(root)
      DTree := temp;
    end
    else
    begin  { имеются два листа }
      temp2 := root^.right
      temp := root^.right
      while temp^.left <> nil do temp := temp^.left;
      temp^.left := root^.left
      dispose(root);
      DTree := temp2
    end;
    else
    begin
      if root^.data < key
      then root^.right :=  DTree(root^.right, key)
      else root^.left :=  DTree(root^.left, key)
      DTree := root;
    end;
  end; { конец функции DTree }
Следует помнить, что в основной программе необходимо обновлять указатель на корень дерева, так как удаленная вершина может оказаться корнем дерева.
Использование двоичных деревьев позволяет создавать мощные, гибкие и эффективные программы по управлению баз данных. Информация в этом случае может находиться на диске и поэтому важное значение может иметь время доступа. Число сравнений при использовании сбалансированных двоичных деревьев для худшего случая равно log2(n). Поэтому в этом случае поиск выполняется значительно быстрее, чем поиск в связанном списке, который посуществу является последовательным поиском.
   Содержание                                                      <<Назад         Далее>>
    Учебник по языку Pascal          Лабораторные работы по программированию          Справочник

Реклама