Визначення й описи структур даних

Begin

End

Begin

End

Begin

Begin

Begin

Begin

End

Begin

Begin

End

End

Begin

Begin

Implementation

Interface

type tData = record

Name: string [50];

Phone: longint;

end;

tItemPtr = ^tItem;

tItem = record

Data: tData;

Next: tItemPtr;

end;

procedure InitList(var l: tItemPtr);

procedure AddItemToHead(var l: tItemPtr; d: tData);

function DeleteItemAfter(var l: tItemPtr; num: word): boolean;

function Count(l: tItemPtr): word;

function GetItem(l: tItemPtr; num: word; var d: tData): boolean;

procedure ClearList(var l: tItemPtr);

{---------------------------------------------------------------}

procedure InitList(var l: tItemPtr);

begin l:= nil end;

procedure AddItemToHead(var l: tItemPtr; d: tData);

var p: tItemPtr;

new(p);

p^.data:=d;

p^.next:=l;

l:=p;

end;

function DeleteItemAfter(var l: tItemPtr; num: word): boolean;

var p,q: tItemPtr;

i: word;

i:=1;

p:=l;

while (i<>num) and (p<> nil) do begin

i:=i+1;

p:=p^.next;

end;

if p<> nil then begin

if p^.next<> nil then begin

q:=p^.next^.next;

dispose(p^.next);

p^.next:=q;

DeleteItemAfter:=true;

else DeleteItemAfter:=false; {не вилучений}

else DeleteItemAfter:=false;

end;

function Count(l: tItemPtr): word;

var p: tItemPtr;

i: word;

i:=0;

p:=l;

while p<> nil do begin

i:=i+1;

p:=p^.next;

end;

count:=i;

end;

function GetItem(l: tItemPtr; num: word; var d: tData): boolean;

var p: tItemPtr;

i: word;

i:=1;

p:=l;

while (i<>num) and (p<> nil) do begin

i:=i+1;

p:=p^.next;

end;

if p<> nil then begin

d:=p^.data;

GetItem:=true;

else GetItem:=false;

end;

procedure ClearList(var l: tItemPtr);

var p: tItemPtr;

while (l<> nil) do begin

p:=l^.next;

dispose(l);

l:=p;

end;

end;

end.

Динамічні змінні: інші види списків, стек і черга.

1. Інші види списків

Крім розглянутих списків можливі більш складні варіанти, зв'язані з наявністю двох додаткових властивостей:

1. Двонаправленність списку. У кожному елементі таких списків є не тільки покажчик на наступний елемент, але і на попередній. Така організація може виявитися корисною при додаванні чи видаленні елемента, що передує зазначеному.

2. Замкнутість списку. Поле next в останньому елементі вказує на перший елемент. Інакше такі списки називаються кільцевими. Цей вид дозволяє спростити процедуру видалення елемента списку й інші операції.

З урахуванням цих властивостей можливі чотири різних типи списків.

Для приклада розглянемо опис і реалізацію кільцевого двонаправленого списку:

type tItemPtr = ^tItem

tItem = record

data: tData;

next,prev: tItemPtr;

end;

var List: tItemPtr; {список - покажчик на один з елементів}

........

{Видалити після зазначеного:}

procedure DelAfter(p: tItemPtr);

var q: tItemPtr;

if (p<> nil) and (p^.next<>p) then begin

q:=p^.next^.next;

dispose(p^.next);

p^.next:=q;

q^.prev:=p;

end;

end;

{Уставити перед зазначеним:}

procedure InsertBefore(p: tItemPtr; d: tData);

var q: tItemPtr;

if p<> nil then begin

new(q);

q^.data:=d;

q^.next:=p;

q^.prev:=p^.prev;

p^.prev:=q;

q^.prev^.next:=q;

end;

end;

2. Стек і черга

Стеком називається такий спосіб збереження даних, при якому елемент, записаний у сховище даних, останнім завжди витягається першим (дисципліна LIFO – «last in - first out»). При витягу елемента відбувається його видалення зі стека.

Розглянемо найпростіший приклад використання стека. Припустимо, що мається рядок, що складається з одних лише відкриваючих і закриваючих дужок. Потрібно визначити, чи є віна правильним дужковим виразом (тобто для кожної відкриваючої дужки повинна знайтися закриваюча). Заведемо масив і змінну для збереження номера останнього значимого елемента в масиві (тобто вершини стека), у який при проході по рядку будемо складати всі дужки, що відкриваються, (зі збільшенням номера вершини на 1), а при зустрічі з закриваючої будемо видаляти відповідну відкриваючу (попросту зменшувати номер вершини стека). Якщо виявиться, що «прийшла» закриваюча дужка, а стік порожній (тобто номер вершини дорівнює 0), то вираз помилковий. Це ж можна сказати й у випадку, коли рядок закінчився, а стек не порожній.

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

Для даних більш складного виду стек можна організувати за допомогою односпрямованого некільцевого списку. Щоб вставити елемент у стек, потрібно додати його в початок списку, щоб витягти зі стека — одержати дані першого елемента, після чого видалити його зі списку.

Будь-яка реалізація стека повинна містити наступні процедури і функції:

procedure InitStack — ініціалізація стека;

procedure Push(d: tData) — вставити елемент у стек;

procedure Pop(var d: tData) – витягти елемент із вершини стека;

function NotEmpty: boolean – перевірка чи стек порожній;

Черга відрізняється від стека тим, що останній елемент, що прийшов у неї, буде витягнутий останнім, а перший (першим («FIFO»). За допомогою списків її можна організувати так: будемо зберігати не тільки покажчик на «голову» списку, але і на «хвіст»; додавати будемо в «хвіст», а витягати з «голови».

Будь-яка реалізація черги (не обов'язково за допомогою списків) повинна «уміти» виконувати такі дії:

procedure InitQueue — ініціалізація черги;

procedure AddQueue(d: tData) — поставити елемент у чергу;

procedure SubQueue(var d: tData) – витягти елемент із черги;

function NotEmpty: boolean – перевірка чи черга порожня;

Дерева і пошук у деревах

Деревами називаються структури даних наступного виду:

Елементи дерева називаються вершинами. Вершина Tree^ називається коренем дерева, а вся множина вершин, зв'язаних з деякою вершиною за допомогою одного з покажчиків називається піддеревом. Вершини, у яких усі покажчики рівні nil, іноді називають листами.

Докладніше ми розглянемо варіант двійкового дерева, тобто такого, у якому кожна вершина має два піддерева (кожне з них може бути порожнім). Такі дерева виявляються дуже зручними для рішення задачі пошуку, коли ключі для наших даних (наприклад прізвища при пошуку телефонних номерів) можна порівнювати на "=", "<" і ">". У кожну вершину дерева заноситься елемент даних, причому робиться це таким чином, щоб для будь-якої вершини всі ключі даних (чи самі дані в найпростішому випадку) з лівого піддерева були менші ключа цієї вершини, а всі ключі з правого — більші. Виконання такої вимоги можна досягти при послідовному додаванні елементів (тобто побудові дерева, починаючи з «нуля», точніше з nil).

При описаній побудові дерева пошук виявляється досить простою справою: спочатку ми порівнюємо шуканий ключ із ключем кореня дерева. Якщо ці два ключі збігаються, то елемент знайдений, у противному випадку виконуємо пошук у левом піддереві, інакше — у правом, далі в обраному піддереві знову виконуємо порівняння його кореня із шуканим ключем, і т.д. Цей процес закінчиться або коли ми знайшли ключ, або коли чергове піддерево виявилося порожнім (це означає, що такий ключ у дереві відсутній).

Для реалізації двійкового дерева спочатку розглянемо його опис на Паскалі:

type tNodePtr = ^tNode; {покажчик на вершину}

tNode = record

data: tMyData;

left,right: tNodePtr;

end;

tTree = tNodePtr; {для доступу до дерева досить зберігати покажчик на його корінь}

Під даними (tMyData) будемо розуміти запис, що складається з ключа, необхідного для порівнянь, і власне даних:

type tMyData = record

key: tKey;

data: tData;

end;

Для того щоб реалізувати дії з двійковим деревом, нам знадобляться так називані рекурсивні процедури.

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

procedure InsertNode(t: tTree; key: tKey; data: tData);

if t= nil then begin

new(t);

t^.key:=key;

t^.data:=data;

else if key<t^.key then InsertNode(t^.left,key,data)

else InsertNode(t^.right,key,data);

end;

Після того як дерево побудоване, можна виконувати пошук (також рекурсивний):

function Search(t: tree; key: tKey; var data: tData): boolean;

{повертає значення знайдене / не знайдений}

if t= nil then Search:=false

else if key = t^.key then begin

data:=t^.data;

Search:=true;

else if key<t^.key then Search:=Search(t^.left,key,data)

else Search:=Search(t^.right,key,data);

end;

Легко помітити, що елементи даних, «покладені» у двійкове дерево можна виводити у відсортованому порядку:

procedure Traversal(t: tTree); {обхід дерева}

if t<> nil then begin

Traversal(t^.left);

writeln('Key:',t^.key,' Data:',t^.data);

Traversal(t^.right);

end;

end;

Таблиці і найпростіші алгоритми пошуку.

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

Ф. И. О.	Адреса	Телефон	Рік народження
Петров Ф. М.	Північна 99-88	29-29-29
Іванов П. С.	Світу 111-222	77-88-99
Козлов Н. В.	Жовтнева 135-246	45-67-89
.................

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

При використанні мови Паскаль для роботи з табличними даними досить зручно використовувати запису як елементи даних. У нашому прикладі таблиця буде складатися з елементів наступного типу:

type tItem {елемент} = record

surname: string [30]; {прізвище, ключове поле}

address: string; {адреса}

phone: longint; {телефон}

birth: word; {рік народження}

end;

При розгляді алгоритмів пошуку ми будемо користатися більш загальною формою для запису типу елемента:

type tItem = record

key: tKey; {ключ}

data: tData; {дані}

end;

Типи tKey і tData залежать від конкретної задачі, яку потрібно вирішувати. У нашому прикладі tKey — рядок до 30 символів довжиною, а tData можна зробити записом із трьох полів (address, phone і birth).

Розглянемо тепер деякі способи реалізації всієї таблиці:

Дата добавления: 2014-12-16