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

Страницы работы

6 страниц (Word-файл)

Содержание работы

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

1. Стек.

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

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

type

tData = integer;      {тип хранимых данных}

pEl = ^tEl;           {указатель на элемент}

tEl = record          {элемент: данные и указатель на предыдущего соседа}

Data: tData;

pPrev: pEl;

end;

var

stp: pEl;       {стековый указатель – указатель на верхний элемент}

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

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

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

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

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

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

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

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

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

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

procedure Init;   {инициализация}

begin

stp := nil;     {явно показать, что стековый указатель не содержит адреса}

end;

function Add(d: tData): boolean;  

{Добавление элемента. Данные передаются параметром по значению}

var

p: pEl;

begin

new(p);

Add := (p <> nil);    {выходное значение функции показывает ее успешность/неуспешность}

if p <> nil then

begin

p^.Data := d;

p^.pPrev := stp;

stp := p;

end;

end;

function Get(var d: tData): boolean;    

{Извлечение элемента. Данные передаются параметром по ссылке, т.к. на выход}

var

p: pEl;

begin

Get := (stp <> nil); {выходное значение функции показывает ее успешность/неуспешность}

if stp <> nil then

begin

d := stp^.Data;

p := stp;

stp := stp^.pPrev;

dispose(p);

end;

end;

function Count: integer;

var

c: integer;

p: pEl;

begin

c := 0;

p := stp;

while p <> nil do

begin

inc(c);

p := p^.pPrev;

end;

Count := c;

end;

procedure Print;

var

p: pEl;

begin

p := stp;

while p <> nil do

begin

writeln(p^.Data);   {раз элементы типа integer, можно в строку: write(p^.Data, ‘, ‘);}

p := p^.pPrev;

end;

end;

procedure Clear;

var

p: pEl;

begin

while stp <> nil do

begin

p := stp;

stp := stp^.pPrev;

dispose(p);

end;

end;

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

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

Похожие материалы

Информация о работе