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

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

  P, Q - рабочие указатели
  V=maketree(key,rec) - процедура, которая создает сегмент ключа и записи
  P=getnode - генерация нового элемента
  r=rec
  k=key
  V=P
  left=nil
  right=nil
  tree - указатель на корень дерева
  Введем сначала первое значение ключа, потом сгенерируем сам элемент узла дерева процедурой maketree. Далее идем по циклу до тех пор, пока указатель не передвинется на нулевое значение.
 
  READ(key,rec)
  tree=maketree(key,rec)
  WHILE not eof DO
  READ(key,rec)
  V=maketree(key,rec)
  WHILE P<>nil DO
  Q=P
  IF key=k(P)
  THEN P=left(P)
  ELSE P=right(P)
  END IF
  END WHILE
  IF P=nil
  THEN WRITELN(' Это корень');
  tree=V
  ELSE IF key   THEN left(P)=V
  ELSE right(P)=V
  END IF
  END IF
  END WHILE
  Процедуры "обхода" дерева
  Пусть задано бинарное дерево :
 
 
 
  Существуют три принципа обхода бинарных деревьев. Рассмотрим их на примере заданного дерева :
  1) Обход сверху вниз (корень посещается ранее, чем поддеревья) : A, B, C ;
  2) Слева направо : B, A, C ;
  3) Снизу вверх (корень посещается после поддеревьев) : B, C, A .
  Наиболее часто применяется 2-ой способ, узлы посещаются в порядке возрастания значения их ключа.
 
  Рекурсивные процедуры обхода дерева :
  1) PROCEDURE pretrave (tree)
  IF tree<>nil
  THEN PRINT info (tree)
  pretrave (left (tree))
  pretrave (right (tree))
  END IF
  RETURN
  2) PROCEDURE intrave (tree)
 
  IF tree<>nil
  THEN intrave (left (tree))
  PRINT info (tree)
  intrave (right (tree))
  END IF
  RETURN
  3) PROCEDURE postrave (tree)
 
  IF tree<>nil
  THEN postrave (left (tree))
  postrave (right (tree))
  PRINT info (tree)
  END IF
  RETURN
  Процедура поиска по бинарному дереву
  Назначение этой процедуры в том, чтобы по заданному ключу осуществить поиск узла дерева. Длительность операции поиска (число узлов, которое надо перебрать для этой цели) зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список (иметь единственную ветвь) - такое дерево может возникнуть, если элементы поступали в дерево в порядке возрастания (убывания) их ключей, например :
 
 
 
  В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. в среднем придется перебрать N/2 элементов.
  Наибольший эффект использования дерева достигается в том случае, когда дерево "сбалансировано". В этом случае для поиска придется перебрать не более LOG2N элементов.
  Опишем процедуру поиска. Переменной search будет присваиваться указатель на найденное звено :
  p=tree
  WHILE p<>nil DO
  IF key=k (p)
  THEN search=p
  RETURN
  END IF
  IF key<>k (p)
  THEN p=left (p)
  ELSE p=right (p)
  END IF
  END WHILE
  search=nil
  RETURN
  Процедура включения элемента в дерево
  Для включения новой записи в дерево прежде всего нужно найти тот его узел, к которому можно "подвесить" (присоединить) новый элемент. Алгоритм поиска нужного узла тот же самый, что и при поиске узла с заданным ключом. Этот узел будет найден в тот момент, когда в качестве очередной ссылки, определяющей ветвь дерева, в которой надо продолжить поиск, окажется ссылка NIL.
  Однако непосредственно использовать описанную выше процедуру поиска нельзя, потому что по окончании вычисления ее значения не фиксируется тот узел, из которого была выбрана ссылка NIL.
  Модифицируем описание процедуры поиска так, чтобы в качестве ее побочного эффекта фиксировалась ссылка на узел, в котором был найден заданный ключ (в случае успешного поиска), или ссылка на узел, после обработки которого поиск прекращен (в случае неуспешного поиска). И опишем процедуру включения элемента в дерево, учитывая, что в дереве нет узла с тем же ключом, что и у включаемого элемента.
  q=nil
  p=tree
  WHILE p<>nil DO
  q=p
  IF key=k (p)
  THEN search=p
  RETURN
  END IF
  IF key   THEN p=left (p)
  ELSE p=right (p)
  END IF
  END WHILE
  {Узел с заданным ключом не найден, требуется вставка элемента. На узел предполагаемого отца указывает q.}
  V=maketree (key, rec)
  {Нужно выяснить, левым или правым сыном будет вставляемый элемент V.}
  IF key   THEN left (q)=V
  ELSE right (q)=V
  END IF
  search=V
  RETURN
 
  Процедура удаления элемента из бинарного дерева
  Удаление узла не должно нарушать упорядоченность дерева. При удалении элемента из бинарного дерева с заданным ключом различают три случая :
  1) удаляемый узел является листом, в этом случае он просто удаляется, не нарушая этим упорядоченность дерева ;
  2) если удаляемый узел имеет только одного сына, то сын перемещается на место удаляемого отца ;
 4) если у удаляемого узла 2 сына. В этом случае на место удаляемого отца помещается либо его предшественник в симметричном обходе (обход слева направо), либо его последователь.
 
 
 
  Разработаем алгоритм для 3-его случая (вершина-узел имеет 2-х сыновей), вместо удаляемого узла поставим его приемника в симметричном обходе. Предшественником удаляемого узла 12 является самый правый узел левого поддерева - узел 11, а приемником или последователем при симметричном обходе (обход слева направо) является самый левый узел правого поддерева - узел 13.
  Будем использовать следующие указатели :
  p - рабочий указатель;
  q - отстает на один шаг от p;
  v - указывает приемника;
  t - отстает от v на один шаг;
  s - опережает v на один шаг.
 
  1) Процедурой поиска элемента находим удаляемый элемент. Указатель p указывает на удаляемый элемент.
  2) Установим указатель v на узел, который будет замещать удаляемый элемент.
  IF left (p)=nil
  THEN v=right (p)
  ELSE IF right (p)=nil
  THEN v=left (p)
  ELSE t=p
  v=right (p)
  s=left (v)
  WHILE s<>nil
  t=v
  v=s
  s=left (v)
  END WHILE
  IF t<>p
  THEN WRITE (v не является сыном p)
  left (t)=right (v)
  right (v)=right (p)
  END IF
  left (v)=left (p)
  IF q=nil
  THEN WRITE (v корень)
  tree=v
  RETURN
  END IF
  IF p=left (q)
  THEN left (q)=v
  ELSE right (q)=v
  END IF
  END IF
  END IF
  FREENODE (p) (процедура создает свободный узел, т.е. очищает ячейку памяти, в которой находится удаленный элемент)
  RETURN
 
  Задания
 
  Варианты:
  1.Описать процедуру или функцию, которая:
  a) присваивает параметру Е запись из самого левого листа непустого дерева Т (лист-вершина, из которого не выходит ни одной ветви);
  b) определяет число вхождений записи Е в дерево Т.
 
  2. Вершины дерева вещественные числа. Описать процедуру или функцию, которая:
  a) вычисляет среднее арифметическое всех вершин дерева;
  b) добавляет в дерево вершину со значением, вычисленным в предыдущей процедуре (функции).
 
  3. Записи вершин дерева - вещественные числа. Описать процедуру, которая удаляет все вершины с отрицательными записями.
 
  4. Записи вершин дерева - вещественные числа. Описать процедуру или функцию, которая:
  a) находит максимальное или минимальное значение записей вершин непустого дерева;
  b) печатает записи из всех листьев дерева.
 
  5. Описать процедуру или функцию, которая:
  a) определяет, входит ли вершина с записью Е в дерево Т;
  b) если такая запись не найдена, то она добавляется.
 
  6. Описать процедуру или функцию, которая:
  a) находит в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины с записью Е; если Е не входит в Т, то за ответ принять -1.
  b) определяет максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня дерева до листьев.
 
  7. Описать процедуру СОРY(Т,Т1), которая строит Т1 - копию дерева Т.
 
  8. Описать процедуру ЕQUAL(T1,T2), проверяющую на равенство деревья Т1 и Т2 (деревья равны, если ключи и записи вершин одного дерева равны соответственно ключам и записям другого дерева).
 
  9. Описать процедуру или функцию, которая:
  a) печатает узлы непустого дерева при обходе слева направо;
  b) удаляет все листья исходного дерева;
  c) печатает модифицированное дерево.
 
  10. Описать процедуру, которая:
  a) присваивает переменной b типа char значение:
  К - если вершина - корень,
  П - если вершина - промежуточная вершина,
  Л - если вершина - лист;
  b) распечатывает атрибуты всех вершин дерева.
 
  11. Описать процедуру или функцию, которая:
  а) вставляет узел с записью Е в дерево, если ранее такой не было;
  b) удалить ее, если она уже существует.
 
  12. Описать процедуру или функцию, которая:
  а) печатает дерево, встречающееся в дереве один раз;
  b) печатает запись, встречающееся в дереве максимальное число раз.
 
  Лабораторная работа № 6 . "СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ"
 
 Цель работы: исследовать и изучить методы сортировки включением.
 
 Задача работы: овладеть навыками написания программ для сортировки методом прямого включения на языке программирования ПАСКАЛЬ .
 
 
  Порядок работы :
 * изучить описание лабораторной работы;
 * по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
 * написать программу на языке ПАСКАЛЬ;
 * отладить программу;
 * решить задачу;
 * оформить отчет.
 
  Краткая теория
 
  При обработке данных в ЭВМ важно знать и информационное поле элемента, и его размещение в памяти машины. Для этих целей используется сортировка. Итак, сортировка- -это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание значения ключа от начала к концу в массиве.
  Различают следующие типы сортировок:
 * внутренняя сортировка - это сортировка, происходящая в оперативной памяти машины
 * внешняя сортировка - сортировка во внешней памяти.
  Если сортируемые записи занимают большой объем памяти, то их перемещение требует больших затрат. Для того, чтобы их уменьшить, сортировку производят в таблице адресов ключей, делают перестановку указателей, т.е. сам массив не перемещается. Это метод сортировки таблицы адресов.
  При сортировке могут встретиться одинаковые ключи. В этом случае при сортировке желательно расположить после сортировки одинаковые ключи в том же расположении, что и в исходном файле. Это устойчивая сортировка.
  Эффективность сортировки можно рассмотреть с нескольких критериев:
 * время, затрачиваемое на сортировку
 * объем оперативной памяти, требуемой для сортировки
 * время, затраченное программистом на написание программы
 
  Рассмотрим второй критерий подробнее: мы можем подсчитать количество сравнений при выполнении сортировки или количество перемещений.
  Предположим, что число сравнений определяется формулой:
  C = 0,01n2 + 10n
  Если n<1000, то второе слагаемое больше.
  Если n>1000, то первое слагаемое больше.
  То есть, при малых n порядок сравнения равен , а при больших n он равен n.
  Различают следующие методы сортировки:
 * строгие (прямые) методы
 * улучшенные методы
 
  Рассмотрим преимущества прямых методов:
  1. Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.
  2. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.
  3. Усложненные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно, не следует.
 
  Методы сортировки "на том же месте" можно разбить в соответствии с определяющими их принципами на 3 категории:
  1. Сортировки с помощью включения (by insertion)
  2. Сортировки с помощью выделения (by selection)
  3. Сортировки с помощью обменов (by exchange)
 
  Сортировка методом прямого включения
 
  Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже "готовую" последовательность a(1),...,a(i-1) и исходную последовательность. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.
 
 
  Алгоритм
 
  Алгоритм сортировки прямым включением таков:
  for x:=2 to n do
  x:=a[i]
  включение х на соответствующее место среди a[1]...a[i]
  end
  В реальном процессе поиска подходящего места удобно, чередуя сравнения
  сравнивается с очередным элементом a( j ), а затем либо х вставляется на свободное место, либо a( j ) сдвигается (передается) вправо и процесс "уходит" влево. Обратите внимание, что процесс просеивания может закончиться при выполнении одного из двух следующих различных условий:
  1. Найден элемент a( j ) с ключом, меньшим, чем ключ у х.
  2. Достигнут левый конец готовой последовательности.
 
  Procedure StraightInsertion
  Var
  i,j:index; x:item;
  begin
  for i:=2 to n do
  x:=a[i]; a[0]:=x; j:=1;
  while x   a[j]:=x
  end
  end StraightInsertion
 
  Задания
 
  В ремонтной мастерской находятся несколько (N) машин. О них имеются следующие сведения: номер, марка, имя владельца, дата последнего ремонта (число, месяц, год), день, к которому машина должна быть отремонтирована (число, месяц, год).
  Требуется (согласно варианту) :
  1.Расположить по алфавиту имена владельцев и, соответственно, вывести информацию об их машинах.
  2.Исходя из того, что машина, дата окончания ремонта которой раньше, должна ремонтироваться в первую очередь, вывести порядок ремонта автомобилей.
  3.Вывести по убыванию количество всех предыдущих ремонтов машин марки "Жигули".
  4.Вывести по убыванию номера тех машин, количество предыдущих ремонтов которых равно 2.
  5.Вывести по возрастанию даты конца ремонта всех машин, которые ранее не ремонтировались.
  6.Вывести по алфавиту в обратном порядке владельцев автомобилей марки "Мерседес"

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

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