Programmirovanie na yazike visokogo urovnya

Построение двоичного дерева основано на принципедобавленияочередного элемента в зависимости от значения его информативной части в правое или в левое поддерево. В правое поддерево новый элемент попадает в случае если его информационная часть больше информационной части корня, в левое поддерево в противном случае. Структуру двоичного дерева можно описать так: typeTypeElm= Char;Assoc= ^ElementOfTree;ElementOfTree= recordElement: TypeElm;Left, Right: Pointerend;4.1 Поиск элемента в дереве.

Функция поиска в двоичном дереве основана на прохождении с вершины дерева по его узлам и сравнении информативной части узла с заданным параметром. functionFoundInTree (Element: TypeElm; var Tree, Result: Pointer): Boolean;varServVar: Assoc;b: Boolean;beginb:= False;ServVar:=Tree;//если дерево не пустоifTree <> nilthenrepeatifServVar^.Element= Element then b:= Trueelse//выбор дальнейшего маршрута в зависимости от значения узлаifElement < ServVar^.Element then ServVar:= ServVar^.LeftelseServVar:= ServVar^.Rightuntil b or (ServVar= nil);FoundInTree:= b;Result:=ServVarend;4.2 Добавление нового элемента в дерево.

Добавление нового элемента в дерево реализуется через реализацию поиска вершины -«предка» нового элемента, а затем непосредственного добавления нового элемента в дерево по найденной позиции. Ниже приведен пример программного кода процедуры поиска «предка» для нового элемента. functionSearchNode (Element: TypeElm; varTree, Result: Assoc): Boolean;varServVar1, ServVar2: Assoc;b: Boolean;beginb:= False;ServVar1:= Tree;if Tree <> nil thenrepeatServVar2:= ServVar1;ifServVar1^.Element= Element then b:= True // элементнайденelsebegin//сохранение текущей обрабатываемой вершиныServVar2:= ServVar1;ifElement < ServVar1^.Element then ServVar1:=ServVar1^.LeftelseServVar1:= ServVar1^.Rightenduntil b or (ServVar1= nil);SearchNode:= b;Result:=ServVar2end;Данная функция похожа на ранее описанную функции поиска элемента дерева (FoundInTree), но в качестве побочного эффекта фиксируется ссылка на вершину, в которой был найден заданный элемент (в случае успешного поиска), или ссылка на вершину, после обработки которой поиск прекращен (в случае неудачного поиска). Ниже представлен программный код процедурыдобавления элемента в двоичное дерево: procedureIncludeInTree (Element: TypeElm; var Tree: Assoc);varResult, Node: Assoc;beginif not SearchNode (Element, Tree, Result) then begin//создание новой вершины в деревеnew (Node);Node^.Element:= Element;Node^.Left:= nil;Node^.Right:= nil;//в случае пустого дерева, новый элемент становится вершиной //дереваif Tree= nil then Tree:= Nodeelse//подсоединитьновуювершинукдеревуifElement < Result^.Element then Result^.Left:= NodeelseResult^.Right:= Nodeendend;Двоичное дерево можно рассматривать как рекурсивную структуру данных, состоящую из корневой записи, указывающей на левое и правое поддерево. Оба поддерева имеют такую же структуру: корень поддерева и правое и левое поддеревья. Для представления двоичного дерева как рекурсивную динамическую структуру целесообразно модифицировать описание типа дерева, приведенное ранее, а именно удобнее изменить тип указателя на левое и правое поддеревья с нетипизированного (Pointer) на типизированный: typeTypeElm1= Char;Assoc1= ^ElementOfTree1;ElementOfTree1= recordElement: TypeElm1;Left, Right: Assoc1end;Используя новое описание, процедуравставкиэлементарекурсивно выглядит следующим образом: procedure IncludeInTree2(NewElement: Assoc1; varSubTree: Assoc1);beginifSubTree= nil then beginSubTree:=NewElement;NewElement^.Left:= nil;NewElement^.Right:= nil;endelseifNewElement^.Element < SubTree^.Element thenIncludeInTree2(NewElement, SubTree^.Left)elseIncludeInTree2(NewElement, SubTree^.Right)end;4.3 Удаление элемента дерева.

Реализация данной операции осложнена тем, что в общем случае, в удаляемую вершину входит одна связь, а выходят две. Поэтому, необходимо найти подходящий элемент дерева, который можно было бы вставить на место удаляемого. Этот элемент является либо самым правым элементом левого поддерева (для достижения этого элемента необходимо перейти в следующую вершину по левой ветви, а затем, переходить в очередные вершины по правым ветвям до тех пор, пока очередная такая ссылка не будет равна nil), либо самый левый элемент правого поддерева (для достижения этого элемента необходимо перейти в следующую вершину по правой ветви, а затем, переходить в очередные вершины по левым ветвям до тех пор, пока очередная такая ссылка не будет равна nil). Процедура исключения элемента из двоичного дерева должна различать три случая:

1. элемента с заданной информативной частью в дереве нет; 2. элемент с заданной информативной частью имеет не более одной ветви; 3. элемент с заданной информативной частью имеет две ветви. Ниже приведен пример программной реализации процедуры удаления элемента дерева: procedureDeleteElementOfTree (var Tree: Assoc1; Element: TypeElm1);varServVar1: Assoc1;procedure Del (varServVar2: Assoc1);beginifServVar2^.Right= nil then beginServVar1^.Element:= ServVar2^.Element;ServVar1:= ServVar2;ServVar2:=ServVar2^.Leftendelse Del (ServVar2^.Right)end;begin//удаление элемента с информативным полем равным Element из дерева TreeifTree= nilthen//первый случай процедуры удаленияwriteln ('Элемент не найден')else//поискэлементасзаданнымключомifElement < Tree^.Element then DeleteElementOfTree (Tree^.Left, Element) elseifElement > Tree^.Element thenDeleteElementOfTree (Tree^.Right, Element) elsebegin//элемент найден, необходимо его удалитьServVar1:=Tree;//второй случай процедуры удаленияifServVar1^.Right= nilthenTree:= ServVar1^.LeftelseifServVar1^.Left= nil thenTree:= ServVar1^.Rightelse//третийслучайпроцедурыудаленияDel (ServVar1^.Left)endend;Рекурсивная процедура «Del» носит вспомогательный характер и вызывается для реализации удаления в третьем случае, переходя к самому правому элементу левого поддерева удаляемого элемента и заменяет информационное поле удаляемого на значение поля найденного элемента.

4.4 Вывод элементов дерева.

Реализация данной задачи также решается с помощью рекурсии: procedurePrintTree (Tree: Pointer);varServVar: Assoc1;beginServVar:= Tree;writeln (ServVar^.Element);ifServVar^.Right <> nil then PrintTree (ServVar^.Right);ifServVar^.Left <> nil then PrintTree (ServVar^.Left);end;Заключение.

Использование при программировании динамических структур и данных является не только признаком «хорошего тона» среди программистов, но и показателем уровня самого программиста: не даром на заре развития компьютерной техники очень ценились именно советские программисты, из-за их способности рассчитывать и использовать минимальное количество оперативной памяти для работы программы. В настоящей работе рассмотрены основные виды ссылочных типов в языке программирования Паскаль и основные операции над ними. Грамотное применение описанных в работе динамических переменных позволит повысить производительность и быстродействие программного продукта.

Список литературы

Рапаков Г. Г. и Ржецукая С. Ю. TurboPascal для студентов и школьников. BHV — С.-Петербург 2004.

Меженный О. А. TurboPascal: учитель программирования. Диалектива 2001.

Культин.

Н. Программирование в TurboPascal и Delphi. BHV 2003.

Фаронов В. В. TurboPascal: учебное пособие. BHV 2006.

Приложение 1. procedureInclWithSort (NewElement: DynamicStr; varHeadStr: Pointer);varCurrAssoc, PredAssoc: DynamicStr; //соответственно.

Тек_Ссыли //Пр_СсылIsFounded: Boolean;beginCurrAssoc:=HeadStr;PredAssoc:= nil;IsFounded:= False;while (CurrAssoc <> nil) and not IsFounded do beginifNewElement^.Element > CurrAssoc^.Element thenbegin//перейтикследующемуэлементуPredAssoc:=CurrAssoc;CurrAssoc:=CurrAssoc^.NextElementendelseIsFounded:= Trueend;//позиция вставки нового элемента найденаifPredAssoc= nilthenbegin//вставка нового элемента в начало спискаNewElement^.NextElement:= HeadStr;HeadStr:=NewElementend;if (PredAssoc <> nil) and (CurrAssoc <> nil) then begin//вставка элемента между элементами, на которые указывают //ссылки PredAssocCurrAssocNewElement^.NextElement:= PredAssoc^.NextElement;PredAssoc^.NextElement:= NewElementend;if (PredAssoc <> nil) and (CurrAssoc= nil) then begin//вставкавконецспискаPredAssoc^.NextElement:= NewElement;NewElement^.NextElement:= nilendend;