Питання до захисту :
У чому переваги і недоліки організації структур у вигляді стека?
Відповідь:____________________________________________________
_____________________________________________________________
У чому переваги і недоліки організації структур у вигляді черги?
Відповідь:____________________________________________________
_____________________________________________________________
Для моделювання яких реальних завдань зручно використовувати стек? А для яких чергу?
Відповідь:____________________________________________________
_____________________________________________________________
З якою метою в програмах виконується перевірка на порожнечу стека і черги?
Відповідь:____________________________________________________
_____________________________________________________________
Роботу виконав Роботу перевірив
Лабораторна робота №3 «Розробка програми створення зв'язаного списку»
1 Тема роботи: Використання зв'язаного список із записів, та реалізація операцій зі зв'язаним списком.
2 Мета роботи: Формування знань і умінь по роботі з динамічною пам'яттю. Придбання навичок роботи з динамічними структурами даних.
3 Теоретичний матеріал
Списком називається впорядкована множина, що складається із змінного числа елементів, до яких застосовні операції включення, виключення. Список, що відображає відносини сусідства між елементами, називається лінійним. Якщо обмеження на довжину списку не допускаються, то список представляється в пам'яті у вигляді зв'язної структури. Лінійні зв'язні списки є простими динамічними структурами даних.
Найчастіше вказівники використовуються для посилання на записи, тим самим досягається значна економія пам'яті. Якщо ж сам запис містить в собі поле-вказівник, який вказує на наступну за нею запис, то це дозволяє утворити пов'язані списки - структуру, в якій окремі записи послідовно пов'язані один з одним. У наведеному нижче прикладі використовуються записи, в яких поряд з даними про автомобіль є вказівник на наступний запис, завдяки чому виходить зв'язаний список (див. рис. 3.1)
Рисунок 3.1 – Зв’язаний список
Одне з полів кожного об'єкта пов'язаного списку має тип вказівник і вказує на черговий об'єкт в списку. Вказівник на перший об'єкт міститься в змінної First, а останній об'єкт має вказівник на Nil.
4 Хід виконання практичної роботи
Необхідно створити зв'язаний список із записів, що містять відомості про автомобілі, а також реалізувати операції зі зв'язаним списком: запис першим у списку, видалення першого об'єкта зі списку, перегляд усього списку, видалення об'єкта, наступного за вказаним.
Program point;
Uses Crt;
Type
NameStr = String [20];
Link = ^ Auto;
Auto = record
Name: NameStr; {Марка автомобіля}
Speed: real; {Швидкість}
Next: Link; {Поле для зв'язку з наступним об'єктом у списку}
end;
Var
Р, First: Link; {Вказівники на запис: поточну, першу}
NamFind: NameStr; {Марка автомобіля для пошуку}
V: 0 .. 4; {Селектор меню}
EndMenu: boolean; {Закінчення виведення меню}
{Пошук об'єкта з ім'ям FN, за результатами пошуку повертає вказівник на знайдений об'єкт або Nil, якщо об'єкт не знайдений}
Function FindName (FN: NameStr): Link;
Var
Curr: Link;
begin
Curr: = First; {Установити вказівник на першому об'єкті в списку}
{Повторювати поки не дійдемо до кінця списку}
while Curr <> Nil do
if Curr ^. Name = FN then {Якщо знайшли заданий об'єкт}
begin
FindName: = Curr; {Повертаємо значення вказівника на нього}
Exit; {Завершуємо функцію}
end
else
Curr: = Curr ^. Next; {Перейти до наступної запису}
FindName: = Nil; {У списку немає шуканого об'єкта}
end; {Кінець FindName}
{Додавання запису першої в зв'язаний список}
procedure AddFirst (A: Link);
begin
A ^. Next: = First; {Новий об'єкт перший у списку}
First: = А; {Голова списку посилається на новий об'єкт}
end; {Кінець AddFirst}
{Видалення першого об'єкта зі списку}
procedure DelFirst (var A: Link);
begin
A: = First;
First: = First ^. Next; {Тепер First вказує на той об'єкт, на який раніше посилався об'єкт А}
end; {Кінець DelFirst}
{Видалення зі списку об'єкта, що стоїть після об'єкта Old}
procedure DelAfter (Old: Link; var A: Link);
begin
A: = Old ^. Next; {Змінній А привласнюється значення вказівника на видаляється об'єкт}
Old ^. Next: = Old ^. Next ^. Next; {Тепер Old вказує на той об'єкт, на який раніше посилався наступний за ним об'єкт, а об'єкт А виключений із зв'язаного списку}
end; {Кінець DelAfter}
{Ввести дані про об'єкт}
procedure InpAvto;
begin
P: = New (Link); {Створити черговий об'єкт типу Auto}
Write ('Введіть марку автомобіля:');
Readln (P ^. Name);
Write ('Максимальна швидкість:');
Readln (Р ^. Speed);
AddFirst (Р); {Виклик процедури додати записи, на яку посилається вказівник Р (Р-фактичний параметр, А - формальний параметр-значення)}
end; {Кінець InpAvto}
{Вивести на екран всі об'єкти із зв'язаного списку}
procedure MyList;
var
Curr: Link; {Локальна змінна - вказівник на черговий об'єкт}
begin
Curr: = First; {Установити вказівник на першому об'єкті в списку}
{Повторювати, поки не дійдемо до кінця списку}
while Curr <> Nil do
begin
Writeln ('Марка:', Curr ^. Name, 'швидкість:', Curr ^. Speed);
Curr: = Curr ^. Next; {Перейти до чергового об'єкту пов'язаного списку}
end;
Write ('Виведення списку закінчено. Натисніть Enter');
Readln;
end; {Кінець MyList}
Begin {Основна програма}
New (P); {Створити нову динамічну змінну і встановити на неї змінну-вказівник}
EndMenu: = False;
repeat {Очищати екран і виводити меню до тих пір, поки EndMenu <> True}
CIrScr;
Writeln ('Вкажіть вид роботи:');
Writein ('1. Запис першим у списку ');
Writeln ('2. Видалення першого об'єкта зі списку ');
Writein ('3. Перегляд всього списку ');
Writein ('4. Видалення об'єкта, наступного у списку за вказаними ');
Writein ('0. Закінчення роботи ');
Readin (V);
Case V of {Виклик різних процедур в залежності від вибору пункту меню}
1: InpAvto; {Введення даних про об'єкт}
2: DelFirst (P); {Видалення першого в списку}
3: MyList; {Виведення списку всіх елементів пов'язаного списку}
4: begin {Видалення об'єкта, наступного за вказаним}
Write ('Введіть марку автомобіля, за яким слідує видаляється зі списку:');
Readln (NamFind);
DelAfter (FindHame (NamFind), P); {Виклик процедури
DelAfter з параметрами: функцією FindName (NamFind) і вказівником Р}
end
else
EndMenu: = True; {Завершити висновок меню}
end;
until EndMenu; {Якщо EndMenu = True, то завершити виведення меню на екран}
Dispose (Р); {Знищити динамічну змінну Р і звільнити пам'ять у купі}
end.