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

Автор работы: Пользователь скрыл имя, 20 Декабря 2010 в 09:12, курсовая работа

Описание

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

Содержание

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

Работа состоит из  1 файл

Копия записка.doc

— 169.50 Кб (Скачать документ)

                        if(this->right == NULL)

                        {

                              this->right = new elem;

                              this->right->p = new char[strlen(str) + 1];

                              strncpy(right->p, str, strlen(str) + 1);

                        }

                        else

                              this->right->push(str);

                        }

                        define_len(0);//вызываем функцию нахождения длины ветвей.тетрадь

            } 

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

      char* getstr() 

            {

                  int size = strlen(p)+1;//записывается размер длину строки текущей ячейки и увеличиваем ее на 1

                  char *mas = new char[size];//выделяем память под строку

                  strncpy(mas, p, size);//копируем строку

                  return mas;//возвращяем указатель на эту строку

            }

// конструктор  дерева без параметров

      tree()

            {

                  this->bal = 0;//

                  this->pu = 0;

                  head = NULL;

            } 

      // конструктор дерева с параметром - количество вершин

      tree(int n)

            {

                  this->bal = 0;

                  this->pu = 0;

                  head = NULL;

                  char** mas = new char*[n];//выделяем память под указатели на строки

                  mas = randstr(n);        

                  for(int i = 0; i < n; i++)

                        push(mas[i]);//

                  balanse();

            } 

      // конструктор дерева с параметрами

      tree(char* string)

            {

                  this->bal = 0;

                  this->pu = 0;

                  head = new elem;

                  head->p = new char[strlen(string) + 1];

                  strncpy(head->p,string, strlen(string) + 1);

                  head->count = 0;

                  head->left = NULL;

                  head->right = NULL;

            } 
 

      // деструктор дерева

      ~tree()  

            {

                  if(head)

                        clear();

            } 

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

      void clear()   

            {

                  head->clear();

                  delete head;

                  head = NULL;

            } 
 

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

      void push(char* mas)

            {

                  this->pu++;

                  if(head)

                        head->push(mas);//если есть указатель на корень то рекурсивно вызываем функц добавления элемента

                  else

                        head = new elem(mas);//если нет то выделяем память

                  if(!prov_balanse())//вызываем функцию проверки сбалансированности дерева

                        balanse();        //если оно не сбаланс то мы его балансируем

            } 
 

      // функция распечатки дерева

      void print()   

            {

                  head->print();

                  cout << "balsnse= " << this->bal << endl << "push= " << this->pu << endl;

            } 

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

      bool prov_balanse()

            {

                  long a = 0;

                  long b = 0;

                  long r = 0;

                  if(head->left)//если у корня есть слева что-нибудь

                        a = head->left->count;//то в а записываем кол-во вершин в поддереве слева

                  if(head->right)

                        b = head->right->count;//справа тоже самое

                  r = a - b;  //проверяем две половины чтоб они были одинаковые

                  if(r == 0)

                  {

                        cout << "YES" << endl;//если сбалансир то да

                        return true;

                  }

                        cout << "NO" << endl;

                        return false;

            } 
 

      // функция балансировки дерева

      void balanse()  

            {

                  int size = this->head->count + 1;

                  int sz = size;

                  char **mas = new char*[size];

                  char **ready_mas = new char*[size*3];

                  int index = 0;

                  while(size != 1)

                        {

                              bal++;

                              for(int i = 0; i < size - 1; i++)

                                    {

                                          int sz1 = strlen(mas[i]);

                                          int sz2 = strlen(mas[i+1]);

                                          if(sz1 > sz2)

                                                {

                                                      char* temp = mas[i];

                                                      mas[i] = mas[i+1];

                                                      mas[i+1] = temp;

                                                }

                                    }

                              size--;

                        }

                  for(int i = 0; i < sz*3; i++)

                        ready_mas[i] = NULL;

                  put_to_ready(0, 0, sz-1, mas, ready_mas);

                  for(int i = 0; i < sz*3; i++)

                        if(ready_mas[i])

                              push(ready_mas[i]);

                  delete[] ready_mas;

                  delete[] mas;

            } 
 
 

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

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

            {                  

                  int current;

                  if(r - l >= 0)

                        {

                              current = med(l, r);

                              ready_mas[index] = mas[current];

                              put_to_ready(2*index + 1, l, current - 1, mas, ready_mas);

                              put_to_ready(2*index + 2, current + 1, r, mas, ready_mas);

                        }

            } 
 
 

      // функция выбора индекса вершины  из диапазона [min,max]

      int med(int min, int max)  

Информация о работе Древовидные структуры