22301

Работа с элементами списка

Лекция

Информатика, кибернетика и программирование

Затем новый элемент списка заполняется информацией: NOV^ := DAT;. Для поиска места подключения нового элемента надо просмотреть все элементы списка от его начала до элемента имеющего NZ = KEY или до конца списка. Продвижение вдоль списка от его начала к его концу осуществляется с помощью двух указателей: CUR и PR.

Русский

2013-08-04

1.26 MB

0 чел.

локальном указателе списка. Затем новый элемент списка заполняется информацией: NOV^ := DAT;.

Новый элемент должен быть подключен к списку, не нарушив упорядоченности его элементов, т. е. после элемента, имеющего NZ меньше KEY, и до элемента, имеющего NZ не менее KEY. Для поиска места подключения нового элемента надо просмотреть все элементы списка от его начала до элемента, имеющего NZ >= KEY, или до конца списка. Продвижение вдоль списка от его начала к его концу осуществляется с помощью двух указателей: CUR и PR.

Схематично продвижение указателей вдоль списка от его начала к концу для поиска места нового элемента представлено на рис. 24.

Рис. 24

Схема перемещения указателей вдоль списка для подключения нового элемента

При этом анализируются значения CUR, CUR^ .NZ и KEY:

1) если CUR  <>   NIL и (CUR^NZ   <   KEY), т. е. список не пуст и значение
NZ текущего элемента списка меньше значения KEY, происходит перемещение указателей CUR и PR на один элемент вправо, к концу списка, с помощью операторов:

PR   := CUR; - указатель предыдущего элемента адресует, текущий;

CUR    :=   CUR^.PTR;   - указатель текущего  элемента  переключается  на следующий справа элемент списка;

2) если CUR   =   NIL или CUR^.NZ   >=   KEY, продвижение указателей CUR
и
PR прекращается, так как место для нового элемента в списке найдено;
это может произойти в одном из случаев:

а) обнаружен конец списка: CUR = NIL;

б) найден элемент списка, значение ключа которого не меньше KEY.

После того как место для нового элемента найдено, элемент надо включить в список (см. программу листинга 39) с помощью указателей:

справа от нового элемента - путем определения значения его указателя:
NOV^.PTR   :=  CUR;

слева - путем определения значения указателя на начало нового элемента.

Для определения значения указателя слева на новый элемент списка анализируется значение PR:

1) если PR  =  NIL, т. е. движения вдоль списка не было, новый элемент становится в начало списка: указатель его начала (вершины) получает значение адреса нового элемента: S   := NOV; это может быть в одном из двух случаев:

а) CUR  =   PR  =  NIL; - список пуст и новый элемент становится первым
и единственным его элементом;

б) CUR  <>  NIL;   PR   =  NIL;  - список не пуст, но новый элемент имеет
значение ключа, меньшее, чем ключ первого элемента;

2) если PR о NIL, т. е. было движение вдоль списка, PR адресует левый элемент старого (не дополненного) списка, к которому и присоединяется новый элемент списка: PR^.PTR := NOV;.

На этом выполнение процедуры DOP завершается.

Процедура СНТ предназначена для вывода данных всего списка. Ее формальным параметром является S - указатель на начало списка. Локальная переменная CUR - указатель на очередной элемент списка; начальное значение CUR = S.

Сначала проверяется заполненность списка с помощью функции РР; она возвращает значение TRUE, если список пуст. При этом выполнение процедуры СНТ завершается. Если результат функции РР = False, т. е. список не пуст, начинается вывод значений всех элементов списка с использованием указателя CUR.

Для этого при каждом значении CUR, не равном NIL:

выводится    содержимое    очередного    элемента    с    помощью    процедуры
Р(
CUR^) ;;

указатель  CUR  переключается   на  следующий   элемент   списка:   CUR    : =
CUR^.PTR;.

По достижении конца списка, т. е. при значении CUR = NIL, выполнение процедуры СНТ завершается.

Процедура POISK предназначена для поиска и вывода требуемого элемента списка. Поисковым признаком (ключом) является номер зачетки. Формальными параметрами процедуры POISK являются:

S - указатель на начало списка;

TNZ - требуемый номер зачетки - значение поискового признака.

Схема алгоритма процедуры POISK представлена на рис. 25.

Рис. 25

Схема алгоритма процедуры POISK - поиска и вывода требуемого элемента списка

CUR - локальная переменная процедуры POISK с начальным значением: CUR = S. До начала поиска производится проверка заполненности списка и выдача сообщения аналогично такой проверке в процедуре СНТ. Если список не пуст, организуется продвижение вдоль списка от его начала до элемента со значением NZ = TNZ или до конца списка. Для этого производится анализ значения результата следующего выражения:

(CUR   <>   NIL)    AND    (CUR^.NZ   <>   TNZ)

  1.  если оно истинно, т. е. конец списка не достигнут и значение NZ очередного элемента списка не равно заданному, то указатель CUR перемещается
    к следующему элементу списка:
    CUR   :=  СUR^ .PTR;;
  2.  если оно ложно, поиск завершен, движение вдоль списка прекращается;
    это может быть в одном из двух случаев:

а) список исчерпан (CUR = NIL);

б) найден элемент списка с NZ = TNZ - требуемым значением ключа (номера зачетки).

Распознавание этих ситуаций производится из анализа CUR:

  1.  если CUR   =   NIL, т. е. достигнут конец списка, а требуемый элемент не
    найден, то выдается сообщение Поиск  неуспешен;
  2.  если CUR<>NIL, т, е. CUR^.NZ  = TNZ - найден требуемый элемент
    списка, выводится его значение с помощью процедуры
    P(CUR^);.

На этом выполнение процедуры POISK завершается.

Процедура UD .предназначена для поиска и удаления заданного элемента списка. Формальные параметры процедуры: S - указатель списка, параметр-переменная; TNZ - требуемый номер зачетки - значение поискового признака.

Локальные переменные процедуры UD: CUR - указатель текущего элемента списка; PR - указатель предыдущего элемента списка.

Процесс поиска требуемого элемента в списке идентичен этому процессу процедуры POISK.

Схематично удаление заданного элемента из списка приведено на рис. 26.

Рис. 26

Схема удаления заданного элемента списка

Схема алгоритма процедуры UD представлена на рис. 27.

Отличие процедуры UD от процедуры POISK состоит в том, что найденный элемент должен быть удален. Для этого по завершении поиска элемента списка анализируются поочередно значения CUR и PR:

  1.  если CUR  =  NIL, т. е. достигнут конец списка, а требуемый элемент списка не найден, выдается сообщение Удаление неуспешно;
  2.  если CUR   <>   NIL, т. е. конец списка не достигнут и найден требуемый
    элемент списка, на который и указывает
    CUR, производится вывод его значения с помощью процедуры: Р   (CUR^); затем определяется: удаляется
    первый или очередной элемент списка.

Рис. 27

Схема алгоритма процедуры UD - удаления заданного элемента из списка

Для этого анализируется значение PR:

  1.  если PR = NIL, т. е. удаляется первый элемент - из вершины списка, то S
    - указатель начала списка переносится на следующий, второй элемент списка:
    S   :=  CUR^PTR;;
  2.  если PR   <>   NIL, т. е. удаляется очередной или последний элемент списка, то указатель слева от удаляемого элемента переключается на элемент
    справа от удаляемого элемента, исключая из списка удаляемый элемент
    (см. схему рис. 26):
    PR^.PTR   :=  CUR^.PTR;.

В любом случае после успешного удаления элемента списка освобождается его ОП с помощью процедуры DISPOSE (CUR) ;.

Процедура OSV предназначена для освобождения ОП списка, т. е. для уничтожения списка. Формальный параметр-переменная процедуры: S - указатель на начало списка. Локальные переменные - указатели:

CUR - текущего элемента списка с начальным значением:   CUR   :=  S;;

PR - предыдущего элемента списка с начальным значением: PR   := NIL;.

Для освобождения ОП указатель CUR перемещается вдоль списка до тех пор, пока не будет достигнут его конец, т. е. значение CUR станет равным NIL. При каждом текущем значении указателя CUR, не равном NIL, происходит продвижение вдоль списка:

PR   :=   CUR;  - указатель предыдущего элемента переключается на текущий элемента списка;

CUR   :=   CUR^.PTR;  - указатель CUR переключается на следующий элемент списка; DISPOSE (PR) ; - освобождается ОП очередного элемента списка.

По завершении освобождения ОП обнуляется указатель на начало списка: S := NIL;. На этом выполнение процедуры OSV завершается.

Бинарное дерево

Дерево - это нелинейная связанная структура. Оно состоит из узлов, соединенных между собой указателями. Каждый узел представляет собой запись, в которую входят данные и указатели, связывающие записи в одну связанную структуру. Дерево имеет корень - это узел, из которого только выходят связи, но в который они не входят. Каждый узел может быть связан указателями с несколькими другими узлами. Узел, подключенный к данному, называют ветвью или поддеревом. Узлы, в которые связи только входят, но не выходят, называют листьями.

Дерево, в котором каждый узел связан не более чем с двумя другими узлами, называют бинарным деревом. В такой структуре запись каждого узла содержит 2 указателя: для связи с левым и правым поддеревом (ветвью). Обычно дерево изображается корневым узлом кверху.

Рис. 28

Пример бинарного дерева из чисел

На рис. 28 приведен пример бинарного дерева, записи которого содержат целые числа.

На рис. 28 число 20 содержит узел корня дерева, нулевой уровень дерева; числа 10, 30 - узлы его левого и правого поддеревьев, первый уровень; числа 8, 12, 22, 34 - листья - узлы без ветвей.

Бинарные деревья используют для поиска и сортировки данных. Для этого дерево формируют таким образом, чтобы строение дерева учитывало значение элемента записи (ключа сортировки), по которому производится упорядочение. Например, можно к корню дерева и к каждому узлу дерева присоединять узел следующего уровня таким образом, чтобы слева располагались узлы с записями, у которых ключ сортировки меньше, чем у данного узла, а справа -у которых значение ключа не меньше, т. е. больше или равно ключу записи данного узла.

Базовые операции над бинарным деревом:

  1.  добавление нового элемента к дереву;
  2.  поиск по дереву по заданному значению ключа;
  3.  обход дерева для получения и вывода сортированной   последовательности
    записей дерева;
  4.  удаление из дерева узла с заданным значением ключа;
  5.  уничтожение дерева и освобождение ОП, которую оно занимало.

Рассмотрим названные операции на примере дерева, состоящего из записей, в состав которых для простоты входит только одно число. Пример этого дерева дан на рис. 28. В листинге 40 приведена программа для формирования и тестирования дерева

Листинг 40. Тестирование дерева с числами.

PROGRAM   DEREVO_AR;   USES CRT;
TYPE

PSTRUCT = ^STRUCT; {- тип - указатель на  запись}

STRUCT  =  RECORD {   Запись   в   составе:    }

А   :   BYTE; {   -  целое  число   }

LEFT,RIGHT : PSTRUCT;{-  указатели  на левое  и  правое  поддерево}

END;

VAR TREE : PSTRUCT; { - указатель на корень дерева }

FI, { - файл для исходных данных }

FR : TEXT; .{ - файл для результатов }

{  Вывод записи }

PROCEDURE P( Z: STRUCT); BEGIN  WRITE (FR, Z.A : 4); END;

{   Включение нового узла   }

PROCEDURE FORM (VAR TR : PSTRUCT; Z : STRUCT ); BEGIN

IF TR = NIL { Формирование новой записи: }

THEN BEGIN NEW (TR); TR^ := Z; END { - в данном узле }

ELSE IF Z.A<TR^.A THEN FORM(TR^.LEFT,Z) {- в левой ветви}

ELSE FORM(TR^.RIGHT, Z);  { - в правой ветви}

END;

{ - - Ввод всех чисел для дерева -  }

PROCEDURE VVOD(NF : STRING);

VAR   Z : STRUCT; { - скалярная запись для ввода }

BEGIN

ASSIGN (FI,NF); RESET(FI)-;

WRITELN(FR, 'ЗАПОЛНЕНИЕ ДЕРЕВА НОВЫМИ ЗАПИСЯМИ');

WHILE NOT SEEKEOF(FI) DO  WITH Z DO  BEGIN

READ (FI, A ); P(Z); { - ввод и вывод данных записи }

 LEFT:=NIL; RIGHT:=NIL; {- начальные значения указателей} FORM(TREE, Z); { - вызов для формирования нового узла }

END;

WRITELN( FR ) ;  CLOSE ( FI ) ; END;

{ —  Обход дерева для вывода сортированных данных дерева  }

PROCEDURE SORT(TR: PSTRUCT);

BEGIN

IF TR <> NIL THEN BEGIN

SORT (TR^.LEFT);   { - спуск по левому поддереву } P(TR^);       { - после обхода левого поддерева }

SORT (TR^.RIGHT); { - спуск по правому поддереву } END; END;

{  Поиск по дереву  }

PROCEDURE POISK_TR( TR :PSTRUCT; ТА : BYTE);

BEGIN

WHILE TR <> NIL DO

IF ТА=TR^.A THEN BEGIN P(TR^); EXIT; END{- запись найдена}

ELSE

IF ТА<ТR^.А THEN TR:=TR^.LEFT  { - спуск по левой ветви } ELSE TR := TR^.RIGHT;  { - спуск по правой ветви } WRITE(FR, ' - ЗНАЧЕНИЕ ОШИБОЧНО'); END;

{ - - Поиск по заданному значению числа   }

PROCEDURE POISK;

VAR  ТА : BYTE;

BEGIN  ASSIGN ( FI, 'TRPOI.DAT');     RESET ( FI );

WHILE NOT SEEKEOF(FI) DO  BEGIN

READLN(FI, ТА); { - ввод требуемого числа }

IF ТА=0 THEN BEGIN WRITELN(FR,'НЕТ ЗНАЧЕНИЯ ДЛЯ ПОИСКА');

CONTINUE END;

WRITE ( FR, #10#13, '  ПОИСК  = ', ТА );

POISK_TR(TREE,ТА); { - вызов процедуры поиска по дереву }

END; END;

{  Удаление заданного узла дерева :  }

PROCEDURE UD_UZ (VAR TR: PSTRUCT; ТА : BYTE);

VAR OLD : PSTRUCT;

{  Удаление записи с двумя поддеревьями }

PROCEDURE UD(VAR TTR: PSTRUCT);

BEGIN IF TTR^.RIGHT = NIL THEN  { - узел найден }

BEGIN {TTR - указатель на узел, который надо перенести}

{ Копирование из него данных в удаляемый узел: }

TR^.A := TTR^.A;

OLD:=TTR; { - сохранить указатель на перемещенный узел}
TTR := TTR^.LEFT; { -
исключение узла TTR }
DISPOSE (OLD);  { -
освободить ОП перемещенного узла }
END ELSE

UD(TTR^.RIGHT); { - искать по правому поддереву } END;

BEGIN

IF TR = NIL THEN BEGIN WRITELN(FR, 'ЗАПИСЬ НЕ НАЙДЕНА'); EXIT; END;

IF ТА < ТR^.А THEN UD_UZ (TR^.LEFT, ТА) { - поиск по левому поддереву }

ELSE IF ТА > TR^.A THEN UD_UZ (TR^. RIGHT, ТА) { - поиск по прав, поддереву }

ELSE

BEGIN { - ключи равны - найден удаляемый узел }

OLD := TR;     { - сохранить указатель на удаляемый узел }

IF TR^.RIGHT=NIL THEN { - есть только левое поддерево } BEGIN

TR := TR^.LEFT;  { - исключить TR - удаляемый узел }
DISPOSE (OLD);   { - освободить ОП удаленного узла }
END ELSE

IF TR^.LEFT = NIL THEN  { - есть только правое поддерево } BEGIN

TR := TR^.RIGHT;   { - исключить TR - удаляемый узел }
DISPOSE (OLD);     { - освободить ОП удаленного узла }
END ELSE { - есть оба поддерева }

UD(TR^.LEFT);    { - искать замену узлу } END; END;

{  Обход дерева для его удаления }

PROCEDURE UDDR(TR: PSTRUCT); BEGIN

IF TR <> NIL THEN BEGIN UDDR(TR^.LEFT); {- спуск по левому поддер. }
P
(TR^); { - вывод удаляемой записи }

UDDR (TR^.RIGHT);     { - спуск по правому поддер. } DISPOSE(TR);     { - после обхода левого и правого поддерева }

TR := NIL;  END; END;

{    Основная программа  }

BEGIN

CLRSCR;     ASSIGN(FR,'TR.RES'); REWRITE(FR);
WRITELN(FR,'СОЗДАНИЕ ДЕРЕВА:');
TREE := NIL; { - начальное значение: дерево пусто }

VVOD('TR.DAT');

WRITELN(FR, 'СОРТИРОВКА ДЕРЕВОМ:');       SORT(TREE); WRITE(FR, #10#13,' УДАЛЯЕМ = ', 34);    UD UZ (TREE, 34 );

WRITELN(ДЛЯ ПРОДОЛЖЕНИЯ НАЖМИТЕ КЛАВИШУ ENTER');

READLN;   POISK;

WRITELN(FR, 'ВЫВОД И УДАЛЕНИЕ ДЕРЕВА:');  UDDR(TREE);

REPEAT UNTIL KEYPRESSED;  { - остановка до нажатия любой клавиши }

CLOSE(FR);

END.

В программе листинга 40 переменная TREE содержит адрес записи корня дерева. В состав записи любого узла входят 2 указателя:

LEFT - указатель на левый узел данного узла;

RIGHT - указатель на правый узел данного узла. Подпрограммы листинга для работы с деревом:

VVOD - процедура ввода исходных данных для формирования дерева с помощью процедуры FORM;

POISK - процедура ввода данных для поиска процедурой POISK_TR;

FORM - рекурсивная процедура для включения в дерево нового узла;

POISK_TR - процедура для поиска записи по заданному значению ее числа;

SORT - рекурсивная процедура для обхода дерева с целью вывода записей, сортированных по числам;

UD_UZ - рекурсивная процедура для удаления узла с записью, заданной ее числом;

UD - рекурсивная процедура, вложенная в процедуру UD_UZ, для поиска и удаления узла с двумя поддеревьями;

UDDR - рекурсивная процедура для обхода дерева и уничтожения каждого

его узла.

Рассмотрим тексты процедур для тестирования дерева с помощью данных текстовых файлов.

Формирование дерева

Для формирования дерева с помощью процедуры VVOD исходные данные (числа узлов дерева) вводятся из файла FI. Формирование нового узла для каждого введенного числа производится посредством вызова процедуры FORM(TREE, Z);.

Процедура FORM предназначена для формирования нового узла с данными, расположенными в скалярной записи Z.

Процедура имеет следующие формальные параметры:

TR - параметр-переменная - указатель на создаваемый узел или на узел, в котором производится поиск места для нового узла;

Z - параметр-значение - запись для нового узла.

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

Определение места узла для новой записи производится на основе анализа

значения указателя TR:

  1.  если TR  =  NIL, например если дерева пока нет или найдено место для
    нового узла, выделяется ОП для записи с помощью
    NEW(TR); и в нее копируется содержимое записи ТR^ := Z;, при этом значение указателя TR
    (параметра-переменной) возвращается в качестве результата;
  2.  если TR не равно NIL, т. е. в этом узле уже есть запись, производится
    анализ  ключа данного  
    TR-узла  сравнением  его  с  ключом  новой  записи
    и рекурсивный вызов процедуры
    FORM:

а) если Z.A < TR^.А, т. е. новое значение меньше ключа данного узла,
то  продолжается  поиск  места  новой  записи  по указателю  на левую
ветвь данного узла; для этого производится рекурсивный вызов процедуры
FORM:

FORM(TR^.LEFT, Z);

б) если Z.A >= TR^.A, т. е. новое значение не меньше ключа данного
узла, то продолжается поиск места новой записи по указателю на правую  ветвь данного узла;  для  этого  производится  рекурсивный  вызов
процедуры
FORM:

FORM(TR^.RIGHT,   Z);

Рекурсивный вызов процедуры FORM производится до тех пор, пока не будет найден узел, у которого TR - требуемый указатель равен NIL.

Поиск по дереву

Для тестирования поиска процедурой POISK исходные данные (требуемые числа) вводятся из файла FI. Поиск узла дерева для каждого введенного числа производится посредством вызова процедуры POISK_TR(TREE, ТА) ;.

Процедура POISK_TR предназначена для поиска и вывода найденной записи. Процедура имеет 2 формальных параметра-значения:

TR - указатель на анализируемый узел;

ТА - требуемое значение ключа.

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

На каждой итерации производится анализ значения ключа текущего узла сравнением его с ТА - искомым значением:

  1.  если ТА  =  TR^A, т. е. найден требуемый узел, выводится его значение с
    помощью процедуры Р; и завершается выполнение процедуры
    POISK_TR;
  2.  если ТА  <>  TR^.A, узел не найден и организуется дальнейший поиск по
    дереву; для этого производится выбор одного из указателей следующего
    уровня дерева на основе анализа ТА:

а) если ТА < R^.А, дальнейший поиск производится по левому поддереву;
для этого устанавливается значение указателя
TR   := ТR^ .LEFT;;

б) если ТА >  R^.А, дальнейший поиск производится по правому поддереву;     для  этого устанавливается значение указателя: TR:=TR^.RIGHT;.

Изменение значения TR в тексте процедуры не вызовет изменения фактического параметра функции, так как формальный параметр TR является параметром-значением. Если запись не найдена до появления TR = NIL, выдается сообщение Значение ошибочно.

Сортировка деревом

Рекурсивная процедура SORT предназначена для организации обхода дерева таким образом, чтобы в результате ее выполнения были выведены записи в порядке возрастания ключа.

TR - формальный параметр-значение процедуры, указатель на анализируемый узел. В процедуре SORT для каждого узла (TR <> NIL) производится:

  1.  спуск   по   левому   поддереву   с   помощью   рекурсивного   вызова   SORT
    (
    TR^.LEFT);;
  2.  вывод записи узла после обхода левого поддерева с помощью P(TR^) ;;
  3.  спуск   по   правому   поддереву   с   помощью   рекурсивного   вызова   SORT
    (
    TR^.RIGHT);.

Освоение процедур с рекурсивным вызовом не всегда просто. Рассмотрим ее работу на примере дерева, представленного на рис.28. Для вывода сортированных данных надо обойти все дерево начиная с самого левого узла до самого правого, т. е. от значения 8 до значения 34. Все вызовы процедуры SORT схематично представлены на рис. 29. В нем для простоты вызовы процедур обозначены в виде:

S(число), где S - сокращение от SORT,

число - значение в узле, для анализа которого вызвана SORT;

Р(число) ; где Р - процедура для вывода записи со значением число;

Nil-L - нулевое значение указателя для левой ветви;

Nil-R - нулевое значение указателя для правой ветви.

Рис. 29

Схема последовательности вызовов процедур SORT и Р

В каждой строке последовательность вызовов процедур SORT и Р для одного вызова SORT связана точками. В верхней строке схемы S(20) - первый вызов SORT для А = 20. Затем вызывается S(10), из нее - S(8) - для обхода левого поддерева. Так как в узле с 8 оба указателя равны NIL, после вызова S(Nil-L) и возврата из S(8) с помощью Р(8) выводится запись самого левого узла дерева, а после вызова S(Nil-R) происходит возврат из вызова S(8) в вызов S(10) и вывод Р(10). Аналогично изложенному происходит вызов S(12) и Р(12) - вывод записи этого узла. На этом завершен вывод записей из правого поддерева, происходит возврат в вызов S(20) и выполняется Р(20). В результате этого обхода значения выведены в последовательности: 8, 10, 12, 20.

Начинается обход правого поддерева вызовом S(30). Обход правого поддерева и вывод значений записей его узлов производится аналогично обходу левого поддерева. Этот процесс можно проследить по схеме рис. 29. По завершении обработки вызова S(30) происходит возврат в вызов S(20) и завершение выполнения процедуры SORT. В результате обхода правого поддерева выводится последовательность значений: 22, 25, 30, 34.

Удаление записи из дерева

Процедура UD_UZ - одна из наиболее интересных. Она предназначена для удаления одного из узлов дерева, заданного значением числа. Схема алгоритма процедуры UD_UZ представлена на рис. 30. Формальные параметры процедуры UD_UZ:

TR - указатель на узел, начиная в котором производится поиск удаляемого

узла; ТА - значение числа узла, который надо удалить.

Локальная переменная OLD - указатель на запись.

В процессе поиска удаляемого узла дерева могут быть 3 случая:

  1.  узла с заданным ТА в дереве нет;
  2.  узел с удаляемым ТА имеет не более одной ветви;
  3.  узел с удаляемым ТА имеет 2 ветви.

Поиск по дереву производится путем обхода дерева по правой или левой ветви в зависимости от значения ТА и значения числа в анализируемом дереве с использованием рекурсивного вызова процедуры UD_UZ. Если в результате этого поиска обнаружено, что указатель TR  =  NIL, значит, такого значения в дереве нет и выдается сообщение Запись не найдена.

Если дерево есть, в начале поиска TR  <>  NIL, начинается обход дерева. Для этого сравниваются значения ТА и ТR^ .А:

  1.  если ТА  <   ТR^.А, т. е. требуемое значение меньше, чем в данном узле,
    рекурсивно вызывается
    UD_UZ   (TR^.LEFT,   ТА) - процедура для поиска
    по левой ветви; если это условие ложно, снова анализируется ТА:
  2.  если ТА  >   ТR^.А, т. е. требуемое значение больше, чем в данном узле,
    рекурсивно вызывается
    UD_UZ   (TR^.RIGHT,   ТА) - процедура для поиска по правой ветви;
  3.  если ТА не больше и не меньше, а равно TR^.A, т. е. найдено требуемое
    значение, начинается его удаление.

Сначала запоминается указатель на найденный удаляемый узел в переменной OLD: OLD := TR;.

Удаление найденного узла производится по-разному, в зависимости от того, одну или две ветви содержит этот узел. Для распознавания этих ситуаций анализируются указатели узла:

Рис. 30

Схема алгоритма процедуры UD_UZ - удаления заданного узла дерева

  1.  если TR~ . RIGHT = NIL, у этого узла нет правого поддерева; в этом случае производится исключение этого узла из дерева установкой нового значения указателя TR: TR := TR^.LEFT;, схематично это представлено на рис. 31; затем освобождается ОП исключенного узла: DISPOSE (OLD);;

2) если TR^.RIGHT <> NIL, т. е. у данного узла есть правая ветвь (поддерево), производится анализ наличия левой ветви сравнением TR^.LEFT и NIL:

а) если TR^.LEFT  =  NIL, т. е. у этого узла нет левого поддерева, а есть
только правое, производится исключение этого узла из дерева установкой нового значения указателя  
TR: TR   := TR^ .RIGHT;;

б) если TR^ .LEFT  <>  NIL, т. е. у этого узла есть и левая и правая ветви,
вызывается
UD(TR^ .LEFT) ; - процедура для поиска замены удаляемому узлу.

Рис.31

Схема исключения удаляемого узла, имеющего только левую ветвь (левое поддерево)

Если удаляемый узел имеет 2 ветви, надо найти такой узел дерева, который можно перенести на место удаляемого. Этим узлом будет самый правый узел левого поддерева удаляемого узла. Для поиска и переноса этого узла вызывается UD(TR^.LEFT) ; - рекурсивная процедура, вложенная в процедуру UD_UZ.

Формальным параметром процедуры UD является TTR - указатель на узел, который проверяется на пригодность для переноса анализом наличия у него правой ветви:

1) если TTR^.RIGHT   =   NIL, узел для переноса найден;  производится его
перенос на место удаляемого; для этого:

- копируется его содержимое на место удаляемого узла:

TR^.A   :=   TTR^.A;;

сохраняется указатель на перемещаемый узел: OLD   := TTR;;

исключается из дерева перемещаемый узел (см. рис. 31):

TTR   :=  TTR^'.LEFT;;

- освобождается ОП перемещенного узла: DISPOSE   (OLD) ;;

2) если TTR^.RIGHT   <>   NIL, поиск узла для перемещения продолжается
с помощью рекурсивного вызова этой же процедуры:
UD(TTR^ .RIGHT) ;.

Удаление всего дерева

Процедура UDDR предназначена для удаления всего дерева. Для этого организуется обход дерева аналогично обходу его в процедуре SORT и вывод каждой удаляемой записи. В результате выполнения этой процедуры все записи дерева выводятся в сортированном виде.

TR - формальный параметр процедуры, указатель на анализируемый узел. В процессе выполнения процедуры указатель на каждый узел дерева анализируется сравнением его с NIL:

1) если TR <> NIL, значит, такой узел есть, при этом:

а) производится обход левой ветви этого узла с помощью рекурсивного
вызова этой же процедуры:
UDDR   (TR^.LEFT) ;  по завершении обхода
каждая запись выводится с помощью вызова
P(TR^) ;;

б) производится обход правой ветви данного узла с помощью рекурсивного
вызова этой же процедуры:
UDDR   (TR^.RIGHT) ; по завершении обхода  левого  и  правого  поддерева  освобождается  ОП  узла  с   помощью
DISPOSE (TR) ; и обнуляется указатель: TR   := NIL;;

2) если TR   =   NIL, обход ветви завершен; начинается обратный ход по рекурсивным вызовам UDDR:

а) по завершении возврата из левой ветви (вызовы UDDR(TR^.LEFT) ;)
производится вывод удаляемой записи узла процедурой
P(TR^ ) ;

б) по завершении возврата из правой ветви (вызовы UDDR(TR^ .RIGHT) ;)
освобождается ОП удаляемого узла процедурой
DISPOSE (TR) ; и обнуляется указатель:

TR   :=  NIL;. На этом удаление узла TR процедурой UDDR завершается.

Контрольные вопросы

  1.  Что такое статические и динамические переменные? Когда надо использовать динамические переменные?
  2.  Как объявить и инициализировать указатель?
  3.  Как обратиться к значению динамической переменной с помощью указателя?
  4.  Назовите основные проблемы, связанные с указателями.
  5.  Поясните назначение и правила использования стандартных подпрограмм для работы с указателями.
  6.  Как возвратить указатель - результат выполнения подпрограммы?
  7.  Как использовать указатель на одномерный массив для работы с одномерным, (многомерным) массивом?
  8.  Как использовать указатель на многомерный массив?
  9.  Для каких задач надо использовать массив указателей?
  10.  Поясните правила объявления и использования массива указателей на динамические массивы данных различных типов.
  11.  Что такое свободные массивы? Поясните, как использовать массив указателей для работы с коллекциями массивов.
  12.  Когда надо использовать указатели для работы с подпрограммами?
  13.  Поясните использование процедурного типа для возврата результата из подпрограммы.
  14.  Поясните основные правила использования массива подпрограмм и массива указателей на подпрограммы.
  15.  Что такое связанные структуры, стек, очередь, список, дерево?
  16.  Поясните работу подпрограмм для реализации базовых операций над стеком, очередью, списком, бинарным деревом.


 

А также другие работы, которые могут Вас заинтересовать

40601. Подход RАD. Стадии реализации и внедрения 19.83 KB
  На данной фазе разработчики производят итеративное построение реальной системы на основе полученных в предыдущей фазе моделей а также требований нефункционального характера. Тестирование системы осуществляется непосредственно в процессе разработки. После окончания работ каждой отдельной команды разработчиков производится постепенная интеграция данной части системы с остальными формируется полный программный код выполняется тестирование совместной работы данной части приложения с остальными а затем тестирование системы в целом. Завершается...
40602. Стандарты проектирования 26.29 KB
  Важнейшие шаги процесса BSP их последовательность получить поддержку высшего руководства определить процессы предприятия определить классы данных провести интервью обработать и организовать данные интервью можно встретить практически во всех формальных методиках а также в проектах реализуемых на практике. ISO IEC 12207:1995 стандарт на процессы и организацию жизненного цикла. В соответствии с базовым международным стандартом ISO IEC 12207 все процессы ЖЦ ПО делятся на три группы: 1.
40603. Стандарты проектирования. АИС 53 KB
  Вендрова Проектирование ПО Ход урока Организационный момент 24 мин: Приветствие оформление документов к занятию Повторение пройденного материала применяемая методика выводы1520 мин Устные ответы на вопросы: Дайте характеристику стадии реализации по классической схеме Дайте характеристику стадии реализации по методологии RD Дайте характеристику стадии внедрения по классической схеме Дайте характеристику стадии внедрения по методологии RD Как осуществляется оценка размера приложений Перечислите основные...
40604. Создание SADT-диаграмм по произвольным проектам 574.5 KB
  Стандарт IDEF0 базируется на трех основных принципах: Принцип функциональной декомпозиции любая функция может быть разбита на более простые функции; Принцип ограничения сложности количество блоков от 2 до 8 в BPwin условие удобочитаемости; Принцип контекста моделирование делового процесса начинается с построения контекстной диаграммы на которой отображается только один блок главная функция моделирующей системы. Диаграммы главные компоненты модели все функции и интерфейсы на них представлены как блоки и дуги. Место соединения дуги...
40605. Создание ERD диаграмм методом IDEF I 499.5 KB
  Панель Toolbox Вид кнопки Назначение кнопки Создание новой сущности. Для установки категориальной связи нужно щелкнуть по кнопке далее по сущностиродителю и затем по сущностипотомку. Для связывания двух сущностей нужно щелкнуть по кнопке далее по сущностиродителю затем по сущностипотомку. Создание связи многие ко многим Создание неидентифицирующей связи После создания сущности ей нужно задать атрибуты.
40606. Построение диаграмм вариантов использования 70.24 KB
  Краткие сведения о диаграмме вариантов использования. Диаграмма вариантов использования является самым общим представлением функциональных требований к системе. Для последующего проектирования системы требуются более конкретные детали которые описываются в документе называемом сценарием варианта использования или потоком событий flowofevents.
40607. Построение диаграмм классов 196.48 KB
  Повторить общие сведения о диаграммах классов Построить диаграмму классов Сформировать отчет по практической работе №7 После того как мы определились с функциональными требованиями к системе и её границами начнём анализировать предметную область с целью построения диаграммы классов. Основные элементы диаграммы классов Основными элементами являются классы и связи между ними. Ассоциация ssocition представляет собой отношения между экземплярами классов.
40608. Построение диаграмм состояний 263.95 KB
  Повторить общие сведения о диаграммах состояний Построить диаграмму состояний Сформировать отчет по практической работе №8 Диаграмма состояний определяет последовательность состояний объектавызванных последовательностью событий. Порядок построения диаграммы Создайте диаграмму состояний для объектов класса Заказ. Соответствующая диаграмма состояний представлена на рисунке: Сохраните диаграмму.
40609. Представление конкретной модели ИС в виде DFD диаграмм 254 KB
  Шаг 1: Создание новой модели В меню File выбрать NewПоявится диалоговое окно BPwin В поле Nme напечатать Банкомат Проверить что в группе Type выбрано Dtflow DFD Нажать OKПоявился пустой прямоугольник контекстного действия. Напечатать:Банкоматзатем нажать OK. Нажать OK. Шаг 4: Рисование внешней ссылки На инструментальной панели BPwin нажать кнопку Externl Reference.