Линейные списки (основные операции)

Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.

Из определения следует, что каждый элемент списка содержит поле данных (Data) (оно может иметь сложную структуру) и поле ссылки на следующий элемент (Next). Поле ссылки последнего элемента должно содержать пустой указатель (NIL).Чтобы список существовал, надо определить указатель на его начало. Опишем переменные:

Var и, х: EXS;

Создадим первый элемент:

New(u); {выделим место в памяти для переменной типа S}

u^.next:=nil; {указатель пуст} и^.data:=3; {информационное поле первого элемента}

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

х:=и; {Введем вспомогательную переменную указательного типа, которая будет хранить адрес последнего элемента списка. Сейчас последний элемент списка совпадает с его началом.}

New(x^.Next)•, {выделим область памяти для следующего элемента списка}

x:=x^.Next; {переменная х принимает значение адреса выделенной области памяти}

x^.Data:=5; {определим значение этого элемента списка} x^.Next.=Nil:

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

Procedure Init(Var u: Exs); {создание списка}
Var х, у: Exs; Digit: Integer; {значение информационной части элемента списка}
Begin
Writeln('Введите список '); u:=Nil; {список пуст}
WriteLn('Bводите элементы списка. Конец ввода 0);
Read(Digit);
While Digit<>0 Do
Begin
New(y); {формирование элемента списка} y^.Nexf:=Nil; y^.Data:=Digit;
If u=nil Then u:=y {вставляем первый элемент списка}
Else x^.Next:=y; {вставляем элемент в конец списка}
х:=у; {переносим значение указателя на последний элемент списка}
Read(Digit);
End;
Writein;
End;
Итак, мы построили список добавлением элементов в конец списка. Вставим элемент со значением 7 в начало списка.

Удаление элемента из начала списка

Напишем фрагмент программы:

х:=и; {запомним адрес первого элемента списка}
u:=u^.next; {теперь и указывает на второй элемент списка}
Dispose(x); {освободим память, занятую переменной х^}

Удаление элемента из середины списка

Для этого нужно знать адреса удаляемого элемента и элемента, находящегося в списке перед ним. х:=и; {переменная х для хранения адреса удаляемого элемента}

{найдем адреса нужных элементов списка }
While (x<>Nil) And (x^.Data<>Digit) Do Begin dx:=x; x:=x^.Next End;

dx^.Next:=x^.Next; Dispose(x);

Удаление элемента из конца списка

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

{найдем предпоследний элемент} х:=и; ах:=и;

While x^.Next<>NIL Do Begin dx:=x; x:=x^.Next; End;

{удаляем элемент х^ из списка и освобождаем занимаемую им память} dx^.Next:= Nil; Dispose(x);

Стек

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

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

Основные операции со стеками

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

Дадим новое определение стека. Стек — это список, в котором добавление новых элементов и извлечение имеющихся происходит с начала (или конца) списка.

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

Таким образом, описать стек можно следующим образом:

Type EXST=^ST;

ST=Record Data: Integer; Next: EXST; End;

Var Stack: EXST; {текущая переменная}

Тогда, если стек пуст, то значением указателя равно NIL.

Занесение в стек

Процедура занесения элемента в стек должна содержать два параметра — первый задает нужный стек, второй — заносимое в него значение. Обозначим их соответственно х1 и с.

Занесение в стек производится аналогично вставке нового элемента в начало списка:

Procedure WriteStack (Var ir.EXST; digit: Integer);
{запись в стек} Var x:.EXST;
Begin
New(x); {создание нового элемента стека} x^.Data:=diglt; х^.Nехt:=u
{созданный элемент определить как вершину стека} u:=х;
End;
Основная программа формирования стека будет иметь вид:
Var Stack: EXST; {текущая переменная} digit: Integer;
Begin
Stack:=Nil;
WriteLn(¹'Введите элементы стека. Окончание ввода — О'); Read(Digit);
While Digit<>O Do Begin WriteStack(Stack, digit); Read(digit); End
End.

Извлечение элемента из стека.

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

Procedure ReadStack(Var u-.EXST; Var i-.Integer); Var x: EXST;
Begin
i:u^.Data; x:=u; u:=u^.Next; Dlspose(x);
End;

Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию проверки пустоты обрабатываемого стека. function Free(u:EXST):Boolean;