Учебное пособие 800529
.pdf
файла, предшествующей Ki (если запись с ключом K вообще существует). Аналогично, если Ki < K, то дальнейший поиск следует вести в части файла, следующей за Ki. Если повторять эту процедуру проверки ключа Ki из середины непросмотренной части файла, тогда каждое безуспешное сравнение K с Ki будет исключать из рассмотрения приблизительно половину непросмотренной части. В «полусинтаксической»форме алгоритм двоичного поиска выглядит следующим образом.
Algorithm BSEARCH (Binary search – двоичный поиск) поиска записи с ключом K в файле с N>>2 записями, ключи которых упорядочены по возрастанию K1<K2<K3< … <KN.
Шаг 0.[Инициализация] Set FIRST |
1; LAST N. (FIRST и LAST – указатели первого и |
последнего ключей в еще не просмотренной части файла). |
|
Шаг 1. [Основной цикл] While LAST |
FIRST do through шаг 4 od. |
Шаг 2. [Получение центрального ключа] Set I (FIRST+LAST)/2 . (KI – ключ, расположенный в середине или слева от середины еще не просмотренной части файла).
Шаг 3. [Проверка на успешное завершение] If K=KI then PRINT «Успешное окончание, ключ равен KI»; and STOP fi.
Шаг 4. [Сравнение] If K<KI then set LAST I-1 else set FIRST I+1 fi.
Шаг 5. [Безуспешный поиск] PRINT «безуспешно»; and STOP.
Пример алгоритма BSEARCH для отыскания K=42 приводится ниже.
211
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
7 |
14 |
27 |
33 |
42 |
49 |
51 |
53 |
67 |
70 |
77 |
81 |
89 |
94 |
95 |
99 |
↑ FIRST=1 |
|
|
|
|
|
|
↑ |
|
|
|
|
|
LAST=16 ↑ |
||
|
|
|
|
|
|
|
|
|
I=8 |
|
|
|
|
|
|
7 |
14 |
27 |
33 |
42 |
49 |
51 |
|
|
|
|
|
|
|
|
|
↑ FIRST=1 |
|
↑ I=4 |
|
|
↑ LAST=7 |
|
|
|
|
|
|
|
|
||
|
|
|
|
42 |
49 |
51 |
|
|
|
|
|
|
|
|
|
|
|
|
FIRST=7 |
↑ |
↑ |
↑ LAST=7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I=6 |
|
|
|
|
|
|
|
|
|
|
42
↑ FIRST=LAST=I=5, K=K5, ВОЗВРАТ
Метод двоичного поиска можно также применить для того, чтобы представить упорядоченный файл в виде двоичного дерева. Значение ключа, найденное при первом выполнении шага 2 (K(8)=53), является корнем дерева. Интервалы ключей слева (1,7) и справа (8,16) от этого значения помещаются на стек. Верхний интервал снимается со стека и с помощью шага 2 в нем отыскивается средний элемент (или элемент слева от середины). Этот ключ (K(4)=33) становится следующим после корня элементом влево, если его значение меньше значения корня, и следующим вправо в противном случае. Подынтервалы этого интервала справа и слева от вновь добавленного ключа [(1,3),(5,7)] помещаются теперь на стек. Эта процедура повторяется до тех пор, пока стек не окажется пустым. Ниже на рисунке показано двоичное дерево, которое построено для 16 упорядоченных ключей предыдущего примера.
212
|
|
|
|
|
|
|
|
53 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
больше |
|
меньше |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
33 |
|
|
|
|
|
|
|
|
|
81 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
49 |
|
|
|
|
|
70 |
|
|
|
94 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
7 |
27 |
42 |
51 |
|
67 |
77 |
89 |
|
95 |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
99 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Двоичный поиск можно теперь интерпретировать как прохождение этого дерева от корня до искомой вершины. Если достигнута конечная вершина, а заданный ключ не найден, искомая запись в данном файле отсутствует. Заметим, что число вершин на единственном пути от корня к заданному ключу K равно числу сравнений, выполняемых алгоритмом BSEARCH при попытке отыскания K.
Представление упорядоченного файла в виде двоичного дерева оказывается полезным при анализе алгоритмов BSEARCH. Для удобства предположим, что число N записей в файле таково, что N=2k-1 при некотором положительном целом k. В этом случае двоичное дерево является полным, то есть у каждой внутренней вершины есть как левая, так и правая дочь, дерево имеет высоту k-1, а число вершин на уровне i равно 2i, i=0,1,2,…,k-1. Эти параметры позволяют определить основную характеристику алгоритма
– необходимое число сравнений. Показано (см. С. Гудман, с.245), что средняя сложность алгоритма бинарного поиска равна
O(log2N).
Мы рассмотрели случай поиска в файле с фиксированным числом записей. Теперь рассмотрим случай переменного размера файла, то есть файла, в котором записи можно вставлять и удалять.
213
Сначала рассмотрим алгоритм обслуживания растущего файла (то есть поиска и вставления записей), упорядоченного по ключам. Для этого нужно выбрать удобную структуру данных и соответствующий алгоритм, который быстро найдет данную запись в структуре, если она там содержится, или вставит запись на подходящее место, если ее там нет.
В качестве структуры можно для этого использовать связанный список, ибо он легко производит вставление и удаление элементов. Однако в нем очень сложно выполнить двоичный поиск. Поэтому остановимся на структуре типа двоичного дерева. Вот его алгоритм.
Algorithm BTSI (Binary Tree Search and Insertion) – (поиск и вставление в двоичном дереве). Нужно найти заданный ключ K в файле с N>>1 записями, организованными в виде двоичного дерева (как, см. предыдущий алгоритм) Т. Если K отсутствует, то для него создается новая вершина. K(Р) означает ключ в вершине Р; LEFT(P) и RIGHT(P) обозначают левого и правого преемников вершины Р. Корневая вершина Т помечена как ROOT; все фиктивные вершины помечены символом .
Шаг 0.[Инициализация] Set P ROOT.
Шаг 1. [Цикл] While K K(P) do шаг 2 od.
Шаг 2. [Сравнение и переход] If K<K(P) then if LEFT(P)
then set P LEFT(P)
else пусть Q обозначает новую вершину; set
K(Q) K;
LEFT(Q) ; RIGHT(Q) ; LEFT(P) Q; and STOP fi
else if RIGHT(P) |
|
|
then set P |
RIGHT(P) |
|
else пусть Q обозначает новую вершину; |
||
set K(Q) |
K; |
|
LEFT(Q) |
; RIGHT(Q) |
; |
RIGHT(P) Q; and STOP fi fi.
Шаг 3. [Успешный поиск] Печать «Успешное завершение поиска»; and STOP.
У алгоритма BTSI возможен худший случай, когда он поведет себя подобно последовательному поиску. В таком случае дво-
214
ичное дерево вырождается в простой путь (отсев отсутствует - Ю.Б.), по существу являющийся линейным списком. Хуже не бывает.
3.13.Концепции построения и развития языков программирования высокого уровня (в части обработки структур данных)
Все изложенные методы и алгоритмы представления и преобразования структур данных реализуются ЯзПр высокого уровня. То есть получается, что ЯзПр позволяет, то и делается. Поэтому нам необходимо рассмотреть основные идеи построения и развития языков в части представления и оперирования со структурами данных. В настоящее время насчитывается более 2-х тыс. ЯзПр. На их развитие значительное влияние оказали достижения теории вычислений, которые привели к формальному пониманию семантики операторов, модулей, абстрактных типов данных и процедур. При этом происходило смещение акцента от программирования отдельных деталей к программированию более крупных компонентов, то есть переход от программирования «в малом» к программированию «в большом».
Зарождение ЯзПр высокого уровня типа Фортран и Алгол-60 было подчинено концепции процедурного программирования. Она гласила: реши, какие требуются (для решения поставленной задачи
– Ю.Б.) процедуры и используй наилучшие доступные алгоритмы. То есть акцент делался на ОБРАБОТКУ – алгоритм, необходимый для выполнения требуемых вычислений, как правило, математических.
Для реализации такой концепции необходимы функции (процедуры, подпрограммы), а также способы передачи аргументов функциям и возврата значений (получения результатов применения) из функций. Рассмотрим чуть подробнее.
Функцией называется выделенная последовательность инструкций, предназначенных для решения определенной задачи (например, извлечения квадратного корня). Для осуществления решения функция вызывается (программой – Ю.Б.) путем передачи ей
215
аргументов с получением результатов вычисления, то есть возврата (в точку вызова) значений из функции. Функции особенно полезны, когда требуется выполнить одну и ту же задачу несколько раз.
Обрабатываемые данные используются в качестве переменных в функциях. Переменные разделяются на: автоматические (локальные) и внешние (глобальные). Рассмотрим их.
Переменная, которая определена ВНУТРИ функции, называется ЛОКАЛЬНОЙ. Локальную переменную можно использовать только внутри функции, во ВНЕ она не действует, то есть имеет смысл только для данной функции.
При наличии только локальных переменных вся программа «рассыпалась» бы на отдельные функции. А как же их связать? Для этого вводятся внешние переменные – ГЛОБАЛЬНЫЕ, которые может использовать и изменять(!) любая функция программы. Хотя использование глобальных переменных кажется более простым (одна на всех!), их применение может привести к трудно обнаруживаемым ошибкам выполнения и к получению неправильных результатов. Поскольку такая переменная может использоваться всеми функциями программы, то любая из них может изменить значение этой переменной, ибо ограничений доступа к такой переменной нет. Если в результате выполнения программы были получены неправильные значения, вам придется исследовать весь текст на предмет поиска ошибок. Безобидная на вид инструкция (оператор функции – Ю.Б.), затерявшаяся где-нибудь в редко используемой функции, может катастрофически изменить значение функции. Значение же локальной переменной может изменить только функция, в которой ОНА ОПРЕДЕЛЕНА.
С учетом сказанного по мере усложнения программ акцент при их разработке сместился от проектирования процедур в сторону организации данных. Сформулировалась модульная концепция, определяющая набор связанных процедур вместе с данными. Она звучит так: реши, какие требуются модули и разбей программу так, чтобы скрыть (локализовать – Ю.Б.) данные в модулях. Техника проектирования «хороших процедур» теперь сместилась в проектирование каждого модуля. При этом используемая информация
216
разделилась: имеется определенная информация (интерфейсная), которую делают широко и открыто доступной, в то время как доступ к другой (внутренней) информации ограничен. То есть пространство имен разбивается на две части: открытую (public), доступную извне модуля, закрытую (private) часть, доступную только внутри модуля.
Кроме того, модули обеспечили раздельную их компиляцию, позволяющую составлять программу, как из кирпичей, из набора заимствованных модулей. Набор этих модулей был дополнен стандартом по обработке ошибок (или в более широком смысле «исключений»), что явилось важнейшим технологическим шагом в разработке сложных программ.
Однако модули, обеспечивая механизм маскировки информации за счет локализации переменных, констант, функций и типов, обладают существенным ограничением: они не позволяют осуществлять размножение своих экземпляров. Чтобы справиться с проблемой размножения специалистам по информатике потребовалось разработать новую концепцию – абстрактных типов данных, не отвергнув, а еще более развив концепцию модульности. Языки, которые поддерживают концепцию абстрактных типов данных (АТД), относятся к разряду объектных. Их более совершенные последователи, поддерживающие наследование и полиформизм, то есть классовую структуру, являются объектно-ориентированными. Их более 200, а родоначальником является ЯзПр Simula, созданный в 1960 г. на идеях АЛГОЛа. Первыми языками такого типа были АЛГОЛ-68 и Pascal. При этом основная суть абстракции заключалась в отделении логической сущности программы (ее интерфейса) от реализации.
Абстрактный тип данных задается программистом. То есть концепция его действия такова: реши, какие требуются типы; обеспечь полный набор операции для каждого типа. С данными абстрактного типа можно манипулировать так же, как и с данными типов, встроенных в используемый ЯзПр. Как и последним АТД соответствует набор допустимых значений и ряд элементарных операций, которые могут быть выполнены над данными, пользователю разрешается создавать переменные (объекты – Ю.Б.), кото-
217
рые принимают значения из допустимого множества, и манипулировать ими, используя имеющиеся операции. Модули этого не обеспечивают.
Модули часто используются при реализации АТД. Но непосредственной логической взаимосвязи между понятиями модуля и АТД нет. Эти две идеи близки, но не идентичны. Чтобы построить АТД, мы должны уметь:
1.Экспортировать определение типа данных.
2.Делать доступным набор операций, использующихся для манипулирования экземплярами типа данных.
3.Защищать данные, связанные с типом данных, чтобы с ними можно было работать только через указанные подпрограммы.
4.Создавать несколько экземпляров абстрактного типа данных.
К концепции модуля относятся только пп.2 и 3. Концепция модульности применима везде, где не нужно более одного объекта определенного типа, так как модуль не размножает экземпляры данных (области памяти).
Абстрактный тип данных объявляется в виде класса, включающего данные и набор операций над ними – функции – члены. Для генерирования экземпляров класса – объектов, то есть для создания нескольких копий областей данных, имеется определенная функция – конструктор, а для его уничтожения – деструктор. Деструктор вступает в действие в том случае, когда объект класса выходит за пределы области видимости. Конструктор выделяет место в памяти, а деструктор освобождает эту память. Функции конструктора и деструктора имеют то же имя, что и класс.
Широкое использование понятия объекта как абстрактного типа данных послужило основой для построения более гибкой и мощной концепции объектно-ориентированного программирования. Хотя оно и строится на концепции АТД (имеется такая цепь развития: процедура, модуль, АТД, объект), однако добавляет значительные новшества, основное из них – иерархия классов и связанный с ним механизм наследования. Тем самым обрубается предметная «дискретность» каждого АТД, которая заполняется
218
более плавным изменением предметных сущностей (свойств), соответствующим совокупности классов, передающих (наследующих) свойства друг другу. При этом совокупность свойств упорядочена отношением «общее свойство всех – особое (частное) свойство конкретного типа (данных)». Получается аналог многослойной модели информации, изначально зарождаемой в виде совокупности дискретных (попредметной! сущности) признаков, иерархически (интегрированно) переходящих в совокупность более мощных знаков (образов, слов, алфавитов, символов).
Механизм наследования представляет следующее решение. Сначала описывается класс, который определяет общие свойства всех возможных (по задаче!) объектов. При этом функции, интерфейс их вызова должны быть определены, а реализация – нет, она должна быть объявлена скрытно (виртуально). Выбор частных свойств конкретных объектов (типов данных) из общего осуществляется с помощью указателей, сведенных в векторы (массивы). Говорят, что производный класс наследует свойства (члены - функции) базового класса, поэтому применение базового и производного класса в совокупности называют наследованием. Концепция программирования теперь звучит так: реши, какие (по предметности) требуются классы, обеспечь полный набор операций для каждого класса и явно вырази общность через наследование.
В тех случаях, когда общности нет, достаточно абстракции данных. При этом иерархия классов и абстрактные классы дополняют, а не исключают друг друга. И опытные разработчики применяют их совместно.
Однако, алгоритмы есть алгоритмы. Их также можно делать общими для многих задач. Поэтому в настоящее время развивается контейнерная концепция обобщенного программирования. Она звучит так: реши, какие требуются алгоритмы, параметризуй их так, чтобы они могли работать со множеством подходящих типов и структур данных. Для этого создаются базовые библиотеки алгоритмов. Ибо ни одна программа приличных размеров не пишется с использованием только «голых» конструкций языка. Всегда существуют (разрабатываются) библиотеки поддержки. Происходит переход от программирования «в большом» к программированию «в
219
огромном».
Приведенный краткий обзор показывает, что все многообразие ЯзПр «вращается» вокруг двух осей: структуры данных и алгоритмы. При этом прослеживается явная тенденция обобщения представления реальности с помощью ЯзПр, начинающего напоминать обычное знаковое (информационное) отображение. Мало людей это понимают, но вы – ДА!
3.14. Маскирующие свойства структур данных
(Материал данного раздела разработал проф. Харин В.Н. (ЛТА), а автор его только отредактировал)
Все вредоносные элементы компьютерного «счѐта» располагаются в памяти компьютера среди перечисленных («законных») структур данных. Поэтому очень правомерен вопрос о том, как они там «уживаются». Для рассмотрения этого введем несколько определений.
Сущностью системы будем называть отличную от нуля двоичную информацию в памяти системы, расположенную в определѐнной последовательности смежных адресов заданного сегмента. Таким образом, для определения сущности необходимо знать адреса памяти еѐ хранения. Будем называть объектом сущность системы в оперативной памяти ЭВМ, расположенную в определенной области данных, имеющую уникальный идентификатор и атрибуты, обеспечивающие локальный контроль неизменности сущности. Потенциальным субъектом будем считать сущность, расположенную в определѐнной области программных кодов системы, имеющую уникальный идентификатор и атрибуты, обеспечивающие локальный контроль неизменности сущности.
Наличие уникального идентификатора позволит отличить одну сущность от другой в рамках одного и разных классов. Наличие атрибутов позволяет определить свойства сущности. Идентификаторы и атрибуты сущностей, при этом, могут храниться по отношению к сущности в несмежных участках памяти.
Будем говорить, что основная память ЭВМ является контролируемой (или CMS-памятью), если для каждого момента времени
220