P=right(P) P:=P^.left;
  EndIf else
  EndWhile P:=P^.right;
  V=maketree(key,rec) End;
  If key   else If key   Right(Q)=V Q^.left:=V
  EndIf else
  search=V Q^.right:=V;
  Return search:=V
 
  Задания
 
  Используя генератор случайных чисел сформировать бинарное дерево, состоящее из 5 элементов (предусмотреть ручной ввод элементов). Причем числа должны лежать в диапазоне от -99 до 99. Произвести поиск с вставкой элементов в соответствии со следующими вариантами заданий:
 
  1. Числа кратные N.
  2. Нечетные числа.
  3. Числа > N.
  4. Простые числа.
  5. Числа по выбору.
  6. Случайное число.
  7. Составные числа.
  8. Числа в интервале от X до Y.
  9. Числа, сумма цифр (по модулю) которого > N.
  10. Числа, сумма цифр (по модулю) которого < N.
  11. Числа, сумма цифр (по модулю) которого лежит в интервале от X до Y.
  12. Числа, взятые по модулю, квадратный корень которых целое число.
  где: N, X, Y - задается преподавателем.
 
 
 
  Лабораторная работа № 13. "ПОИСК ПО ДЕРЕВУ С ИСКЛЮЧЕНИЕМ"
 
 Цель работы: исследовать и изучить методы поиска с помощью дерева.
 
 Задача работы: овладеть навыками написания программ для поиска с помощью бинарного дерева на языке программирования ПАСКАЛЬ .
 
  Порядок работы :
 * изучить описание лабораторной работы;
 * по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
 * написать программу на языке ПАСКАЛЬ;
 * отладить программу;
 * решить задачу;
 * оформить отчет.
 
  Краткая теория
 
  Удаление узла дерева не должно нарушать упорядоченность дерева. При удалении возможны следующие варианты расположения узлов:
 1) найденный узел является листом - он просто удаляется (рис.1);
 
 
 
 2) найденный узел имеет только сына - в этом случае сын перемещается на место удаленного отца (рис.2);
 
 
 
 3) у удаляемого отца два сына - в этом случае основная трудность состоит в удалении отца, поскольку в удаляемую вершину входит одна стрелка, а выходит две.
  В этом случае нужно найти подходящее звено поддерева, которое можно было бы вставить на место удаляемого, причем это подходящее звено должно просто перемещаться. Такое звено всегда существует:
  - это самый правый элемент левого поддерева (для достижения этого звена необходимо перейти в следующую вершину по левой ветви, а затем переходить в очередные вершины только по правой ветви до тех пор, пока очередная ссылка не будет равна nil);
  - это самый левый элемент правого поддерева (для достижения этого звена необходимо перейти в следующую вершину по правой ветви, а затем переходить в очередные вершины только по левой ветви до тех пор, пока очередная такая ссылка не будет равна nil).
  Очевидно, что такие подходящие звенья могут иметь не более одной ветви.
  Алгоритм
  Рассмотрим алгоритм в котором вместо удаляемого узла ставится самый левый узел правого поддерева. Удалим узел с номером 150, тогда на его место станет элемент под номером 152, т.к. он является самым левым из правого поддерева.
  Введем следующие обозначения:
 
  P - рабочий указатель
  Q - указатель отстающий от Р на один шаг
  V - указатель на элемент, который будет замещать удаляемый узел
  T - указатель, отстает от V на один шаг
  S - указатель, опережает V на один шаг
 
 
 
  Пример программы удаления элементов бинарного дерева
  (Псевдокод)
 
  Q=nil
  P=Tree
  While (P<>nil)and(K(P)<>key)do {поиск узла с нужным ключем}
  If key   Else P=Right(P)
  EndIf
  EndWhile
  If P=nil then "Ключ не найден" {проверка если такого элемента нет}
  Return {выход}
  EndIf
  If Left(P)=nil then V=Right(P) {если левая ссылка равна nil
  Else
  If Right(P)=nil then V=Left(P)
  Else
  GetNode(P)
  T=P
  V=Right(P) S = Left(V)
  While S <> nil {поиск самого }
 
  T = V {левого эл-нта}
  V = S {правого поддерева}
  S = Left(V)
  EndWhile
  If T <> P then
  "V-не сын"
  Left(T) = Right(V)
  Right(V)= Right(P)
  EndIf
  Left(V) = Left(P)
  If Q = nil then
  "p - корень"
  Tree = V
  Return
  EndIf
  If P = Left(Q) then
  Left(Q) = V
  Else
  Right(Q)= V
  EndIf
  EndIf
  EndIf
  FreeNode(P)
  Return
  Иллюстрация процесса удаления узла 150, в соответствии с вышеприведенным алгоритмом (красным цветом выделены новые связи в дереве).
 
 
 
  Конечный вариант дерева после удаления
 
 
 
 
  Задания
 
  Используя генератор случайных чисел сформировать бинарное дерево, состояшее из 15 элементов (предусмотреть ручной ввод элементов). Причем числа должны лежать в диапазоне от -99 до 99. Произвести поиск с удалением элементов в соответствии со следую-щими вариантами заданий:
  1. Числа кратные N.
  2. Нечетные числа.
  3. Числа > N.
  4. Числа < N.
  5. Числа по выбору.
  6. Простые числа.
  7. Составные числа.
  8. Числа в интервале от X до Y.
  9. Числа, сумма цифр (по модулю) которого > N.
  10. Числа, сумма цифр (по модулю) которого < N.
  11. Числа, сумма цифр (по модулю) которого лежит в интервале от X до Y.
  12. Числа, взятые по модулю, квадратный корень которых целое число.
  где: N, X, Y - задается преподавателем.
 
 
 
  ТЕСТЫ К ЛАБОРАТОРНЫМ РАБОТАМ
  Лабораторная работа 1. Полустатические структуры данных (стеки).
 
 1. В чём особенности очереди ?
 - открыта с обеих сторон ;
 - открыта с одной стороны на вставку и удаление;
 - доступен любой элемент.
 2. В чём сосбенности стека ?
 - открыт с обеих сторон на вставку и удаление;
 - доступен любой элемент;
 - открыт с одной стороны на вставку и удаление .
 3. Какую дисциплину обслуживания принято называть FIFO?
 - стек;
 - очередь ;
 - дек.
 4. Какая операция читает верхний элемент стека без удаления?
 - pop;
 - push;
 - stackpop .
 5. Какого правило выборки элемента из стека ?
 - первый элемент;
 - последний элемент ;
 - любой элемент.
 
 
 Лабораторная работа 2.Списковые структуры данных (односвязные очереди).
 
 1. Как освободить память от удаленного из списка элемента ?
 - p=getnode;
 - ptr(p)=nil;
 - freenode(p) ;
 - p=lst.
 2. Как создать новый элемент списка с информационным полем D ?
 - p=getnode;
 - p=getnode; info(p)=D ;
 - p=getnode; ptr(D)=lst.
 3. Как создать пустой элемент с указателем p ?
 - p=getnode ;
 - info(p);
 - freenode(p);
 - ptr(p)=lst.
 4. Сколько указателей используется в односвязных списках ?
 - 1 ;
 - 2;
 - сколько угодно.
 5. В чём отличительная особенность динамических объектов?
 - порождаются непосредственно перед выполнением программы;
 - возникают уже в процессе выполнения программы ;
 - задаются в процессе выполнения программы.
 
  Лабораторная работа 3.Списковые структуры данных.
 
 1. При удалении элемента из кольцевого списка…
 - список разрывается;
 - в списке образуется дыра;
 - список становится короче на один элемент .
 2. Для чего используется указатель в кольцевых списках ?
 - для ссылки на следующий элемент;
 - для запоминания номера сегмента расположения элемента;
 - для ссылки на предыдущий элемент ;
 - для расположения элемента в списке памяти.
 3. Чем отличается кольцевой список от линейного ?
 - в кольцевом списке последний элемент является одновременно и первым;
 - в кольцевом списке указатель последнего элемента пустой;
 - в кольцевых списках последнего элемента нет ;
 - в кольцевом списке указатель последнего элемента не пустой.
 4. Сколько указателей используется в односвязном кольцевом списке ?
 - 1;
 - 2;
 - сколько угодно.
 5. В каких направлениях можно перемещаться в кольцевом двунаправленном списке ?
 - в обоих ;
 - влево;
 - вправо.
 
  Лабораторная работа 4. Модель массового обслуживания.
 
 1. Чем отличается заявка первого приоритета от заявки второго приоритета ?
 - тем, что заявка второго приоритета обслуживается с вероятностью P=1, а заявка первого приоритета обслуживается с вероятностью P(B);
 - тем, что заявка второго приоритета становится в начало очереди, а первого приоритета становится в конец очереди ;
 - ничем, если есть очередь.
 2. Может ли заявка первого приоритета вытеснить из очереди заявку второго приоритета ?
 - да, если P(B)=1;
 - да;
 - нет .
 3. Может ли на обслуживании находится заявка первого приоритета, если в очереди находится заявка второго приоритета ?
 - да, если P(B)=1;
 - да ;
 - нет.
 4. С помощью какой структуры данных наиболее рационально реализовать очередь ?
 - стек;
 - список ;
 - дек.
 5. Когда заявка покидает систему. Найдите ошибку.
 - если заявка обслужилась подложенное ей число тактов;
 - если заявка находится в очереди больше Т тактов;
 - если заявок второго приоритета стало больше, чем заявок первого приоритета .
 
  Лабораторная работа 5. Бинарные деревья (основные процедуры).
 
 1. Для включения новой вершины в дерево нужно найти узел, к которому её можно присоединить. Узел будет найден, если очередной ссылкой, определяющей ветвь дерева, в которой надо продолжать поиск, окажется ссылка:
 - p=right(p);
 - p=nil ;
 - p=left(p).
 2. Для написания процедуры над двумя деревьями необходимо описать элемент типа запись, который содержит поля:
 - Element=Запись
  Left,Right : Указатели
  Rec : Запись;
 
 - Element=Запись

<< Пред.           стр. 14 (из 19)           След. >>

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