Методичні вказівки. Теоретичні відомості

Теоретичні відомості

Ключові терміни:

LІFO (Last Іnput - Fіrst Output) - це метод доступу до елементів стеку за принципом "останнім прийшов - першим вийшов";

вершина стеку - це доступний елемент стеку;

стек (англ. stack - стопка) - це структура даних, у якій новий елемент завжди записується в її початок (вершину) і черговий елемент, що, зчитується, також завжди вибирається з її початку (рис. 1).

У стеку є обмеження доступу до елементів.

У стеках використається метод доступу до елементів LІFO. Найчастіше принцип роботи стеку порівнюють зі стопкою тарілок: щоб взяти другу зверху, потрібно спочатку взяти верхню.

Стек починається з вершини. Взяти елемент можна тільки з вершини стеку, додати елемент можна тільки у вершину стеку. Наприклад, якщо записані в стек числа 1, 2, 3, то при наступному витягу одержимо 3,2,1.

Рисунок 1. Стек и його організація

Опис стеку виглядає в такий спосіб:

struct им’я_типу {

інформаціне поле;

адресне поле;

};

де

- інформаційне поле - це поле кожного раніше оголошеного або стандартного типу;

- адресне поле - це вказівник на об'єкт того ж типу, що і обумовлена структура, у нього записується адреса наступного елемента стеку.

Например:

struct list {

type pole1;

list *pole2;

} stack;

Робота зі стеком завжди іде із заголовку. Для доступу до стеку досить зберігати вказівник вершини стеку, що вказує на перший елемент. Якщо стек порожній, то вказівник має значення NULL.

Основні операції, роботи зі стеком:

- створення стеку;

- перегляд стеку;

- додавання елемента у вершину стеку;

- витяг елемента з вершини стеку;

- перевірка чи порожній стек;

- очищення стеку.

Методичні вказівки

В даній роботі пропонується написати програму мовою програмування Сі, у якій сформувати стек відповідно до завдання на основі базових операцій: - створення, перегляд стеку, очищення стеку; додавання елемента у вершину стеку; витяг елемента з вершини стеку; перевірка чи порожній стек;

В першу чергу слід звернути увагу на введення даних елементів стеку з урахуванням типу інформаційних полів, їх обробку і виведення на екран у зазначеному форматі. Для зберігання даних використати ресурси динамічної пам'яті. Введення даних здійснити із файлу з урахуванням вимог до вхідних даних, що зазначені у завданні. Обмеженнями на вхідні дані є максимальний розмір рядкових даних, діапазони числових типів полів структури і припустимий розмір області динамічної пам'яті обраної мови програмування.

Завдання на лабораторну роботу:

1. Розробіть алгоритм розв’язування завдання. Для перевірки коректності введених даних скористатися циклом «до»;

2. Розділіть алгоритм на підалгоритми;

3. Проаналізуйте алгоритм, виділивши при цьому всі види даних, розділивши їх на вхідні, допоміжні та вихідні дані кожного підалгоритму. Для вхідних даних передбачте їх зберігання у файлі;

4. Визначте функції, які будуть реалізовувати підалгоритми;

5. Визначте типи даних, класи пам’яті для даних, які розміщуються у внутрішній пам’яті, та параметри функцій;

6. Вхідні дані організуйте у вигляді стеку;

7. Підготуйте тестові дані для перевірки коректності роботи програми;

8. Завантажте середовище програмування Visual Studio;

9. Введіть код програми;

10. Відкомпілюйте і налагодьте програму;

11. Здійснити тестування роботи програми з використанням тестових даних;

12. Оформіть звіт про виконання лабораторної роботи.

Варіанти завдань:

Згідно з наданим номером завдання.

Зміст звіту:

1. Титульна сторінка з номером варіанта завдання;

2. Мета виконання роботи;

3. Завдання на лабораторну роботу;

4. Алгоритм розв’язування завдання з поділом на під алгоритми у вигляді блок-схеми;

5. Код програми з коментарями;

6. Тестові дані для перевірки коректності роботи програми у формі:

Дано: <перелік вхідних даних>

Результат: <перелік вхідних даних>;

7. Скріншоти результату виконання програми;

8. Опис результатів тестування.

9. Код програми з детальним поясненням призначення кожного оператора.

10. Висновки.

Принцип оцінювання роботи:

1. Для отримання оцінки «задовільно» досить програмно, на основі завдання до лабораторної роботи №5, реалізувати обов’язкові функції: створення та перегляд стеку; додавання елемента у вершину стеку; витяг елемента з вершини стеку; запис даних на зовнішній носій інформації; зчитування даних з зовнішнього носія інформації у стек; обчислення. Необхідні дані можуть бути оголошені глобально.

2. Для отримання оцінки «добре» досить програмно, на основі завдання до лабораторної роботи №4, реалізувати обов’язкові функції: створення та перегляд стеку; додавання елемента у вершину стеку; витяг елемента з вершини стеку; запис даних на зовнішній носій інформації; зчитування даних з зовнішнього носія інформації у стек; обчислення. Необхідні дані повинні бути оголошені локально з передачею параметрів у функцію.

3. Для отримання оцінки «відмінно» досить програмно, на основі завдання до лабораторної роботи №6, реалізувати обов’язкові функції: створення, перегляд, очищення стеку; додавання елемента у вершину стеку; витяг елемента з вершини стеку; перевірка чи порожній стек; запис даних на зовнішній носій інформації; зчитування даних з зовнішнього носія інформації у стек; обчислення. Необхідні дані повинні бути оголошені локально з передачею параметрів у функцію.

Література

1. Конспект лекцій.

2. Страуструп Б. Язык программирования C++. Специальное издание — М.: Бином-Пресс, 2007. — 1104 с.

Поиск по сайту: