Контрольні запитання

1. Що таке іменований тип?

2. Наведіть порівняльну характеристику індексованого та іменованого типів.

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

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

Лабораторні робота 2.4

ДОСЛІДЖЕННЯ ЛІНІЙНИХ ТА НЕЛІНІЙНИХ СТРУКТУР ДАНИХ

Мета лабораторних робіт - вивчити можливості та особливості створення та обробки лінійних та нелінійних структур даних.

Теоретичні відомості

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

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

Стек – це структура даних, яка побудована на метафорі «магазин автомату» або «трубка з одним відкритим кінцем» та забезпечує доступ до елементів тільки з одного кінця за дисципліною «Перший увійшов – останній вийшов» - Firstin – Lastout (LIFO). Стек забезпечує дві операції з його елементами - «помістити» - Push, та «витягнути» - Pop. Один й той же елемент може бути витягнутий зі стеку тільки один раз, коли він знаходиться на вершині.

Рис 2.1. Стек

Черга – це структура даних, яка побудована на метафорі «черга обслуговування» або «однонаправлена трубка з двома відкритими кінцями» та забезпечує дисципліну «Перший увійшов – перший вийшов» - Firstin – Firstout (FIFO). Черга забезпечує дві операції з його елементами – «Помістити у чергу» - Enqueue та «Взяти з черги» - Dequeue. Елемент може бути взятий з черги тільки один раз.

Рис. 2.2 Черга

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

Рис. 2.3 Зв’язаний список

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

Рис. 2.4 Дерево

Завдання

Написати програми, які складаються з наступних дій:

1. Опису структури даних, використовуючи пойменований тип, згідно з варіантом (табл.2.5).

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

3. Опису змінної індексованого типу з 10 елементів вказаного у варіанті типу даних (табл. 2.5) та її ініціювання.

4. Для векторного представлення – ініціювання, а для зв’язаного – ініціювання та створення, N елементів описаної структури даних, використовуючи змінну індексованого типу, що описана в п.3 даного завдання, де N – це ціле значення з діапазону від 0 до 9.

5. Видалення M елементів з описаної структури даних, де M – це ціле значення з діапазону від 0 до 15. Виконується тільки для лінійних структур даних.

Примітка 1: при ініціюванні структури даних необхідно аналізувати її переповнення. При видаленні елементів – їх відсутність.

6*. Студенти, що бажають отримати за виконане завдання оцінку «відмінно», створюють структуру даних у зв’язаному представленні не із таблиці варіантів(табл. 2.5), а із додаткового переліку (табл. 2.5а) за домовленістю із викладачем:

Таблиця 2.5

№ варіанта	Структура даних	Тип даних
1	“Стек” векторне представлення	Дійсний
	“Черга” зв’язане представлення	Цілий
2	“Черга” векторне представлення	Символьний
	“Односпрямований список” зв’язане представлення	Цілий
3	“Черга” векторне представлення	Символьний
	“Стек” зв’язане представлення	Дійсний
4	“Стек” векторне представлення	Дійсний
	“Односпрямований список” зв’язане представлення	Цілий
5	“Односпрямований список ” векторне представлення	Символьний
	“Стек” зв’язане представлення	Цілий
6	“Односпрямований список” векторне представлення	Дійсний
	“Черга” зв’язане представлення	Цілий
7	“Стек” векторне представлення	Дійсний
	“Черга” зв’язане представлення	Символьний
8	“Черга” векторне представлення	Символьний
	“Односпрямований список” зв’язане представлення	Цілий
9	“Черга” векторне представлення	Цілий
	“Стек” зв’язане представлення	Дійсний
10	“Стек” векторне представлення	Дійсний
	“Односпрямований список” зв’язане представлення	Символьний
11	“Односпрямований список ” векторне представлення	Цілий
	“Стек” зв’язане представлення	Символьний
12	“Односпрямований список” векторне представлення	Дійсний
	“Черга” зв’язане представлення	Цілий
13	“Стек” векторне представлення	Цілий
	“Черга” зв’язане представлення	Символьний
14	“Черга” векторне представлення	Символьний
	“Односпрямований список” зв’язане представлення	Дійсний
15	“Черга” векторне представлення	Цілий
	“Стек” зв’язане представлення	Символьний

Таблиця 2.5а

№ варіанта	Структура даних	Тип даних
1	“Дек” зв’язане представлення	Дійсний
2	“Двоспрямований список” зв’язане представлення	Цілий
3	“Бінарне дерево” зв’язане представлення	Символьний
4	“Дек” зв’язане представлення	Символьний
5	“Двоспрямований список” зв’язане представлення	Дійсний
6	“Бінарне дерево” зв’язане представлення	Цілий