Упражнение №5. Cтруктуры данных.

 

Цель работы: познакомится с языком программирования Си. Изучить основные структурные элементы программы и основные структуры данных.

Задание: изучить теоретические сведения, выполнить все задания упражнения и продемонстрировать преподавателю, оформить результаты выполнения в виде отчёта.

Содержание отчёта: сформулировать цель работы, теоретические сведения, листинги программ, получившихся при выполнении заданий упражнения, скриншоты консоли с результатами, заключение. Пример оформления титульного листа отчета приведён в конце упражнения. Объём 3-6 страниц.

Стек.

Стек (англ. stack — стопка) — структура данных, в которой доступ к элементам организован по принципу «последним пришёл — первым вышел».

Для работы со стеком существуют несколько операций: push (проталкивание в стек нового элемента), pop (выталкивание из стека элемента, находящегося на вершине).

 

 

Задание 1.

Создадим стек для хранения переменных типа int. Стек будет организован на массиве конечного размера. Используем массив размером в 10 элементов. Переменная stackTop является указателем на вершину стека. Если стек пуст, в данной переменной содержится значение -1. Если в стеке записаны данные, то в переменной будет записан номер элемента массива, в котором хранится верхний элемент стека. В программе созданы две функции pushStack и popStack. Первая функция предназначена для записи элемента в стек. В качестве аргумента функции передаётся число, которое необходимо сохранить в стеке. Функция popStack возвращает число из вершины стека.

Листинг программы:

 

 

После компиляции и проверки работоспособности программы создайте блок схему алгоритма работы.

 

Очередь.

Очередь — структура данных, в которой доступ к элементам организован по принципу «первым пришёл — первым вышел». Для работы с очередью определяются несколько операций: enqueue (запись в очередь) и dequeue (чтение из очереди).

 

Существует несколько вариантов реализации очереди. Одним из таких вариантов является построение очереди из двух стеков.

 

 

СПИСОК ЛИТЕРАТУРЫ

 

1. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. Пер. с англ. М.: Мир, 2000. – 720 c.

2. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. Пер. с англ. М.: Мир, 2000. – 832 c.

3. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. Пер. с англ. М.: Мир, 2000. – 824 c.

4. Матрос Д.Ш., Поднебесова Г. Б. Теория алгоритмов. М.: Бином. Лаборатория знания, 2008. – 208c.

5. Миллер Р., Боксер Л. Последовательные и параллельные алгоритмы: общий подход. М.: Бином. Лаборатория знания, 2006. – 406 c.

6. Новиков Ф.А. Дискретная математика для программистов. Учебник для вузов. 2-е изд.-СПб.: Питер, 2000. – 301 c.

7. Кинг Д. Создание эффективного программного обеспечения. - М.: Мир, 1991. - 367с.

8. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978. - 432c.