Модуль 2 / Задание на L3

Модуль2

Лабораторна робота № 3.

Тема: Структури. Списки. Стеки. Черги.

Завдання:

Для наведених нижче задач

1. зробити математичну постановку;

2. скласти алгоритм програми;

3. скласти програму мовою С++ для обчислення;

4. проаналізувати результати роботи програми;

5. оформити протокол.

Деякі теоретичні повідомлення.

Структури.

Дуже часто у програмах необхідно обробляти набори даних різних типів як єдине ціле. Наприклад, якщо вводити у програму дані з екзаменаційної відомості: прізвище студента (описується як масив символів), номер залікової книжки (цілочисельний тип), екзаменаційна оцінка (тип-діапазон 2..5 на базі цілочисельного). Всі ці дані пов’язані між собою і повинні оброблятися як єдине ціле. Враховуючи те, що студентів в групі не більше 30, можна було би використовувати масив, але дані різнотипні, тому простий масив використати неможна.

У таких випадках для найдоцільнішим буде використання типу структури.

Структура – це спеціальний структурований тип даних, який створює користувач для опрацювання інформації про об’єкти є деякої предметної області. Така інформація може складатися з даних різних типів. Структура складається з полів і кожне поле описується певним типом.

Структуру описують за допомогою такої конструкції:

struct <назва типу структури>

{

< тип поля 1> < назва поля 1>;

<тип поля 2> < назва поля 2>;

. . .

< тип поля n> < назва поля n>;

};

Коли у програмі описана структура, то оголосити змінні або вказівники цього типу можна так:

< назва типу структури> < список змінних і вказівників>;

Оголосити змінні типу структура можна ще й так:

struct <назва типу структури>

{

< тип поля 1> < назва поля 1>;

<тип поля 2> < назва поля 2>;

. . .

< тип поля n> < назва поля n>;

} < список змінних і вказівників > ;

Доступ до конкретного поля змінної типу структура дає складне ім’я вигляду:

< назва змінної> < назва поля >

Можна також створювати вказівники на структури. Доступ до полів вказівника на структуру здійснюється інакше, ніж до полів відповідної змінної:

< назва вказівника> - > < назва поля >

Масив змінних типу структура можна оголосити так:

< назва типу структура> < назва масиву >[кількість елементів];

Доступ до полів окремих елементів массиву здійснюється так:

< назва елемента> [індекс] < назва поля>

Списки.

Список – це скінченний набор даних одного типу, між якими налагоджено зв'язок. Елемент однонаправленного списку складається з двох частин: самого данного (часто складного) та вказівника на наступний елемент списку. Для опису списку використовують такий опис:

struct <назва типу структури>

{

< тип поля 1> < назва поля 1>;

<тип поля 2> < назва поля 2>;

. . .

< тип поля n> < назва поля n>;

< тип вказівника> * < назва типу списку>;

};

< назва типу списку > * < назва вказівника 1>, … ,

*< назва вказівника n >;

Стеки та черги.

Стек – це структура даних, у яких елемент, записаний останнім, зчитують першим. Принцип обслуговування LIFO (last in — first out) «останній прийшов – перший пішов». Додавання та вибірка елементів виконується з одного кінця (це приватний випадок однонаправленого списку). Стек використовують у програмуванні, зокрема, для реалізації рекурсії. Рекурсія виконується так: спочатку всі виклики нагромаджуються, а потім виконуються вклдадені функції.

Стек описують і створюють у пам'яті за допомогою типу даних структура. Над елементами стека визначені лише дві операції: занесення елементів у стек та вилучення елементів зі стека. У стеку завжди доступний лише верхній елемент, який називають вершиною стека.

Черга – це структура даних, у якій елемент записаний першим, зчитують першим. Принцип обслуговування FIFO (first in — first out) «перший прийшов – перший пішов». Чергу, як і стек, описують з використанням структури. Над елементами черги визначені лише операції: занесення елементів у чергу та вибірка елементів з черги. У черзі доступним є лише нижній елемент.

Задача 1. Масив структур.

Придумати і описати структуру деякого сюжету (не менше п’яти полів) та скласти програму для створення масиву з п’яти – семи елементів типу структура і опрацювання відповідних даних згідно з деяким сюжетом. У сюжеті задати і описати критерій пошуку деякої інформації. Результати роботи програми (всі введені а потім знайдені у результаті пошуку дані) вивести на екран.

Теми сюжетів:

1. Дані про студентів.

2. Дані про літаки.

3. Дані про комп’ютери.

4. Дані про сузір’я.

5. Дані про квіти.

6. Дані про автомобілі.

7. Дані про принтери.

8. Дані про річки.

9. Дані про туристичні путівки.

10. Дані про дисципліни, які вивчають на першому курсі.

11. Дані про озера.

12. Дані про птахів.

13. Дані про гори.

14. Дані про диких тварин.

15. Дані про промислові товари.

16. Дані про мікропроцесори.

17. Дані про книги.

18. Дані про автомобілі.

19. Дані про телефонну книгу.

20. Дані про театральні вистави.

21. Дані про відомі архітектурні споруди.

22. Дані про відомих письменників та їх твори.

23. Дані про розклад літаків.

24. Дані про рослини.

25. Дані про автомобілі на складі.

26. Дані про аудіотехніку.

Задача 2. (не є обов’язковою).

Придумати і описати створення списку або стеку або черги. Та роботу з ними.

.

4