_TPLab_My_Посібник

Функція MaxAvail:Longint - повертає розмір найбільшої неперервної вільної області (блоку) в купі. Купа формується випадковим чином і є послідовністю зайнятих і незайнятих ділянок пам'яті. Тому в різних випадках результатом даної функції може бути різне значення.

Функція MemAvail:Longint - повертає розмір всієї вільної пам'яті в купі. Наприклад:

Begin

Writeln (MemAvail, 'байт вільно ');

Writeln ('Найбільший вільний блок містить ', MemAvail,' байт ');

End.

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

Процедура GetMem (Var p: Pointer; Size: Word) - створює динамічну змінну розміру Size (виділяючи для неї пам'ять розміром Size байтів) і записує її адресу у вказівник р будь-якого посилального типу. Самий великий блок, який може бути безпечно розподілений в купі за один виклик процедури GetMem, рівний 65528 байт (64К-$8) (Фаронов В.В. вказує інший розмір – 65521 байт, Павловская Т.А. – 65520 байт).

Процедура FreeMem (Var p: Pointer; Size: Word) - звільняє пам'ять вказаного розміру, зайняту динамічною змінною і знищує цю змінну. Процедуру FreeMem не можна використовувати спільно з

Mark чи Release.

Примітка: Не можна поєднувати GetMem і Dispose, або FreeMem і New.

Процедури та функції керування динамічною пам'яттю.

Функція MemAlloc (Size:Word):Pointer - розподіляє пам'ять в купі і повертає вказівник на блок. Якщо блок вказаного розміру не може бути розподілений, то повертається значення NIL.

Процедура Mark (Var p:Pointer) - записує стан купи у вказівник - вказівнику присвоюється значення, яке вказує на вершину купи. Не може використовуватись спільно з FreeMem чи Dispose.

Процедура Release (Var p:Pointer) - повертає купу в заданий стан. Не може використовуватись спільно з

FreeMem чи Dispose.

Наприклад:
Var	p: Pointer;
pl, p2, p3: ^Integer;
Begin
New (p1); {Розподіляємо пам'ять під Integer}
Mark (p); {Зберігаємо стан купи}
New (р2); {Розподіляємо пам'ять ще під два числа}
New (рЗ);
Release(p);{Пам’ять, розподілена під р2^ та рЗ^,		}
	{звільняється, а пам'ять, розподілена під р1^, }
End.	{ все ще може використовуватись	}

Функція SizeOf (<тип>) - цій функції як параметр передається змінна або її тип; результатом є число байтів, необхідних для зберігання даноїзмінної або змінних даного типу.

If MaxAvail >= SizeOf (pi) Then pi New (pin);

Функція Addr (<параметр>): Pointer - повертає адресу свого параметру (будь-якої змінної або ідентифікатора процедури чи функції).

Функція Seg (<параметр>):Word - повертає значення сегментної частини адреси свого параметру (будьякої змінної або ідентифікатора процедури чи функції) в пам'яті.

Функція Ofs (<параметр>):Word - повертає значення зміщення свого параметру (будь-якої змінної або ідентифікатора процедури чи функції) в пам'яті.

91

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Функція Ptr (Seg, Ofs:Word):Pointer - перетворює свій параметр-адресу в значення вказівника, який вказує на адресу Seg : Ofs.

Наприклад:

p1:= Ptr ($1234,$4567);

If Byte (Ptr ($40, $49)^) = 7 Then WriteLn (' Повідомлення ');

Функція Sseg:Word; - повертає поточне значення регістру SS, яке є сегментною частиною адреси сегменту стеку.

Функція SPtr:Word; - повертає зміщення вказівника на вершину стеку всередині сегменту стеку

Функція CSeg:Word; - повертає поточне значення регістру CS, яке є сегментною частиною адреси сегменту коду, в якому булла викликана функція CSeg.

Функція DSeg:Word; - повертає поточне значення регістру DS, яке є сегментною частиною адреси сегменту даних.

При опрацюванні масивів можна використовувати як масив вказівників, так і вказівник на масив. Потрібно враховувати, що масив вказівників розміщується в статичній пам'яті і займатиме 4N байт (N - довжина масиву). Більшого ефекту в економії пам'яті можна досягти, використавши вказівник на масив і розподіливши під нього динамічну пам'ять процедурою GetMem(р, N*SizeOf(<mun>)), де N і тип - відповідно кількість і тип компонент масиву.

Приклади.

Задача 1. Програма виведення на екран символів за їх кодом, використовуючи вказівники.

Program Point_1;

Uses Crt;

Var рх:^Char; і: Byte;

Begin Clrscr;

New (px);

For i 0 To 255 Do Begin

px^ Chr(i); Write(i:3,'=',px^);

End;

Dispose (px);

Repeat Until Keypressed; End.

Задача 2. Програма введення та виведення на екран елементів масиву, використовуючи вказівники.

Program Point_2;

UsesCrt;

Type

Vect = Array[1..10] Integer;

Var

px:^Vect; i: Byte;

Begin Clrscr;

New (px);

For i l To 10 Do Begin

Writeln(' Введіть елемент масивуN ', i, '');

Readln (px^[i]);

End;

Writeln('Вміст масиву:');

92

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

For i l To 10 Do Write (px^[i]:3);

Dispose(px);

Repeat Until Keypressed;

End.

ДИНАМІЧНІ МАСИВИ.

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

Type Mas = Array [ Word ] OF Byte;

компілятор видасть повідомлення про помилку - Error 22: Structure too large (структура дуже велика). Нехай, наприклад, необхідно забезпечити доступ до елементів матриці дійсних чисел розміром

100x200 типу Extended [18, С. 161].

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

Var

і, j: Integer;

PtrArr: Array[1..100, 1..200] Of ^Real;

Begin

For i l To 100 Do For j l To 200 Do

New (PtrArr[ij]);

……………………….

End.

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

PtrArr [1,1]^:=0;

If PtrArr [l,j*2]^ > 1 Then...

Але згадаємо, що довжина внутрішнього представлення вказівника рівна 4 байти. Таким чином, для розміщення масиву PtrArr необхідно 100x200x4=80 000 байт, що також перевищує розмір сегменту даних, доступний для розміщення статичних змінних.

Виходом з цього стану могло би стати використання адресної арифметики, тобто арифметики над вказівниками, тому що в такому випадку можна було б відмовитись від створення масиву вказівників PtrArr і обчислювати адресу будь-якого елементу матриці безпосередньо перед звертанням до нього. Але ж в Turbo Pascal над вказівниками не визначені ніякі операції, крім операцій присвоювання і відношення.

Тим не менше, розв'язати таку задачу все таки можна.

Відомо, що будь-який вказівник містить адресу об'єкта, яка складається з двох слів типу Word для зберігання сегменту і зміщення. В Turbo Pascal визначені дві вбудовані (стандартні) функції Seg та Ofs типу Word, за допомогою яких можна одержати значення цих слів. Аргументом цих функцій може бути будь-яка змінна, в тому числі і та, на яку вказує вказівник.

Наприклад, якщо маємо

VarPr:^Real; Begin

…………….

New (Pr);

Pr^ 3.14;

……………..

End

то функція Seg (Pr) поверне сегментну частину адреси, за якою розміщується вказівник Рг, а функція Seg (Pr^) поверне сегментну частину адреси 6-байтної ділянки купи, де зберігається число 3,14.

93

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

З іншого боку за допомогою вбудованої функції Ptr (Seg, Ofs) можна створити значення вказівника, сумісне із вказівниками будь-якого типу.

Тепер розв'язати вказану задачу можна, наприклад, наступним чином.

Спочатку процедурою GetMem з купи забираються декілька фрагментів пам'яті потрібного розміру (довжини). Для нашої задачі зручно резервувати фрагменти такої довжини, щоб в них могли розміститись рядки матриці, тобто 200x10=2000 байт. Початок кожного фрагменту, тобто фактично початок розміщення кожного рядку, запам'ятовується в масиві PtrStr, який складається із 100 вказівників. Тепер для доступу до будь-якого елементу рядка потрібно обчислити зміщення цього елементу від початку рядка і сформувати відповідний вказівник:

Const SizeOfReal= 6;

Var

i,j : Integer;

PtrStr: Array [1.100] Of Pointer; Pr : Real;

Begin

For i:=l To 100 Do

GetMem (PtrStrf [і], SizeOfReal*200);

…………………………………

{Звертання до елементу матриці [i, j]}

Pr Ptr (Seg(PtrStr[і]^), Ofs(PtrStr[і]^)+ (j-1)* SizeOfReal);

If Pr^ >1 Then...

……………………………………

End.

Оскільки оператор обчислення зміщення Pr:=Ptr... буде використовуватись в програмі неодноразово, то доцільно ввести допоміжну функцію GetR, яка повертала б значення елемента матриці, і процедуру PutR, яка присвоювала б елементу нове значення. Кожна з них, в свою чергу, буде звертатись до функції Addrr для обчислення адреси.

Приклад. Програма формування матриці NxM випадкових чисел і обчислення їх середнього арифметичного значення[18, С. 163].

Const SizeQfReal = 6; {довжина змінної типу Real} N= 100; {кількість рядків матриці} М= 200; {кількість стовпців матриці}

Type RealPoint = ^Real; Var i,j: Integer;

s: Real;

PtrStr: Array [1..N] Of Pointer; Function AddrR (i, j: Word): RealPoint;

{ За сегментом і та зміщенням j видає адресу дійсної змінної }

Begin

AddrR: = Ptr (Seg (PtrStr[і]^), Ofs (PtrStr [i]^)+(j-l)*SizeOfReal)

	End;	{AddrR}
Function GetR(і,j: Integer) : Real; {Видає значення змінної }
	Begin		{ за сегментом і та зміщенням j її адреси}
				Видає значення елементів тільки останнього рядка
		GetR := AddrR (i, j)^
	End;	{GetR}
Procedure PutR (і,j: Integer; х: Real);
{ Присвоює змінній, адреса якої має сегмент і та зміщення j, } { дійсне значення х
}	Begin
		AddrR (i, j)^ x
	End;	{PutR};
Begin		{Main}
94	For і 1 To N Do

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Begin

GetMem (PtrStr[i], M*SIzeOfReal);

{Виділення пам’яті для рядка матриці}

For j 1 To M Do PutR (i, j, Random)

{Генерування значень елементів і-го рядка}

End; s := 0;

For і 1 To N Do

For j 1 To M Do s s + GetR (i, j);

{Обчислення суми значень елементів матриці} Writeln(s/(N * M):12:10) {Друк значення середнього}

End. {Main}

ПРИМІТКА. У розглянутому прикладі передбачається, що кожний рядок матриці розміщується в купі, починаючи із границі параграфа, і зміщення для кожного вказівника PTRSTR дорівнює нулю. У дійсності при послідовних звертаннях до процедури GetMem початок чергового фрагменту слідує відразу за кінцем попереднього і може не потрапити на границю сегменту. У результаті, при розміщенні фрагментів максимальної довжини (65 521 байт) може виникнути переповнення при обчисленні зміщення останнього байта.

КОНТРОЛЬНІ ЗАПИТАННЯ.

1.Що буде результатом виконання наступних дій: p^:=q^;

If p=q Then p:=Nil

Else If p^=q^ Then q:=p;

If p=q Then q^:=4;

Writeln (p^)

2.Дано опис змінних. Var p, q: ^ Integer; r : ^Char; Які з наступних операторів неправильні і чому?

І) a) p:=q, b) q:=r, c) p:=Nil, d) r:=Nil, e) q:=p^, f) p^:=Nil.

ІІ) a) r^:=p^, d) If q<>Nil Then q^:=p^, b) If q=p Then Write (q), c) If q<>r Then Read (r^).

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ.

Завдання 1.

1.В програмі опрацювання масиву (завдання 2 лабораторної роботи №4) згенерувати масив великого розміру (1000x1000)тарезультати компіляції програми подати в звіті.

2.Модифікувати програму, використавши вказівники.

3.Результати компіляції (відеокопію екрану) подати в звіті.

4.Перед запуском на виконання програму ще раз модифікувати – згенерувати масив невеликої розмірності (від 10х10),щобзабезпечитивиконанняпрограмизакороткийчас.

95

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

ЛАБОРАТОРНА РОБОТА № 11 Проектування та відлагодження програм опрацювання однозв’язаних списків даних.

МЕТА РОБОТИ: Навчитись проектувати алгоритми та програми опрацювання абстрактних типів даних – однозв’язаних списків.

ЗАВДАННЯ:

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

МЕТОДИЧНІ ВКАЗІВКИ

4.Перед виконанням роботи необхідно пригадати:

логічну структуру програми на мові Turbo Pascal;

правила опису простих та структурованих типів даних;

правила запису виразів;

синтаксис основних операторів;

синтаксис опису та правила застосування стандартних (бібліотечних) процедур і функцій;

правила розподілу пам'яті при виконанні програми;

правила опису вказівників;

способи ініціалізації вказівників;

способи доступу до змінної за вказівником;

допустимі операції над вказівниками;

процедури та функції керування динамічною пам'яттю;

процедури та функції створення, опрацювання та знищення динамічних змінних;

5.Перед виконанням цієї роботи необхідно вивчити:

правила опису та способи організації однозв’язаного списку;

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

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

ВІДОМОСТІ З ТЕОРІЇ.

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

Динамічні структури даних мають дві особливі властивості, які відрізняють їх від статичних структур даних:

1)наперед невідома кількість елементів структури;

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

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

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

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

Відзначимо, що динамічні структури даних відносяться до абстрактних типів даних (АТД), для

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

96

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

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

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

адресної – містить поля, які є вказівниками (посиланнями) на інші елементи структури, наприклад, на попередній і наступний елементи.

У найпростішому випадку елемент динамічної структури даних повинен складатися з двох полів:

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

Head Info Link

Info Link

Info Nil

…

Рисунок 1. Схема найпростішої динамічної структури.

Зображена на Рис.1 структура може бути оголошена наступним чином:

Type TInfo= <ім’я_типу> {тип інформаційного поля може бути} {довільним – стандартним або попередньо описаним}

TLink = ^TList;	{ вказівник на тип список	}
TList = Record	{ тип елементів списку	}
Info: TInfo;	{ інформаційна частина	}

Next:TLink{поле вказівника на наступний елемент}

End;

Var Head: TLink; {вказівник на перший елемент списку}

Правило послідовності описів у Turbo Pascal вимагає, щоб кожен ідентифікатор був описаний, перш ніж він буде використовуватися для інших оголошень. Однак у наведеному прикладі, як би не розміщувалися описи типів покажчика TLink і елемента TList, це правило виконане не буде. Тому для опису типів елементів динамічних структур даних зроблений виняток. Тип покажчика на елемент динамічної структури даних може і повинний бути описаний перед описом типу цього елемента.

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

До основних видів динамічних структур даних відносяться лінійні зв’язані структури – списки,

черги, стеки, деки і нелінійні зв’язані структури – дерева і мережі.

Лінійні структури мають багато спільного:

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

-максимальна кількість елементів структури обмежується об’ємом оперативної пам’яті (ОП);

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

New, GetMem, FreeMem і Dispose;

-лінійна структура має «хвіст», вказівник якого має значення NIL і «голову» (вершину), яку звичайно адресує вказівник (заголовок) стека, черги чи списку;

-якщо «голова» і «хвіст» лінійної структури зв’язані між собою, то така структура називається

кільцевою.

Примітка. За загальноприйнятою термінологією «головою» (вершиною) лінійної структури є останній доданий до неї елемент. Тому, на відміну від «живої» черги людей, початком лінійної структури є її голова (останній елемент), а кінцем – хвіст (перший елемент).

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

СПИСКИ.

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

Означення 2. Лінійний список – це множина скінченного числа пов’язаних між собою та лінійно впорядкованих (послідовно організованих) елементів даних, в якій порядок елементів визначається їх адресною частиною.

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

97

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

До різновидів зв’язаних списків відносяться також ХОР-зв’язаний список, розгорнутий зв’язаний список та список з пропусками.

Математична модель лінійного списку (за А.В.Ахо) представляється у вигляді послідовності L(List) з n ≥ 0 однорідних елементів

L = (a1, a2, a3, …, an),

лінійно впорядкованих так, що: a) при n >0:

першим елементом є a1;

останнім елементом є an;

кожен елемент ai має позицію і;

для всіх 1<i<n та для ai існує попередній елемент ai-1 та наступний ai+1;

n називається довжиною списку;

b)при n = 0 список є порожнім (не містить елементів);

c)постулюється існування позиції, яка слідує за останнім елементом списку (наприклад, можна створити функцію END(L), яка буде повертати позицію, наступну за позицією n в n-елементному списку).

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

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

«Але не існує однієї множини операторів, виконуваних над списками, яка би задовольняла одночасно всі застосунки.» [7,С.46]

Тому для кожного способу реалізації (представлення) структури типу «список» необхідно задавати відповідну множину операторів.

Визначимо множину базових операцій над списками:

1. Початкове формування списку: створення першого елемента;

2. Вставка в список нового елемента:

a)елемент х вставляється в задану позицію р, зміщуючи всі елементи від позиції р в наступну, більш високу позицію:

a1, a2, …, ap-1, x, ap+1, …, an;

b)елемент х вставляється перед або після елемента із заданим ключем.

c)елемент х вставляється в кінець списку:

a1, a2, a3, …, an, x

3.Локалізація (пошук) в списку елемента із заданим ключем х: визначення позиції елемента, якщо такого елемента в списку немає, то видається відповідне повідомлення;

4.Визначення (зчитування) елемента, який знаходиться на заданій позиції р: результат операції невизначений, якщо позиції р в списку немає або р = END(L);

5.Видалення зі списку елемента за ключем чи за позицією;

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

7.Знищення списку шляхом звільнення ОП: р = END(L);

8.Виведення всіх елементів списку;

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

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

СПОСОБИ РЕАЛІЗАЦІЇ СПИСКІВ.

Списки можна організовувати за допомогою масивів, вказівників та курсорів. Кожна з цих структур реалізує операції над списками по різному і з різною ефективністю.

РЕАЛІЗАЦІЯ ОДНОЗВ’ЯЗАНОГО СПИСКУ ЗА ДОПОМОГОЮ МАСИВУ.

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

98

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

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

Схема такого списку зображена на Рис.2.

1-й елемент

2-й елемент

Список

Last Останній елемент

Вільні комірки

Рисунок 2. Реалізація списку за допомогою масиву.

Описати такий список можна наступним чином:

Const Length = 100;

Type TInfo = <ім’я_типу> { тип елементів списку}

TList = Record

Info: Array [1.. Length] Of TInfo; Last: Integer

End; Var List: TList;

Позиція елемента списку визначається номером (індексом) компоненти масиву, тобто конструкція List.Info[i] визначає i-й елемент списку. List.Last – довжина списку.

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

1. Початкове формування списку.

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

Procedure ListInitialize (Var L: TList);

Var i: Integer;

Begin

For i 1 To Length Do

Begin

Write ('List.Info[', i, ']=');

{ присвоювання значень елементам масиву}

Readln (L.Info[i]);

L.Last[i] i

End

End;

2. Вставка в список нового елемента.

a) Вставка нового елемента x на р-у позицію здійснюється в два етапи: по-перше, всі значення з компонент масиву Info з індексами р,р+1,…,Last переміщуються відповідно в компоненти з індексами р+1, р+2,…,Last+1; по-друге, в р-у компоненту поміщається елемент x, а значення поля Last збільшується на одиницю.

Procedure Insert (x: TInfo; p: Integer; Var L: TList); Var i: Integer;

Begin

If L.Last >= Length Then Write (' Помилка – список повний '); If ((p>L.Last+1) Or (p<1))

Then Write (' Помилка – неіснуюча позиція ')

99

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Else Begin

For i L.Last DownTo p Do L.Info[i+1] L.Info[i];

{ Переміщення елементів на одну позицію до кінця списку}

L.Las L.Last + 1; L.Info[p] x;

End;

End; { Insert }

b)Для вставки елемента х перед або після елемента із заданим ключем необхідно знайти відповідну компоненту масиву, визначити її номер (індекс) та виконати процедуру Insert.

c)Вставка елемента х в кінець масиву:

L.Info[Last] x;

L.Last L.Last + 1;

3. Локалізація в списку заданого елемента х.

Procedure Locate (x: TInfo; Var L: TList; Var p: Integer); Var i: Integer;

Begin

For i 1 To L.Last Do

If L.Info[i] = x Then p i

Else Write ('Такого елемента не існує ');

End; {Locate}

4. Видалення елемента зі списку.

a)Процедура Delete (p:Integer; Var L:TList) переміщує значення із компонент р+1, р+2,…, Last в

компоненти р, р+1,…, Last -1 та зменшує довжину списку на одиницю.

b)Процедура Delete (x:TInfo; Var L:TList) визначає позицію р – індекс компоненти масиву із заданим значенням х і переміщує значення із компонент р+1, р+2,…, Last в компоненти р, р+1,…, Last -1 та зменшує довжину списку на одиницю.

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

РЕАЛІЗАЦІЯ СПИСКУ ЗА ДОПОМОГОЮ ВКАЗІВНИКІВ.

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

Схема лінійного однозв’язаного списку зображена на Рис.1, а нижче приведено один з можливих описів такого списку. Як видно на схемі, в списку є заголовок (Head), який вказує на перший елемент списку, кожен елемент списку містить адресну частину із вказівником на наступний елемент, адресна частина останнього елемента містить вказівник Nil, який не вказує ні на який елемент.

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

Спроектуємо процедури та функції для реалізації базових операцій над однозв’язаним списком, використавши його опис, приведений на с.165 (після Рис.1).

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

Реалізація базових операцій над списком.

1. Початкове формування списку: створення першого елемента.

Var x: TInfo; { інформаційна частина нового елемента }

Read (x);

100

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)