Лабораторна робота № 12.
Розробка програм з використовуванням
динамічних структури даних.
1. Мета роботи
1. Придбання навиків роботи з динамічною пам'яттю.
2. Вивчення методів роботи з динамічними структурами даних.
2. Зміст роботи
1. Вивчити основні теоретичні положення об організації динамічних структур даних (одно зв'язний і двох зв'язний список, стек, черга) і основні операції над ними.
2. Розробити алгоритм і скласти програму з використанням динамічних структур даних відповідно до індивідуального завдання. Підготувати контрольні тести і план відладки програми
3. Відладити програму і оформити звіт.
3. Зміст звіту:
1. Назва і мета лабораторної роботи.
2. Постановка задачі, блок-схема алгоритму і текст програми з промальовуванням зміни значень елементів динамічної структури і змінних, що використовуються, – покажчиків.
3. Результати, аналіз і висновки по реалізації Pascal-програми.
4. Короткі теоретичні відомості.
4.1. Статичні і динамічні змінні
При описі простих змінних і змінних типу масив, запис до виконання програми фіксується розмір значень, які можуть привласнюватися цим змінним, і відповідно розмір що виділяється для них пам'яті. Ці змінні називаються статичними.
Проте багато задач вимагають складніших інформаційних структур. Для таких задач характерний, щоб що використовуються в них структури створювалися і могли змінюватися в процесі виконання програми.
В мові Паскаль передбачена можливість створення змінних в процесі виконання програми. Знов створені і не оголошені наперед, змінні розміщуються на вільні ділянки в динамічній області оперативної пам'яті. Такий спосіб розподілу пам'яті називається динамічним. При цьому виділяється область пам'яті для окремих компонент у момент появи їх в процесі виконання програми, причому виділяється фіксований об'єм пам'яті для зберігання адреси (покажчика) динамічно розміщуваної змінної, а не самої змінної.
Змінні, які розміщуються в динамічній області оперативної пам'яті за допомогою покажчиків, називаються динамічними. На базі таких динамічних змінних звичайно створюються динамічні об'єкти з достатньо складною структурою.
4.2. Посилання і покажчики
Для встановлення і розриву зв'язків між динамічними даними в процесі виконання програми використовують новий тип даних — посилання, тобто адреси (розміром по 4 байти), по яких можна звертатися до даних. Змінні, значеннями яких є адреси, називаються покажчиками.
Покажчик — це елемент даних, що є посиланням (адреса) на певний елемент оперативної пам'яті.
Для оголошення покажчиків використовується спеціальний символ — ^, після якого указується тип динамічної змінної.
Турe <имя_типа>=^ <тип>;
Маючи в програмі визначення посилального типу, можна за загальними правилами описати змінні цього типу, як за допомогою ідентифікаторів, так і явно.
Var <имя_переменной> : <имя__типа>;
<имя_переменной> : ^ <тип>;
Наприклад:
|
Type |
ptr = ^integer; |
{ цей опис визначає безліч покажчиків на цілі значення } |
|
Var |
x, у: ptr; |
{ змінні посилального типу указують на змінні цілого типу } |
|
|
a: ^real; |
{ значення змінної а посилається (указує) на деяке значення дійсного типу } |
Значеннями змінних x, у є покажчики (адреси елемента пам'яті) областей пам'яті, виділених в програмі для змінних цілого типу, значенням змінної а є адреса елемента пам'яті для змінної дійсного типу.
Безпосередньо до значень динамічних змінних можна звернутися так: <ім'я_змінної > ^.
Тобто x^ — це посилальна змінна цілого типу, значення якої зберігається в тій динамічній області пам'яті, на яку указує значення змінної х.
Для привласнення значення динамічної змінної використовується звичайний оператор привласнення, наприклад: x^:=15 — в область пам'яті, на яку указує x, поміститься число 15.
Перш ніж виконувати якісь дії над динамічною змінною, необхідно помістити її в оперативну пам'ять. Це робиться за допомогою стандартної процедури New(x), де x — це покажчик на динамічну змінну.
Графічно це можна виразити так
|
Статична змінна |
Динамічна змінна | |||
|
x |
|
|
|
х^ |
Тут зберігається адреса В цій області пам'яті буде
змінною цілого зберігатися значення змінної
типу цілого типу
це покажчик це динамічна змінна
В результаті роботи цієї процедури створюється нова динамічна змінна, адреса її розміщення в оперативній пам'яті зберігається в х.
Якщо в процесі роботи динамічна змінна стає непотрібною, її потрібно видалити за допомогою процедури Dispose(x), яка звільняє пам'ять, зайняту динамічній змінній. При цьому значення її покажчика стає невизначеним
Необхідно виділити спеціальний стандартний покажчик, який нікуди не указує, тобто є порожнім (рівний адресі 0000:0000). Він позначається службовим словом NIL. Це значення говорить про відсутність динамічної змінної, тобто покажчику привласнено "порожнє посилання".
Отже, будь-які дії з покажчиком x передують процедурою New(x) і закінчуються процедурою Dispose (x).
Var x : ^<тип>
Begin
New(x);
-
Дії над покажчиком
Dispose (x) (значення динамічної змінної не визначено }
End.
Для визначення вмісту сегменту і зсуву об'єкту, а також розміру використовуються функції:
|
Функція |
|
Виконувані дії |
|
Seg(x) : Word |
- |
Повертає сегмент для переданого об'єкту |
|
Ofs(x) : Word |
- |
Повертає зсув для переданого об'єкту |
|
SizeOf(x) : Integer |
- |
Повертає кількість байт, займаних аргументом. В якості аргументу передається змінна або ім'я типу, розмір якого потрібно визначити |
Program p1;{ Визначення розміру типів даних і змінних}
var p_byte : ^byte; { указатель на byte }
Розмір Тип
(байт) byte1 Покажчикна byte 4 p_byte^
1 real
6 Покажчик
на real 4 p_real^
6
BEGIN
writeln('Тип Розмір (байт)');
writeln('byte':20,sizeof(byte):5);
writeln('Покажчик на byte':20,sizeof(p_byte):5);
writeln('p_byte^':20,sizeof(p_byte^):5);
writeln('real':20,sizeof(real):5);
writeln('Покажчик на real':20,sizeof(p_real):5);
writeln('p_real^':20,sizeof(p_real^):5); readln;
END.
Program p2;{Визначення вмісту сегментних регістрів і адрес змінних }
var a,b,c : word;
x,y,z :^integer;
{------- Процедура виводу слова в 16с/с (чотири 16-річних сімвола)---}
procedure WrHexW(w:Word);
const mas: array [0..$F] of char = '0123456789ABCDEF';
{ Функції Hi(w) і Lo(w) повертають відповідно старший і молодший байт аргументу w }
begin
Write (mas [Hi(w) shr 4], mas [Hi(w) and $F],
mas [Lo(w) shr 4], mas [Lo(w) and $F] );
end;
{--------------------------------------------------------}
Begin
new(x); x^:=17; new(y); y^:=-5; new(z); z^:=65;
write('Сегмент кода : CS --> '); WrHexW(CSeg); writeLn;
write('Сегмент даних : DS --> '); WrHexW(DSeg); writeLn;
write(' ':18,'a --> ');WrHexW(seg(a)); write(':'); WrHexW(ofs(a));
write(' b --> '); WrHexW(seg(b)); write(':'); WrHexW(ofs(b));
write(' c --> '); WrHexW(seg(c)); write(':'); WrHexW(ofs(c)); writeLn;
write(' ':18,'x --> ');WrHexW(seg(x)); write(':'); WrHexW(ofs(x));
write(' y --> '); WrHexW(seg(y)); write(':'); WrHexW(ofs(y));
write(' z --> '); WrHexW(seg(z)); write(':'); WrHexW(ofs(z)); writeln;
write('Сегмент стека : SS --> '); WrHexW(SSeg);
write(' SP --> '); WrHexW(SPtr); writeLn;
write(' ':6,'К у ч а : -----> '); WrHexW(OvrHeapOrg); writeLn;
write(' ':17,'x^ -->');WrHexW(seg(x^)); write(':');WrHexW(ofs(x^));
write(' y^ --> '); WrHexW(seg(y^)); write(':');WrHexW(ofs(y^));
write(' z^ --> '); WrHexW(seg(z^)); write(':');WrHexW(ofs(z^));writeLn;
x^:=x^+y^; write('x^=',x^); y^:=y^+12; write(' y^=',y^); z :=y;
write('z^=':5,z^,'z^-->':25); WrHexW(seg(z^)); write(':'); WrHexW(ofs(z^));
dispose(x); dispose(y); dispose(z); readln;
End.
{ Протокол роботи програми
Сегмент кода : CS --> 175E
Сегмент даних : DS --> 18EA
a --> 18EA:0062 b --> 18EA:0064 c --> 18EA:0066
x --> 18EA:0068 y --> 18EA:006C z --> 18EA:0070
Сегмент стека: SS --> 1918 SP --> 3FFC
К у ч а : -----> 1D18
x^ --> 1D18:0000 y^ --> 1D18:0008 z^ --> 1D19:0000
x^=12 y^=7 z^=7 z^ --> 1D18:0008}
Покажчики є ефективним засобом побудови динамічних структур даних (лінійні списки, стеки, черги і дерева).
Лінійний список — це лінійний набір (тобто послідовність) об'єктів (вузлів, елементів), які сполучені між собою за допомогою посилань (покажчиків). Програма дістає доступ до об'єктів через посилання на його перший об'єкт. До кожного з подальших об'єктів можна звернутися через посилання, що зберігається в попередньому об'єкті. Відповідно до угоди, посиланню в останньому об'єкті списку привласнюється значення nil, що відзначає кінець списку. Дані в лінійному списку зберігаються динамічно — кожний об'єкт створюється в міру необхідності. Об'єкти можуть містити дані будь-якого типу, у тому числі посилання на об'єкти інших типів.
Стеки і черги також відносяться до лінійних структур даних і є окремими випадками лінійного списку.
Дерева — це нелінійні структури даних.
Примітка. Списки даних можна берегти і в масивах, але лінійні списки мають деякі переваги. Вживання лінійних списків доречно у тому випадку, коли число елементів, які повинні бути представлені в структурі даних, наперед не відоме. Лінійні списки є динамічними структурами даних, тому довжина списку при необхідності може збільшуватися або зменшуватися. Розмір же «звичайного масиву» в Паскалі не може бути змінений, оскільки він фіксується у момент його створення програмою. «звичайні масиви» можуть бути заповнені повністю. Лінійні списки можуть «переповнюватися» тільки у разі, коли в системі недостатньо пам'яті для задоволення запитів на динамічне її виділення.