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

Динамическими называют структуры данных, динамически создаваемые в ходе выполнения программы. Они размещаются в динамической памяти. К ним относятся списки: однонаправленные (стек, очередь), двунаправленные; графы (и прежде всего дерево как ориентированный граф).

Стек

Стеком называется структура данных, организованная по правилу LIFO: last input – first output, т.е последним вошел – первым вышел.

Глубина стека – количество элементов в нем.

Вершина стека – «верхний», т.е. доступный элемент.

Стек как структуру данных, размещенную в динамической памяти, можно представить как «цепочку» записей (Record), одно из полей которых есть указатель на предыдущий элемент. Стек из четырех элементов «выглядит» в памяти так, как изображено на Рис. 8:

Примеры решаемых задач

Пример 1. Составить программу, которая формирует стек из 10 элементов, а затем удаляет его из памяти.

Программа:

Program stack10;

Uses Crt;

Const n=10;

Type stack = ^elem;

elem = Record

num : Integer;

p : stack

End;

Var st,beg_st : stack;

i : Integer;

Begin

Clrscr;

beg_st := nil;

For i := 1 To n Do

Begin

New (st);

st^.p := beg_st;

beg_st := st;

Write ('введите ', i ,' элемент стека ');

Readln (st^.num)

End;

Writeln ('в динамической памяти создан стек:');

st := beg_st;

While st <> nil Do

Begin

Writeln (st^.num);

st:=st^.p

End;

Readln;

Writeln ('Освобождаем память - удаляем элементы стека из кучи ');

i := n;

st := beg_st;

While beg_st<>nil do

Begin

st := beg_st;

Writeln ('Удалили ', i ,' элемент ');

beg_st := st^.p;

i := i - 1;

Dispose (st);

End;

Readln

End.

Контрольные задания

1. Составить программу, которая создает стек из N элементов (произвольного типа) и:

   1. выводит содержимое стека на экран;

   2. вставляет элемент в стек на k-е место;

   3. удаляет элемент с номером k из стека.

2. Составить программу, которая создает очередь из N элементов (произвольного типа) и:

   1. выводит элементы очереди на экран;

   2. вставляет элемент в очередь на k-е место;

   3. удаляет элемент с номером k из очереди.

3. Составить программу, которая формирует двунаправленный список из N элементов (произвольного типа) и:

   1. выводит элементы списка на экран;

   2. вставляет элемент в список на k-е место;

   3. удаляет элемент с номером k из списка.

Список литературы

1. Алексеев Е.Р. Турбо Паскаль 7.0. М.: НТ Пресс, 1996.

2. Грызлова Т.П., Грызлов В.И. Турбо Паскаль 7.0: для школьников, студентов и преподавателей. Изд. 4-е, испр-е. М.: ДМК Пресс, 2005.

3. Кораблев В. Турбо Паскаль 7.0. Самоучитель. Изд. 16-е . Спб.: Питер, 2005.

4. Немнюгин С., Перколаб Л. Изучаем Турбо Паскаль. Спб.: Питер, 2004.

5. Попов В.Б. Турбо Паскаль для школьников. М.: Финансы и статистика, 2004.

6. Фаронов В.Р. Турбо Паскаль 7.0: начальный курс. М.: Нолидж, 1997.

7. Чеснокова О.Р. Турбо Паскаль 7.0. Шаг за шагом. М.: НТ Пресс, 2004.

Газейкина Анна Ивановна

Основы структурного программирования на языке Паскаль

Учебно-методическое пособие/ Урал. гос. пед. ун-т.

Оригинал-макет подготовлен автором

ЛР №040330 от 18.04.97

Подписано в печать Формат 60х84 1/16

Печать плоская. Бумага для множ. апп.

Гарнитура Таймс. Усл. печ. л. 6 . Тираж 100 экз.

Заказ

Уральский государственный педагогический университет 620017, г. Екатеринбург, пр. Космонавтов, 26.

Тираж отпечатан в отделе множительной техники

1 Память в персональном компьютере адресуется двумя шестнадцатеричными словами (BA:BS), где BA - сегментный адрес, BS - смещение. Сегмент – участок памяти длиной 64 Кбайта, который начинается с физического адреса, значение которого кратно числу 16. Смещение определяет номер байта в сегменте.

2