program Form6;

type

TypeElm=Char;

Link=^Lanka;

Lanka=record

Elem: Char;

Next: Link;

Predd: Link;

end;

function SeekLst(List:Link; Elm:char; var LanLst:Link): Boolean;

var p,q: Link;

b: boolean;

begin

p:=List; q^P^Next;

b:=False; LanLst:=Nil;

while (p<>q) and (not B) do

if q^,Elem:=Elm then

begin

b:=true; LanLst:=q;

end

else q:=q^.next;

SeekLst:=b;

end;

begin

end.

2.4. Поняття черги і стека

У програмуванні поняття черги як динамічної структури даних використовують для моделювання процесів, пов'язаних з почерговим виконанням деяких замовлень. Над чергою визначені дві операції: введення елемента в чергу і вибір елемента з черги для обслуговування з вилученням із черги. Є такі два види черг, що відрізняються дисципліною обслуговування:

1) черги з дисципліною обслуговування FIFO (First In – First Out) перший у чергу – перший з черги, тобто раніше буде обслужений той елемент, який раніше потрапив у чергу;

2) черги з дисципліною обслуговування LIFO (Last In – First Out) останній у чергу – перший із черги, тобто першим буде обслужений той елемент, який останнім потрапив у чергу.

Другий вид черги називають стеком. Для відображення стека використаємо введену раніше структуру – динамічний ланцюг ланок. У цьому випадку єдино доступною позицією вважатимемо першу ланку ланцюга, яку називають вершиною стека. Нульової ланки тепер не потрібно, а значення вказівника, що визначає весь стек, є вказівка на вершину стека. В кожній ланці є вказівка на наступну, значення вказівки останньої ланки є nil.

Отже, стек можна описати за допомогою таких типів:

type

TypeElm=Char;

Link=^Ls;

Ls=record

Elem: Char;

Next: Link;

end;

Stack=Link;

Тепер, використовуючи ці описи, стек як об'єкт програми можна ввести за допомогою опису змінної:

var

St: Stack;

Схематично стек зображено на рис. 22.

Рис. . Стек

Перед формуванням стека його треба зробити порожнім за допомогою присвоєння

St:=nil;

Працюючи зі стеком, найчастіше використовують дві процедури: введення елемента в стек і вибір елемента зі стека. Процедура введення в стек містить як формальні параметри вказівку на потрібний стек і значення елемента, який уводять у цей стек;

program Form7;

type

TypeElm=Char;

Links=^s;

Ls=record

Elem: Char;

Next: Link;

end;

Stack=Link;

procedure lnStack(var St: Stack; Elm: Char);

var Rb; Link;

begin new(Rb);

Rb^.EIem;=Elm;

Rb^.Next:=St;

St:=Rb;

end;

begin

end.

Процедура вибору зі стека полягає у виборі елемента, що є в його вершині, і присвоєнні значення цього елемента деякій змінній, а також ліквідації першої ланки стека:

program Form8;

type

TypeElm=Char;

LInk=^Ls;

Ls=record

Elem: Char;

Next: Link;

end;

Stack=Link;

procedure OutStack(var St: Stack; var a: Char);

var Rb: Stack;

begin

Rb:=St;

a:=St^.EIm;

St:= St^.Next;

Dispose(Rb)

end;

begin

end.

Це найпростіший варіант процедури вибору із стека. Досконалішою буде процедура, яка враховує можливість порожнього стека і видає в цьому випадку повідомлення про спробу вибору елемента з порожнього стека. Інше можливе вдосконалення – знищення першої ланки стека за допомогою процедури Dispose. В нашій процедурі OutStack, хоча вершина й переноситься на наступну ланку, попередня вершина залишається в пам'яті.

2.5. Таблиці

Для створення й експлуатації автоматизованих інформаційних систем доводиться зберігати й опрацьовувати великі обсяги інформації у вигляді записів. Доступ до окремих записів у таких системах не повинен залежати від попередніх звертань до них, тому розглянуті раніше структури (черги, стеки) непридатні для використання в таких системах. Тим більше вони непридатні, що для доступу до окремих записів треба знати їхнє розміщення в структурі.

Таблиці як структура даних, організовані засобами мови Паскаль, дають змогу уникати цих недоліків. Таблицею вважатимемо набір записів, кожному з яких відповідає повне ім'я.

Потрібний запис у таблиці шукають за відповідним іменем. Ім'я запису інакше ще називають ключем. Ключі можуть бути довільні, однак для того, щоб під час шукання запису можна було порівняти ключі, доцільно, щоб це були або цілі числа, або рядки символів однакової довжини, для яких визначені операції порівняння.

Над таблицею визначені такі операції:

1) шукання запису із заданим ключем;

2) введення в таблицю запису з заданим ключем;

3) вилучення з таблиці запису з заданим ключем. Таблиці часто наводять у вигляді ланцюга, подібного до однонапрямленого списку (рис. 23).

Рис. . Таблиця у вигляді списку

Кожна ланка містить ключ запису, текст запису і вказівку на наступну ланку. Таке зображення таблиці є простим в опрацюванні; однак має той недолік, що у випадку великих обсягів інформації для пошуку запису за заданим ключем потрібно послідовно перебирати всі записи. З огляду на це використовують зображення таблиць у вигляді ланцюгів з упорядкованими записами. Впорядкованість може бути різною, зокрема, за зростанням ключів записів. Тоді для шукання запису із заданим ключем немає потреби перебирати всі записи, а лише ті, величина ключа яких не перевищує заданої. Проте за таких умов для вставлення запису з конкретним ключем треба відшукати місце в таблиці, що відповідає цьому ключу, тоді як без упорядкування за ключами новий запис можна ввести в таблицю довільно, наприклад, на початку списку, якщо відомо, що запису з таким ключем немає.

Розглянемо ще один спосіб зображення таблиць, коли текст запису зберігається окремо від ключів, а при ключі є тільки вказівка на нього. Тоді всі елементи списку стають однотипними, оскільки вони вже не залежать від структури тексту, який відповідає кожному елементу і може бути різним для різних елементів. Елемент списку тепер є записом, що містить тільки два поля: ключ і вказівку на відповідний текст. Ці елементи тепер можна (оскільки вони однотипні) і доцільно об'єднати не в список, а в одновимірний масив. Вигляд одержаної структури показаний на рис. 24.

Рис. .

2.6. Графи і дерева

Графом називають скінченну множину точок-вершин графа, для деяких пар якої налагоджені зв'язки – ребра графа. Розглянемо використання графів для зображення динамічних структур. Нехай є деяка структура, що складається з записів, пов'язаних між собою системою вказівок, причому кожен запис може містити вказівки на декілька інших записів. Тепер зіставимо вершини графа