Лекция 7.

Структуры данных. Реализация стека на базе массива. Стековый калькулятор.

Как называл свою книгу Н.Вирт, «Алгоритмы + структуры данных = программы».

Наиболее популярные структуры данных: массив, очередь, стек, дек, список, дерево, граф.


Стек — это структура данных, организованная по принципу «первый пришел, первый ушел», по английски First In First Out, сокращенно FIFO. В бытовом смысле это обычная очередь.


Список предписаний структуры «Очередь элементов типа E»:

1. Начать работу

2. Сделать очередь пустой

3. Очередь пуста: да/нет

4. Добавить элемент <вх: E> в конец очереди

5. Взять элемент из начала очереди в <вых: E>

6. Начало очереди: E

7. Удалить начало очереди

8. Кончить работу


Стек — это структура данных, организованная по принципу «последний пришел, первый ушел», по английски Last In First Out, сокращенно LIFO. В бытовом смысле это просто стопка, из которой можно брать и в которую можно класть только сверху.


Список предписаний структуры «Стек элементов типа E»:

1. Начать работу

2. Кончить работу

3. Сделать стек пустым

4. Стек пуст: да/нет

5. Добавить элемент <вх: E> в стек

6. Взять элемент из стека в <вых: E>

7. Вершина стека: E

8. Удалить вершину стека


Дек похож на стек, но операции положить/вытолкнуть можно производить не только сверху, но и снизу дека.


Список предписаний структуры «Дек элементов типа E»:

1. Начать работу

2. Сделать пустым

3. Пуст: да/нет

4. Добавить элемент в начало/конец дека <вх: E>

5. Взять элемент из начала/конца дека в <вых: E>

6. Начало/конец дека: E

7. Удалить начало/конец дека

8. Кончить работу


Список предписаний структуры «Множество элементов типа E»:

1. Начать работу

2. Сделать множество пустым

3. Множество пусто: да/нет

4. Добавить элемент <вх: E> в множество

5. Удалить элемент <вх: E> из множества

6. Элемент <вх: E> принадлежит множеству: да/нет

7. Взять какой-нибудь элемент множества в <вых: E>

8. Кончить работу


Список предписаний структуры «Последовательность элементов типа E»:

1. Начать работу

2. Сделать последовательность пустой

3. Последовательность пуста: да/нет

4. Добавить элемент <вх: E> в конец последовательности

5. Встать в начало последовательности

6. Есть/нет непрочитанные элементы

7. Прочесть очередной элемент последовательности в <вых: E>

8. Очередной элемент последовательности: E

9. Пропустить очередной элемент последовательности

10. Кончить работу


Список предписаний структуры «Л2-список элементов типа E»:

1. Начать работу

2. Сделать список пустым

3. Список пуст: да/нет

4. Установить указатель в начало/конец списка

5. Указатель в начале/конце списка: да/нет

6. Передвинуть указатель списка вперед/назад

7. Добавить элемент <вх: E> до указателя/за указателем списка

8. Взять элемент списка до указателя/за указателем в <вых: E>

9. Элемент списка до указателя/за указателем: E

10. Удалить элемент списка до указателя/за указателем

11. Кончить работу


Название списка «линейный двунаправленный» означает, что элементы списка упорядочены линейно, а указатель можно двигать вперед/назад.

В линейном однонаправленном списке элемены упорядочены тоже линейно, но указатель можно двигать только вперед:


Список предписаний структуры «Л1-список элементов типа E»:

1. Начать работу

2. Сделать список пустым

3. Список пуст: да/нет

4. Установить указатель в начало списка

5. Указатель в конце списка: да/нет

6. Передвинуть указатель списка вперед

7. Добавить элемент <вх: E> за указателем списка

8. Взять элемент списка за указателем в <вых: E>

9. Элемент списка за указателем: E

10. Удалить элемент списка за указателем

11. Кончить работу


Список предписаний структуры «Вектор элементов типа E с индексом типа И»:

1. Начать работу

2. Элемент вектора с индексом <вх: И>: E

3. Кончить работу


Реализация одних структур на базе других

1. Реализация последовательности на базе двух очередей.


Последовательность будем хранить в левой (ЛО) и правой (ПО) очередях. Левая часть будет соответствовать прочитанной части последовательности, а правая — непрочитанной.


Предписание Начать работу

ЛО. Начать работу

ПО. Начать работу

Конец предписания

Предписание Сделать последовательность пустой

ЛО.Сделать очередь пустой

ПО. Сделать очередь пустой

Конец предписания

Предписание Последовательность пуста: да/нет

Ответ := ЛО.пуста и ПО.пуста

Конец предписания

Предписание Добавить элемент <вх: E> в конец последовательности

ПО.Добавить элемент <вх: E> в конец очереди

Конец предписания

Предписание Встать в начало последовательности

// Перекладываем все элементы из правой очереди в левую

Цикл Пока ПО.Очередь не пуста выполнять

ПО.Взять элемент из начала очередь в <вых: E>

ЛО.Добавить элемент <вх: E> в конец очереди

Конец цикла

Утверждение: ПО.Очередь пуста

// Перекладываем все элементы из левой очереди в правую

Цикл Пока ЛО.Очередь не пуста выполнять

ЛО.Взять элемент из начала очередь в <вых: E>

ПО.Добавить элемент <вх: E> в конец очереди

Конец цикла

Утверждение: ЛО.Очередь пуста

Конец предписания

Предписание Есть непрочитанные элементы

Ответ: ПО.очередь не пуста

Конец предписания

Предписание Прочесть очередной элемент в <вых: E>

ПО.Взять элемент из начала очереди в <вых: E>

ЛО.Добавить элемент <вх: E> в конец очереди

Конец предписания

Предписание Очередной элемент последовательности: E

Ответ := ПО.Начало очереди

Конец предписания

Предписание Пропустить очередной элемент последовательности: E

ПО.Взять элемент из начала очереди в <вых: E>

ЛО.Добавить элемент <вх: E> в конец очереди

Конец предписания

Предписание Кончить работу

ЛО.Кончить работу

ПО.Кончить работу

Конец предписания


2. Задачи на реализацию одних структур на базе других:

1) Реализовать стек на базе L1-списка

2) Реализовать очередь на базе L1-списка

3) Дек на базе L2-списка


Реализация стека на базе вектора на языке C++

Реализация стека вещественных чисел на базе вектора, class RealStack (Борисенко В.В.):

RealStack.h

RealStack.cpp


Пример использования класса RealStack для разработки стекового калькулятора на языке C++ (Борисенко В.В.):

StackCalc.cpp


Литература

1. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов — М.: Наука. Гл.ред.физ.-мат.лит., 1988