_TPLab_My_Посібник

Procedure ListFirst (Var x: TInfo; Var PtrHead: TLink);

Var Temp: TLink; { вказівник на новий елемент }

Begin

New (Temp); {створюємо новий елемент}

Temp^.Info x; {заповнюємо його інформаційну частину} Temp^.Next Nil; {список був порожній, тому }

{адресна частина першого елемента рівна Nil }

PtrHead Temp

{заголовок списку вказує на перший елемент}

End;

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

a) Вставка нового елемента на початок списку:

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

Read (x);

Procedure InsertFirst (Var x: TInfo ; Var PtrHead: TLink);

Var Temp: TLink; { вказівник на новий елемент }

Begin

New (Temp); {створюємо новий елемент}

Temp^.Info x; {заповнюємо його інформаційну частину}

If PtrHead=Nil Then {якщо список порожній}

Begin

PtrHead Temp;

Temp^.Next Nil

	End
Else
	Begin
	Temp^.Next PtrHead;			(1)
	PtrHead		Temp	(2)
End; {InsertFirst}	End

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

в адресну частину (поле вказівника) записується вказівник на «старий» перший елемент (оператор 1);

заголовок списку стає вказівником на «новий» перший елемент (оператор 2).

Head

Info Next

Info Nil

…

2

1

Temp

Info Next

Рисунок 3. Схема вставки нового елемента на початок списку.

На рис.3 і далі пунктирними стрілками зображені нові зв’язки між елементами списку, а цифрами позначені відповідні оператори процедури.

b) Вставка нового елемента після заданої позиції в списку.

Var n: Integer; {порядковий номер елемента списку}

Read (n);

Procedure InsertNumberRight (Var n:Integer; Var x: TInfo ; Var PtrHead: TLink);

Var Temp: TLink; { вказівник на новий елемент } Ptr: TLink; { вказівник для перегляду списку }

found: Boolean; { ознака локалізації шуканого елемента} i: Integer; { лічильник кількості елементів списку }

Begin

New (Temp); {створюємо новий елемент}

101

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

Temp^.Info x; {заповнюємо його інформаційну частину}

Ptr PtrHead; found False; i 1;

While (Ptr <>Nil) And Not (found) Do

If i=n Then found True {елемент знайдено} Else {перехід до наступного елемента }

Begin

Ptr Ptr^.Next; i i+1

End;

If found Then {вставка елемента після заданої позиції }

	Begin	Next
	Temp^.				Ptr^.Next;	(1)
	Ptr^.Next			Temp		(2)
	End

Else Write(‘Такого номера не існує, вставка не виконана’)

End; { InsertRight }

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

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

в адресну частину нового елемента записується вказівник, який був в адресній частині локалізованого (заданого) елемента, тобто вказівник на наступний елемент списку (оператор 1);

в адресну частину локалізованого елемента записується вказівник на новий елемент (оператор 2). Схема такої вставки (включення «справа») зображена Рис.4.

Head	I	II	n
	Info Next	Info Next	Info Nil

…

2

1

Temp

Info Next

Рисунок 4. Схема вставки нового елемента в список.

Процедуру вставки нового елемента після (справа) заданої позиції (номера елемента в списку) призначена і для вставки нового елемента в кінець списку. Для цього необхідно задати номер останнього елемента списку.

c) Вставка нового елемента після елемента із заданим ключем.

Ptr

key

(Head)

Info

Info

1

…

Next

Next

Ptr^.Next

x

Temp

Info

2

Next

Temp^.Next

Рисунок 5. Схема вставки нового елемента після елемента із заданим ключем.

102

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

Var key: TInfo; {значення ключового поля}

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

Read (key); Read (x);

Procedure InsertKeyRight (Var key, x: TInfo; Var PtrHead: TLink);

Var Temp: TLink; { вказівник на новий елемент } Ptr: TLink; { вказівник для перегляду списку }

found: Boolean; { ознака локалізації шуканого елемента}

Begin

New (Temp); {створюємо новий елемент}

Temp^.Info x; {заповнюємо його інформаційну частину}

Ptr PtrHead; found False;

While (Ptr <>Nil) And Not (found) Do

If Ptr^.Info= key Then found True {елемент знайдено} {вказівник, який міститься в його адресній частині } { вказує на наступний елемент списку}

Else Ptr Ptr^.Next;

If found Then {вставка нового елемента після заданого }

Begin

Temp^.Next Ptr^.Next; Ptr^.Next Temp

End

Else Write(‘Такого елемента не існує, вставка не виконана’)

End; { InsertKeyRight }

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

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

Temp^.Next := Ptr^.Next;

Ptr^.Next := Temp;

Temp^.Info := Ptr^.Info;

Ptr^.Info:= x;

d) Вставка нового елемента в кінець списку.

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

Read (x);

Procedure InsertEnd (Var x: TInfo ; Var PtrHead: TLink);

Var Temp: TLink; { вказівник на новий елемент } Ptr: TLink; { вказівник для перегляду списку }

Begin

New (Temp); {створюємо новий елемент}

Temp^.Info x; {заповнюємо його інформаційну частину}

Temp^.Next Nil;

If PtrHead=Nil Then PtrHead Temp {список порожній}

Else {список не порожній}

Begin

Temp PtrHead;

{ проходимо список до кінця}

103

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

While (Ptr^.Next <>Nil) Do Ptr Ptr^.Next; Ptr^.Next Temp;

{зв’язуємо останній елемент з новим}

End

End; {InsertEnd}

3.Локалізація (пошук) елемента в списку.

a)Локалізація елемента із заданим ключем.

Procedure LocateKey (Var key: TInfo; Var PtrHead: TLink);

Var Ptr: TLink; { вказівник для перегляду списку }

found: Boolean; { ознака локалізації шуканого елемента}

Begin

Ptr PtrHead; found False;

n 1; {номер шуканого елемента, глобальна змінна}

While (Ptr <>Nil) And Not (found) Do

If Ptr^.Info=key Then found True {елемент знайдено}

Else Begin

Ptr Ptr^.Next; n n+1

End;

If found Then PtrHead Ptr

Else Write(‘такого елемента не існує’)

End. { LocateKey }

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

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

по-перше, при перегляді (проході) списку зберігати попередній вказівник Previous, тобто вказівник на локалізований елемент, і для видалення локалізованого елемента виконати переадресацію за наступною схемою:

Previous^.Next Ptr^.Next;

Dispose(Ptr); {збирання сміття}

по-друге, видалити наступний елемент за локалізованим, попередньо переславши вміст його інформаційної частини до інформаційної частини локалізованого елемента:

Temp:= Ptr ^.Next;

(1)

{ допоміжний вказівник також вказує на наступний елемент}

Ptr^.Info:= Ptr^.Next^.Info;	(2)
{ в інформаційну частину локалізованого	елемента	}

{ записуємо інформаційну частину наступного елемента }
Ptr ^.Next := Ptr ^.Next^.Next;	(3)
{ в адресну частину локалізованого елемента записуємо		}
{ вказівник з адресної частини наступного елемента,		}

{ тобто вказівник на наступний-наступний елемент списку }

Dispose(Temp);

(4)

{ звільняємо пам'ять, розподілену для наступного елемента }

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

104

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

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

Ptr				Ptr^.Info			Ptr^.Next^.Info
(Head)							2
			Info		key			Info		Info	…
			Next		Next			Next		Next

Ptr^.Next 3

Info 1

Temp Next

Temp^.Next

Рисунок 6. Схема видалення елемента із заданим ключем.

a) Видалення елемента із заданим ключем.

Procedure DelKey (Var key: TInfo; Var PtrHead: TLink);

Var Ptr: TLink; { вказівник для перегляду списку } Temp: TLink; { допоміжний вказівник }

found: Boolean; { ознака локалізації шуканого елемента}

Begin

Ptr PtrHead; found False;

While (Ptr <>Nil) And Not (found) Do

If Ptr^.Info=key Then found True {елемент знайдено} Else Ptr Ptr^.Next;

If found Then Begin

Temp:= Ptr ^.Next; Temp^.Info:= Ptr^.Next^.Info; Ptr ^.Next := Ptr ^.Next^.Next; Ptr ^.Info := Temp^.Info; Dispose(Temp) {збирання сміття}

End

Else Write(‘такого елемента не існує’)

End. { DelKey }

Примітка. В процедурах формування списку та вставки нових елементів доцільно використати вбудовану функцію MaxAvail для перевірки наявності вільної динамічної пам’яті, наприклад, таким чином:

Procedure ListFirst (Var x: TInfo; Var PtrHead: TLink);

Var Temp: TLink; { вказівник на новий елемент }

Begin

If MaxAvail>=SizeOf(x) Then

{ вільної пам’яті є достатньо }

Begin

New (Temp);

Temp^.Info x;

Temp^.Next Nil;

PtrHead Temp

End

Else Write(‘не вистачає пам’яті’)

End;

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

105

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

Program Spisоk;

{Декларативна частина – опис всіх типів, змінних і процедур} {--------------------------- Головна програма --------------------------}

Begin

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

{Процедура виведення сформованого списку }

ozn true; { ознака закінчення роботи }

While ozn Then Do Begin

Write (‘Введіть код операції зі списком:’); Writeln (‘1 - вставка, 2 - пошук, 3 - видалення’); Write (‘код = ’);

Read (cod);

Case cod Of

1: Begin { вставка }

Write (‘Значення нового елемента x=’); Read (x);

Write (‘Номер елемента, після якого ’) Write (‘вставити новий n=’); Read(n);

InsertNumberRight (n, x, Head)

End;

2: Begin { локалізація-пошук}

Write (‘Ключ шуканого елемента key=’); Read (key);

LocateKey (key, Head)

End;

3: Begin { видалення }

Write (‘Значення елемента key=’); Read (key);

DelKey(key,Head)

End End; {Case}

{Процедура виведення опрацьованого списку}

Write (‘Продовжити роботу? Так – 1, ні – 0: ’); Read (PressKey);

If PressKey=0 Then ozn=false

End {While_Do}

End. { Головна програма }

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

1.Чому списки називаються зв’язаними структурами даних?

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

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

106

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

4.В чому полягає відмінність операцій вставки нового елемента на початок та в кінець списку?

5.Що таке ХОР-зв’язаний список?

6.Яким чином організовується розгорнутий зв’язаний список?

7.Скільки операторів (які саме) необхідно використати для організації порожнього однозв’язаного списку?

8.Як необхідно модифікувати процедуру InsertRight для вставки нового елемента перед (зліва) елементом із заданим номером?

9.Процедура InsertKeyRight вставляє новий елемент після елемента із заданим ключем. Як можна модифікувати цю процедуру для вставки нового елемента перед елементом із заданим ключем?

10.Функція LocateKey локалізує перший з елементів із заданим ключем. Як можна модифікувати цю функцію для знаходження всіх елементів із заданим ключем?

11.Поясніть, чому процедуру DelKey не можна застосовувати для видалення останнього елемента списку.

12.Приведіть приклади використання однозв’язаних списків в інформатиці/програмуванні.

13.Приведіть приклади використання однозв’язаних списків в математиці.

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

Завдання 1.

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

a)формування списку – мінімум 5 елементів;

b)вставка нових елементів – мінімум 1 на задану позицію (на початок, в середину чи в кінець списку) та мінімум 1 зліва/справа елемента із заданим ключем;

c)пошук елемента (виведення на друк його інформаційної частини) - мінімум 1 за номером в списку та мінімум 1 за ключем;

d)видалення елементів – мінімум 1 із заданої позиції та мінімум 1 із заданим ключем.

Критерії для пошуку та видалення елементів списку сформулювати самостійно – наприклад, наприклад в списку студентів відшукати та видалити тих, хто має «трійку» з інформатики; в списку моделей комп’ютерів відшукати та видалити ті, об’єм оперативної пам’яті яких менший заданого тощо.

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

Варіанти списків:

1.Прізвища студентів з оцінками за іспити (мінімум 2).

2.Моделі комп’ютерів з тактовою частотою процесора та об’ємом оперативної пам’яті.

3.Моделі комп’ютерів з об’ємом оперативної пам’яті та ціною.

4.Моделі «вінчестерів» з ємністю та типом інтерфейсу.

5.Моделі «вінчестерів» з ємністю та ціною.

6.Моделі «вінчестерів» з типом інтерфейсу та ціною.

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

8.Модулі оперативної пам’яті з об’ємом та ціною.

9.Модулі оперативної пам’яті з типом пам’яті та об’ємом.

10.Моделі моніторів з дозволяючою здатністю та розміром за діагоналлю.

11.Моделі моніторів з дозволяючою здатністю та ціною.

12.Моделі моніторів з розміром за діагоналлю та ціною.

13.Моделі принтерів з типом друку та ціною.

14.Моделі аудіосистем з максимальною потужністю та ціною.

15.Моделі флеш-накопичувачів з ємністю та ціною.

16.Моделі DVD-дисків з ємністю та ціною.

17.Моделі відеоадаптерів з об’ємом відеопам’яті та ціною.

18.Моделі ноутбуків з розміром екрану та ціною.

19.Моделі ноутбуків з тактовою частотою процесора та ціною.

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

21.Моделі ноутбуків з тактовою частотою процесора та об’ємом відеопам’яті.

22.Моделі ноутбуків з розміром екрану та об’ємом відеопам’яті.

23.Прізвища абітурієнтів з назвою спеціальності та балами сертифікату.

107

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

24.Прізвища студентів з оцінкою з інформатики та назвою спортивної секції.

25.Види (версії) операційних систем з типом адресності та ціною.

26.Системи комп’ютерної алгебри з назвою виробника та ціною.

27.Системи комп’ютерної графіки з типом графіки та ціною.

28.Навчальні дисципліни з об’ємом годин та кількістю іспитів.

29.Підручники з математичних дисциплін з автором та роком видання.

30.Підручники з інформатики/програмування з автором та кількістю сторінок.

Завдання 2:

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

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

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

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

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

6.Створити процедуру сортування елементів однозв’язаного списку.

7.Створити програму злиття двох однозв’язаних списків.

108

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

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

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

ЗАВДАННЯ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Математична модель і множина базових операцій над двозв’язаними списками приведені в попередній лабораторній роботі.

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

Схема двозв’язаного списку зображена на Рис.1.

Current

	Info	Info	…	Info
Head	Next	Next		Nil
	Nil	Prev		Prev

Рисунок 1. Схема двозв’язаного списку.

109

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

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

Type TInfo= <ім’я_типу>		{ тип інформаційного поля }
TLink= ^TList;		{ вказівник на тип список	}
TList= Record		{ тип елементів списку	}
Info: TInfo;		{ інформаційна частина	}
Next,	{поле вказівника на наступний елемент}
Prev: TLink {поле вказівника на попередній елемент}
End;	{ вказівник на перший елемент списку }
Var Head,

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

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

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

Приведемо приклад процедури видалення елемента з двозв’язаного списку.

Procedure Del_Element (Var PtrHead, PtrCurrent: TLink);
Var Temp: TLink; { допоміжний вказівник }
Begin
If PtrCurrent<>Nil Then { поточний елемент існує }
Begin {1}
If PtrCurrent = PtrHead Then { видаляємо перший }
			Begin {2}
						PtrHead^.Next;
			PtrHead
			PtrHead^.Prev						Nil;
			Dispose		(PtrCurrent);
			PtrCurrent					PtrHead
			End {2}
		Else { видаляємо не перший }
			Begin {3}
			If PtrCurrent^.Next=Nil Then
			{ видаляємо останній }
			Begin {4}
			PtrCurrent^.Prev^.Next							Nil;
			Dispose (PtrCurrent);
			PtrCurrent						PtrHead
			End {4}
Begin {5}			Else
{ видаляємо не перший і не останній }
	PtrCurrent^.Next;									(1)
Temp
PtrCurrent^.Prev^.Next					PtrCurrent^.Next; (2)
PtrCurrent^.Next^.Prev PtrCurrent^.Prev;										(3)
Dispose (PtrCurrent);										(4)
PtrCurrent			Temp							(5)
End; {5}			End; {3}

End; {1}

End; { Del_Element }

110

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