Списки
СТРУКТУРЫ ДАННЫХ .
Под структурами данных (далее с/д) понимают элементы данных и связи между
ними.Каждая с/д характеризуется типовым набором операций с элементом :
- поиска (доступа)
- записи (включения)
- выборки (удаления)
Элементы могут быть либо простые ,либо составные.
Из изученных нами с/д являются :
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;