• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

Begin

Else

End

Begin

Then

Else

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 – перевірка чи черга порожня;

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

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

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

if key = t^.key

data:=t^.data;

Search:=true;

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;

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

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

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

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

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).

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

1. Масив

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

Для того щоб зберігати таблицю, нам буде потрібний запис із двох полів: сам масив і цілочисльне поле, що позначає поточний розмір масиву:

const maxsize = 2000; {максимальний розмір таблиці}

type tTable = record

a: array[1..maxsize] of tItem; {це сам масив}

n: integer; {а це - реальне число елементів}

end;

var Table: tTable;

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

2. Список

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

Як виглядає така таблиця на Паскалі нам уже відомо:

type tItemPtr = ^tItem; {покажчик на елемент списку}

tItem = record {елемент списку}

key: tKey;

data: tData;

next: tItemPtr;

end;

tList: tItemPtr; {задається покажчиком на перший елемент}

var Table: tList {таблиця є списком}

3. Дерево

Як зберігати і шукати дані в двійковому дереві, ми вже знаємо, а таблицю можна задати так:

type tItemPtr = ^tItem; {покажчик на елемент}

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

key: tKey;

data: tData;

left, right: tItemPtr;

end;

tTree = tItemPtr;

var Table: tTree; {таблиця є деревом}

Читайте також:

1. I визначення впливу окремих факторів
2. II. Визначення мети запровадження конкретної ВЕЗ з ураху­ванням її виду.
3. II. Мотивація навчальної діяльності. Визначення теми і мети уроку
4. III. Географічна структура світового ринку позичкового капіталу
5. III. Процедура встановлення категорій об’єктам туристичної інфраструктури
6. IV. Закономірності структурно-функціональної організації спинного мозку
7. Ocнoвнi визначення здоров'я
8. VІ. План та організаційна структура заняття
9. VІ. Структурно-логічні схеми
10. А. Структурно-функціональна класифікація нирок залежно від ступеню злиття окремих нирочок у компактний орган.
11. Адаптивні організаційні структури управління.
12. Адміністративно – територіальний устрій і соціальна структура Слобожанщини у половині XVII – кінці XVIII століття

Переглядів: 644