Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

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

 

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

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

 
 

Елементи дерева називаються вершинами. Вершина 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 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;

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

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

 

Ф. И. О. Адреса Телефон Рік народження
Петров Ф. М. Північна 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).

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

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 століття




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

<== попередня сторінка | наступна сторінка ==>
Стан покажчика | Спадкування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.013 сек.