Министерство  образования Российской Федерации

Новосибирский Государственный Технический Университет

 
 
 
 
 
 
 

Курсовой  проект по дисциплине "Программирование"

Древовидные структуры 
 

                                  Факультет: АВТФ  
                                                                       Группа: АП-819 
Выполнил: Терехов Е.Л.                                                        Проверил: Романов Е.Л.

Новосибирск 2010

 

Содержание

 

1. Задание………………………………………….……………...…………………3
2. Структурное описание разработки……………………………...……………...4
3. Функциональное описание………………………………………..……………..8
4. Описание работы программы на контрольном примере и выводы……….…9
5. Литература…………………………..………………………………………..…12

 

Задание

     6. Древовидные структуры

     Для древовидных структур данных предусмотреть  вывод характеристик сбалансированности дерева (средняя длина ветви) и процедуру выравнивания (балансировки).

     2. Двоичное дерево, каждая вершина которого содержит указатель на строку, счетчик вершин в поддереве. 

  Структурное описание  разработки

     Данная  программа представляет собой реализацию нелинейной структуры данных в памяти и предлагает интерфейс для работы с ней. Чтобы реализовать структуру данных в памяти используется динамический массив указателей на строки, в который при вводе сохраняются указатели на вводимые строки, затем они сортируются по возрастанию длины. Полученный массив указателей сортируется таким образом, чтобы линейно с помощью операции вставки в дерево сформировать сбалансированное дерево. Структура данных представляет собой:  

Двоичное дерево

 

Рис.1.Графическое  представление заданной структуры данных с тремя элементами 
 

 

В программе  имеется один класс с вложенной структурой:

1. Класс Tree – представляющий собой эту структуру данных. Содержит в себе указатель на вешину дерева (elem *head) и последний (LowerList *end) элементы верхнего списка.

 

2. Структура Elem - представляет собой структуру вершины дерева. Содержит в себе указатели на левого (elem* left) и правого (elem* right) потомков.  Так же в каждой вершине хранится длинна ветви (int len), т. е. путь до верхушки дерева.

 

3.  Структура  Felem  - представляет собой вспомогательную структуру вершины дерева для сохранения его в двоичный файл. Содержит в себе указатели на левого (long fl) и правого (long fr) потомков в файле. Так же в каждой вершине хранится длина записываемой строки в файле (int sz).

 
 
 
 
 
 
 
 
 
 
 
 
 

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

 Рассмотрим  принцип построения двоичного  дерева поиска на примере построения  дерева для набора данных 9, 44, 0, –7, 10, 6, –12.

     Согласно  определению двоичного дерева поиска число 9 помещаем в корень, все значения, меньшие его — на левое поддерево, большие или равные — на правое. В каждом поддереве очередной элемент можно рассматривать как корень и действовать по тому же алгоритму. 
 

     

 

Рис.2.Пример построения двоичного  дерева поиска 

     Поскольку максимальный путь до листьев дерева определяется высотой дерева, то при заданном числе n узлов дерева стремятся построить дерево максимальной высоты. Этого можно добиться, если размещать максимально возможное количество узлов на всех уровнях, кроме последнего. В случае двоичного дерева это достигается таким образом, что все узлы распределяются поровну слева и справа от каждого узла. Бинарное дерево считается идеально сбалансировано если для каждого его узла количество узлов в левом и правом поддеревьях различается не более чем на 1. 
 
 
 
 
 
 
 
 
 

 

     Пример: дерево, построенное из 15 случайных строк

 

Рис.3. Пример работы программы 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

     Функциональное  описание разработки

      Функции класса Tree – класс дерева.

      Функция добавления элемента в дерево

void push(char* str);

      В функцию передается указатель на помещаемую в дерево строку. В зависимости от длинны данной строки она размещается по принципу двоичного дерева поиска. Вставка производится рекурсивно.  Если дерево пустое, то эта строка помешается в корневой элемент дерева. Затем проверяется сбалансированность дерева с помощью функции bool test_balanse();. Если дерево в данной вершине не сбалансировано, то вызывается функция балансировки void balance();.

      Функция проверки на сбалансированность

bool balanse(); 

     В функцию не передаются никакие параметры. Функция находит модуль разности количества подвершин у левого и правого потомков и возвращает true, если дерево сбалансировано и false – если дерево не сбалансировано.

      Функция балансировки

void balance();

      В функцию не передаются никакие параметры. Функция балансировки производится в два этапа. Сначала выделяется массив указателей на строки размерности size и все дерево рекурсивно записывается в массив с помощью функции void savetomas(char** mas,int& index) полученный массив сортируется методом пузырька по возрастанию длин строк. Далее создается вспомогательный массив указателей на строки для сортировки и линейного вызова функции добавления элемента в дерево. Таким образом дерево получается сбалансированным. 

      Функция сортировки строк  для построения сбалансированного  дерева

void put_to_ready(int index,int l,int r,char** mas,char** ready_mas);

     В функцию передается индекс указателя на строку в отсортированном массиве         ( index ), количество элементов слева ( l ), количество элементов справа ( r ), исхоный массив ( mas ) и массив, готовый для построения дерева ( ready_mas ).

      Функция подсчета средней длины ветви

void med_len();

      В функцию не передаются никакие параметры. Функция вызывает функцию в структуре с аналогичным названием, но которая возвращает значение типа int. Эта функция в свою очередь вызывает функцию подсчета длинн всех ветвей и функцию нахожения всех подвершин в дереве, а затем возвращает частное от деления всех длинн ветвей на количество вершин.

      Функция выбора среднего значения из диапозона

int med(int min, int max);

      В функцию передаются два параметра, минимальное и максималное знечения в диапозоне. В результате вычисления функция возвращает среднее значение из данного диапозона. 

Функция подсчета длинн ветвей

void len();

      В функцию не передаются накакие параметры. Она вызывает функцию структуры elem void define_len(int _len); , которая рекурсивно проходит по всему дереву, начиная с вершины и считает длинну ветви в каждой вершине. 

Функции структуры elem – структура узла дерева 

     Функция рекурсивной распечатки дерева

void print();

      В функцию не передаются никакие параметры. Она рекурсивно проходит по всмеу  дереву и распечатывает значения счетчика подвершин, длины ветви  и строку для каждой вершины.

      Функция рекурсивной очистки дерева

void clear();

      В функцию не передаются никакие параметры. Она рекурсивно освобождает память из под строк.

      Функция создания копии строки из текущей вершины

Char* getstr();

      В функцию не передаются никакие параметры. Функция выделяет память под строку размером на один больше, чем размер строки в текущей вершине, таким образом вместе со строкой копируется символ конца строки и возвращается указатель на копию. 
 
 
 
 
 
 
 
 
 
 

 

Литература

1. Романов Е.Л. Язык СИ++ в задачах, вопросах и ответах. Новосибирск: Изд-во НГТУ, 2003.
2. С++ lessons
3. Роберт Седжевик С++. Пер. с англ./Роберт Седжевик. –СПб, 2000г. – 496с.
4. А. Поя. Обьектно-ориентированное программировании на С++. 1992г.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

      

Приложение

Листинг программы 

#include <iostream>

#include <time.h>

#include <conio.h>

#include <string>

#define FNULL -1L

#define TSZ sizeof(felem)

using namespace std; 

class tree