Описание организации структур данных

Для реализации стека, очереди и дека созданы структуры steck,qucue и дек имеющие следующие поля.

В стеке:

1. поле а – информационное поле;

2. поле pred – поле указатель на предыдущий элемент.

В очереди:

1. поле а – информационное поле;

2. поле next – поле указатель на следующий элемент.

В деке:

1. поле а – информационное поле;

2. поле pred – поле указатель на предыдущий элемент;

3. поле next – поле указатель на следующий элемент.

Структура р является текущим элементом. Структура top головным элементом.

Описание алгоритма

Создание стека:

1. Создаем головной элемент;

2. Создаем текущий элемент поле указатель, которого указывает на головной элемент;

3. Текущий элемент становится головным.

Добавление элемента в начало:

1. Осуществляем переход в начало стека;

2. Поле указатель первого элемента заносим адрес добавляемого элемента;

Добавление элемента в конец:

1. Поле указатель добавляемого элемента заносим адрес головы стека.

Добавление элемента середину:

1. Осуществляем переход в середину;

2. Поле указатель добавляемого элемента заносим адрес первого элемента;

3. Поле указатель третьего элемента заносим адрес добавляемого элемента.

Удаление первого элемента:

1. Переходим в начало стека;

2. Поле указатель второго элемента заносим 0;

3. Удаляем элемент.

Удаление последнего элемента:

1. Предыдущий элемент становится головным;

2. Удаляем элемент.

Удаление элемента из середины:

1. Осуществляем, переходим в середину;

2. Поле указатель следующего элемента заносим адрес, хранящийся в поле указателя удаляемого элемента;

3. Удаляем элемент.

Формальное описание входных и выходных данных

Входными данными являются:

1. Размер стека;

2. Элементы стека;

3. Добавляемый элемент;

4. Удаляемый элемент.

Выходными данными являются:

1. Содержимое стека.

Аналогично для очереди и дека.

Описание диалога

При запуске программы создается стек и появляется окно, в которой перечислены операции над стеком. (Рис.1)

Потом выбираем нужный нам пункт к примеру, я выбрал 1 и нажимаем Enter. И сразу внизу появляется запись «введите элемент» водим элемент который мы хотим занести в стек. (рис.2)

Выбираем 2 пункт «Удалить элемент». Рис.3

Выбираем 4 пункт «Поиск элемента в стеке». Если веденный пользователем элемент присутствует в стеке, выводится сообщение о нахождении. Рис.4

Аналогично для очереди и дека.

Описание процедур и функций

В программе были использованы функции, хранящиеся в заголовочных файлах. Список заголовочных файлов из стандартной библиотеки C++, используемых в программе (в описании приведены функции, использующиеся в данной программе):

• iostream – в ней реализована поддержка для файлового ввода/вывода данных встроенных типов. Операции ввода/вывода выполняются с помощью классов istream (потоковый ввод) и ostream (потоковый вывод). Третий класс, iostream, является производным от них и поддерживает двунаправленный ввод/вывод.

Так же были написаны собственные функции для реализации алгоритмов сжатия:

1. void vivod() – вывод стека;

2. void addToTop() – добавление элемента в начало;

3. void addToPos() – добавление элемента в указанную позицию;

4. void delet() – удаление элемента;

5. void poisk() – поиск элемента в стеке.