Алгоритмы на абстрактных структурах данных

Программа 2. Ханойская башня.

На стержне $$A$$ в исходном порядке находится $$N$$ дисков, уменьшающихся по размеру снизу вверх. Диски должны быть переставлены на стержень в исходном порядке при использовании в случае необходимости промежуточного стержня $$B$$ для временного хранения дисков. В процессе перестановки дисков обязательно должны соблюдаться правила: одновременно может быть переставлен только один самый верхний диск ( с одного из стержней на другой); ни в какой момент времени диск не может находиться на другом диске меньшего размера.

Программа реализована с помощью абстрактного типа данных – стек для произвольного числа дисков.

{Программа написана на языке программирования Turbo-Pascal}

uses crt,graph;
type PEl=^El;
     El=record
      n:byte;
      next:PEl;
     end;

var ster:array[1..3] of PEl;
    number: byte;
    p:PEl;
    th,l: integer;
    i:integer;
    nhod:word;
    s:string;

procedure hod(n,f,t:integer);
begin
if n>1 then begin
 hod(n-1,f,6-(f+t));
 hod(1,f,t);
 hod(n-1,6-(f+t),t);
end else begin
 p:=ster[f];
 ster[f]:=ster[f]^.next;
 p^.next:=ster[t];
 ster[t]:=p;
 inc(nhod);
 str(nhod,s);
{**********************************************************}
 setfillstyle(1,0);bar(0,0,50,10);
 setcolor(2);outtextxy(0,0,s);
 setfillstyle(1,0);setcolor(0);p:=ster[f];i:=1;
 while p<>nil do begin p:=p^.next;inc(i);end;
 fillellipse(160*f,460-(i-1)*th,(number-ster[t]^.n+1)*l,10);
 setfillstyle(1,4);setcolor(4);p:=ster[t];i:=1;
 while p<>nil do begin fillellipse(160*t,460-(i-1)*th,(number-
ster[t]^.n+1)*l,10);inc(i);p:=p^.next;end;
{**********************************************************}
{ readkey;}{delay(50);}
end;
end;

procedure start;
 var i:integer;grD,grM: Integer;
begin
clrscr;write('Enter the number of rings, please.');readln(number);
for i:=1 to 3 do ster[i]:=nil;
for i:=1 to number do begin new(p);p^.n:=i;p^.next:=ster[1];ster[1]:=p;end;
nhod:=0;
grD:=Detect;{InitGraph(grD,grM,'');}InitGraph(grD,grM,'c:\borland\tp\bgi');
th:=20;l:=round(50/number);
setfillstyle(1,4);setcolor(4);
for i:=1 to number do begin fillellipse(160,460-(i-1)*th,(number-
i+1)*l,10);end;
end;

begin
start;
{readkey;}
hod(number,1,3);
{closegraph;}
end.

Очереди

Очередь - одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения (head) и конца (tail) очереди в соответствии с правилом FIFO ("first-in, first-out" - "первым введен, первым выведен").

Head:=1; tail:=1;

Queue[tail]:=x; tail:=tail+1;
If tail>qd then tail:=1;
Здесь qd - размерность очереди.

x:=queue[head]; head:=head+1;
if head>qd then head:=1;

Temp:=tail+1;
If temp>qd then temp:=1;
If temp=head then \{переполнение\}
Else btgin queue[tail]:=x; tail:=temp end;

If head:=tail then
\{очередь пуста\}
else begin
x:=queue[head]; head:=head+1;
if yead>qd then head:=1;
end;

Отметим, что при извлечении элемента из очереди все элементы могут также перемещаться на один шаг к ее началу.

Связанные списки

Связанный список представляет собой структуру данных, которая состоит из узлов (как правило, записей), содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель (звено связи).

Приведем основные базисные операции для работы с однонаправленным связанным списком.

Link[q]:=link[p];
Link[p]:=q;

Здесь q – индекс элемента, который должен быть вставлен в список после элемента с индексом p.

If link[x]<>null then
Link[x]:=[link[x]]
else
\{Элемент x не имеет преемника\};

Отметим, что элемент, следующий в списке за элементом x, называется преемником элемента x, а элемент, pасположенный перед элементом x, называется предшественником элемента x. Если элемент x не имеет преемника, то содержащемуся в нем указателю присваивается значение nil.

Prev:=0;
While(link[prev]<>nil)and(link[prev]<>x)do
Prev:=link[prev];
If link[prev]=x then
Btgin link[prev]:=y; link[y]:=x end
Else
\{Элемент x не найден\};
Здесь link[0]является началом списка.

Отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка.

В двунаправленном связанным списке каждый элемент имеет два указателя (succlink - описывает связь элемента с преемником, predlink - с предшественником).

Приведем основные базисные операции для работы с двунаправленным связанным списком.

Ответ 1 Включение y перед элементом x:

Succlink[y]:=x;
Predlink[y]:=predlink[x];
Succlink[predlink[x]]:=y;
Predlink[x]:=y;

Ответ 2 Включение элемента y после элемента x:

Succlink[y]:=succlink[x];
Predlink[y]:=x;
Predlink[succlink[x]]:=y;
Succlink[x]:=y;

Ответ 3 Исключение элемента x.

Predlink[succlink[x]]:=predlink[x];
Succlink[predlink[x]]:=succlink[x];

Программа 3.Список целых чисел.

{Создается список целых чисел. Числа выбираются  случайным образом 
из интервала 0..9999, затем он упорядочивается,
сначала - по возрастанию, затем - по убыванию.
Программа написана на языке программирования Turbo-Pascal}

uses crt;
type TLink=^Link;
     Link=record
      v : integer;
      p, n : TLink
     end;

var i : integer;
    p, q, w : TLink;
    s1,s2,rs : TLink;

procedure Sort( sp : TLink; t : integer );
 var temp : integer;
begin
q:=sp;
while q^.n<>nil do begin
 q:=q^.n;
 p:=sp;
 while p^.n<>nil do begin
  if (p^.v-p^.n^.v)*t>0 then begin
    temp:=p^.v;
    p^.v:=p^.n^.v;
    p^.n^.v:=temp;
  end;
  p:=p^.n;
 end;
end;
end;

function CreatRndSpis(deep : integer):TLink;
begin
new(q);
for i:=1 to deep do begin
 if i=1 then begin
  p:=q;q^.p:=nil;
 end;
 q^.v:=random(9999);
 new(q^.n);
 q^.n^.p:=q;
 q:=q^.n;
end;
q^.p^.n:=nil;
dispose(q);
CreatRndSpis:=p;
end;

function CreatSortDawnSpis(deep : integer):TLink;
begin
if deep<9999 then begin
 new(q);
 for i:=1 to deep do begin
  if i=1 then begin
   q^.p:=nil;p:=q;
  end;
  q^.v:=random(round(9999/deep))+round(9999*(1-i/deep));
  new(q^.n);
  q^.n^.p:=q;
  q:=q^.n;
 end;
 q^.p^.n:=nil;
 dispose(q);
end else p:=nil;
CreatSortDawnSpis:=p;
end;

procedure Show( s : TLink; sp: integer );
 var i : integer;
begin
 p:=s;
 i:=1;
 while p<>nil do begin
  gotoxy(sp,i);write(' ' : 5); gotoxy(sp,i);writeln(p^.v);
  p:=p^.n;
  inc(i);
 end;
end;

function min( c1, c2 : integer) : integer;
begin
case c1<c2 of
 true : min:=c1;
 false: min:=c2;
end;
end;

function CreatConcSortUpSpis( sp1, sp2 : TLink ) : TLink;
begin
 q:=sp1;while q^.n<>nil do q:=q^.n;
 w:=sp2;while w^.n<>nil do w:=w^.n;
 new(p);

CreatConcSortUpSpis:=p;
 p^.p:=nil;
 while(w<>nil)and(q<>nil)do begin
  if(w<>nil)and(q<>nil)then begin
   p^.v:=min(q^.v,w^.v);
   case p^.v=q^.v of
    true : q:=q^.p;
    false: w:=w^.p;
   end;
   new(p^.n);
   p^.n^.p:=p;
   p^.n^.n:=nil;
   p:=p^.n;
  end;
  if(w=nil)and(q<>nil)then begin
   while q<>nil do begin
    p^.v:=q^.v;q:=q^.p;
    new(p^.n);
    p^.n^.p:=p;
    p^.n^.n:=nil;
    p:=p^.n;
   end;
  end;
  if(w<>nil)and(q=nil)then begin
   while w<>nil do begin
    p^.v:=w^.v;w:=w^.p;
    new(p^.n);
    p^.n^.p:=p;
    p^.n^.n:=nil;
    p:=p^.n;
    end;
  end;
 end;
 p^.p^.n:=nil;
 dispose(p);
end;

begin
clrscr;
randomize;
s1:=CreatRndSpis(15);Sort(s1,-1);
s2:=CreatRndSpis( 5);Sort(s2,-1);
rs:=CreatConcSortUpSpis(s1,s2);
Show(s1,10);
Show(s2,20);
Show(rs,30);
Sort(rs,-1);
Show(rs,40);
readln;
end.

Двоичные деревья

Основные определения и понятия о графах даются в лекции 12. В лекции 16 и 17 рассматриваются комбинаторные алгоритмы на графах. В данной лекции приведены несколько понятий, необходимых для описания абстрактной структуры данных, - двоичное дерево.

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

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

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

Граф задается аналогично спискам через записи и указатели.

Программа 4. Создание и работа с деревом.

//Алгоритм реализован на языке Turbo-C++.
//Вершины дерева задаются структурой: поле целых,
//поле для размещения адреса левого "сына" и поле для размещения
//адреса правого "сына"
//Значение целого выбирается случайным образом из интервала 0..99.
//Число уровней дерева равно N. В примере N = 5.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#define N 5
struct tree{int a;
        tree* left;
        tree* right;};

void postr(tree* root,int h)
{
 root->a=random(100);
 if (h!=0){
 if (random(3)){
  root->left=new(tree);
  postr(root->left,h-1);}
 else root->left=NULL;
 if (random(3))
  {root->right=new(tree);postr(root->right,h-1);}
 else root->right=NULL;}
else {root->right=NULL;root->left=NULL;}
}

void DFS(tree* root)
{printf("%d ",root->a);
 if (root->left!=NULL)  DFS(root->left);
 if (root->right!=NULL) DFS(root->right);}

void main()
{clrscr();
 randomize();
 tree* root1;
 root1=new(tree);
 postr(root1,N);
 DFS(root1);
 getch();
}