Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
Кафедра АПЕПС
Алгоритмізація та програмування - 2. Процедурне програмування
ЗВІТ
до лабораторної роботи № 4
«Списки»
Варіант № 12
Дата «28» червня 2022
Завдання до роботи
1. Дослідити особливості створення одно- та дво-направлених списків.
2. Вивчити і реалізувати механізми додавання нових записів у список, пошуку записів у списку за певними полями, видалення записів зі списку та редагування знайдених записів, а також збереження всього списку у файлі та зчитування списку із файлу до пам’яті з відновленням всіх зв’язків.
3. Розробити Блок-схему програмного алгоритму.
4. Оформити ЗВІТ до лабораторної роботи згідно вимог та методичних рекомендацій.
Варіант-12
/
Теоретичні відомості
Елемент списку є складовою (структурованою) змінною, що містить збережені дані і покажчики на сусідів:
struct elem {
int value;
elem *next;
elem *links[10];
};
Як видно з прикладу, змінна такого типу може містити одну, дві, не більше10 і довільну (динамічний масив) кількість вказівників на аналогічні змінні. Але це ще не список, а опис його складових (елементів) як типу даних. З нього випливає тільки, що кожен з них посилається на аналогічні елементи. Ніяк не можна визначити ні кількості таких змінних в структурі даних, ні характеру зв’язків між ними (послідовний, циклічний, довільний).
Отже, конкретний тип структури даних (лінійний список, дерево, граф) залежить від функцій, які з нею працюють.Залежно від зв’язків списки бувають наступних видів:
• однозв’язні – кожен елемент списку має покажчик на наступний;
• двозв’язні – кожен елемент списку має покажчик на наступний і на
попередній елементи;
• циклічні – перший і останній елементи списку посилаються один на одного і ланцюжок представляє собою кільце.
Звідси ж випливає, що звичайні (розімкнуті) списки мають в якості обмежувача послідовності NULL-покажчик. Відповідно, можливий випадок пустого списку, в якому заголовок – покажчик на перший елемент також містить значення NULL.
Бінарне дерево – це впорядковане дерево, кожна вершина якого має не більше двох піддерев, причому для кожного вузла виконується правило: в лівому піддереві містяться тільки ключі, що мають значення, менші, ніж значення даного вузла, а в правому піддереві містяться тільки ключі, що мають значення, більші, ніж значення даного вузла.
Дерево складається з гілок (вузлів) і листя (елементів). Листя – це вузли, які не вказують ні на кого, у них немає гілочок. Бінарне дерево – це дерево, в якому у гілки може бути не більше двох листів або гілок. Звідси і його назва – «бінарне», тобто елементів два або менше. Але ніяк не більше двох.
Розглянемо структуру, що описується як динамічний список: Поле даних і два покажчика на праву і ліву гілки. У динамічних списках два покажчика зазвичай пов’язують наступний і попередній елементи, у випадку з деревом цього не знадобиться, оскільки, як правило, прохід по дереву йде з кореня. Хоча звичайно ж може бути і зворотний зв’язок.
struct Branch
{
char Data;
Branch *LeftBranch;
Branch *RightBranch;
};
Поле Data представляє дані, на підставі яких будується дерево. Точніше один з елементів даних. Поля Branch описують ліву і праву гілки дерева, і є покажчиками на таку ж структуру.
Елементами дерева можуть бути будь-які значення. Масиви, рядки, інші дерева. Полів з даними може бути безліч. На кожне поле можна будувати своє дерево.
Блок-схема
/
Результати роботи
Перегляд повного списку товарів
/
/
/
Пошук товару
/
Вихід
/
Утворені файли
/
Висновки
Під час виконання роботи даної лабораторної роботи було розглянуто особливості роботи зі списками.
Створено програму, яка створює окремий файл для кожного з товарів, введених користувачем. Інформацію про окремий товар можан переглянути вибравши дію <2> після запису всіх товарів, вивести повний список товарів, для цього необхідно вибрати дію <1>, щоб завершити виконання програми необхідно натиснути <0>.
Програмний код (додаток)
https://replit.co...
