Курсовая работа: Динамические структуры данных

Элемент динамической структуры состоит из двух полей:

информационного поля или поля данных, в котором содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой-вектором, массивом, записью и т.п.;

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

Когда связное представление данных используется для решения прикладной задачи, для конечного пользователя видимым делается только содержимое информационного поля, а поле связок используется только программистом-разработчиком.

Достоинства связного представления данных:

в возможности обеспечения значительной изменчивости структур;

размер структуры ограничивается только размером памяти машины;

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

Однако существуют и недостатки:

работа с указателями требует, как правило, более высокой квалификации от программиста;

на поля связок расходуется дополнительная память;

доступ к элементам связной структуры может быть менее эффективным по времени.

Применение динамических структур

Последний недостаток является наиболее серьёзным и именно им ограничивается применимость связного представления данных. Если в смежном представлении данных для вычисления адреса любого элемента нам во всех случаях достаточно было номера элемента или информации, содержащейся в дескрипторе структуры, то для связного представления адрес элемента не может быть вычислен из исходных данных.

Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее поиск и требуемого элемента выполняется следованием по цепочке указателей от элемента к элементу. Поэтому связное представление практически никогда не применяется в задачах, где логическая структура данных имеет вид вектора или массива - с доступом по номеру элемента, но часто применяется в задачах, где логическая структура требует другой исходной информации доступа (таблицы, стеки, списки, деревья и т.д.).

Задание курсового проекта

По списку номер 2, тогда имеем следующее задание.

Реализовать стек, содержащий 4-ре поля:

Имя функции, возвращаемое значение, количество параметром и сами параметры.

Реализовать для данного стека работу следующих операций:

добавление элемента;

удаление элемента;

очистка памяти от стека;

вывод на экран всех значений списка;

проверка о переполнении стек;

вывод сообщения на экран о переполнении стека.

1.1 Описание структуры данных "стек"

Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым.

Обычно над стеками выполняется три операции:

начальное формирование стека (запись первой компоненты);