- •Понятие о структуре данного. Уровни представления структур данных.
- •Классификация сд в программах пользователя и в памяти эвм
- •Сд в оперативной памяти
- •Сд типа массив.
- •Сд типа запись (прямое декартово произведение).
- •Сд типа таблица.
- •Операции над таблицей:
- •Временная сложность алгоритмов.
- •Сд типа хеш-таблица.
- •Операция включения элемента в таблицу.
- •Операция исключения элемента из таблицы:
- •Сортировки. Улучшенные методы сортировок.
- •Классификация задач по временной сложности.
- •Сд типа стек.
- •Алгоритм сортировки Хоара (стек используется для хранения границ сортируемой области в таблице):
- •Сд типа очередь.
- •Связное распределение памяти.
- •Сд типа линейный односвязный список.
- •Сд типа указатель.
- •Статические и динамические переменные.
- •Сд типа циклический линейный список.
- •Сд типа двусвязный линейный список.
- •Сд типа дек.
- •Многосвязные списки.
- •Средства объектно-ориентированного программирования.
- •Объекты и свойства инкапсуляции.
- •Наследование и переопределение.
- •Полиморфизм. Виртуальные методы.
- •Динамические объекты. Деструкторы.
- •Обработка ошибок при работе с динамическими объектами.
- •Модули, экспортирующие объекты.
- •Нелинейные структуры данных.
- •Сд типа дерево.
- •Представление деревьев в связной памяти эвм.
- •Алгоритмы прохождения деревьев в глубину и в ширину.
- •Представление деревьев в виде бинарных.
- •Представление бинарных деревьев в связной памяти. Прошитые деревья
- •Формирование бинарного дерева.
- •Применение бинарных деревьев в алгоритмах поиска.
- •Операция включения в сд типа бинарное дерево.
- •Операция исключения из бинарного дерева.
- •Представление бинарного дерева в прямоугольной памяти.
- •Применение бинарных деревьев.
- •Сд типа граф.
- •Представление графа в памяти эвм.
- •Алгоритмы прохождения графа.
- •Топологическая сортировка.
- •Организация данных во внешней памяти. Типы и характеристики устройств внешней памяти.
- •Сд типа последовательный файл.
- •Сд типа файл прямого доступа.
- •Сд типа индексно-последовательный файл.
- •Сд типа хеш-файл.
- •Внешняя сортировка.
- •Алгоритм прямого слияния.
- •Многофазная сортировка.
- •Сущность базы данных. Системы управления базами данных.
- •Общая структура субд.
- •Реляционная модель субд.
- •Язык реляционной алгебры.
Средства объектно-ориентированного программирования.
Вообще существует несколько стилей программирования: структурное, логическое, функциональное, объектное.
Объектно-ориентированное программирование (ООП) – совокупность новых принципов и понятий, позволяющих существенно повысить производительность труда программистов, сделать программы более компактными и легко расширяемыми.
Появившись впервые в начале 80-х годов, этот термин (ООП) был связан с семейством языков Smalltalk, который, в свою очередь, использовал некоторые понятия известного с 60-х годов языка Simula-67. К настоящему времени многие распространенные языки, первоначально рассчитанные на традиционный подход к программированию, содержат ряд объектно-ориентированных расширений.
Как структурный так и объектно-ориентированный подходы к программированию имеют свои достоинства и недостатки. Поскольку в основу структурного программирования положены структуры управления, этот подход дает прекрасные результаты при сложном управлении и простых структурах данных. В свою очередь ООП базируется на структурах данных и работает лучше всего, когда сложность построения алгоритмов заключена в выборе организации данных.
Объекты и свойства инкапсуляции.
С формальной точки зрения, объектовые типы в языке Turbo Pascal похожи на СД типа запись, т.е. возможно следующее описание:
Type Point = Object
x, y: integer; {координаты точки}
v: boolean; {видимость точки}
end;
С помощью такого описания можно в дальнейшем определять как статические, так и динамические переменные.
Этими свойствами возможности объектовых типов не исчерпываются. Важнейшим и радикальным отличием от обычной СД типа запись является возможность, наряду с полями, задавать в объектовом типе подпрограммы – процедуры и функции. В этом и заключается одна из главных идей объектно-ориентированного подхода к программированию: предполагается, что объект содержит не только информацию о свойствах (в рассматриваемом примере – координаты точки и условия ее “видимости”), но и правила ее поведения, оформленные в виде подпрограмм. Это поведение может задаваться следующими операциями (для рассматриваемого примера):
операция инициализации точки (установка значений координат);
операция “включения” точки;
операция “выключения” точки;
операция перемещения точки;
получение текущей координаты X точки;
получение текущей координаты Y точки.
Подпрограммы, определенные в объектовом типе, называются методами объекта. Вообще, объектовый тип на языке Turbo Pascal имеет следующий вид:
Type <имя объекта> = Object
<поля данных>
<заголовки методов>
end;
Технически в языке Turbo Pascal определение подпрограмм в объектовых типах делается следующим образом: непосредственно в объектовом типе задаются только заголовки подпрограмм-методов, а полные их описания должны быть заданы отдельно, причем имя подпрограммы-метода формируется из имени объектового типа-“хозяина”, символа “точка” и имени подпрограммы, например:
Type Point =Object
x, y: integer;
v: boolean;
Procedure Init (a, b: integer);
Procedure SwitchOn;
Procedure SwitchOff;
Procedure Move (dx, dy: integer);
Function GetX: integer;
Function GetY: integer;
End;
Procedure Point.Init (a, b: integer);
begin
x:=a; y:=b;
v:=false;
end;
Procedure Point.SwitchOn;
begin
v:=true;
PutPixel (x, y, GetColor);
end;
……………………..
Procedure Point.GetY;
begin
GetY:=y;
end;
Инкапсуляция означает объединение в одном объекте данных и действий над ним. Инкапсуляция характеризуется скрытием информации, т.к. в ООП имеется возможность запретить прямой доступ к полям объекта. Обращение к полям осуществляется при этом только через методы. Внутренняя структура объекта в этом случае оказывается скрытой от пользователя, и объекты можно считать вполне самостоятельными сущностями. Для того, чтобы объект произвел некоторое действие, ему извне нужно послать сообщение, которое инициирует выполнение нужного метода. Например:
Var ObPoint: Point; {определяем экземпляр объекта}
begin
ObPoint.Init (30, 40); {выполнили инициализацию экземпляра}
…………………….
Для объектовых типов допускается использование оператора присоединения. Например, для вышеописанного примера:
with ObPoint do
begin
Init (30, 40);
………..….
end;
Таким образом, создавая программу с использованием объектно-ориентированных понятий, программист может конструировать ее не в виде бессистемной совокупности отдельно заданных данных и подпрограмм, а как коллектив независимых объектов с полностью определенным поведением.
Замечания:
Не рекомендуется обращаться к полям данных объекта непосредственно. Это считается отступлением от объектно-ориентированного стиля, согласно которому все действия с объектом осуществляются только посредством его методов.
На первый взгляд, объектовый тип похож на модуль. Однако в языке Turbo Pascal модуль рассматривается как часть программы, оформленная в виде отдельно хранящейся и раздельно компилируемой конструкции; нельзя, например, определить переменную “модульного типа”. В отличие от этого, определив некоторый объектовый тип, можно создавать произвольное число переменных этого типа.
Объект может содержать несколько десятков методов, но в результирующий код попадут только те методы, которые используются в данной программе пользователя.