SHPORA.net :: PDA

[ Back ]

СТРУКТУРЫ ДАННЫХ .



Под структурами данных (далее с/д) понимают элементы данных и связи между

ними.Каждая с/д характеризуется типовым набором операций с элементом :

- поиска (доступа)

- записи (включения)

- выборки (удаления)

Элементы могут быть либо простые ,либо составные.

Из изученных нами с/д являются :



1) одиночное значение (переменная) ;

2) вектор (одномерный массив) ;

3) матрица (двумерный массив) ;

4) линейные списки ;

5) деревья ;

6) графы .

Список в памяти компьютера может быть представлен одним из двух способов :

1) последовательное представление ;

2) связанное представление .



1 Последовательное представление

В этом случае соседние элементы списка физически следуют друг за другом,

распологаясь в соседних элементах массива.



е(i-1) e(i) e(i+1)

──┬─────────────┬─────────────┬──────────────┬────

│ U(i-1) │ U(i) │ U(i+1) │

──┴─────────────┴─────────────┴──────────────┴────



2 Связанное представление

Каждый элемент содержит ссылочную часть на соседний элемент.



е(i-1) e(i) e(i+1)

┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐

──── │ U │ Y │ ──── │ U │ Y │ ──── │ U │ Y │ ────

│(i-1)│(i-1)│ │ (i) │ (i) │ │(i+1)│(i+1)│

└─────┴─────┘ └─────┴─────┘ └─────┴─────┘



Простейшие разновидности списков :

1) Стек (Stack);

2) Очередь (Queue);

3) Дек (Double Extended Queue - DEQ).









СТЕК .



Стек - это список ,в котором включение и выключение элементов произво-

дится только с одного конца ,называемого вершиной стека (физический пример -

стопка книг).Стек также называют LIFO-списком ,от англ. -

Last In First Out



Для стека существуют две операции :

PUSH - поместить в стек ;

POP - взять из стека .

Стек широко используется в программировании , в частности - в вызове п/п .



* П. работы со стеком:



┌───┬───┬───┬───┬───┬───┐

Stack │ │ │ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Top Maxpos=6



PUSH (10)



┌───┬───┬───┬───┬───┬───┐

Stack │ 10│ │ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Top Maxpos=6



PUSH (20)



┌───┬───┬───┬───┬───┬───┐

Stack │ 10│ 20│ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Top Maxpos=6



POP (k) k=20



┌───┬───┬───┬───┬───┬───┐

Stack │ 10│ │ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Top Maxpos=6





При работе со стеком возможны две ошибочные ситуации :

1) переполнение ;



┌───┬───┬───┬───┬───┬───┐

Stack │ 10│ 20│ 30│ 40│ 50│ 60│

└───┴───┴───┴───┴───┴───┘



Top

2) недостаток стека



┌───┬───┬───┬───┬───┬───┐

Stack │ │ │ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Top Maxpos=6

РОР (к) ;



* П.:



Program List1;



Const

MaxPos = 4;



Var

Stack:array[1..MaxPos] of byte;

top:byte;

k:byte;



Procedure Initstack;

begin

top:=1;

end;



Procedure Push (el:byte);

begin

if top>MaxPos

then writeln(#7,'Error')

else begin

Stack[top]:=el;

inc(top);

end;

end;



Procedure Pop (var el:byte);

begin

if top = 1

then writeln(#7,'Error')

else begin

dec(top);

el:=Stack[top];

end;

end;



Procedure Printstack;

var

i:integer;

begin

for i:=top-1 downto 1 do

write(Stack[i],' ');

writeln;

end;



Begin

Initstack;

Push(10);

Push(20);

Push(30);

Push(40);

Push(50);

Pop(k);

k:=40;

Push(60);

Pop(k);

k:=60;

Printstack; { 30 20 10 }

End.









ОЧЕРЕДЬ .



Очередь - структура данных ,в кот. элементы добавляются с одного края ,

а удаляются с другого .

Край , в кот. выполняется включение - конец очереди (Tail) .

Край , с кот. выполняется извлечеие - голова (Head) .

Другое название очереди - FIFO , от англ. -

First In First Out .



* П. работы с очередью :



1) Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ │ │ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Head Maxpos=6



Insert(10);



Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ 10│ │ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Head Maxpos=6



Insert(20);



Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ 10│ 20│ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Head Maxpos=6



Extract(k); k = 10



Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ │ 20│ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Head Maxpos=6

Extract(k); k = 20



Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ │ │ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Head Maxpos=6





2)

Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ │ │ │ │ │ │

└───┴───┴───┴───┴───┴───┘



Head

Insert(100)



Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ │ │ │ │ │100│

└───┴───┴───┴───┴───┴───┘



Head



Когда Tail достигнет позиции MaxPos ,впереди элементы иссякнут . В этом

случае Tail необходимо переместиьть на первую позицию .



1 Условия переполнения списка



1) Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ │ │ │ │ │ │ Head = 1

└───┴───┴───┴───┴───┴───┘ Tail = MaxPos



Head Maxpos=6



2) Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ │ │ │ │ │ │

└───┴───┴───┴───┴───┴───┘ Head-1 = Tail



Head Maxpos=6





2 Условие пустоты массива



Tail

¬

┌───┬───┬───┬───┬───┬───┐

Queue │ │ │ │ │ │ │ Head = Tail

└───┴───┴───┴───┴───┴───┘



Head Maxpos=6



Список также широко используется в программировании .



* П.:

Клавиатура



Program List2;



Const

MaxPos = 4;



Var

Queue:array [1..MaxPos] of word;

Head,Tail:byte;



Procedure InitQueue;

begin

Head:=1;

Tail:=1;

end;



Procedure Insert(var el:word);

begin

if ((Head = 1) and (Tail = MaxPos))

or (Tail+1 = Head)

then writeln(#7,' Error ')

else begin

Queue[Tail]:=el;

inc(Tail);

if Tail>MaxPos

then Head:=1;

end;

end;



Procedure Extract(var k:word);

begin

if Head = Tail

then writeln(#7,' Error ')

else begin

k:=Queue[Head];

inc(Head);

if Head>MaxPos

then Head:=1;

end;

end;



Procedure PrintQueue(var i:byte);

begin

if Tail>Head

then

for i:=Head to Tail-1 do

write(Queue[i])

else

if Tail<Head

then begin

for i:=Head to MaxPos do

write(Queue[i]);

for i:=1 to Tail do

write(Queue[i]);

end;

end;



Begin

InitQueue;

Insert(10);

Insert(20);

Insert(30);

Extract(k);

k:=30;

PrintQueue;

End.





Двусторонняя очередь .



Двусторонняя очередь - очередь ,в кот. вставлять и извлекать элементы

из кот. можно из любого конца .

Набор типовых операций с двусторонней очередьювключает в себя :

1) вставка элемента в голову , в хвост ;

2) извлечение элемента из головы , из хвоста .













СВЯЗАННОЕ ПРЕДСТАВЛЕНИЕ СПИСКОВ .



* П.:

Для последующих примеров



type type

TPTR = ^Tel ; PItem = ^Item ;

Tel = record Item = record

Inf:integer; el:byte;

Next:TPTR; Next:PItem

end; end;



По количеству указателей списки разделяют на односвязные и двусвязные .



* П.:

Реализация связанного стека



Var

top:PItem;



Procedure Initstack;

begin

top:=nil;

end;



Procedure Push(var el:byte);

var

p:Item;

begin

New(p);

p^.el:=el;

p^.next:=top;

top:=p^;

end;



Procedure Pop(var el:byte);

var

p:PItem;

begin

if top=nil

then writeln(#7,' Error ')

else begin

el:=top^.el;

p:=top;

top:=p^.next;

dispose(p);

end;

end;



Procedure Printstack;

var

p:PItem;

begin

p:=top;

while p<>nil do

begin

write(p^.el,' ');

p:=p^.next;

end;

writeln;

end;



Begin

Initstack;

Push(10);

Push(20);

Push(30);

Push(40);

Push(50);

Pop(k);

k:=40;

Push(60);

Pop(k);

k:=60;

Printstack; { 30 20 10 }

End.





Разработаем набор процедур ,обеспечиваюших работу с универсальным спис-

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

следующие операции :

1) Вставка в начало ;

в конец ;

в произвольное место ;

2) Извлечение из начала ;

из конца ;

из любого места ;

3) Чтение значения элемента

из начала ;

из конца ;

из любого места ;

4) Изменение значения любого элемента ;

5) Инициализация списка ;

Очистка списка ;

Печать списка .



* П.:



Type

PItem = ^Item;

Item = record

el:byte;

next:PItem;

end;



Var

Head,

Tail:PItem;



Инициализация списка.



Procedure InitList;

begin

Head:=nil;

Tail:=nil;

end;



Очистка списка.



Procedure ClearList;

var

p:PItem;

begin

while Head<>nil do

begin

p:=Head;

Head:=Head^.next;

dispose(p);

end;

Tail:=nil;

end;



Вставка в голову.



Procedure InsertToHead(el:byte);

var

p:PItem;

begin

New(p);

p^.el:=el;

p^.next:=Head;

Head:=p;

if Tail=nil

thenTail:=p;

end;



Вставка в хвост.



Procedure InsertInTail(el:byte);

var

p:PItem;

begin

New(p);

p^.el:=el;

p^.next:=nil;

if Tail=nil

then HEad:=p;

else Tail^.next:=p;

Tail:=p;

end;



Извлечение из головы.



Procedure ExtractFromHead(var el:byte);

var

p:PItem;

begin

if Head<>nil

then begin

el:=Head^.el;

p:=Head;

Head:=Head^.next;

dispose(p);

if Head=nil

then Tail:=nil;

end

else writeln(p^.el,' ');

end;



Извлечение из конца списка.



Procedure ExtractFromTail(var el:byte);

var

p:PItem;

begin

if Tail<>nil {если список не пустой}

then begin

el:=Tail^.el;

if Tail=Head

then begin

dispose(Tail);

Head:=nil;

Tail:=nil;

end

else begin

p:=Head;

whilep^.next<>Tail do

begin

p:=p^.next;

p^.next:=nil;

dispose(Tail);

Tail:=p;

end;

end

else writeln(p^.el,' ');

end;





Вставка элемента в произвольное место списка.



Procedure InsertEl(el:byte;i:word);

{i-перед каким элементом вставлять}

var

n:word; {индекс элемента списка}

p:PItem; {вставляемый элемент}

pnext,pprev:PItem; {следующий и предыдущий элементы}

begin

pnext:=Head;

pprev:=nil;

n:=1;

{ищем местоположение вставл. эл.}

while pnext<>nil do

begin

if i=n

then break;

pprev:=pnext;

pnext:=pnext^.next;

inc(n);

end;

New(p);

p^.el:=el;

p^.next:=pnext;

end;







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



┌────┬────┐ ┌────┬────┐

│ │ │ │ │ │

┌── │ │ │ ──────────── │ │ │ ───┐

│ │ │ │ │ │ │ │

│ └────┴────┘ └────┴────┘ │

│ │

└─────────────────────────────────────────────┘











Двусвязные списки .



* П.:



Type

PDItem = ^DItem;

DItem = record

el:byte;

next:PDItem;

prev:PDItem;

end;



Var

Head,Tail:PDItem;

num:word; {кол-во элементов в списке}





Вставка в голову списка .



Procedure InsertToHead;

var

p:PDItem;

begin

New(p);

p^.el:=el;

p^.prev:=nil;

if Head=nil

then begin

p^.next:=Head;

Head^.prev:=p;

Head:=p;

end;

inc(num);

end;



Извлечение из хвоста.



Procedure ExtractFromTail(var el:byte;i:word);

var

p:PDItem;

begin

if Tail<>nil

then begin

el:=Tail^.el;

p:=Tail;

Tail:=Tail^.prev;

dispose(p);

if Tail=nil

then Head:=nil

else Tail^.next:=nil;

dec(num);

end

else write(#7,' Error ');

end;





Извлечение из головы.



Procedure ExtractFromHead(var el:byte);

begin

el:=Head^.el;

end;



Вставка в конец .



Procedure WriteTail(var el:byte);

begin

Tail^.el:=el;

end;





Вставка элемента в произвольное место списка .



Procedure InsertEl(var el:byte;i:word);

var

n:word;

p:PDItem;

pnext,pprev:PDItem;

begin

New(p);

p^.el:=el;

if Head = nil

then begin

p^.next:=nil;

p^.prev:=nil;

Head:=p;

Tail:=p;

end

else if i<=1

then begin

p^.next:=Head;

p^prev:=nil;

Head^.prev:=p;

Head:=p;

end

else if i>=num

then begin

p^.next:=nil;

p^prev:=Tail;

Tail^.prev:=p;

Tail:=p;

end

else begin

pnext:=Head;

n:=1;

while n<>i do

begin

pnext:=pnext^.next;

inc(n);

end;

p^.prev:=pnext;

pnext:=pnext^.next;

pnext^.next^.prev:=p;

pnext^.next:=p;

end;

inc(num);

end;





Печать списка .



Procedure PrintList;

var

p:PDItem;

begin

p:=Head;

while p<>nil do

begin

write(p^.el:3,' ');

p^:=p^.next;

end;

writeln;

end;