МІНІСТЕРСТВО освіти и науки України
Національний технічний університет України В«КПІВ»
Кафедра МЕДИЧНОЇ кібернетики та телемедицини
Лабораторна робота № 1
Тема: динамічні структури данних
Варіант № 16 (Задачі № 16.13 (а), 16.18 (а), 16.33).
Виконала:
студент ІМ-81
Плахтій Артур Миколайович
Перевірів:
старший викладач
Зінченко Ніна Павлівна
Київ 2009
теоретичність частина
1. Динамічні структури даних
Раніше досліджувані типи даних відносяться до так званих статичним. Пам'ять під них виділяється під час компіляції, кількість таких об'єктів не змінюється під час виконання програми. Однак існує ряд завдань, де статичні структури неефективні. У мові Паскаль є засоби створення динамічних структур даних, які дозволяють під час виконання програми:
В· утворювати об'єкти;
В· виділяти для них пам'ять;
В· знищувати, коли в них зникає необхідність.
Інша назва динамічної пам'яті - купа.
Для отримання ясного уявлення про динамічних змінних треба розглянути структуру пам'яті під час виконання програми на мові Паскаль (див. рис.1).
Дані в динамічній пам'яті розміщують з використанням покажчиків. Покажчик - це посилання на певну комірку пам'яті, починаючи з якої записується значення змінної, тому дані такого типу називаються ще й посилальним типом даних.
<p> Формат опису посилального типу даних:
Type <тип покажчика> = ^ <ідентифікатор типу>,
тобто покажчик пов'язаний з деяким типом даних. Такі покажчики називаються типізований.
Приклад опису змінних посилального типу:
Type
p1 = ^ integer;
p2 = ^ real;
Var
A, B, C: p1;
X, Y, Z: p2;
P: char;
Cсилочние змінні A, B, C вказують на динамічні об'єкти цілого типу, X, Y, Z - речового, P - символьного. Значенням посилальної змінної є адреса в динамічно виділеної пам'яті, де зберігається об'єкт цього типу.
Рис. 1. Структура пам'яті під час виконання програми
Для звернення до посилальної змінної використовують запис "A ^", що означає: "йти по адресою, що зберігається в A ". Пам'ять під покажчики відводиться на етапі компіляції.
Однак в Турбо Паскалі можна оголошувати покажчик і не пов'язувати його з конкретним типом даних. Такий покажчик називається нетипізовані. Для його оголошення служить стандартний тип pointer. Структура і тип таких даних можуть змінюватись під час виконання програми.
При роботі з покажчиками обов'язкові етапи два:
1. оголошення покажчика;
2. формування динамічних даних, пам'ять яких відводиться під час виконання програми.
Для роботи з вказівниками використовуються такі процедури:
New (P) - процедура, яка створює в динамічної пам'яті нову змінну. Р - покажчик змінної того типу, який треба створити. Кожна окрема процедура new може створити тільки одну динамічну змінну.
Dispose (P) - процедура, що дозволяє повернути в купу ділянку пам'яті, зайнятий об'єктом з покажчиком Р.
Параметрами процедур new і dispose може бути тільки типізований покажчик. Для роботи з нетипізований покажчиками використовуються аналогічні процедури:
GetMem (P, Size) - резервування пам'яті;
FreeMem (P, Size) - звільнення пам'яті.
Тут Р - нетипізований покажчик, Size - розмір в байтах необхідної або визволеної частини купи (до 65521 байт).
Над покажчиками можуть бути визначені операції перевірки на рівність і присвоювання (рис.2):
Рис. 2. Допустиме присвоювання
Приклад.
Var x, y: ^ integer;
Begin
new (x); {породжуємо динамічний об'єкт цілого типу}
x ^: = 13; {за адресою x заносимо значення 13}
y: = x; {в у заносимо значення того ж адресами, що і х}
writeln (y ^);
end.
посилальної змінної може бути присвоєної "порожнє" значення адреси, позначене службовим словом nil, що означає, що посилальна змінна не вказує ні на один динамічний об'єкт. Це присвоювання можна робити до виконання процедури new. Значення nil - Це два нульових слова. Воно може бути присвоєно покажчику будь-якого типу.
Динамічно розміщення дані можна використовувати в будь-якому місці програми, наприклад:
Var a, b, c = ^ Real;
Begin a ^: = sqr (b ^) + c ^ -17;
Неприпустимо писати a: = sqr (b ^), так як покажчику не можна привласнити значення речового вираження.
2. Лінійні списки. Стек, чергу
Покажчики є ефективним засобом побудови списковому структур, до яких відносяться, в Зокрема, лінійні списки.
Лінійний список - це безліч, що складається з змінного числа вузлів X [1], X [2], ... , X [n].
Структурні властивості такого списку:
1. Якщо n> 0, то Х [1] є першим вузлом;
2. Якщо 1
3. Х [n] є останнім вузлом.
Серед можливих списковому структур виділяють деякі спеціальні списки.
Стек - це лінійний список, у якому всі включення і виключення (і звичайно всякий доступ) робляться в одному кінці списку
Наочний приклад стеків: стопка підносів в їдальні, залізничний тупик. Стеки використовуються в роботі алгоритмів, що мають рекурсивний характер. Кінець стека називається вершиною стека. Принцип роботи стека - "останній прийшов - перший вийшов". Внизу знаходиться найменш доступний елемент. Часто говорять, що елемент опускається в стек.
Черга - це лінійний список, в один кінець якого додаються елементи, а з іншого кінця виключаються. Принцип роботи черзі: "перший прийшов - перший вийшов".
3. Організація списків у динамічній пам'яті
Для організації списків використовуються структури типу запис, що складаються з двох частин: інформаційної, де власне і знаходяться дані, і посилальної, що містить покажчик на наступний елемент списку (рис.1). Cоздадім в динамічній пам'яті структуру:
Рис. 1. Приклад списковому структури
де Di - дані. Щоб отримати доступ до даних, достатньо зберігати в пам'яті адресу початку цього списку nach.
У мові Турбо Паскаль послідовно проводиться принцип, згідно з яким, ідентифікатор, перед його використанням, повинен бути описаний. Виняток зроблено тільки для покажчиків, які можуть посилатися на ще не оголошений тип даних. Для опису елементів структури подібної зображеної на рис. 3 можна використовувати Наступного контрольний тип:
Type element = ^ Ptr;
Ptr = record
d: integer;
link: element;
end;
Список в динамічній пам'яті можна створювати в прямому або зворотному порядку (щодо послідовності вводяться елементів).
Приклад створення списку у зворотному порядку (Див. рис.2):
Рис. 2. Приклад створення списку у зворотному порядку
Var i, n, a: integer;
tek, nach: Ptr;
Begin
tek: = nil;
readln (n);
for i: = 1 to n do
begin
readln (a);
new (nach);
nach ^. d: = a;
nach ^. link: = tek; {ланцюжок приєднується до nach}
{*} tek: = nach;
end;
end;
Звернемо увагу на виклик процедури new (nach). В результаті цього виклику в динамічній пам'яті відводиться місце для змінної типу record, яка в нашому випадку складається з двох полів: для зберігання цілочисельного значення і значення покажчика, тобто адреси. Тут важливо уявляти, що після того, як змінна nach (або яка інша) створена в динамічній пам'яті, тим самим маємо її адресу, який сам є ім'ям змінної, тобто nach. Якщо у нас є інша змінна того ж типу, tek, то ми знаємо ...
