Лабораторна робота №8 Динамічні структури даних в мові Pascal
Мета: Засвоєння навичок опису та використання динамічні структур даних (списки, стеки, черги).
Обладнання: ПК, програмне забезпечення Turbo Pascal, методичні вказівки та завдання до лабораторної роботи.
Теоретичні відомості
До цих пір ми розглядали статичні змінні. Доступ до них відбувається за їх іменами, а тип визначається при описі цих змінних. Такі змінні автоматично створюються при вході в той блок програми, де вони описуються, і знищуються при виході з цього блоку. Існують крім статичних даних ще й динамічні, які на відміну від статичних створюються і знищуються тільки по спеціальним вказівкам програміста в процесі виконання програми. Динамічні дані теж мають тип, але не мають імені. Для доступу до динамічних даних існують спеціальні змінні, які називають вказівниками. Тип вказівник задається у вигляді:
^<тип динамічної змінної>;
Таким чином, кожній змінній типу вказівник буде приписаний тип тих динамічних даних, на які буде вказувати (посилатися) ця змінна. Значенням змінної такого типу є адреса в пам’яті першого байту, по якому записані дані.
Для створення динамічних змінних існує стандартна процедура
NEW (<змінна типу вказівник>);
де <змінна типу вказівник> отримує значення вказівник на створену на порожньому місці пам’яті динамічну змінну.
Приклад:
var p,q:^real;….
new(p); new(q);
Після виконання цих операторів в пам’яті буде відведено місце для зберігання двох дійсних чисел, а адреси цих місць будуть присвоєні відповідно змінним P і Q
P:
Q:
Тут знаки питання підкреслюють той факт, що у створених динамічних даних поки, що немає значення. Для доступу до динамічних даних використовується операція розіменування:
<змінна типу вказівника>^
Приклад:
P^:=3.1415; Q^:=-2*A^+1;
Після виконання цих операторів наша схема набуде такого вигляду
P
:
Q:
Видно, що змінні з вказівниками нічим не відрізняються від звичайних змінних (наприклад P^ – змінна дійсного типу)ї
Для знищення динамічних структур служить стандартна процедура
DISPOSE(<змінна вказівного типу>)
Тут <змінна вказівного типу> повинна вказувати нату динамічну змінну, яка знищується. Після виконання цієї процедури <змінна вказівного типу> отримує значення NIL, а пам’ять, відводилась під цю змінну, звільняється і може бути використана для розміщення нових динамічних даних.
Одним із застосувань динамічних даних в програмі є спискові структури. До них можна віднести списки, стеки, черги.
Списком називають впорядковану множину елементів одного типу. Списки можна зберігати послідовно і зв’язано. Прикладом послідовного зберігання списків є масиви. При зв’язаному зберіганні списку крім значень вузла зберігають ще вказівник на наступні елементи.
Тип елементів зв’язаного списку можна описати наступним чином:
tуре link=^sр;
sp=record
vаl:іnteger;
nехt:link;
end;
При зв’язаному зберіганні список досить легко створюється, причому наперед непотрібно задавати кількість елементів списку.
Функція, що створює список (функція без параметрів, повертає вказівник на початок списку):
Function Create_list:link;
var top, p,q:link;
с:сhar;
bеgin
write(‘Input the first element of list:’);
new(top);
readln(top^.val);
top^.next:=nil;
p:=top;
write(‘Will be next yet(Y\N)?’);
readln(c);
while (c=’Y’) do
begin
new(q);
p^.next:=q;
write(‘Input the element of list:’);
realn(q^.val);
q^.next:=nil;
p:=q;
write(‘Will be next yet(Y\N)?’);
readln(c);
end;
Create_list:=top;
End;
Процедура, яка друкує елементи списку (параметром процедури є вказівник на вершину списку):
Procedure Print_list (top:link);
Var p:link;
Begin
If (top<>nil) then
Begin
P:=top;
While(p<>nil) do
Begin
Write(p^.val,’’);
P:=p^.next;
End;
End
Else write(‘List is empty’)
End;
Процедура включення елементу v в кінець списку:
Procedure Add_end(top:link, v:integer);
Var p,q:link;
Begin
P:=top;
While(p^.next<>nil) do p:=p^.next;
New(q);
P^.next:=q;
Q^.val:=v;
Q^.next:=nil;
End;
Процедура добавлення вузла на початок списку:
Procedure Add_begin(top:link, v:integer);
Var p:link;
Begin
New(P);
p^.val:=v;
p^.next:=top;
top:=p;
End;
Процедура включення вузла в список після елемента, заданого вказівником p:
Procedure Add(p:link, v:integer);
Var q:link;
Begin
New(q);
Q^.val:=v;
Q^.next:=p^.next;
P^.next:=q;
End;
Процедура включення вузла в список перед елементом, заданим вказівником p:
Procedure Add1(p:link, v:integer);
Var q:link;
Begin
New(q);
Q^.val:=p^.val;
Q^.next:=p^.next;
P^.val:=v;
P^.next:=q;
End;
Процедура виключення елемента з списку, заданого вказівником p:
Procedure del(p:link; var top:link);
Var q:link;
Begin
Q:=top;
If (p=q) then top:=p^.next;
Else
Begin
While(q^.next<>p) do q:=q^.next;
Q^.next:=p^.next;
End;
End;
Функція пошуку елемента v в списку:
Function find(top:link; v:integer):Boolean;
Var p:link; f:Boolean;
Begin
P:=top; f:=false;
While((p<>nil) and (f=false)) do
Begin
If (p^.val=v) then f:=true;
P:=p^.next;
End;
Find:=f;
End;
Черга - це такий лінійний список, в якому вилучаються елементи тільки з початку списку, а додаються в його кінці. Прикладом є звичайна черга в магазині. Елементи черги описуються аналогічно елементам списку.
Створення черги повністю аналогічне створенню лінійного списку, так як при організації лінійного списку ми кожний наступний добавляли в кінець списку.
Включення елементів в чергу аналогічне включенню елемента списку в кінець. Вилучення елемента з черги здійснюється як вилучення початкового елемента списку.
Function del_ch (var top:link):integer;
Begin
Del_ch:=top^.val;
Top:=top^.next;
End;
Найчастіше в програмуванні приходиться мати справу зі стеками.
Стек — це лінійний список, де операції додавання і вилучення елемента та доступу до елемента виконуються тільки в його кінці. Стек можна подавати як купу книг на столі, де додати або взяти нову книжку можна лише зверху.
Елементи стеку можна описати наступним чином:
Type
Link=^st;
St=record
Val:integer;
Next:link
End;
Функція створення стеку. Результатом цієї функції буде вказівник на вершину стеку. function Create_stek^link;
Var top, p,q:link;
C:char;
Begin
Write(‘Input the element of stek’);
New(top);
Readln(top^.val);
Top^.next:=nil;
P:=top;
Write(‘Will be the next yet(Y\N) ?’);
Readln(c);
While (c=’y’) do
Begin
New(q);
Q^.next:=top;
Write(‘Input the element of stek’)
readln(q^.val);
top:=q;
writeln(‘Will be the next yet (Y\N)?’);
readln(c);
End;
Create_stek:=top;
End;
Процедура виводу елементів стеку:
Procedure Print_stek(top:link)
Var p:link;
Begin
If (top<>nil) then
Begin
P:=top;
While (p<>nil) do
Begin
Write(p^.val,’’);
P:=p^.next;
End;
End
Else
Writeln(‘Stek is empty’);
End;
Процедура вводу елемента з значенням v в стек:
Procedure Add_stek(var top:link; v:integer);
Var p:link;
Begin
New(p);
P^.val:=v;
P^.next:=top;
Top:=p;
End;
Процедура вилучення вузла з стеку:
Procedure Del_stek(var top:link);
Begin
Top:=top^.next;
End;
Порядок виконання роботи:
Створити алгоритм для розв’язування поставленої задачі.
Записати текст програми обробки динамічних структур даних згідно умови завдання;
Запустити програму на виконання і перевірити правильність роботи програми.
Відповісти на контрольні запитання та оформити звіт.
Контрольні запитання
Чим відрізняються статичні змінні від динамічних?
Що таке динамічна пам’ять?
Дати означення лінійного списку. Яку структуру мають елементи списку?
Які дії можна виконувати при роботі зі стеком, чергою?
Які покажчики потрібні при роботі зі стеком, чергою?
Звіт повинен містити:
Тему, мету, обладнання лабораторної роботи.
Завдання згідно варіанту.
Текст програми.
Результат виконання програми.
Аналіз допущених під час роботи помилок.
Відповіді на контрольні запитання
Висновки.
Викладач Смерека А.Г.
Завдання до лабораторної роботи №8
Варіант 1. Створити однозв’язний список. Замінити в ньому всі від’ємні елементи на протилежні їм. Видати результуючий список.
Варіант 2. Із заданого зв’язаного списку цілих чисел надрукувати всі нулеві елементи, якщо вони існують.
Варіант 3. Створити список цілих чисел. Замінити в ньому всі від’ємні елементи на нулі, додатні на одиницю збільшити.
Варіант 4. Створити список символів. Подвоїти всі букви латинського алфавіту в ньому. Вивести результуючий список.
Варіант 5. Створити лінійний однозв’язний список. Знайти максимальний елемент списку.
Варіант 6. Створити стек, елементами якого є цілі числа. Вивести елементи стеку.
Варіант 7. Задано цілочисельний лінійний список, що зберігається зв’язано. Надрукувати його елементи з додаванням одиниці до елементів.
Варіант 8. Задано цілочисельний лінійний список, що зберігається зв’язано. Надрукувати не нулеві елементи.
Варіант 9. Створити лінійний цілих чисел. Обчислити кількість входжень заданого числа в черзі.
Варіант 10. Створити стек з цілих чисел. Обчислити добуток елементів стеку і помістити результат в стек.
Варіант 11. Елементи заданого списку надрукувати в оберненому порядку. (Вказівка: використати стек, в який заносити елементи списку, а потім роздрукувати елементи стеку)
Варіант 12. Створити чергу цілих чисел. Здійснити циклічний зсув на одиницю вліво всіх елементів вліво.
Варіант 13 Створити чергу цілих чисел. Здійснити циклічний зсув вліво на n позицій.
Варіант 14. Створити чергу цілих чисел. Здійснити циклічний зсув вправо на n позицій.
Варіант 15. Організувати перевірку парності дужок при вводі виразу за допомогою стеку. Вказівка6 кожна ліва дужка заноситься в стек. Коли зустрічається права дужка, то із стеку вилучається одна. В кінці виразу перевіряється, чи стек порожній (помилки немає) чи стек не порожній (виникає помилка)
Лабораторна робота №1. Прості оператори мови С++.
Мета: Засвоїти структуру простої програми на мові С++, набуття навичок в організації вводу/виводу даних та створення програм з використанням лінійних операторів.
Обладнання: ПК, програмне забезпечення Borland С++, методичні вказівки та завдання до лабораторної роботи.