Основы программирования. Указатели. Динамические структуры данных. Абстрактные типы данных. Классы - 28 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

30
затронет клиентские программы. Тем самым обеспечивается независимость поль-
зователя типа данных от его разработчика.
Первый шаг реализации абстрактного типа данных – выбор его внутреннего
представления. Если абстрактный тип данных достаточно сложен, то в качестве
внутреннего представления выбирают некоторую структуру данных. Помимо
структуры данных, для реализации АТД используются некоторые средства языка
программирования,
обеспечивающие отделение реализации от интерфейса и со-
крытие реализации. В языке Паскаль такими языковыми средствами являются
модули и классы.
Далее мы приведем простой и часто используемый абстрактный тип данных,
называемый стеком. Будут даны две его реализации: с использованием массива и
односвязного списка. В качестве языковых средств будут вначале использованы
модули, а
затем классы.
3.1 АТД «Стек» и его реализация с помощью модуля
Стек – это абстрактный тип данных, состоящий из последовательности эле-
ментов, которые можно добавлять и извлекать из этой последовательности только
с одного конца, называемого вершиной стека. Кроме того, можно проверять стек
на пустоту.
Примером стека является колода карт, если для нее разрешено лишь добав-
лять или снимать карты с вершины колоды; действия
с серединой колоды запре-
щены. Другой пример – магазин автомата, для которого также можно либо доба-
вить патрон первым в магазин, либо убрать первый патрон из магазина.
Говорят, что стек реализует принцип LIFO – last in first out (последним при-
шел – первым вышел): элемент, положенный на стек последним, выходит из него
первым.
Будем считать, что стек хранит элементы целого типа и составим его интер-
фейс:
procedure Push(i: integer);
function Pop: integer;
function Top: integer;
function IsEmpty: boolean;
Процедура Push кладет элемент i на вершину стека, функция Pop снимает эле-
мент
с вершины стека и возвращает его значение. Функция Top возвращает зна-
чение элемента на вершине стека, не снимая его (вместо имени Top часто исполь-
зуют также имя Peek). Функция IsEmpty возвращает логическое значение: пуст

Страницы