Включення у список після елемента, вказівник на який відомий

Вступ.

Дисципліна "Структура та організація даних в ЕОМ" за планом підготовки спеціалістів напряму " Комп’ютерні науки" включена до циклу професійно-орієнтованих дисциплін.

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

Вивчення даної дисципліни здiйснюється на базі знань, одержаних студентами на першому курсі при вивченні дисципліни "Основи програмування та алгоритмічні мови", "Архітектура та функціонування ЕОМ", "Основи дискретної математики". Дисципліна "Структура та організація даних в ЕОМ" фактично є продовженням дисципліни "Основи програмування та алгоритмічні мови" на більш високому рівні. Вивчаються статичні та динамічні структури даних, різні методи сортування, рекурсивні алгоритми, рекурсивні структури даних такі як списки, дерева.

Систематичний та науковий пiдхiд до побудови програм важливий в першу чергу у випадку великих програм iз складними даними. Таким чином, методи програмування включають також i всi варiанти структурування даних. Зрештою програма є конкретним формулюванням абстрактного алгоритму, заснованим на конкретних уявах i структурах даних. Рiшення про структурування даних неможливо приймати без знання алгоритму, i навпаки, структура та вибiр алгоритмiв iстотно залежить вiд структури даних, тобто будова програми i структури даних нерозривно зв’язанi мiж собою.

Автор мови Pascal – Ніклаус Вірт – професор, директор інституту інформатики Швейцарської вищої політехнічної школи, лауреат Т’юринговської премії, автор таких загальновідомих робіт угалузы програмування, як мови програмування – Ейлер, Модула, Модула-2, методика покрокового уточнення при розробці алгоритмів – вважав, що запорукою одержання хорошої програми є ретельно продумана структура даних. Саме про це свідчить назва книги Вірта “Алгоритми + структура даних = програми”, приклади програм з якої використано в даній роботі як взірець високого мистецтва програмування автора мови Pascal.

1. Сортування

Сортування – процес переставлення об’єктів множини у визначеному порядку з метою полегшення наступного пошуку елементів у відсортованій множині.

Елементи сортування є практично в усіх задачах (телефонні книги, відомості, звіти).

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

Введемо термінологію: визначимо тип елементу як

Type

item = Record

key: Integer;

…………..... {опис інших компонент}

End;

де

key – ключ, який використовується для ідентифікації запису (наприклад, порядковий номер);

опис інших компонент – усі суттєві дані про елемент.

Метод сортування має назву стійкого, якщо при сортуванні не змінюється порядок елементів з однаковими ключами.

1.1. Сортування масивів

Основна вимога до методів сортування — економне витрачання пам’яті, тому сортування треба виконувати in situ (на тому ж місці).

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

Визначають три класи сортування масивів in situ:

1. Сортування простими включеннями;

2. Сортування простим вибором;

3. Сортування простим обміном.

Масив елементів типу item може бути описаний таким чином:

Const

N=20;

Type

index = 0..n;

Var a: Array [1..n] Of item;

1.1.1. Сортування простими включеннями

Алгоритм сортування:

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

For i:=2 To n Do

Begin

x:=a[i];

< вставити х на підходяще місце >

End;

Цей метод звичайно використовують гравцi у карти. Починаючи з 2-ої, карти роглядаються та розміщуються на потрібне місце.

Початкові ключі 44 55 12 42 94 18 06 67

i=2 44 55 12 42 94 18 06 67

i=3 12 44 55 42 94 18 06 67

i=4 12 42 44 55 94 18 06 67

i=5 12 42 44 55 94 18 06 67

i=6 12 18 42 44 55 94 06 67

i=7 06 12 18 42 44 55 94 67

i=8 06 12 18 42 44 55 67 94

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

Можливі два виходу з циклу:

– знайдено елемент з ключем, меншим за x, тоді х ставиться перед ним;

– досягнуто лівий кінець послідовності.

У цьому випадку застосовується заcіб фіктивного елемента (“бар’єра”).

Procedure StraightInsertion;

Var

i,j: index;

x: item;

Begin

For i:=2 To n Do

Begin

x:=a[i];

a[0]:=x; { розширити діапазон індексів в описі }

j:=i–1;

While x.key < a[j].key Do

Begin

a[j+1]:=a[j];

j:=j–1

End;

a[j+1]:=x

End

End;

Цей алгоритм описує стійке сортування (порядок елементів з однаковими ключами залишається незмінним).

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

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

1.1.2. Сортування простим вибором

Алгоритм сортування:

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

Procedure StraightSelection;

Var

i,j,k: index;

x: item;

Begin

For i:=1 To n–1 Do

Begin

k:=i;

x:=a[i];

For j:=i+1 To n Do

If a[j].key < x.key Then

Begin

k:=j;

x:=a[j];

End;

a[k]:=a[i];

a[i]:=x;

End;

Алгоритм сортування простим вибором має перевагу над алгоритмом сортування простими включеннями, крім випадків, коли ключі розсортовані у зворотному порядку.

1.1.3. Сортування простим обміном (засіб “бульбашки”)

За основу взято принцип порівняння та обміну пар сусідніх елементів доти, поки не будуть розсортовані всі елементи — від кінця до початку “спливе” найлегший.

Procedure BubbleSort;

Var

i,j: index;

x: item;

Begin

For i:=2 To n Do

For j:=n DownTo i Do

If a[j–1].key > a[j].key Then

Begin

x:=a[j–1];

a[j–1]:=a[j];

a[j]:=x

End;

i=2	i=3	i=4	i=5	i=6	i=7	i=8
44	06	06	06	06
55	44	12	12	12
12	55	44	18	18
42	12	55	44	42
94	42	18	55	44
18	94	42	42	55
06	18	94	67	67
67	67	67	94	94

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

Крім того, слід звернути увагу на таку ситуацію:

– у варіанті “бульбашка” у “важкому” кінці:

12 18 42 44 55 67 94 06

сортування відбудеться за один прохiд

– у варіанті неправильно розташований елемент у “легкому” кінці:

94 06 12 18 42 44 55 67

для сортування необхідно сім проходів.

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

1.1.4. Шейкер-сортування

Наведений нижче алгоритм Шейкер-сортування є вдосконаленим варіантом сортування простим обміном і має також назву засіб “бульбашки” з обмеженнями.

44 06 06 06 06

55 44 44 12 12

12 55 12 44 18

42 12 42 18 42

94 42 55 42 44

18 94 18 55 55

06 18 67 67 67

67 67 94 94 94

Procedure ShakerSort;

Var

i,k,left,right: index;

x: item;

Begin

left:=2;

right:=n;

k:=n;

Repeat

{прохід вверх}

For j:=right DownTo left Do

If a[j–1].key > a[j].key Then

Begin

x:=a[j–1];

a[j–1]:=a[j];

a[j]:=x;

k:=j

End;

left:=k+1;

{прохід вниз}

For j:=left To right Do

If a[j–1].key > a[j].key Then

Begin

x:=a[j–1];

a[j–1]:=a[j];

a[j]:=x;

k:=j

End;

right:=k–1

Until left>right

End;

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

Сортування обміном та його поліпшений варіант гірше, ніж сортування включеннями та вибором. Алгоритм Шейкер-сортування вигідно використовувати, якщо відомо, що елементи майже впорядковані.

1.1.5. Швидке сортування

Алгоритм сортування:

Вибирається елемент x приблизно посередині. Переглядається масив зліва направо, поки не зустрінеться елемент a[i]>x, а потім справа наліво, поки не зустрінеться елемент a[j]<x. Елементи a[i] та a[j] міняються місцями, поки i та j не зустрінуться.

44 55 12 42 94 06 18 67

18 06 12 42 94 55 44 67

В результаті ми отримали два підмасиви: зліва елементи з меншими ключами, справа — з більшими відносно елемента з ключем 42.

a[k].key <= x.key для k=1,...,i–1
a[k].key >= x.key для k=j+1,...,n

Тепер необхідно зробити те саме з обома отриманими частинами масиву, частинами частин і т.д., поки кожна частина не буде містити в собі тільки один елемент.

Procedure QuickSort;

Procedure Sort (left, right: index);

Var

i,j: index;

x,w: item;

Begin

i:=left;

j:=right;

x:=a[(left+right) div 2];

Repeat

While a[i].key < x.key Do i:=i+1;

While a[j].key > x.key Do j:=j–1;

If i<=j Then

Begin

w:=a[j];

a[i]:=a[j];

a[j]:=w;

i:=i+1;

j:=j–1

End

Until i>j;

If left<j Then Sort(left,j);

If i<right Then Sort(i,right)

End;

Begin

Sort(1,n);

End;

Цей алгоритм дуже простий та ефективний, часто використовується професійними програмістами.

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

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

1.2. Сортування масива рядків

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

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

‘Іванчук’ > ’Іванченко’

З двох збіжних за символами рядків різної довжини меншим є коротший: ’ABR’ < ’ABRAKAD’

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

Для сортування використовуємо метод швидкого сортування.

Процедура сортування рядкiв має вигляд:

Procedure SortString (Var inm:StringArray; n:Integer);

{StringArray – масив рядків, n– кількість рядків}

Procedure InSort (left,right:Integer; Var m:StringArray);

Var

a,b: InData;

i,j: Integer;

Begin

i:=left;

j:=right;

a:= m[(left + right) div 2];

Repeat

While m[i] < a Do i:=i+1;

While a < m[j] Do j:=j–1;

If i<=j Then

Begin

b:=m[i];

m[i]:=m[j];

m[j]:=b;

i:=i+1;

j:=j–1

End

Until i>j;

If left<j Then InSort (left,j,m);

If i<right Then InSort (i,right,m);

End;

Begin

InSort (1,n,inm);

End;

1.3. Сортування файлів

Сортування здійснюється відповідно до значення якої-небудь ознаки (наприклад, за табельним номером).

Для прикладу розглянемо файл, який складається із записів, оскількі комбінований тип даних становить практичний інтерес.

В залежності від засобу доступу до файлу сортування поділяється на послідовне та пряме. Розглянемо алгоритм прямого сортування записів у типізованому файлі.

{ Створити файл записів: табельний номер, прізвище, ім’я, по батькові, оклад; відсортувати за табельним номером. Сортування виконується без створення додаткового файлу, на тому ж місці.}

Uses Crt;

Type

Karta = Record

tabnomer: Integer;

fio: String[20];

oklad: Real;

End;

Stroka = String[80];

Fv = File Of Karta;

Var

test: Karta;

t,t2: Integer;

namef: Fv;

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

{ Створення файлу }

Procedure Sozd;

Begin

Assign(namef, ’a:Sps.txt’);

ReWrite(namef);

While True Do

Begin

Write(’Табельний номер:’);

Readln(test.tabnomer);

If test.tabnomer = 0 Then

Begin

Close(namef);

Exit;

End;

Write(’Оклад:’);

Readln(test.oklad);

Write(’Прізвище...:’);

Readln(test.fio);

Write(namef,test);

End;

End; {Sozd}

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

Function Poisk(Var fpoisk:Fv; i:Integer):Integer;

Var

t: Karta;

Begin

i:=i-1;

Seek(fpoisk,i);

Read(fpoisk,t);

Poisk:=t.tabnomer;

End; {Poisk}

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

Procedure SortFile(Var zam:Fv; count:Integer);

Procedure SortIn(left,right:Integer);

Var

i,j,s: Integer;

x,y,z: Karta;

Begin

i:=left;

j:=right;

s:=(left+right) div 2;

Seek(zam,s–1);

Read(zam,x);

Repeat

While Poisk(zam,i) < x.tabnomer Do i:=i+1;

While x.tabnomer < Poisk(zam,j) Do j:=j–1;

If i<=j Then

Begin

Seek(zam,i–1);

Read(zam,y);

Seek(zam,j–1);

Read(zam,z);

Seek(zam,j–1);

Write(zam,y);

Seek(zam,i–1);

Write(zam,z);

i:=i+1;

j:=j–1;

End

Until i>j;

If left<j Then SortIn(left,j);

If i<right Then SortIn(i,right);

End; {SortIn}

Begin

SortIn(1,count);

End; {SortFile}

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

Begin

ClrScr;

Sozd;

Assign(namef,’a:Sps.txt’);

Reset(namef);

t:=FileSize(namef);

SortFile(namef,t);

Reset(namef);

ClrScr;

Writeln(’Вiдсортований список’);

While Not Eof (namef) Do

Begin

Read(namef, test);

Writeln(test.tabnomer:10, test.fio:20, test.oklad:10);

End;

Close(namef);

Repeat Until KeyPressed

End.

2. Рекурсивні алгоритми

Об’єкт називається рекурсивним, якщо він містить себе в самому собі, або він визначений за допомогою самого себе.

Рекурсія дозволяє визначити безліч об’єктів за допомогою скінченої кількості виразів.

Якщо процедура включає явний виклик самої себе, то вона називається прямо-рекурсивною. Якщо процедура P викликає процедуру Q, а та в свою чергу викликає P, то процедура P називається косвено-рекурсивною.

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

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

Hе слід виконувати рекурсію, якщо задача має очевидне інтерактивне рішення. Однак, алгоритми, які за своєю природою рекурсивні, бажано реалізовувати у вигляді рекурсій.

2.1. Алгоритми з поверненням

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

2.1.1. Шахова задача про хід коня

Дана дошка, розміром n x n, яка має n x n полів. Кінь, що може ходити за шаховими правилами, розміщується на полі з координатами x0, y0. Hеобхідно конем пройти по всім полям дошки, тобто виконати обхід дошки, якщо він існує, за (n*n ‑ 1) ходів, за умови, що на кожне поле кінь стає тільки один раз.

Очевидним є такий алгоритм: або виконати наступний хід, або він неможливий.

Procedure <Cпроба_наступного_ходу>;

Begin

Repeat

<вибір наступного з можливих ходів> {із списка чергових ходів}

If <хід можливий> Then

Begin

<записуємо хід>

If <дошка не заповнена> Then

Begin

<спроба наступного ходу>

If <невдача> Then

<видалення попереднього ходу>

End

Until <хід був вдалим> or <немає інших можливих ходів>

End

Виберемо подання для даних.

Дошку можна представити у вигляді матриці h розміром n x n.

Type

index=1..n;

Var

h: array [index,index] Of integer;

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

Для цього можна прийняти такі узгодження:

h[x,y]=0 – поле (x,y) не відвідувалось

h[x,y]=i – поле відвідувалося на i-тому ходу (1<= i <= n * n)

Параметри процедури повинні визначати початкові умови для наступного ходу, а також повідомляти про його вдалість чи невдалість. Початкові умови для наступного ходу визначаються заданням координат поля x, y, з якого треба робити хід, а також номером ходу i (для його фіксації). Для рішення останньої задачі необхідний булевий параметр-результат:

q=true – хід виконано;

q=false – хід не виконано.

Ще деякі узгодження:

якщо i<= n * n – дошка не заповнена;

якщо u та v – локальні змінні для координат ходу, то “хід можливий” за таких умов:

1<= u <=n та 1<= v <=n – тобто поле не за межами дошки

h[u,v]=0 – поле раніше не відвідувалось

фіксація ходу – h[u,v]=i;

стирання ходу – h[u,v]=0;

Звернемось до задачі:

Якщо задані початкові координати, то для наступного ходу є вісім різних можливостей вибору координат (u,v). Для того, щоб отримати з координат (x,y) координати (u,v), будемо додавати до них різниці координат, тобто відстань у клітинках поля від початкової позицїї коня до поточної, які будем зберігати у масивах a та b.

а= 2, 1, -1, -2, -2, -1, 1, 2

b= 1, 2, 2, 1, -1, -2, -2, -1

Рекурентна процедура перший раз викликається з параметрами x0,y0. Цьому полю присвоюється індекс 1.

{ “Хід коня” }

Program KnightSTore;

Const

n=5;

nsq=25;

Type

index=1..n;

Var

i,j: integer;

q: boolean;

s: set Of index;

a,b: array [1..8] Of integer;

h: array [index,index] Of integer;

Procedure Try(i:integer; x,y:index; Var q:boolean);

Var

k,ux,vy: integer;

q1: boolean;

Begin

k:=0;

Repeat

k:=k+1;

q1:=false;

ux:=x+a[k];

vy:=y+b[k];

If (ux in s) and (vy in s) Then

If h[ux,vy]=0 Then

Begin

h[ux,vy]:=i;

If i<nsq Then

Begin

Try (i+1,ux,vy,q1);

If Notq1 Then

h[ux,vy]:=0;

End

Else

q1:=true;

End;

Until q1 or (k=8);

q:=q1;

End; {Try}

{—————————————————————————}

Begin

s:=[1,2,3,4,5];

a[1]:=2; b[1]:=1;

a[2]:=1; b[2]:=2;

a[3]:=-1; b[3]:=2;

a[4]:=-2; b[4]:=1;

a[5]:=-2; b[5]:=-1;

a[6]:=-1; b[6]:=-2;

a[7]:=1; b[7]:=-2;

a[8]:=2; b[8]:=-1;

{—————очистити дошку———————————}

For i:=1 To n Do

For j:=1 To n Do

h[i,j]:=0;

{—————починаємо з першої позиції————}

h[1,1]:=1;

Try(2,1,1,q);

Ifq Then

For i:=1 To n Do

Begin

For j:=1 To n Do

Write(h[i,j]:5);

Writeln;

End

Else

Writeln(‘Немає рішення’);

End.

Загальна схема алгоритма з поверненням назад має вигляд:

Procedure Try;

Begin

<ініціювати вибір можливих кроків>

Repeat

<вибрати наступний крок>

If <можливо> Then

Begin

<запам’ятати його>

If <рішення неповне> Then

Begin

<спробувати наступний крок>

If <невдача> Then

<стерти запис>

End;

Until <хід зроблено> або <хід неможливий>;

End

Якщо кількість досліджуваних подальших путів розв’язку фіксовано, наприклад, m, тоді процедура може мати такий вигляд:

Procedure Try(i:integer);

Var

k:integer;

Begin

k:=0;

Repeat

k:=k+1;

If <можливий> Then

Begin

<записати>

If i<n Then

Begin

Try(i+1);

If <невдача> Then

<витерти запис>

End;

Until <успіх> або (k=m);

End;

2.1.2. Шахова задача про вісім ферзів

Треба розставити вісім ферзів на шаховій дошці таким чином, щоб ні один з них не погрожував іншому.

Hеобхідно вибрати подання даних. Ферзь може бити фігури, що розташовані по вертикалі, горизонталі, діагоналям. Відповідно, кожна вертикаль може мати на собі тільки одного ферзя (дошка 8х8). Вибір позиції обмежується вісім’ю можливими значеннями індекса по горизонталі (j).

По аналогії з попередньою задачею дошку можна було б зобразити у вигляді квадратної матриці. Але в цьому випадку перевірка безпечної позиції виявилася б дуже складною.

Виходячи з того, що ферзь розташований на кожній вертикалі, перевіряється, чи вільні для даної позиції відповідна горизонталь і діагональ.

Зробимо опис даних:

Var

x:array [1..8] Of integer;

a:array [1..8] Of boolean;

b:array [2..16] Of boolean;

c:array [-7..7] Of boolean;

де:

x[i] – позиція ферзя на i-той вертикалі;

a[i]=true – на j-тій горизонталі ферзя немає;

b[i]=true – на к-тій діагоналі напрямку (/) ферзя немає;

c[i]=true – на к-тій діагоналі напрямку (\) ферзя немає;

Hа / – діагоналі всі поля мають однакову сумму індексів i+j;

На \ – діагоналі всі поля мають однакову різницю індексів i-j.

Тому для b[2,16] – мінімальна та максимальна сума індексів:

(1+1, 8+8)

a для с[-7,7] – мінімальна та максімальна різниця індексів:

(1-8, 8-1)

Поставити ферзя – це означає наступне:

x[i]:=j; наприклад, 1-й ферзь у 1-ому рядку – x[1]=1, 7-й ферзь у 2-ому рядку – x[7]=2;

a[j]:=false; ферзь є у цьому рядку;

b[i+j]:=false; ферзь є на діагоналі /;

c[i-j]:=false; ферзь є на діагоналі \.

Забрати ферзя означає наступне:

a[j]:=true;

b[j]:=true;

c[j]:=true;

Умови безпечного розташування ферзя:

a[j] and b[i+j] and c[i-j] {тобто всі дорівнюють true}

Загальна схема алгоритма.

Procedure Try(i:integer);

Begin

<ініціювати вибір для і-того ферзя>

Repeat

<вибрати позицію>

If <безпечно> Then

Begin

<поставити ферзя>

If i<8 Then

Begin

Try(i+1)

If <невдача> Then

<забрати ферзя>

End

Until <вдало> or <більше немає позиції>

End

{ Вісім ферзів (одне рішення) }

Var

i: integer;

a: array [1..8] Of boolean;

b: array [2..16] Of boolean;

c: array [-7..7] Of boolean;

x: array [1..8] Of integer;

q: boolean;

Procedure Try(i:integer; Var q:boolean);

Var

j: integer;

Begin

j:=0;

Repeat

j:=j+1;

q:=false;

If a[j] and b[i+j] and c[i-j] Then

Begin

x[i]:=j;

a[j]:=false;

b[i+j]:=false;

c[i-j]:=false;

If i<8 Then

Begin

Try(i+1,q);

If Notq Then

Begin

a[j]:=true;

b[i+j]:=true;

c[i-j]:=true;

End;

End

Else

q:=true;

End

Until q or (j=8);

End;{Try}

{———————————————}

Begin

For i:=1 To 8 Do a[i]:=true;

For i:=2 To 16 Do b[i]:=true;

For i:= -7 To 7 Do c[i]:=true;

Try(1,q);

If q Then

For i:=1 To 8 Do Write (x[i]:4);

Writeln;

End.

3. Динамічні інформаційні структури

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

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

До динамічних структур належать:

– стекові структури;

– однозв’яні та двозв’язні списки;

– бiнарнi дерева і т.i.

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

Альтернативою масивам є вказівники. Їх перевага полягає у тому, що:

– вони дозволяють створювати динамічні структури необхідної розмірності;

– програмiст отримує можливості оперувати великими об’єктами за допомогою 4-байтних вказівників;

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

3.1. Динамічні змінні. Вказівники

Динамічні структури даних будуються з динамічних змінних. Динамiчнi данi згiдно з картою розподілу оперативної пам’яті DOS можуть розміщуватися у так званій Heap -області (Heap – “купа”). На відміну від статичних динамічні змінні не мають імени, вони не описуються у розділі Var, для них не виділяється пам’яті під час компіляції, тип може бути будь-яким, крім файлового. Динамічні змінні створюються та знищуються під час виконання програми. Для роботи з динамічними змінними використовуються змінні базового типу Pointer, які мають назву вказівників.

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

Змістовно будь-який зсилочний тип визначає множину значень, які є вказівниками на значення деякого визначеного типу.

Ознакою того, що змінна є вказівником, є або тип Pointer, або символ ^ перед позначенням типу.

Приклади опису:

Type

mas = array [1..10] Of integer;

dmas = ^mas;

Var

p: ^integer;

q: ^char;

workmas: dmas;

r,s,t: pointer;

де:

p – вказівник на динамічний об’єкт цілого типу;

q – вказівник на динамічний об’єкт символьного типу;

workmas – вказівник на динамічний об’єкт, значенням якого є масив з 10 цілих чисел;

r,s,t – вказівники на динамічні змінні будь-якого типу.

В змінній типу вказівник зберігається адреса динамічної змінної у Heap -області.

3.1.1. Засоби створення та використання динамічних даних

Процес створення динамічної змінної складається з наступних кроків:

– пошук та резервування місця у Heap -області для розміщення динамічної змінної;

– засилання адреси зарезервованої ділянки у вказівник;

–заповнення динамічної змінної, тобто занесення значення за адресою у вказівник.

Зв’язок вказівника з об’єктом схематично має вигляд:

об’ект

Вказівник може мати порожню вказівнику Nil. (Nil – службове слово).

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

New(Var p:pointer);

де

p – фактичний параметр, вказівник.

У результаті виконання оператору процедури породжується новий динамічний об’єкт типу, на який посилається вказівник, що є фактичним параметром процедури New. Вказівнику присвоюється його адреса.

У наведеному прикладі породжується динамічна змінна типу integer, а вказівнику р присвоюється її адреса. При цьому породженому динамічному об’єкту не присвоюється яке-небудь значення, а тільки резервується пам’ять.

Динамічним об’єктам на відміну від статичних імен не дається. Для звернення до динамічного об’єкту використовують змінну – вказівник у вигляді:

Наявність символу ^ після змінної - вказівника говорить про те, що мова йде не про значення самого вказівника, а про значення тієї змінної, на яку вказує вказівник.

Динамічну змінну можна ініціювати будь-яким з відомих засобів.

p^:=10; – означає присвоєння значення 10 динамічній змінній, на яку вказує p.

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

r^:=p^+3;

Один з поширених засобів роботи з Неар-областю реалізується за допомогою пари процедур New-Dispose.

Приклад:

Var

x1,x2,s: ^integer;

Begin

New(x1);

New(x2);

New(s);

Readln(x1^);

Readln(x2^);

s^:=x1^+x2^;

Writeln(‘сумма=’, s^);

Dispose(x1);

Dispose(x2);

Dispose(s)

End.

В опису

Var

x1,x2,s: ^integer;

знак ^ перед типом вказує на те, що кожна із змінних x1,x2,s є вказівником на динамічну змінну цілого типу.

У результаті виконання процедур

New(x1);

New(x2);

New(s);

у Heap-областi резервується пам’ять для збереження трьох змінних цілого типу, адреси цих областей пам’яті заносяться відповідно у змінні-вказівники x1, x2, s.

Змінна-вказівник, записана зі знаком ^ справа вказує на те, що мова йде не про адресу динамічної змінної, а про значення динамічної змінної. Тому процедури:

Readln (x1^);

Readln (x2^);

здійснюють ввід значень самих динамічних змінних, на які зсилаються вказівники x1, x2.

Оператором присвоєння

s^:=x1^+x2^;

за адресою s заноситься відповідна сума – так формується третя динамічна змінна, значення якої виводиться на екран:

Writeln (‘сума=’, s^);

Кожному виклику New повинен відповідати виклик Dispose, тобто необхідно знищити всі динамічні змінні, інакше вони будуть продовжувати займати пам’ять (стають “сміттям”).

Над вказівниками визначені операції присвоєння, порівняння. Вказівник може мати порожню зсилку: p:=Nil.

Наприклад p,d - вказівники:

Var p,d: ^integer;

тоді операції:

p^:=3; d^:=58; p:=d;d:=Nil;

схематично можна зобразити у наступному вигляді:

p^:=3; d^:=58;

p:=d;

d:=Nil;

Інший засіб розміщення динамічних змінних у Неар-областi реалізується за допомогою двох взаємно пов’язаних процедур:

GetMem (Var P:pointer; Size:work);

FreeMem (Var P:pointer; Size:work);

GetMem створює динамічну змінну P^ визначеного розміру Size. FreeMem – звільнює динамічну змінну заданого розміру. Природньо, що виклики GetMem та FreeMem повинні відповідати один одному, а значення для одної пари викликів Size співпадати.

Дія пар процедур однакова.. Однак процедури GetMem, FreeMem мають більш широкий спектр застосування. Наприклад, можна виділити пам’ять визначеного розміру:

GetMem(P,20);

.............

FreeMem(P,20);

– що неможливо у New-процедурі.

Третя пара процедур Mark і Release використовується дляфіксації та відновлення стану Неар-області.

Процедура Mark(Var p:pointer) записує поточний стан Heap-області у змінну-вказівник p.

Процедура Release(Var p:pointer) повертає Heap через p до того стану, який був збережений відповідним викликом Mark, тобто за допомогою Release звільняються усі динамічні змінні, розподілені будь-яким чином після виклику Mark. При цьому функція MemAvail(Var i:longint) повертає розмір вільної пам’яті. MaxAvail (Var i:longint) – розмір найбільшої безперервної частини вільної пам’яті.

Приклад:

Uses Crt;

Var

i: longint;

p: ^integer;

Begin

ClrScr;

i:=MemAvail;

Writeln(‘.....’, i);

New(p);

p^:=4566;

i:=MemAvail;

Writeln(‘....’, i);

Readln

End.

Протокол роботи:

тобто змінна цілого типу займає у Неар-області 8 байт.

У зв’язку з процедурою New з’являється важлива проблема: можливе вичерпання областi пам’ятi, що вiдведена пiд динамiчнi змiннi. Якщо при виконаннi New з’ясовується, що для розмiщення нової змiнної в кучi не хватає пам’ятi, то значення вказiвника, заданого у параметрi процедури, не змiниться. При цьому виконання програми не перерветься i нiяких повiдомлень видано не буде. Тому подальша робота з невстановленим вказiвником може привести до непередбачених наслiдкiв.

Для пiдвищення надiйностi програми слiд перевiряти поточний стан динамiчної пам’ятi перед кожним зверненням до New. Це можна зробити за допомогою стандартної функцiї MaxAvail, яка повертає максимальний розмiр безперервної частини вiльної пам’ятi, в якому можливо розмiстити динамiчну змiнну.

3.1.2. Проблема загублених вказівників

Робота з динамiчними змiнними через вказiвники потребує великої ретельностi i охайностi при проектуваннi програм. Зокрема, потрiбно звiльняти видiленi пiд динамiчнi змiннi областi одразу пiсля того, як необхiднiсть у них вiдпадає, iнакше “забруднення” пам’ятi непотрiбними диамiчними змiнними може привести до швидкого її вичерпання.

Крiм того, необхiдно враховувати ще одну проблему, пов’язану з протирiччям мiж стековим принципом розмiщення статичних змiнних i довiльним характером створення i знищення динамiчних змiнних.

Розглянемо наступний схематичний приклад програми:

Type

PtrAnk = ^Anketa;

Anketa = Record

...

End;

Procedure GetAnketa;

var

P: PtrAnk;

Begin

P: New (PtrAnk)

End;

Begin

WriteLn(MemAvail);

GetAnketa;

WriteLn(MemAvail)

End.

Виклик New в процедурi GetAnketa веде до вiдведення пам’ятi для динамiчної змiнної типу Anketa. Вказiвник на цю змiнну присвоюється змiннiй P. Розглянемо ситуацiю, яка створюється пiсля виходу з процедури GetAnketa.

За правилами блочностi всi локальнi змiннi пiдпрограми перестають iснувати пiсля її за вершення. В цьому випадку зникае локальна змiнна P. В той же час, область пам’ятi, яка вiдведенна в процесi 0виконання процедури GetAnketa продовжує iснувати, бо звiльнити її можна тiльки явно, через процедуру Dispose. Таким чином, пiсля виходу iз GetAnketa вiдсутнiй будь-який доступ до динамiчноїзмiнної, оскiльки вказiвник на неї вiдсутнiй.

При проектуваннi програм, якi iнтенсивно використовують динамiчну пам’ять необхiдно уважно вiдноситись до даної проблеми та, або вчасно звiльняти пам’ять, або, в разi потреби, запам’ятовувати вказівника на динамiчнi змiннi.

3.2. Рекурсивні типи даних

Існують аналогії проміж методами структурування алгоритмів та методами структурування даних.

Елементарним неструктурованим оператором являється оператор присвоювання. Відповідний йому тип даних – простий, скалярний, неструктурований (тип вважається скалярним, якщо всі його значення впорядковані – це всі стандартні, а також перелічимий).

Оператор присвоювання та прості типи даних являються атомарними будівельними блоками для складних типів даних.

Аналог складеного (Begin... End) – запис, обидві структури складаються з кінцевої кількості компонент.

Щоб описати повторення, число яких відоме і кінцеве, використовують цикл з параметром For; аналог – структура масив. Вибір з двох або більше варіантів виконується умовним оператором вибору; аналог структури даних – запис з варіантами.

Циклам While i Repeat, які допускають потенціально нескінченне число повторень, відповідає структура даних – файл.

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

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

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

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

3.3. Списки

3.3.1. Лінійні однозв’язні списки

Лінійний список – це послiдовнiсть однотипних елементів, що розташовані лінійно один за одним та пов’язаних вказівникми.

Кожна змінна списку являє собою запис, оскільки складається мінімум з двох компонент: ідентифікуючого ключа (значення) та вказівника на попередній елемент.

Список може бути порожнім.

Опис типу елемента списку може мати вигляд:

Type

list = ^elem;

elem = Record

key: integer;

next: list;

.......... {інша можлива інформація}

End;

Var p,q: list;

………………………………..

Правила мови тільки при описі вказівників допускають використання імені (elem) до його опису.

Приклад списку у схематичному виглядi:

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

Базисними операціями для списку є:

– створення порожнього списку;

– перевірка на порожність;

– перевірка існування попереднього та наступного елементів;

– призначення поточним першого, останнього, попереднього, наступного елементів;

– заміна поточного елемента із списку на деяке значення базисного типу;

– вилучення поточного елементу із списку;

– включення елементу базисного типу у список перед поточним елементом або після нього.

Список, кожен елемент якого зсилається на попереднiй, називається однозв’язним.

Для того, щоб у списку змінити послiдовнiсть записів, достатньо поміняти місцями лише значення вказівників, самi ж елементи списку залишаються на своїх мiсцях. З цієї точки зору над елементами списку зручно робити потужні операції, пов’язані з переставленням, наприклад, сортування.

Побудова списку

Починаючи з порожнього списку, включаючи елементи у початок списку, можна побудувати список з n елементів наступним чином:

{Побудова списку з n елементів.}

{q – допоміжна змінна зсилочного типу}

{n – ідентифікуючий ключ 4,3,2,1}

{p – вказівник на список }

Type

list = ^elem;

elem = Record

key: integer;

next: list;

End;

Var

p,q: list;

n: integer;

Begin

n:=4;

p:=Nil; {створити порожній список}

While n>0 Do

Begin

New(q);

q^.key:=n;

q^.next:=p;

p:=q;

n:=n-1

End;

Writeln(‘Список створено ‘);

End.

Процес створення списку можна представити схематично наступним чином:

– на першому кроці при P=Nil маємо порожній список:

– при n=4:

New(q); q^.key:=n; q^.next:=p; p:=q;

– при n=3 (поетапно):

New(q);

q^.key:=n;

q^.next:=p;

p:=q;

тобто p – тепер вказівник на новий елемент списку, який є заголовним елементом списку, і т.д.

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

Елементарні дії із списками – включення та вилучення елементів, перегляд списку (або прохід по списку).

Прохід по списку

Основна операція із списком – прохід по списку (з метою виконання будь-якої операції з кожним елементом списку).

Описується наступним чином:

While p<>Nil Do

Begin

p(p^);

p:=p^.next

End;

Тут p(p^) – будь – які дії з кожним елементом списку.

(Поки вказівник на наступний елемент не дорівнює Nil, виконати потрібні дії з елементом списку, перейти до наступного елементу).

Включення у список після елемента, вказівник на який відомий.

Елемент, на який вказує вказівник q, необхідно включити у список після елемента, на який вказує вказівник p.

Елемент q повинен посилатися на той, на який посилається p, тобто:

q^.next:=p^.next;

Елемент p повинен посилатися на q, тобто:

p^.next:=q;

Включення у список перед елементом, вказівник p^ на який відомий.

Щоб включити новий елемент перед елементом з ключем 5, необхідно знати вказівник на нього, але він невідомий. Можна включити елемент після нього, а потім як би поміняти їх місцями.

New(q);

q^:=p^; {усі поля змінної q отримають значення змінної p}

p^.key:=8;

p^.next:=q; {поля змінної p отримають значення змінної q}

Вилучення із списку

Вилучення із списку здійснюється аналогічно включенню.

Якщо p – заголовний елемент списку, то

p^.next – адреса другого елементу списку,

(p^.next)^.next – адреса третього елементу списку і т.д.

Наприклад– вилучити із списку перший елемент:

q:=p;

p:=p^.next;

Dispose(q);

Пошук у списку за заданим ключем x

..........................

b:=true;

While (p<>Nil) and b Do

If p^.key=x Then b:=false

Else

p:=p^.next;

..........................

If Notb Then <є такий елемент>

Else <такого елемента немає>;

{p=Nil or Notb} – умова виходу з циклу.

Задача. Складання частотного словника

Після зчитування тексту визначається список різних вхідних у нього слів та вказується частота їх появи у тексті.

Опис алгоритму:

– кожне чергове слово, що прочитане у тексті, шукається у списку;

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

– якщо немає слова у списку, воно додається у нього.

{Пошук з включенням у список}

Uses Crt;

Type

ref = ^Wword;

Wword = Record

key: integer;

count: integer;

next: ref

End;

Var

k: integer;

root: ref;

Procedure Search (x:integer; Var root:ref);

Var

w: ref;

b: boolean;

Begin

w:=root;

b:=true;

While (w<>Nil) and b Do

If w^.key=x Then b:=false

Else w:=w^.next;

If b Then

Begin

{новий елемент}

w:=root;

New(root); {формується адреса нової вершини}

With root^ Do

Begin

key:=x;

count:=1;

next:=w

End

Else

w^.count:=w^.count+1

End; {Search}

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

Procedure Printlist (w:ref);

Begin

While w<>Nil Do

Begin

Writeln (w^.key,’ ’, w^.count);

w:=w^.next

End

End; {Printlist}

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

Begin

ClrScr;

root:=Nil;

Writeln(‘Введіть текст’);

Read(k);

While k<>0 Do

Begin

Search(k, root);

Read(k)

End;

Printlist(root);

Repeat Until KeyPressed

End.

Процедура Printlist – приклад проходу по списку.

Процедура пошуку нагадує пошук у масивах та файлах. При пошуку у списку можна також використовувати фіктивний елемент чи бар’єр.

Більш ефективно робити пошук в упорядкованому списку, так як перегляд завершується одразу ж після знаходження елементу. Упорядкованості списку можна досягти завдяки включенню нових елементів при створенні списку не у початок, а у відповідні в залежності від значення ключа місця.

Завдяки легкості включення в зв’язаний список упорядкованість забезпечується майже без додаткових витрат. Масиви та файли такої можливості не надають.

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

{Включення елемента d у вiдповiдне мiсце списка p, таким чином, щоб список був упорядкованим за зростанням значень}

Procedure Add_Element (Var p:Point_typ; d:Data_typ);

Var

q: Point_typ;

Begin

If p=Nil Then

Begin

New (q);

q^.next:=Nil;

q^.data:=d;

p:=q;

End

Else

If p^.data>d Then

Begin

New (q);

q^.next:=p;

q^.data:=d;

p:=q;

End

Else

Add_Element (p^.next,d)

End;

3.3.2. Двозв’язні та кiльцевi списки

Лінійний список, в якому кожний елемент має вказівник на наступний, називається односпрямованим або однозв’язним списком.

По односпрямованому списку можна рухатися тільки в одному напрямку, що при розв’язанні задач може викликати незручності.

Двоспрямованим або двозв’язним списком називається динамічна структура, кожен з елементів якої має вказівник як на наступний, так і на попередній елемент.

Опис типу для елементу двоспрямованого списку може мати вигляд:

Type

List=^T;

T = Record

key: integer;

next: List;

pred: List

End;

aбо

Type

T = Record

key: integer;

next: ^T;

pred: ^T

End;

Двозв’язний список завдяки двом вказівникм надає можливість рухатися по списку у будь-якому напрямку.

Двозв’язні та однозв’язні списки часто узагальнюють наступним чином: замість Nil останнього елементу використовують вказівник на заголовний елемент, або навпаки.

Такі списки мають назву кільцевих.

3.3.3. Черги і стеки

Обмежуючи набір базисних операцій над списками, можна отримати такі структури даних, як черги та стеки.

Структура даних – черга – використовується для моделювання реальнiх черг з ціллю визначення їх характеристик (середня довжина черги, час перебування заказа у черзі, ймовірність відмови поставити у чергу, якщо вона задовга і т.д.), так і при вирішенні інших задач, не пов’язаних з реальними чергами. По своїй суті черга являється динамічним об’єктом – з часом і довжина черги змінюється, і набір елементів, з яких вона складається.

Над чергою визначені дві операції:

– занесення у чергу

– вибір з черги

В черзі доступні дві позицїї: початок і кінець.

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

– FIFO – first input first output - першим обслуговується елемент, що був першим занесений.

Такі черги у програмуванні використовуються досить рідко, називаються так само - черги;

– LIFO - last input first output - першим обслуговується елемент, що був занесений останнім.

Такі черги називаються стеки, або магазини.

У стеку доступна тільки одна позиція – вершина стека – позиція, у якій знаходиться останній за часом надходження у стек єлемент. Значенням вказівника на стек являється вказівник на вершину стека. Кожен елемент стека має вказівник на наступний елемент.

Элемент, який був записаний у стек самим першим, має вказівник Nil.

Опис елемента стека аналогічний опису елемента списку:

Type

stack:=^elstack;

elstack:= Record

elem: integer;

next: stack

End;

Занесення єлемента в стек

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

{занесення в стек}

Procedure Instack (Var st:stack; Newelem:integer);

Var

q: stack;

Begin

New(q);

q^.elem:=Newelem;

q^.next:=st;

st:=q

End;

Вибір елемента із стека

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

{ вибір зі стека }

Procedure Forstack (Var st:stack;Var a:integer);

Var

q: stack;

Begin

If st=Nil Then

Writeln (‘стек пустий’)

Else

Begin

a:=st^.elem;

q:=st;

st:=st^.next;

dispose(q)

End

End;

Приклад:

Заданий рядок символів, признаком кінця являється точка. У рядку можуть бути дужки (,{,[. Перевірити баланс дужок.

Баланс дужок витримується якщо:

– для кожної вікриваючої дужки є закриваюча;

– відповідні пари дужок різних типів правильно вкладені одна в одну { [()] }, а не [{(])).

Як результат вивести повідомлення про дотримання балансу та рядок, або рядок до першого по порядку порушения балансу дужок.

Пропонується наступний алгоритм з використанням стека:

– створити пустий стек

– занести першу відкриваючу скобку в стек, другу і т.д.

– якщо потім зустрінеться закриваюча дужка, вибрати із стека відкриваючу, порівняти, якщо відповідають – видалити із стека відкриваючу, якщо ні – не виконується друга умова балансу

– якщо в момент вибору із рядка чергової закриваючої дужки стек виявився пустим, або, навпаки, після завершення вводу символів рядку стек не вичерпано, – не виконана перша умова балансу дужок.

{ Перевірка балансу дужок у рядку літер }

Uses Crt;

Type

tipelem = char;

stack =^elstack;

elstack = Record

next: stack;

elem: tipelem;

End;

Var

sym: char;

s: stack;

b: boolean;

{————————————————————}

Procedure Instack (Var st:stack; Newelem:tipelem);

Var

q: stack;

Begin

New (q);

q^.elem:=Newelem;

q^.next:=st;

st:=q

End;

{————————————————————}

Procedure Forstack (Var st:stack; Var a:tipelem);

Begin

a:=st^.elem;

st:=st^.next;

End;

{————————————————————}

Function Corresp:boolean;

Var

r: char;

Begin

Forstack (s,r);

Case sym of

‘)’: Corresp:= r=’(‘;

‘]’: Corresp:= r=’[‘;

‘}’: Corresp:= r=’{‘

End

End;

{————————————————————}

Begin

ClrScr;

s:=Nil;

Read (sym);

b:=true;

While (sym<>’.’) and b Do

Begin

Write (sym);

If sym in [‘(‘, ‘[‘, ‘{‘] Then

Instack (s,sym)

Else

If sym in [‘)’, ‘]’, ‘}’] Then

If (s=Nil) or (not Corresp) Then b:=false;

Read (sym);

End;

Writeln;

If Notb or (s<>Nil) Then

Writeln (‘балансу дужок немає’)

Else

Writeln (‘баланс дужок є’);

Repeat Until KeyPressed

End.

3.4. Деревовидні структури

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

Записи – вершини, або вузли.

Вказівники – ребра, або гілки.

Окремий випадок графу – дерево.

де:

A – корінь

А,Б,В,Ж – вершини, або вузли

Г,Д,Е,З,І,К – листки

А Б \

А В – ребра, або гілки

Б Г /

….

Дерево, як і список, є рекурсивною структурою.

Список можна визначити наступним чином: список може бути або порожнім, або складається з вузла (елемента списку), який містить в собі вказівник на список.

Дерево – або порожнє, або складається з вузла, який містить вказівники на дерева, що не перехрещуються.

Списки можна з однаковою легкістю обробляти як рекурсивними, так і ітеративними алгоритмами.

Дерева набагато легше обробляти за допомогою рекурсивних алгоритмів.

Список також має назву виродженого дерева.

Верхній вузол дерева має назву корінь дерева.

Вузел y, який знаходиться безпосередньо під вузлом x має назву (безпосереднього) нащадка x. Якщо x знаходиться на рівні i, то y знаходиться на рівні i+1. Вузел x по відношенню до вузла y має назву (безпосереднього) предка.

Корiнь дерева розміщений на рівні 1. Максимальний рівень, на якому знаходиться елемент (найнижчий) має назву глибини або висоти дерева.

Елемент, який немає нащадків, називається термінальним, або листком.

Елемент, який н