Лабораторна робота 2.12 дослідження абстрактних типів даних
Теоретичні відомості
Абстрактний тип даних (АТД) дозволяє визначити дані програми та процедури, які здійснюють обробку цих даних як єдиний абстрактний інкапсульований програмний об’єкт. Абстрактний тип даних може бути створений різними шляхами, один з яких є використання процедурного типу (Паскаль) або покажчика на функцію (Сі). Визначення АТД на процедурному рівні містить запис (структуру), яка містить поля з визначеннями даних та посилання на підпрограми, які реалізують обробку цих даних.
Процедурні типи у мові Паскаль та покажчики на функції у мові С можуть використовуватися для гнучкого використання підпрограм. Це дозволяє визначити абстрактну процедуру або функцію (за допомогою синтаксису, аналогічному заголовку підпрограми) без визначення тіла підпрограми. Процедурний тип потім може бути використаний для визначення відповідної процедурної змінної та привласнення їй будь-якої процедури або функції, яка має такий самий список параметрів. Ті ж самі операції, що і з процедурною змінною можна виконувати над покажчиками на функцію.
Паскаль:
<процедурний тип>::=<позначка типу>=procedure{ (<список формальних
параметрів) }0
< позначка типу>::=<ідентифікатор>
<список формальних параметрів>::=<формальний параметр>|
{;<формальний параметр>}0
<формальний параметр>::={var}0 < позначка формального параметру>:<опис
типу>
<позначка формального параметру>::= <ідентифікатор>
<опис процедури>::= procedure<позначка>{ (<список формальних параметрів) }0 <тіло>
Приклад:
Паскаль:
Type
Func=function(x,y:integer):integer; {Визначення процедурного типу Func }
Var
f1, f2 : func; { Об’ява змінної типу Func }
function Add( a, b : integer) : integer; { Визначення функції }
begin
Add := a + b;
end;
begin
……
f1 := Add; { Функція Add призначається процедурної змінній f1 }
…..
end.
Посилочна функція у мові С грає роль, подібну до процедурного типу у мові Паскаль. Приклад нижче показує посилочну функцію “process” з цілім типом результату та двома формальними параметрами .
int process ( (int*)func(int a, b))
{
…
}
Методичні вказівки
Кожна закрита підпрограма абстрактних типів даних повинна реалізовувати єдину концепцію.
Розглядайте операції абстрактних типів даних (АТД) тільки як конструктори, селектори та ітератори.
Сформулюйте порівняльні характеристики для АТД, що реалiзовані на мовах Паскаль та Сі, перевірте їх на прикладах програм лабораторної роботи.
Завдання
Написати програми на мовах Паскаль та Сі, які складаються з наступних дій:
Опису елемента структури даних згідно з варіантом (табл. 2.32).
Опису абстрактного типу даних (АТД) згідно з варіантом (табл. 2.32).
Реалізації АТД:
запису до АТД декілька значень („операція_1”);
читання з АТД декілька значень („операція_2”).
Таблиця 2.32
№ варіанта |
Мова |
Склад АТД |
||||||
Структура даних |
Тип значення структури даних |
„Операція_1” |
„Операція_2” |
|||||
|
|
Паскаль |
“Черга” зв’язане представлення |
Цілий |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Стек” векторне представлення |
Символьний |
||||||
|
|
Паскаль |
“Дерево” зв’язане представлення |
Дійсний |
Запис одного значення |
Послідовний обхід |
|||
Сі |
“Черга” векторне представлення |
Символьний |
Запис одного значення |
Читання одного значення |
||||
|
|
Паскаль |
“Стек” зв’язане представлення |
Дійсний |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Черга” векторне представлення |
Цілий |
||||||
|
|
Паскаль |
“Дерево” зв’язане представлення |
Символьний |
Запис одного значення |
Паралельний обхід |
|||
Сі |
“Стек” векторне представлення |
Дійсний |
Запис одного значення |
Читання одного значення |
||||
|
|
Паскаль |
“Стек” векторне представлення |
Цілий |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Черга” зв’язане представлення |
Дійсний |
||||||
|
|
Паскаль |
“Черга” векторне представлення |
Символьний |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Стек” зв’язане представлення |
Дійсний |
||||||
|
|
Паскаль |
“Черга” векторне представлення |
Символьний |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Дерево” зв’язане представлення |
Цілий |
Запис одного значення |
Обхід у ширину |
||||
|
|
Паскаль |
“Стек” векторне представлення |
Цілий |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Дерево” зв’язане представлення |
Дійсний |
Запис одного значення |
Послідовний обхід |
||||
|
|
Паскаль |
“Черга” зв’язане представлення |
Дійсний |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Стек” векторне представлення |
Цілий |
||||||
|
|
Паскаль |
“Дерево” зв’язане представлення |
Символьний |
Запис одного значення |
Паралельний обхід |
|||
Сі |
“Черга” векторне представлення |
Цілий |
Запис одного значення |
Читання одного значення |
||||
|
|
Паскаль |
“Стек” зв’язане представлення |
Символьний |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Черга” векторне представлення |
Дійсний |
||||||
|
|
Паскаль |
“Дерево” зв’язане представлення |
Цілий |
Запис одного значення |
Обхід у ширину |
|||
Сі |
“Стек” векторне представлення |
Символьний |
Запис одного значення |
Читання одного значення |
||||
|
|
Паскаль |
“Стек” векторне представлення |
Дійсний |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Черга” зв’язане представлення |
Цілий |
||||||
|
|
Паскаль |
“Черга” векторне представлення |
Дійсний |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Стек” зв’язане представлення |
Символьний |
||||||
|
|
Паскаль |
“Черга” векторне представлення |
Цілий |
Запис одного значення |
Читання одного значення |
|||
Сі |
“Дерево” зв’язане представлення |
Дійсний |
Запис одного значення |
Послідовний обхід |
||||