Практическая работа №9
Линейные структуры данных в C++
Section titled “Линейные структуры данных в C++”Цель работы: Научиться реализовывать основные линейные структуры данных (массив, список, стек и очередь), понимать их применение и различия, научиться проводить базовые операции и анализировать их
Основные теоретические положения
Section titled “Основные теоретические положения”Основные линейные структуры данных:
- Массив — статическая структура, элементы которой располагаются подряд в памяти, позволяет доступ по индексу.
- Односвязный список — динамическая структура из элементов (узлов), каждый из которых содержит данные и указатель на следующий элемент.
- Стек — структура данных, работающая по принципу LIFO (последним пришёл — первым вышел), поддерживает операции push/pop.
- Очередь — структура данных, работающая по принципу FIFO (первым пришёл — первым вышел), поддерживает операции enqueue/dequeue.
Краткие характеристики
| Структура | Доступ | Вставка/Удаление | Использование |
|---|---|---|---|
| Массив | Быстрый по индексу | Медленная, сдвиги элементов | Когда известен размер заранее |
| Односвязный список | Последовательный | Быстрая с корректным указателем | Динамическое изменение размера |
| Стек | Последовательный | push/pop — быстрые операции | Обратный порядок, рекурсия |
| Очередь | Последовательный | enqueue/dequeue | Планирование, буферы данных |
Пример реализации (теория, псевдокод)
Section titled “Пример реализации (теория, псевдокод)”Свой стек (на массиве):
- Вводим массив фиксированной длины data[N].
- Переменная top хранит индекс последнего элемента.
- push(x): увеличить top, вставить x.
- pop(): вернуть и уменьшить top.
- Проверка: если top < 0 — стек пуст.
Своя очередь (на массиве, кольцевой буфер):
- Массив с длиной N.
- Переменные head (индекс первого для удаления), tail (индекс для вставки).
- Добавление: в позицию tail, затем увеличиваем tail (по модулю N).
- Удаление: из позиции head, затем увеличиваем head (по модулю N).
- Проверка переполненности: если следующий tail == head, очередь заполнена.
Компиляция и запуск программы
Section titled “Компиляция и запуск программы”g++ *имя_файла*.cpp -o *название_файла_для_компиляции*
./*название_скомпилированного_файла*Общие требования
Section titled “Общие требования”Задания для выполнения
Section titled “Задания для выполнения”Вариант 1
| № | Задача | Описание |
|---|---|---|
| 1 | Реализация стека | Реализуйте свой стек на массиве. Добавьте 10 элементов с клавиатуры, затем снимите все элементы по одному, выведите содержимое. |
| 2 | Реализация очереди | Реализуйте свою очередь на массиве. Заполните 10 элементов, выполняйте удаление и добавление, выведите состояние очереди на каждом шаге. |
| 3 | Анализ | Опишите возможные проблемы при переполнении/опустошении структур, сравните их алгоритмические особенности. |
Вариант 2
| № | Задача | Описание |
|---|---|---|
| 1 | Стек на связном списке | Реализуйте стек через односвязный список. Тест: добавьте/снимите элементы, покажите работу. |
| 2 | Очередь на связном списке | Аналогично — через односвязный список, продемонстрируйте работу. |
| 3 | Пояснение | Отчёт: сравните структуру и работу массивного и списочного подходов. |
Контрольные вопросы
Section titled “Контрольные вопросы”- Чем отличается стек от очереди с точки зрения управления доступом?
- Назовите ситуации, где стек предпочтительнее очереди, и наоборот.
- Какие проблемы могут возникнуть при работе с массивами для этих структур?
- Как изменяется сложность операций при работе с динамическими структурами?
- В чём суть принципов LIFO и FIFO?