Здесь можно найти образцы любых учебных материалов, т.е. получить помощь в написании уникальных курсовых работ, дипломов, лабораторных работ, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


курсовая работа Способы построения и представления деревьев

Информация:

Тип работы: курсовая работа. Добавлен: 15.05.2012. Сдан: 2011. Страниц: 15. Уникальность по antiplagiat.ru: < 30%

Описание (план):


     Содержание 

Введение
   1.Теоретическая часть…………………………………………………….. …...3
   1.1. Рекурсии……………………………………………………………………4
   1.2. Общие сведения о деревьях…………………………………………….….5
   1.3. Леса………………………………………………………………………....6
   1.4. Представление деревьев в памяти ЭВМ………….………………….…….7
   1.5. Идеально сбалансированное бинарное дерево……………….……...…….8
   1.6. Бинарные деревья поиска……………………………………….……...…..9
   1.7. Сбалансированные деревья поиска…………………………...…………..10
  1.7.1. Сбалансированные АВЛ-деревья поиска……………...…………..……10
  1.7.2. Рандомизированные деревья поиска……………………………..……..11
   1.8. Операции над деревьями………………………………………….………11
   2. Практическая часть……………………………………………….……..…..17
   Заключение…………………………………………………………....….……25
  Список используемой литературы……………………...……………….……..26 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Введение 

     Нелинейные структуры данных позволяют выражать более сложные отношения между элементами. К нелинейным структурам данных относят графы, деревья и леса. Эти структуры находят широкое применение при решении практических задач.
     Для представления нелинейных структур и реализации алгоритмов их обработки во многих случаях удобно использование рекурсий.
             Целью работы является:
    -  Рассмотреть способы построения и представления деревьев
       Задача  данной работы:
      Изучить сведения о деревьях
      Изучить основные операции над деревьями
      Закрепить теоретические и практические знания по программированию на С++
 
 
 
 
 
 
 
 
 
 
 
 
 
 
     
    Теоретическая часть.
 
      Рекурсии
     Рекурсивным называется объект, частично определяемый с помощью самого себя. Мощность такого определения заключается в том, что оно позволяет с помощью конечного высказывания (описания типа данных) определить бесконечное множество объектов, например дерево, список.
     Аналогично с помощью конечной процедуры можно описать бесконечное вычисление. Рекурсивной называют процедуру, которая прямо или косвенно обращается к самой себе. Если процедура Р содержит явное обращение к самой себе, то ее называют прямо рекурсивной. Если же она ссылается на другую процедуру Q, которая, в свою очередь, явно или косвенно обращается к процедуре Р, то процедура Р является косвенно рекурсивной.
     Рекурсивную процедуру Р можно представить как некоторую композицию Р из множества операторов S, не содержащих Р, и самой Р:
     Р => P[S,P].
     Для того чтобы рекурсивная процедура не привела к незаканчивающимся вычислениям, необходимо наличие в процедуре Р некоторого условия В обращения к самой себе. Тогда схему рекурсивной процедуры будет:
     Р => if В then P[S,P] или Р => P[S, if В then Р].
     Использование любой процедуры требует организации связи по управлению и связи по данным между вызывающей процедурой А и вызываемой процедурой В. Связь по управлению обеспечивает передачу управления вызываемой процедуре В и возврат в вызывающую процедуру А после завершения выполнения процедуры В. Вызов процедуры осуществляется посредством оператора вызова по имени вызываемой процедуры.
     Связь по данным обеспечивает передачу в вызываемую процедуру фактических параметров и адреса точки возврата в процедуру А, т.е. адреса оператора, следующего за оператором вызова. В качестве фактических параметров могут быть переданы либо значения определенного типа, либо адреса переменных. 

      Общие сведения о деревьях
 
     Дерево определяется как иерархическая структура. Дерево представляет собой иерархию элементов называемых узлами (вершинами). На самом верхнем уровне иерархии имеется только один узел — корень дерева. Каждый узел кроме корня, связан только с одним узлом на более высоком уровне, называемым исходным узлом (предком, отцом). Каждый элемент может быть связан посредством ребер (ветвей) с одним или несколькими элементами на следующем, более низком, уровне (с порожденными узлами, дочерними узлами). Элементы, расположенные в конце ветви, т.е. не имеющие порожденных, называются листьями (висящими вершинами). От корня до любого узла существует только один путь. Длина пути (число ветвей) от корня до некоторой вершины называется уровнем или глубиной уровня этой вершины. Уровень корня — нулевой. Наибольшая длина пути от корня до листьев дерева (максимальный уровень дерева) называется высотой дерева.
     Любой узел дерева с его потомками на всех уровнях также образует дерево, называемое поддеревом, дочерние узлы также образуют поддеревья. Следовательно, каждый узел имеет столько поддеревьев, сколько у него дочерних узлов.
     Отсюда возникает рекурсивное определение дерева : дерево содержит одну или несколько вершин, причем одну из них называют корнем, а остающиеся объединяют в конечное множество деревьев, называемых поддеревьями
     Древовидная структура с базовым типом Т— это либо 1) пустая структура, либо 2) узел типа Т, с которым связано конечное число древовидных структур с базовым типом Т, называемых поддеревьями. Верхний узел называется корнем.
     Число поддеревьев данного узла образует степень узла, максимальное значение m степени всех узлов дерева является степенью дерева. Дерево степени m называется m-арным деревом. Если все узлы дерева, кроме листьев, имеют степень, равную т, то такое дерево называется полным т-арным деревом. Дерево степени 2 называется бинарным (двоичным) деревом. Оно также может быть полным и неполным.
     Если в дереве на каждом уровне задан порядок следования вершин, то такое дерево называется упорядоченным деревом. Обычно деревья считаются упорядоченными, порядок следования вершин любого узла считается заданным слева направо. Каждая вершина m-арного дерева может быть представлена строкой символов над алфавитом {0,1,..., т-1}, при этом корень дерева характеризуется пустой строкой. Узлам первого уровня приписываются односимвольные строки 0,l,...,m-1, узлам второго уровня — двухсимвольные строки, узлы i-го уровня характеризуются строками длины i. Любая дочь вершины v характеризуется строкой, префикс которой является строкой узла v, к которой справа приписывается символ 0,1,...или т- 1 в зависимости от ее позиции в нижележащем от v уровне. Строка, приписанная к листу дерева, не является префиксом ни для каких других строк, характеризующих другие вершины дерева, т.е. является уникальной. Множество строк, соответствующих листьям некоторого дерева, образует префиксный код этого дерева.  

     1.3. Леса
     Множество, состоящее из некоторого числа непересекающихся деревьев, называется лесом. Если удалить из дерева корень со всеми  его связями с поддеревьями, получим лес, состоящий из поддеревьев корня. Наоборот, добавив к любому лесу с однотипными элементами всего один узел и связав его с корнями деревьев леса, получим дерево, корнем которого станет добавленный узел.
     Лес может быть преобразован в бинарное дерево. Алгоритм преобразования леса в бинарное дерево схож с алгоритмом преобразования m-арного дерева. Сначала каждое дерево леса обрабатывается точно так же, как и отдельное дерево на первом этапе. Затем корни деревьев соединяются горизонтальными линиями и осуществляется поворот по часовой стрелке на 45 градусов относительно корня первого (левого) дерева. Таким образом, корнем леса, представленного бинарным деревом, становится корень первого дерева, второе дерево становится правым поддеревом корня первого, третье дерево — правым поддеревом корня второго дерева и т.д.
     Представление m-арного дерева и леса бинарным деревом дает возможность однообразного физического представления деревьев в ЭВМ и облегчает их обработку. 

     1.4. Представление деревьев в памяти ЭВМ
     Элементы древовидной структуры могут быть размещены как в последовательной (векторной) памяти, так и в динамически получаемых областях памяти. Поскольку каждый узел дерева имеет логические связи со своими дочерними узлами, эти связи должныI быть отражены и в физической структуре в явном или неявном виде. Рассмотрим бинарное дерево. При явном отражении связей каждый узел дерева имеет структуру вида:
     Данные Левый указатель LPTR — Правый указатель RPTR.
     Здесь поля LPTR и RPTR содержат указатели на левое и правое поддеревья данного узла. Форма указателей может быть различной
     Представление дерева в векторной памяти допустимо только тогда, когда в процессе обработки объем памяти, занимаемой его элементами, не превышает фиксированного объема векторной памяти, т.е. число элементов дерева не может превышать некоторого предельного значения. Элементы дерева занимают последовательные ячейки векторной памяти. При явном задании связей указатели LPTR и RPTR можно задавать двояко: либо в виде индексов элементов вектора, либо их адресов в памяти.
     Связанное размещение элементов дерева в динамических областях памяти более удобно, обеспечивает возможность легко вставлять в дерево вершины или удалять их из него; кроме того, дерево может разрастаться до произвольного размера. Для управления любым деревом необходимо наличие дескриптора или в указателя на корень дерева. 

     1.5. Идеально-сбалансированное бинарное дерево
     Поскольку максимальный путь до листьев дерева определяется высотой дерева, то при заданном числе и узлов дерева стремятся построить дерево минимальной высоты. Этого можно достичь, если размещать максимально возможное количество узлов на всех уровнях, кроме последнего. В случае двоичного дерева это достигается таким образом, что все поступающие при построении дерева узлы распределяются поровну слева и справа от каждого узла.
     Бинарное дерево идеально сбалансировано, если для каждого его узла количество узлов в левом и правом поддеревьях различается не более чем на 1.
     Если число узлов п известно и дана последовательность значений поля данных вершин а[0], а[1],… а[n-1], то можно использовать следующий рекурсивный алгоритм построения идеально сбалансированного дерева.
     1. Начиная с а[0], берем очередное значение a[i] в качестве зна- 
чения корня дерева (поддерева).

    Строим левое поддерево с п1 = n/2 узлами тем же способом.
    Строим правое поддерево с nr = n-nl-l узлами.
     Таким образом, значение а[0], окажется в корне дерева, и именно на него будет ссылаться указатель дерева, а[1],… а[nl],  значения попадут в левое поддерево, остальные — в правое поддерево. Следовательно, распределение значений по узлам дерева полностью определяется исходной последовательностью данных. 

     1.6.Бинарные (двоичные) деревья поиска
     Бинарные деревья чаще всего применяются для представления множеств данных, элементы которых ищутся по уникальному, только им присущему ключу. Если бинарное дерево организовано таким образом, что для каждого узла ti, все ключи в левом поддереве меньше ключа ti, а ключи в правом поддереве больше ключа ti, то это дерево называется бинарным деревом поиска. В дереве поиска можно найти место каждого ключа, двигаясь начиная от корня и переходя на левое или правое поддерево каждого узла в зависимости от значения ключа. Таким образом, места элементов в дереве распределяются как значениями ключей, так и последовательностью их поступления. Определяющим фактором является значение ключа, от последовательности поступления элементов зависит степень сбалансированности дерева. При случайном распределении ключа в исходной последовательности получается почти сбалансированное дерево. Если же исходная последовательность упорядочена по возрастанию или убыванию ключей, то дерево вырождается в последовательный список. Высота такого дерева равна числу элементов дерева, уменьшенному на 1.
     Создание дерева поиска заключается в следующем. Первый элемент образует корень дерева. Для последующих элементов осуществляется поиск места включения по ветвям дерева до тех пор, пока не будет найден подходящий узел с нулевым указателем, туда и подключается элемент. Для каждого узла запрашивается динамическая память, ее адрес заносится в указатель узла-предка, данные элемента помещаются в узел, и обнуляются левый и правый указатели нового узла.  
 

     1.7.Сбалансированные деревья поиска
     Длина поиска в двоичном дереве поиска определяется высотой самого дерева. Она для заданного числа элементов п зависит от порядка поступления элементов при построении дерева и может колебаться от log2n в случае идеальной сбалансированности дерева до (n-1) в случае вырождения дерева в линейный список. Таким образом, затраты на поиск и включение элемента будут порядка от O(log2n) до O(п).
     При случайном порядке включения элементов в дерево средние затраты на поиск элемента будут l,386* O(log2n) Увеличение затрат на 39% вполне оправдано более простыми средствами поддержания обычного дерева поиска по сравнению с идеально сбалансированным деревом поиска. Однако при работе с большими деревьями свойство случайности распределения поступающих данных редко. Обычно входные последовательности являются частично упорядоченными (по фамилиям, номенклатурным номерам, квалификационным признакам и т.п.). Для таких ситуаций наиболее подходящими являются так называемые сбалансированные деревья поиска. Рассмотрим два вида таких деревьев: АВЛ-деревья, предложенные в 1962 г. Адельсоном-Вельским и Ландисом, и рандомизированные деревья поиска
     1.7.1.Сбалансированные АВЛ-деревья поиска
     Требования к сбалансированности в АВЛ-деревьях менее жесткие, чем в идеально сбалансированных деревьях. АВЛ-деревом называется такое дерево, у которого высота поддеревьев для каждой вершины различается не более чем на 1.
     Отличие АВЛ-деревьев от обычных деревьев поиска заключается в том, что при включении и удалении элементов необходимо поддерживать сбалансированность дерева в целом. Для этого в каждый узел дерева добавляется одно вспомогательное поле, содержащее информацию о равновесности поддеревьев (показатель сбалансированности узла). Его значениями могут быть:
    0 — высоты правого и левого поддеревьев равны;
    + 1 — высота правого поддерева больше;
    - 1 — высота правого поддерева меньше.
     При попытке добавить или удалить элемент в поддереве с показателем сбалансированности, отличным от нуля, дерево может стать несбалансированным, и потребуется операция балансировки 

     1.7.2.Рандомизированные деревья поиска 

     Создание рандомизированных деревьев поиска основано на том, что «случайность» включается в алгоритм вставки элемента в дерево без каких-либо допущений относительно порядка вставки элементов. Идея заключается в том, что при вставке нового узла в дерево, состоящее из N узлов, вероятность появления нового узла в корне дерева должна быть равна 1/(N +1). 

     1.8. Операции над деревьями
     Деревья используются для представления некоторых данных и для манипулирования ими. Конкретное представление данных и выполняемые над ними операции зависят от решаемой прикладной задачи. Рассмотрим общие операции над деревьями, которые могут выполняться при решении любых задач. К этим операциям можно отнести следующие:
    создание дерева;
    поиск (локализация) элемента в дереве;
    включение элемента в дерево;
    обработка данных в вершинах дерева;
    удаление элемента из дерева;
    сохранение и восстановление бинарного дерева; -
    уничтожение бинарного дерева.
     Эти операции рассматриваются ниже применительно к двоичным деревьям, размещаемым в динамической памяти.
     Создание дерева. Для управления деревом как динамической структурой необходимо наличие дескриптора. Если дескриптор построен в динамической памяти, то доступ к дереву осуществляется через цепочку указателей
     В простейшем случае дескриптор не используется, доступ к дереву осуществляется по указателю, объявленному в программе как переменная.
     Алгоритм включения в дерево отдельных элементов состоит из трех действий:
    поиск места включения;
    получение динамической памяти для элемента;
    образование связи узла с деревом с помощью указателя;
    занесение данных элемента в узел.
     Последние два действия не зависят от вида дерева. Поиск месста включения существенно зависит от вида дерева. Поскольку новые элементы можно включать в дерево поиска в любой момент выполнения программы, то создание дерева сводится к управлению вызовом функции включения элемента.
     Поиск (локализация) элемента в дереве. Поиск элемента может преследовать различные цели. Во-первых, определить, имеется ли искомый элемент в дереве или нет. В этом случае результатом будет возврат признака о наличии или отсутствии элемента. Во-вторых, поиск с целью выборки и обработки данных элемента, тогда результат возвращается в виде адреса вершины. В-третьих, поиск с целью удаления элемента: такой поиск обычно является частью операции удаления, а не самостоятельной операцией.
     Алгоритм поиска в бинарном дереве поиска: поиск осуществляется целенаправленным движением по ветвям дерева. Если ключ поиска равен ключу в вершине, значит, ключ найден и его адрес возвращается через параметр-указатель. Если ключ поиска меньше ключа в вершине, то осуществляется движение вниз влево, в противном случае — вниз вправо. Если в очередной вершине дальнейшее движение вниз невозможно (указатель равен NULL), то это означает, что искомого ключа нет в дереве. Максимальная длина поиска равна высоте дерева.
     Включение элемента в дерево. Особенности операций включения зависят от вида дерева.
     Включение элемента в сбалансированное АВЛ-дерево поиска. Операция включения выполняется в два этапа. Поскольку сбалансированное дерево является частным случаем обычного дерева поиска, то на первом этапе выполняется включение элемента в дерево точно так же, как и при включении в обычное дерево, т.е. проходом по пути поиска, получением динамической памяти и формированием в ней новой вершины дерева. Дополнительно в новой вершине устанавливается признак ее сбалансированности, равный 0, так как новая вершина не имеет поддеревьев. Второй этап выполняется при обратном и заключается в восстановлении сбалансированности в узлах дерева, если она была нарушена. При этом учитывается, откуда (слева или справа) осуществляется возврат в вершину, каков показатель сбалансированности в ней, выросла ли высота поддерева.
     Включение элемента в рандомизированное дерево поиска.
     При вставке нового узла в дерево, состоящее из N узлов, вероятность появления нового узла в корне дерева должна быть равна 1/(N + 1). Следовательно, для реализации алгоритма вставки необходимо, чтобы каждый узел дерева содержал счетчик узлов в дереве (поддереве), имел генератор случайных чисел и, обеспечил вставку элемента в корень дерева
     Для поддержания счетчика узлов необходимо в структуре эле- 
мента дерева предусмотреть соответствующий элемент целого типа.

     Структура элемента имеет вид
     define struct RECORD
     { int DATA;             /* ключ+данные, здесь только ключ */
     RECORD *LPTR, *RPTR;    /* указатели на дочерние узлы */
     int N; /* счетчик узлов */
     int bal;         /* признак сбалансированности в АВЛ-деревьях */
     };
     Счетчик в заданном узле равен сумме чисел узлов в левом и правом поддеревьях + 1 (сам узел). Тогда счетчик для данного узла Т определится по рекурсивной функции:
     int count(RECORT *Т) {if (T==NULL) return 0 ; else
         return (count(T->LPTR) + count(T->RPTR) +1);
     }
     Для установки счетчиков во всех узлах дерева достаточно выполнить обход всех узлов и при посещении каждого узла выполнить функцию count для этого узла
     Особенности вставки элемента в корень дерева поиска. Сначала элемент вставляется в дерево обычным порядком и попадает в нижнюю часть дерева, образуя конечный узел {лист). После этого осуществляется продвижение нового узла вверх с сохранением свойств бинарного дерева поиска. Оно выполняется с использованием так называемых ротаций {ротация вправо и ротация влево). При каждой ротации вставляемый элемент поднимается на один уровень. Таким образом, число ротаций равно начальной глубине уровня вставляемого узла.
     В ротации узла участвуют три связи (указателя):
    в ротации вправо — указатель на корень, на левый дочерний узел и на правый дочерний узел дочернего узла (на правую внучку);
    в ротации влево — указатель на корень, на правый дочерний узел и на левый дочерний узел дочернего узла.
     Ротация выполняется за счет обменов значениями указателей. При ротации вправо правая связь левого дочернего узла становится левой связью старого корня. Правая связь нового корня указывает на старый корень, а указатель на старый корень заменяется указателем на левый корень.
     При ротации влево левая связь правого дочернего узла становится правой связью старого корня. Левая связь нового корня указывает на старый корень, а указатель на старый корень заменяется указателем на правый корень
     Обработка данных в вершинах дерева.
     Различают два вида обработки:
    выборочную обработку отдельной вершины;
    последовательную обработку всех вершин.
      Выборочная обработка включает поиск элемента, и если он найден, то и обработку данных в вершине. Обработка данных зависит от решаемой задачи и может сводиться к извлечению данных без их изменения либо обновлению данных в вершине дерева.
     При последовательной обработке осуществляется так называемый обход дерева. Обход дерева — это процесс одноразового посещения и обработки данных каждой вершины дерева. В зависимости от того, в каком направлении осуществляется движение по ветвям дерева и когда обрабатываются данные в вершинах, различают шесть видов обхода.
     Левый нисходящий обход Lpreorder — движение сверху вниз, от корневой вершины к листьям.
     Левый восходящий обход Lpostorder — снизу вверх, от листьев вверх к корню:
    левый восходящий обход левого поддерева;
    левый восходящий обход правого поддерева;
    обработка данных в узле.
     Левый смешанный обход Linorder — слева направо, от самого левого листа вверх к корню, затем вниз к самому правому листу:
    левый смешанный обход левого поддерева;
    обработка данных в узле;
    левый смешанный обход правого поддерева.
     Удаление элемента из дерева. Особенности операции удаления зависят от вида дерева.
     Удаление элемента из бинарного дерева поиска.
     После удаления элемента дерево поиска должно сохранить свое свойство — обеспечение поиска элементов. Действия по удалению определяются тем, в каком месте дерева находится удаляемый элемент. В процедуре удаления различают следующие ситуации.
    Элемента с искомым ключом нет, дерево не изменяется, во врат с признаком отсутствия ключа.
    Удаляемый элемент — лист, в родительском узле соответствующий указатель на удаляемый элемент обнуляется, память из-под элемента освобождается.
    Удаляемый элемент только с одним поддеревом. Корректируются указатели, память освобождается.
     Сохранение и восстановление бинарного дерева. Выполняя левый нисходящий обход дерева, необходимо сохранить ключ и данные каждого узла в файле. Указатели сохранять не нужно. Последовательно читая из файла сохраненные ключ и данные узлов, строится бинарное дерево.
     Уничтожение бинарного дерева. Для уничтожения бинарного дерева достаточно произвести обход дерева и при посещении каждого узла освободить память из-под него. После освобождения всей занятой памяти указатель дерева необходимо обнулить. 
 
 
 
 
 
 
 
 
 

     2. Практическая часть 
 

     Написать программу учета нарушений правил дорожного движения. Для каждой автомашины необходимо хранить в базе список нарушений. Для каждого нарушения фиксируется дата, время, вид нарушения и размер штрафа. При оплате всех штрафов автомашина удаляется из базы.
     Алгоритм работы программы:
     При вводе нового нарушения запрашивается номер автомашины и выполняется поиск в базе. Если такая автомашина уже фигурирует в базе, в список ее нарушений добавляется новое, а если нет, то создаются новый узел дерева и первый элемент списка нарушений.
     При вводе информации об уплате штрафа выполняется поиск заданной автомашины, а затем- поиск соответствующего нарушения. При этом запрашивается время совершения нарушения, поскольку все остальные параметры нескольких нарушений могут совпадать (например ,автолюбителя семь раз за день оштрафовали за превышение скорости при развороте задним ходом на перекрестке под запрещающий сигнал светофора). Если после удаления записи о нарушении список оказывается пустым, соответсвующий узел дерева удаляется.
#include <fstream.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
      #include <iomanip.h> 

     const char* filename = "dbase"; enum Action {INSERT, DEL. INFO}; enum Dir {LEFT. RIGHT};
     const int l_time = 20. l_type = 40, l_number = 12;
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.