Формирование и проверка работоспособности программы и модуля

Информационные технологии лекция. Реализация структур данных на основе связного списка.

1. Стек.

Для организации стека можно использовать односвязный список с направлением связи к предыдущему элементу, т.к. активным в стеке является только последний элемент (его добавляют/извлекают), то и логично устроить связь от него к предыдущему, а ссылку на сам последний элемент хранить отдельно (эта ссылка называется «стековый указатель» = «stack pointer», у нас: «stp»).

Элемент стека будет состоять из двух полей: Data для данных (специально объявим тип данных tData, чтобы в дальнейшем можно было его легко изменять) и pPrev для указателя на предыдущий элемент.

Для работы со структурой данных опишем ряд типовых процедур:

Init – Инициализация, т.е. выполнение действий, необходимых для подготовки к работе (в данном случае требуется явно определить значение стекового указателя stp как nil (отсутствие адреса).

Add – Добавление элемента (хотя для стека обычно называется Push – «протолкнуть») – функция, выходное значение которой показывает успешность или неуспешность выполнения операции.

Get – Извлечение элемента (для стека обычно называется Pop – «вытолкнуть»), тоже булевская функция.

Clear – Очистка стека, т.е. удаление всех элементов и освобождение памяти. Необходима именно из-за того, что при прекращении пользования стеком требуется вернуть системе выделенную под структуру данных память.

И дополнительные функции, нужные, в основном, в учебных целях и для отладки (стек полностью функционален и без них):

Count – подсчет числа элементов (функция).

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

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

Перед завершением работы программы следует сделать очистку стека. Тоже принудительно.

Теперь сделаем саму основную программу, которая будет использовать стек.

Пусть в программе будет меню (для начала – примитивное текстовое, в стиле «нажмите нужную кнопочку»), и пользователь сможет сам выбирать действия со стеком и их последовательность.