    Сейчас на сайте: 1 посетителей (1 зарегистрированных, 0 гостей) |   426057681  574055213 |  Партнерам |  Авторам |  Покупателям |
Разработать структуру данных (двоичные деревья поиска).
| курсовые работы, Программирование Объем работы: 28 стр. Год сдачи: 2008 Стоимость: 1050 руб. Просмотров: 1054 | Не подходит работа? |
Оглавление
Введение
Литература
Заказать работу
1. Двоичное дерево 3
2. Представления двоичных деревьев 5
3. Двоичное дерево поиска 7
4. Добавление элемента 8
5. Вывод в виде скобочной последовательности 9
6. Поиск элемента 10
7. Подсчет суммы элементов 11
8. Разработка структуры 12
9. Создание тестовых файлов 14
10. Вывод предметного указателя. 15
Список литературы 16
Приложение 1. 17
Приложение 2 28
1. Двоичное дерево
Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.
Представьте себе список, в котором за каждым элементом может идти не один следующий, а два.
Рисунок 1
Однако дерево принято рисовать так:
Рисунок 2
Элементы дерева называются вершинами (vertex) или узлами (node), а соединения – ребрами (edge) или дугами (arc).
От каждой вершины вниз идет не более двух ребер (поэтому дерево – двоичное).
Вершины, с которыми соединена данная, и которые расположены ниже нее, называются детьми данной вершины (также часто говорят «сыновья»). При этом различаются правый и левый сын. Если вершина A является ребенком вершины B, то вершина B называется родителем A. У каждой вершины может быть не более одного родителя.
Вершина, не имеющая родителя, называется корнем дерева. То есть мы изображаем дерево корнем вверх – так удобнее.
Вершины, не имеющие детей, называются листьями дерева.
Так на рисунке 5 – корень дерева, вершина 3 – левый сын вершины 5, вершина 2 - правый сын вершины 1, вершины 2, 6, 8 являются листьями.
Все сказанное выше неформально описывает двоичное дерево. На самом деле двоичное дерево – это математический объект и его можно определить строго. Одно из определений – рекурсивное – звучит так:
Определение.
• Каждая вершина...
2. Представления двоичных деревьев 5
3. Двоичное дерево поиска 7
4. Добавление элемента 8
5. Вывод в виде скобочной последовательности 9
6. Поиск элемента 10
7. Подсчет суммы элементов 11
8. Разработка структуры 12
9. Создание тестовых файлов 14
10. Вывод предметного указателя. 15
Список литературы 16
Приложение 1. 17
Приложение 2 28
1. Двоичное дерево
Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.
Представьте себе список, в котором за каждым элементом может идти не один следующий, а два.
Рисунок 1
Однако дерево принято рисовать так:
Рисунок 2
Элементы дерева называются вершинами (vertex) или узлами (node), а соединения – ребрами (edge) или дугами (arc).
От каждой вершины вниз идет не более двух ребер (поэтому дерево – двоичное).
Вершины, с которыми соединена данная, и которые расположены ниже нее, называются детьми данной вершины (также часто говорят «сыновья»). При этом различаются правый и левый сын. Если вершина A является ребенком вершины B, то вершина B называется родителем A. У каждой вершины может быть не более одного родителя.
Вершина, не имеющая родителя, называется корнем дерева. То есть мы изображаем дерево корнем вверх – так удобнее.
Вершины, не имеющие детей, называются листьями дерева.
Так на рисунке 5 – корень дерева, вершина 3 – левый сын вершины 5, вершина 2 - правый сын вершины 1, вершины 2, 6, 8 являются листьями.
Все сказанное выше неформально описывает двоичное дерево. На самом деле двоичное дерево – это математический объект и его можно определить строго. Одно из определений – рекурсивное – звучит так:
Определение.
• Каждая вершина...
1. Подсчет суммы элементов
Часто возникают задачи следующего вида: перебрать все элементы дерева и вычислить некоторую величину, например, сумму всех элементов.
Такие задачи также решаются с помощью рекурсии.
Рассмотрим для примера задачу о сумме всех элементов в дереве.
Рекурсивная функция, решающая эту задачу будет определяться так:
• Для пустого дерева вернуть 0
• Для непустого дерева вернуть сумму трех значений: значения этой функции на левом поддереве, значения этой функции на правом поддереве, значения поля Data вершины.
Подсчет общего количества элементов работает также, но вместо прибавления поля Data нужно прибавлять 1 (логично: если во всех элементах дерева единицы, то сумма всех элементов равна их количеству).
8. Разработка структуры
Перейдём от изучения общих вопросов, связанных с двоичными деревьями поиска к задачам, связанным с темой данного курсового проекта.
Все данные, с которыми необходимо работать разобьём на три большие группы:
• термины
• подтермины
• номера страниц
Данные каждой группы будем представлять в виде двоичных деревьев поиска.
Структура данных для хранения номеров страниц представлена следующим образом:
uks=^pages;
pages=record
left,right:uks;
str:integer;
end;
Здесь left и right это указатели на сыновей узла а str номер страницы, узел дерева.
Структура данных для хранения подтерминов представлена следующим образом:
ukp=^podt;
podt=record
left,right:ukp;
podterm:string[20];
str:uks;
end;
Здесь left и right это указатели на сыновей узла, str указатель на вершину дерева, содержащего номера страниц для подтермина, а podterm это узел дерева.
Структура данных для хранения терминов представлена следующим образом:
terms=record
left,right:ukt;
term:string[20];
podterm:ukp;
str:uks;
end;
1. Фаронов. Программирование на языке Турбо Паскаль. СПб 2005
2. Бреслав А.А. Информатика. М. 2003
После офорления заказа Вам будут доступны содержание, введение, список литературы*
*- если автор дал согласие и выложил это описание.