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

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

 

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

 

Логин:

Пароль:

 

Запомнить

 

 

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

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

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

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


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


курсовая работа Программирование. Структура деревьев

Информация:

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

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


 
 
 
 
  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Министерство  образования и науки Российской Федерации
Федеральное агентство по образованию

      ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
Факультет информационных технологий
Кафедра управления и информатики в технических системах 
 

Задание на курсовую работу
Реализация  прикладной задачи с использованием пирамиды 
 

    Исходные  данные:   Массив, нелинейные структуры данных, пирамида.  

    Перечень  подлежащих разработке вопросов:
                           а) раскрыть понятие дерева;
                           б) охарактеризовать бинарные (двоичные) деревья;
                           в) ввести понятие  пирамиды;
                           г) изучить способы  реализации пирамиды;
                           д) реализовать сортировку на основе пирамиды. 

    Перечень  графического материала:
                           Рисунки, характеризующие  структуру дерева. 
 
 

    Дата  выдачи задания «___»______________200__ г.
    Руководитель 
    Исполнитель
    студент группы
    Срок  защиты работы «___»______________200__ г.
Аннотация 

    Курсовая  работа содержит 25 страниц, в том числе 3 рисунка, 1 таблица, 7 источников и 2 приложения. В данной курсовой работе изложена теория, связанная с понятием дерева, бинарных деревьев, двоичных деревьев поиска. Вводится понятие пирамиды, а так же программная реализация, основные операции (создание, удаление, добавление, обход и сортировки).
    В курсовой работе изложены основные понятия  деревьев и представлены способы  реализации пирамиды на практике. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Содержание 
 
 
 
 
 
 
 

 

Введение 

    Как известно, деревья появились уже  на третий день сотворения мира и на протяжении веков древовидные структуры (особенно генеалогические деревья) очень широко применяются.  Как  математический объект понятие дерева было впервые формально определено в работе Г.Р. Кирхгофа. Он использовал свободные деревья для поиска набора фундаментальных циклов и электрической цепи, которые теперь носят его имя. Спустя десятки лет термин дерево появился в работах Артура Кэли. Он не знал о работах Кирхгофа, и свои исследования начал, изучив структуру алгебраических формул. Позднее Кэли продолжил их в основном для изучения задач. Древовидные структуры так же независимо изучались М.Э. Жорданом и К.И. Боркарелом.
    Данная тема остается, актуальной и в наше время, так как находит свое применение во всех сферах деятельности. Деревья используются при анализе электрических цепей, представление структур математических формул. Они так же естественным путем возникают во многих областях информационных наук. Например, деревья используются для организации информации в системах управления базами данных и для представления синтаксических структур и компиляторах программ.
    Целью данной курсовой работы является исследование одной из важных разновидностей деревьев – пирамиды.
    Для достижения данной цели нужно выполнить  следующие задачи:
    раскрыть понятие дерева;
    охарактеризовать бинарные (двоичные) деревья;
    ввести понятие пирамиды;
    изучить способы реализации пирамиды;
    реализовать сортировку на основе пирамиды.
    Объектом  являются нелинейные структуры данных. Предметом исследования курсовой работы выступает одна из разновидностей двоичных деревьев – пирамида.
 

     1 Динамическая структура данных «Дерево»
    1.1  Деревья
    1.1.1 Определение. Основные понятия
    Дерево  – это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский – дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называют листьями.
    Узел является экземпляром одного из двух типов элементов графа, соответствующим объекту некоторой фиксированной природы. Узел может содержать значение, состояние или представление отдельной информационной структуры или самого дерева. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву (по соглашению, деревья 'растут' вниз, а не вверх, как это происходит с настоящими деревьями). Узел, имеющий потомка, называется узлом-родителем относительно своего потомка (или узлом-предшественником, или старшим). Каждый узел имеет не больше одного предка. Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (краевому узлу), называемому листом. Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути до корневого узла.
    Самый верхний узел дерева называется корневым узлом. Быть самым верхним узлом подразумевает отсутствие у корневого узла предков. Это узел, на котором начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по рёбрам (или ссылкам). Каждый узел дерева можно рассматривать как корневой узел поддерева, «растущего» из этого узла.
    Узлы  самого нижнего уровня дерева называются листовыми узлами или листьями. Так как они находятся на самом нижнем уровне, они не имеют никаких потомков.
    Внутренний  узел — любой узел дерева, имеющий потомков, и таким образом, не являющийся листовым узлом.
    Поддерево — часть деревообразной структуры данных, которая может быть представлено в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. То есть поддерево связано с корневым узлом целым деревом, а отношения поддерева со всеми прочими узлами определяются через понятие соответствующее поддерево (по аналогии с термином «соответствующее подмножество»).
    Высотой поддерева будем считать максимальную длину цепи y1, …,его вершин такую, что yi+1 – потомок yi для всех i. Высота пустого дерева равна нулю, высота дерева из одного корня – единице.
    Степенью  вершины в дереве называется количество дуг, которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево. При этом листьями в дереве являются вершины, имеющие степень ноль.
При использовании  деревьев часто встречаются такие  понятия как путь между начальной и конечной вершиной (последовательность проходимых ребер или вершин).
        Классификация деревьев
    Классификацию деревьев можно провести по разным признакам.
    1. По числу возможных потомков  у вершин различают двоичные (бинарные) или недвоичные (сильноветвящиеся) деревья.
Двоичное  дерево: каждая вершина может иметь  не более двух потомков.
Недвоичное  дерево: вершины могут иметь любое  число потомков.
На рисунке  1 представлены двоичное и недвоичное деревья.





 

Рисунок 1 – Двоичное и недвоичное деревья 

    2. Если в дереве важен порядок  следования потомков, то такие  деревья называют упорядоченными. Для них вводится понятие левый и правый потомок (для двоичных деревьев) или более левый/правый (для недвоичных деревьев). В этом смысле два следующих простейших упорядоченных дерева с одинаковыми элементами считаются разными:
    На  рисунке 2 представлены 2 простейших упорядоченных дерева.
    [2] Дональд Э. Кнут, Глава 2.3. Деревья. – Искусство программирования. — М.: Вильямс, 2000 — 832 с.

 

 

Рисунок 2 – Упорядоченные деревья
    1.2 Двоичные деревья
    1.2.1 Определение.  Основные понятия
    Двоичным  деревом поиска (ДДП) называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовём их левым и правым), и все вершины, кроме корня, имеют родителя.
    Элементы  дерева называются вершинами или  узлами, а соединения – ребрами  или дугами. От каждой вершины вниз идет не более двух ребер (поэтому дерево – двоичное). Вершины, с которыми соединена данная, и которые расположены ниже нее, называются детьми данной вершины (также часто говорят «сыновья»). При этом различаются правый и левый сын. Если вершина A является ребенком вершины B, то вершина B называется родителем A. У каждой вершины может быть не более одного родителя. Вершина, не имеющая родителя, называется корнем дерева. Вершины, не имеющие детей, называются листьями дерева. Все сказанное выше описывает двоичное дерево. На самом деле двоичное дерево – это математический объект и его можно определить строго. Одно из определений – рекурсивное – звучит так:
        - Каждая вершина имеет не более двух детей и не более одного родителя.
         - Одна вершина, не имеющая ни детей, ни родителей, является двоичным деревом.
    - Вершина, каждый из двух детей которой либо пуст, либо является двоичным деревом, тоже является двоичным деревом.
    Часть двоичного дерева, являющаяся двоичным деревом, называется поддеревом. Так для каждой вершины есть левое и правое поддеревья (возможно, пустые). 

    1.2.2 Программная реализация
    Существует  множество различных способов представления  деревьев. Наиболее общий способ представления изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других), или как элементы массива, связанные между собой отношениями, определёнными их позициями в массиве.
    PTree =^TTree;
    TTree =record
            Data: DataType; {элемент дерева}
            Left, Right: PTree; {указатели на поддеревья}
    End;
    Left, Right равны nil, если соответствующие поддеревья пусты. Для обработки дерева достаточно знать адрес корневой вершины. Для хранения этого адреса надо ввести ссылочную переменную:
    Var Tree: PTree
    Двоичное  дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее  значение узла, чем любой элемент  в левом поддереве, и меньшее  или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Важное свойство такого дерева: все элементы его различны. Название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: O(n)=C*log2n (в худшем случае O(n)=n). 

    1.2.3 Основные операции (алгоритмы) 

     Добавление элемента в дерево
    Алгоритм  добавления включает следующие шаги:
    -    выделение памяти для новой вершины
    -    формирование информационной составляющей
    -    формирование двух пустых ссылочных полей на будущих потомков
    -   формирование в родительской вершине левого или правого ссылочного поля – адреса новой вершины.
 Удаление элемента из дерева
    Удаление  реализуется более сложным алгоритмом:
Ситуация 1. Удаляемая вершина не имеет ни одного потомка, т.е. является терминальной. Удаление реализуется очень легко обнулением соответствующего указателя у родителя.
Ситуация 2. Удаляемая вершина имеет только одного потомка. В этом случае удаляемая вершина вместе со своим потомком и родителем образуют фрагмент линейного списка. Удаление реализуется простым изменением указателя у родительского элемента.
Ситуация 3. Пусть удаляемая вершина имеет двух потомков. Этот случай наиболее сложен, поскольку нельзя просто в родительской вершине изменить соответствующее ссылочное поле на адрес одного из потомков удаляемой вершины. Это может нарушить структуру дерева поиска.
Обход дерева
Обход в прямом направлении:
-   обработать корневую вершину текущего поддерева
-   перейти к обработке левого поддерева таким же образом
-   обработать правое поддерево таким же образом
 Cимметричный обход:
-   рекурсивно обработать левое поддерево текущего поддерева
-   обработать вершину текущего поддерева
-   рекурсивно обработать правое поддерево 

Обход в обратном направлении:
-   рекурсивно обработать левое поддерево текущего поддерева
-   рекурсивно обработать правое поддерево текущего поддерева
-   затем – вершину текущего поддерева
На рисунке 3 представлен обход в трех направлениях. 

Прямой  обход: A - B - C Симметричный  обход: B - A - C Обратный обход: B - C - A
 
Рисунок 3 – Обход в трех направлениях 

Поиск элементов в дереве
Алгоритм поиска в двоичное дерево очень прост. Начиная с корневой вершины для каждого текущего поддерева надо выполнить следующие шаги:
  -   сравнить ключ вершины с заданным значением х
  - если заданное значение меньше ключа вершины, перейти к левому потомку, иначе перейти к правому поддереву. Поиск прекращается при выполнении одного из двух условий:
  -   либо если найден искомый элемент
  -  либо если надо продолжать поиск в пустом поддереве, что является признаком отсутствия искомого элемента.
[1] Ахо А., Хопкрофт Дж., Ульман Дж, Структуры данных и алгоритмы. – М:Мир, 2000 – 256 с.
[7] http://www.rsdn.ru/ 

    1.3 Пирамида
    1.3.1 Определение. Основные понятия
    Пирамида  – это специальная разновидность  двоичного дерева, построенная по особым правилам и имеющая особые свойства.
Пирамида  представляет собой полное дерево, в котором заполнение нового уровня начинается только после того, как предыдущий уровень заполнен целиком, а все узлы на одном уровне заполняются слева направо.
    Можно отметить следующие полезные свойства пирамиды:
- на вершине пирамиды всегда находится наименьший элемент во всем массиве (элемент а1), элемент а2   является наименьшим для левого поддерева, элемент а является наименьшим для правого поддерева и т.д.
- вершины, лежащие на самом нижнем уровне пирамиды, всегда образуют из себя элементарные пирамиды, поскольку у них нет никаких потомков и их сравнивать не с кем.    
 
    1.3.2 Сортировка на основе пирамиды
    1.3.2.1  Представление исходного массива в виде пирамиды
    Условно разделяем исходный массив на две половины: левую с индексами от 1 до [n/2], и правую с индексами от [n/2]+1  до  n (здесь [ ] обозначает целую часть); считаем пока, что левая половина образует верхнюю часть строящейся пирамиды, а правая – нижний слой терминальных вершин
    Выбираем  в левой половине последний элемент (его индекс m=[n/2]), а в правой половине – его непосредственных потомков (одного или двух, но хотя бы один будет обязательно) с индексом  2m  и, возможно,  2m+1
    Если потомков два, то выбираем из них наименьшего
    - Сравниваем элемент аm с наименьшим из потомков: если он больше, то меняем эти элементы в массиве местами для получения фрагмента пирамиды; в противном случае оставляем все без изменений, поскольку эти элементы уже образуют фрагмент пирамиды
    Повторяем все описанные действия последовательно для оставшихся в левой части элементов справа налево, т.е. для  аm-1, аm-2,  аm-3, . . ., а1,  при этом если происходит обмен между родительской вершиной и одним из потомков, выполняется проверка для новой вершины-потомка, т.к. она может иметь своих потомков, с которыми возможно потребуется ее обменять для выполнения условия пирамиды.
    Тем самым, для каждого элемента массива  находится его новое расположение в массиве таким образом, чтобы  выполнялись условия пирамиды. Процесс определения нужного положения элемента в массиве-пирамиде называют просеиванием элемента через пирамиду. Построение пирамиды заканчивается после просеивания первого элемента  а1. Пример для 15 элементов приведен в таблице  (символ  ~  обозначает перестановку элементов).
    В худшем случае каждый шаг в просеивании  очередного элемента требует двух сравнений: сначала сравниваются два потомка  текущего элемента, а потом наименьший из них сравнивается с самим элементом. В примере для построения пирамиды потребовалось 11*2=22 сравнения и 9 пересылок. 
 
 
 
 

    Таблица 1 –Присвоение элемента через пирамиду. 

а1 а2 а3 а4 а5 а6 а7 а8 а9 а10 а11 а12 а13 а14 а15 сравнение и  обмен
45 40 28 25 30 44 33 22 60 15 55 47 66 20 50 33> min(20, 50), 33~20
45 40 28 25 30 44 20 22 60 15 55 47 66 33 50 44< min(47, 66), нет
45 40 28 25 30 44 20 22 60 15 55 47 66 33 50 30> min(15, 55), 30~15
45 40 28 25 15 44 20 22 60 30 55 47 66 33 50 25> min(22, 60), 25~22
45 40 28 22 15 44 20 25 60 30 55 47 66 33 50 28>min(44, 20), 28~20
45 40 20 22 15 44 28 25 60 30 55 47 66 33 50 28<min(33, 50), нет
45 40 20 22 15 44 28 25 60 30 55 47 66 33 50 40>min(22, 15), 40~15
45 15 20 22 40 44 28 25 60 30 55 47 66 33 50 40>min(30, 55), 40~30
45 15 20 22 30 44 28 25 60 40 55 47 66 33 50 45>min(15, 20), 45~15
15 45 20 22 30 44 28 25 60 40 55 47 66 33 50 45>min(22, 30), 45~22
15 22 20 45 30 44 28 25 60 40 55 47 66 33 50 45>min(25, 60), 45~25
15 22 20 25 30 44 28 45 60 40 55 47 66 33 50 Пирамида построена
 
 
 
 
    
          Последовательное удаление минимального элемента с вершины пирамиды
Реализация этапа  состоит в  (n-1)-кратном повторении следующих действий:
С вершины пирамиды забирается минимальный элемент  а1
На его место в вершину пирамиды помещается последний элемент в массиве, причем индекс этого последнего элемента на каждом шаге будет уменьшаться от  аn до  а2  
Помещенный в вершину элемент просеивается через пирамиду обычным образом, при этом он встает на свое место, а в вершину пирамиды выталкивается минимальный из оставшихся в массиве элементов
На последнем шаге в пирамиде останется один элемент (самый большой) и сортировка будет закончена
При больших  n  метод в среднем немного уступает быстрой сортировке и имеет оценку порядка (n*log 2 n)/2. Единственное, в чем он превосходит быструю сортировку, так это поведение на аномальных входных данных, когда быстрая сортировка перестает быть “быстрой”, а пирамидальная сохраняет свою трудоемкость порядка O(n*log 2 n). В указывается, что пирамидальную сортировку выгодно использовать в том случае, когда требуется не провести полную сортировку большого набора данных, а лишь найти несколько (причем – немного) первых наименьших элементов.
[3] Кормен Т, Пирамидальная сортировка. – М:Мир, 2000 – 390 с
[6] httr://www.codelab.ru/t/pyramid_sort/
 

     2 Реализация прикладной задачи с использованием пирамиды
    2.1 Постановка задачи
Написать диалоговую программу для работы с пирамидами. При запуске программы должно отображаться меню, пункты которого реализуют основные операции с пирамидой.
Программа должна быть однозначной и защищена от неправильных действий пользователя.
    2.2 Алгоритм решения задачи
Шаг 1. Задаем массив от 1 до 1000.
Шаг 2. Заполняем массив случайными числами.
Шаг 3. Программа  сортирует массив в порядке возрастания.
2.3 Описание программных средств
2.3.1 Описание переменных
2.3.1.1 Глобальные  переменные
var
   a: array[1..MaxN] of LongInt – массив пирамиды;
   n, hs – переменные для построения пирамиды;
 i – постепенно из пирамиды выбрасывает максимальный элемент;
2.3.1.2 Локальные переменные
Рrocedure swap(var x, y: LongInt);
x, y, z – переменные для создания пирамиды;
Рrocedure pushdown(j: LongInt);
j, max – элементы, для выбора максимального значения из трех.
Рrocedure heapsort;
n– переменная для построения кучи и сортировки массива 

    2.4 Описание процедур и функций и их значения
Procedure swap (var x, y: LongInt) – используется для создания пирамиды;
Рrocedure pushdown(j: LongInt) – процедура выбора максимального элемента;
Рrocedure heapsort– сортировка пирамиды;
Рrocedure input – процедура для ввода значений;
Рrocedure output – выводит отсортированный массив. 
 

    2.5 Входная и выходная информация
    2.5.1 Входная информация
    Входной информацией  является определенный массив случайных  чисел. Размерность массива задается пользователем.
    Экранная  форма

    2.5.2 Выходная информация
    Выходной  информацией является отсортированный  массив.
    Экранная  форма

    2.6 Руководство пользователя
    В строку «Введите количество элементов (не более 1000)» необходимо ввести число  от 1 до 1000. Число будет соответствовать  размеру массива. Затем следует  нажать клавишу «Enter», появится заранее заданный массив. Нужно заполнить массив случайными числами. После каждого введенного числа необходимо нажать клавишу «Enter», чтобы перейти к вводу следующего. После того, как массив будет заполнен, программа отсортирует его по принципу пирамидальной сортировки. Для завершения работы с программой необходимо нажать клавишу «Enter». 

    2.7 Технология разработки программного средства
    2.7.1 Технология разработки программы
    Данная  программа разрабатывалась в  несколько этапов:
    - получение  задания на курсовое проектирование
    - сбор сведений о поставленной задаче
    - выбор  реализуемого в программе алгоритма
    - определение  структуры и типов данных
    - написание  на выбранном языке алгоритма
    - отладка  и тестирование
    - сдача  программы 

    2.7.2 Описание процесса отладки и испытания программы
    Процесс отладки сопровождал написание  каждой строчки программного кода. Благодаря чему программе не потребовалось  существенных переработок кода после  каждого выявления случаев некорректной работы программы.
    Порядок испытаний проходил в следующем  порядке:
    - поиск и отладка синтаксических ошибок;
    - корректность расчетов проводимых  в программе;
    - корректность отображения выходной  информации;
    Корректность  расчетов, проводимых в программе, проверялась  путем расчета исходных данных, вначале  вручную, а затем с помощью программы. После чего сравнивались результаты. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

Заключение 

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


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


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


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


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


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