Занесение элемента в стек

Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека.

Процедура формирования стека будет иметь следующий вид:

Procedure FormStack; Var   Stack : EXST; {Текущая переменная}   Digit : integer; Procedure writeStack(Var u : EXST; Digit : integer); Var   x : EXST; Begin   new(x); {выделяем память под хранение нового элемента стека}   x^.Data := Digit; {заполняем поле данных элемента}   x^.Next := u; {новый элемент "связываем" со стеком}   u := x; {созданный элемент определяем как вершину стека} End; Begin   Stack := Nil; {инициализация стека}   writeln('Введите элементы стека. Окончание ввода – 0');   read(Digit);   while Digit <> 0 do     begin       writeStack(Stack, Digit);       read(Digit);     end; End;

Извлечение элемента из стека

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

Procedure readStack(Var u : EXST; Var i : integer); Var   x : EXST; Begin   i := u^.Data; {считываем значение поля данных в переменную}   x := u; {запоминаем адрес вершины стека}   u := u^.Next; {переносим вершину стека на следующий элемент}   dispose(x); {освобождаем память, занятую уже ненужным элементом стека} End.

Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию, определяющую, пуст ли обрабатываемый стек.

Function FreeStack(u : EXST) : boolean;

22. Динамические структуры данных: односвязный список.

Элемент односвязного списка содержит два поля (рис. 3.2): информационное поле (INFO) и поле указателя (PTR).

Особенностью указателя является то, что он дает только адрес последующего элемента списка. Поле указателя последнего элемента в списке является пустым (NIL). LST - указатель на начало списка. Список может быть пустым, тогда LST будет равен NIL.  Доступ к элементу списка осуществляется только от его начала, то есть обратной связи в этом списке нет. 

22. Технология объектно-ориентированного программирования. Поля и методы объектов, инкапсуляция, наследование, полиморфизм.

23. Технология объектно-ориентированного программирования. Виртуальные правила, конструкторы и деструкторы.

Абстрактные типы данных

Понятие абстрактных типов дан­ных является ключевым в программировании. Абстракция подразумевает разделение и независимое рассмотрение ин­терфейса и реализации .

Рассмотрим пример. Все мы смотрим телевизионные про­граммы. Назовем телевизор модулем или объектом. Этот объект имеет интерфейс с пользователем, т. е. средства управ­ления (совокупность кнопок), воспроизведения изображения и звука. Чем совершеннее интерфейс, тем удобнее телевизор в использовании. Мы переключаем программы, нажимая опре­деленные кнопки, и при этом не задумываемся о физических процессах, происходящих в телевизоре. Об этом знают спе­циалисты. Когда мы выбираем телевизор, нас интересуют его цена и эксплуатационные параметры, т. е. качество изобра­жения, звука и т. п. Однако нас не интересует то, что находит­ся внутри. Другими словами, мы возвращаемся к свойствам объекта (модуля), какими являются интерфейс и реализация. Основная цель абстракции в программировании как раз и заключается в отделении интерфейса от реализации.

Вернемся к нашему примеру. Предположим, некоторый субъект уверен, что хорошо знает устройство телевизора. Он снимает крышку и начинает «усовершенствовать» его. Хотя иногда это и приводит к определенным промежуточным (локальным) успехам, окончательный результат почти всегда отрицательный. Поэтому подобные действия надо запрещать. В программировании это поддерживается механизмами за­прета доступа или скрытия внутренних компонентов. Каждо­му объекту (модулю) предоставлено право самому распоря­жаться «своим имуществом», т. е. данными функциями и опе­рациями. Игнорирование этого принципа нарушает стабиль­ность системы и часто приводит к ее полному разрушению. Принцип абстракции обязывает использовать механизмы скрытия, которые предотвращают умышленное или случай­ное изменение внутренних компонентов.

Абстракция данных предполагает определение и рассмот­рение абстрактных типовданных(АТД) или, что то же самое, новых типов данных, введенных пользователем .

Абстрактный тип данных — это совокупность данных вместе с множеством операций, которые можно выполнять над этими данными .

Понятие объектно-ориентированного программирования

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

Объектно-ориентированная методология так же, как и структурная методология, была создана с целью дисциплинировать процесс разработки больших программных комплексов и тем самым снизить их сложность и стоимость.

Объектно-ориентированная методология преследует те же цели, что и структурная, но решает их с другой отправной точки и в большинстве случаев позволяет управлять более сложными проектами, чем структурная методология.

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

Другими словами, алгоритмическая декомпозиция учитывает в большей степени структуру взаимосвязей между частями сложной проблемы, а объектно-ориентированная декомпозиция уделяет больше внимания характеру взаимосвязей.

На практике рекомендуется применять обе разновидности декомпозиции: при создании крупных проектов целесообразно сначала применять объектно-ориентированный подход для создания общей иерархии объектов, отражающих сущность программируемой задачи, а затем использовать алгоритмическую декомпозицию на модули для упрощения разработки и сопровождения программного комплекса.

ОО-программирование является, несомненно, одним из наиболее интересных направлений для профессиональной разработки программ.