Основы программирования — второй семестр 08-09; Михалкович С.С.; V часть — различия между версиями
Admin (обсуждение | вклад) |
Admin (обсуждение | вклад) (→АТД стек) |
||
Строка 22: | Строка 22: | ||
===АТД стек=== | ===АТД стек=== | ||
+ | |||
+ | Стек - это набор данных, устроенный по принципу LIFO (Last In First Out) - последним пришел - первым вышел. | ||
+ | |||
+ | Стек следует представлять как стопку предметов, положенных один на другой. В каждый момент можно положить предмет на вершину стека, посмотреть предмет на вершине стека, снять предмет с вершины и проверить, пуст ли стек. Причем, если предмет последним положили на вершину стопки, то он будет снят первым - отсюда и название LIFO. | ||
+ | |||
+ | Хорошим примером стека является колода карт и магазин автомата. | ||
+ | |||
+ | Опишем операции со стеком | ||
+ | # Положить значение на вершину стека (Push, втолкнуть значение в стек) | ||
+ | # Вернуть значение на вершине стека (Peek) | ||
+ | # Взять значение с вершины стека и вернуть его (Pop, вытолкнуть значение из стека) | ||
+ | # Пуст ли стек (IsEmpty) | ||
+ | |||
+ | Опишем интерфейс стека в виде класса: | ||
+ | |||
+ | type Stack = class | ||
+ | procedure Push(i: integer); | ||
+ | function Pop: integer; | ||
+ | function Top: integer; | ||
+ | function IsEmpty: boolean; | ||
+ | end; | ||
===Классы: основные понятия=== | ===Классы: основные понятия=== |
Версия 22:06, 31 марта 2009
Что известно о классах к настоящему моменту:
- Класс - тип данных
- Класс, как и запись, содержит поля и методы
- Переменная типа класс и переменная типа запись по-разному хранятся в памяти (ссылочная и размерная организация данных)
- Для создания объекта класса и связывания его с переменной класса вызывается специальная функция-метод, называемая конструктором
- Можно создавать шаблоны классов, параметризованные одним или несколькими типами
Абстрактные типы данных
Класс является реализацией более общей концепции абстрактного типа данных (АТД).
До сих пор мы сталкивались с конкретными типами данных, простыми или составными (массивы, записи, списки). Каждый тип данных характеризуется:
- набором допустимых значений;
- тем, как эти значения хранятся в памяти;
- операциями, которые можно выполнять над данными этого типа.
Абстрактный тип данных - это тип данных, доступ к которым осуществляется только через некоторый набор действий (операций, подпрограмм). Этот набор действий называется интерфейсом абстрактного типа данных. По существу, абстрактный тип данных - это интерфейс, набор операций. То, как эти данные хранятся, АТД не определяет.
Клиенту, использующему тип данных, не важно знать, как он устроен внутри, а важны лишь операции, которые можно выполнять над объектами этого типа, т.е. важен только интерфейс. То есть, клиент оперирует с типом данных как с абстрактным. Реализация должна быть скрыта от клиента (принцип сокрытия реализации).
Для того, чтобы абстрактным типом данных можно было пользоваться, необходимо реализовать все операции, входящие в его интерфейс. Наиболее распространенной реализацией АТД является класс.
АТД стек
Стек - это набор данных, устроенный по принципу LIFO (Last In First Out) - последним пришел - первым вышел.
Стек следует представлять как стопку предметов, положенных один на другой. В каждый момент можно положить предмет на вершину стека, посмотреть предмет на вершине стека, снять предмет с вершины и проверить, пуст ли стек. Причем, если предмет последним положили на вершину стопки, то он будет снят первым - отсюда и название LIFO.
Хорошим примером стека является колода карт и магазин автомата.
Опишем операции со стеком
- Положить значение на вершину стека (Push, втолкнуть значение в стек)
- Вернуть значение на вершине стека (Peek)
- Взять значение с вершины стека и вернуть его (Pop, вытолкнуть значение из стека)
- Пуст ли стек (IsEmpty)
Опишем интерфейс стека в виде класса:
type Stack = class
procedure Push(i: integer); function Pop: integer; function Top: integer; function IsEmpty: boolean;
end;