If (q^.Data = poisk) Then если нашли удаляемый узел:
flag:= 1; флаг поиска – на 1
Break; и выходим из цикла поиска
End; {If}
v:=q; если еще не нашли: подтянули ссылку v к поисковику q
If (poisk < q^.Data) и сделали шаг по дереву на уровень ниже
Then q:=q^.Left
Else q:=q^.Right;
End; {While}
Если удаляемый узел найден (flag=1), то начинается его анализ:
1. если это лист – то безболезненно его удаляем (q – указатель на удаляемый узел, v – указатель на его предка):
If (q^.Left = Nil) And (q^.Right = Nil) Then это лист
If (v^.Left = q) если он подвешен слева от предка,
Then v^.Left:=Nil то вместо него Nil,
Else v^.Right:=Nil; иначе Nil - справа от предка
Dispose(q); освобождаем от него память
{на продолжение}
2. если у него слева – ничего нет, а справа - поддерево:
If (q^.Left = Nil) And (q^.Right <> Nil) Then
If (v^.Left = q) если он подвешен слева от предка,
Then v^.Left:=q^.Right то слева вместо него - правое поддерево узла q,
Else v^.Right:=q^.Right; иначе справа вместо него - правое поддерево узла q
Dispose(q); освобождаем от него память
{на продолжение}
3. если у него справа – ничего нет, а слева - поддерево:
If (q^.Right = Nil) And (q^.Left <> Nil) Then
If (v^.Left = q) если он подвешен слева от предка,
Then v^.Left:=q^.Left то слева вместо него -левое поддерево узла q,
Else v^.Right:=q^.Left; иначе справа вместо него - левое поддерево узла q
Dispose(q); освобождаем от него память
{на продолжение}
4. если у него и слева и справа – поддеревья. В этом случае нужно:
· сделать шаг влево и идти до конца все время направо или
· сделать шаг вправо и идти до конца все время налево.
q – ссылка на удаляемый узел,
r – ссылка на узел, который поставим на место удаляемого,
v – ссылка на предка узла r.
Найденным узлом r заменим удаляемый узел q :
If (q^.Right <> Nil) And (q^.Left <> Nil) Then
v:=q; подтягиваем указатель v к q
r:=q^.Right; ссылкой r делаем шаг вправо
от удаляемого узла
While (r^.Left <> Nil) Do идем все время налево до конца
v:=r; подтягиваем указатель v к r
r:=r^.Left; и делаем по дереву шаг влево
End; {While}
q^.Data:=r^.Data; помещаем вместо удаляемого узла q найденный самый левый на этом пути,
If (r^.Right = Nil)
Then v^.Left:=Nil а вместо него подвешиваем Nil
Else v^.Left:=r^.Right; или его правое поддерево
Dispose(r); освобождаем память от найденного узла
Задачи, решаемые программистами, становятся все объемнее, поэтому новые методы программирования развиваются в сторону упрощения разработки и поддержания сложных программных продуктов. Основное направление развития – попытка приблизить программу, как реализацию алгоритма, к моделируемой области.
Паскаль позволяет обрабатывать сложные структуры данных: числа, символы, массивы, строки, множества, файлы и записи. Это обеспечивается таким свойством языка, как возможность описания комплексных совокупностей различных базовых типов. Запись, например, позволила создавать программы по формированию и обработке файлов записей различной структуры – баз данных. Алгоритмы обработки информационных полей записей формируются в виде процедур и функций, что позволяет создавать достаточно эффективные программы. Однако зачастую, обрабатывая файлы записей, не удавалось реализовать алгоритмы обработки информационных полей небольшим количеством процедур, а сами процедуры сделать более наглядными. Это привело к необходимости появления таких конструкций, которые бы характеризовались не только информационным составом, но и методами обработки информационных полей. Была создана высшая абстракция данных – объекты и новая технология программирования – объектно-ориентированное программирование.
Объектно-ориентированное программирование (ООП) является воплощением такого подхода и делает возможным построение алгоритма, исходя из описания объектов решаемой задачи. То есть основой программы становятся объекты, являющиеся отображением объектов описываемой модели. Далее, на основе сконструированных объектов описываются связи между ними, в результате чего получается полное описание модели. В отличие от аналогичного описания через переменные и процедуры, разбросанные по разным частям программы, объектное описание модели в программе намного нагляднее, что существенно упрощает работу с моделью. Использование таких возможностей ООП, как наследование и полиморфизм приводит как к более ясному описанию самих объектов, так и к удобству их использования в программе. Объектно-ориентированный подход к ее разработке позволяет провести ее сверху вниз, описывая предметную область на языке программирования, а не снизу вверх, создавая множество программных модулей и соединяя их для получения конечного описания модели.
Таким образом, объектно-ориентированное программирование – самая передовая технология современного программирования. Она является логическим продолжением структурного и модульного программирования. На определенном этапе развития программирования пришло понимание, что всякую сложную задачу для облегчения ее решения полезно разделить на простые подзадачи. Подпрограммы избавили программистов от необходимости вникать в подробности реализации простейших задач: после того, как соответствующая подпрограмма создана, ею можно пользоваться, не зная, как она устроена. Необходимо только быть в курсе, что делает та или иная процедура или функция. Позже эта идея получила дальнейшее развитие. Речь идет о концепции модулей.
Модуль – это отдельно компилируемый файл Паскаля, в котором могут содержаться описания констант, переменных, типов данных, структур, а также процедур и функций. ООП – результат естественной эволюции более ранних методологий программирования. Подобно тому, как подпрограмма позволяет программисту не вникать в подробности реализации простейших задач, с помощью ООП можно манипулировать данными, не зная, как эти данные организованы.
В основе объектно-ориентированного программирования лежат понятия объекта, инкапсуляции, наследования и полиморфизма.
Объекты – это сложные структуры данных, которые взаимодействуют друг с другом и окружающим миром, моделируя состояние и взаимодействие объектов реального мира. Объекты напоминают записи: они тоже включают в себя разнотипные поля. Но кроме полей, они включают процедуры и функции, использующие эти поля как глобальные параметры, то есть определяющие поведение объекта.
Инкапсуляция – это соединение данных и подпрограмм их обработки в единой структурной единице, защищающее эти данные от некорректного использования. Эта структурная единица, как уже было сказано, является сложным описанием, задающим тип (он называется классом). Она позволяет использовать переменные данного класса – объекты. Представление данных скрывается внутри объектов, и они напрямую (непосредственно) недоступны пользователю. Доступ к ним (инициализация, изменение) возможен только с помощью специальных подпрограмм, образующих интерфейс класса. Это позволяет отделить использование операций от их реализации и упрощает программирование. Мы сталкивались с такой ситуацией в модулях, когда интерфейс и реализация подпрограмм модуля разъединены – интерфейс (Interface) открыт пользователям, а реализация подпрограмм – их текст (Implementation) – закрыт. Подпрограммы обработки данных объекта (методы) становятся такими же компонентами объекта, как и сами данные (поля). Это позволяет наделять объекты собственным поведением, реализуя их взаимодействие путем вызова интерфейсных подпрограмм.
Наследование состоит в том, что при определении нового класса (потомка) может быть использован другой, ранее определенный класс (предок). Наследование позволяет использовать (наследовать) поля и методы класса-родителя, не переопределяя их в классе-потомке. В нем обычно добавляются новые поля и связанные с ними методы, а также переопределяются некоторые методы класса-родителя. Наследование позволяет строить и использовать иерархию классов. От библиотек подпрограмм, характерных для ранних стадий развития программирования, мы переходим к библиотекам классов.
Инкапсуляция и наследование обеспечивают свойство полиморфизма операций над объектами – способ выполнения операции, определенный для класса-родителя, можно изменить в классе-потомке, но реализовать методом с тем же именем. То есть полиморфизм – это существование различных реализаций одной и той же операции над данными для объектов разных классов в одной иерархии объектов. Он позволяет использовать один и тот же интерфейс для разных классов, не вникая в различия реализации операций, скрытых в классах.
Пример: создать программу, рисующую на экране точку (используется модуль Graph) и перемещающую ее на некоторое расстояние.
если это лист – то безболезненно его удаляем (q – указатель на удаляемый узел, v – указатель на его предка):
{на продолжение}
