Автор работы: Пользователь скрыл имя, 20 Декабря 2010 в 09:12, курсовая работа
Данная программа представляет собой реализацию нелинейной структуры данных в памяти и предлагает интерфейс для работы с ней. Чтобы реализовать структуру данных в памяти используется динамический массив указателей на строки, в который при вводе сохраняются указатели на вводимые строки, затем они сортируются по возрастанию длины. Полученный массив указателей сортируется таким образом, чтобы линейно с помощью операции вставки в дерево сформировать сбалансированное дерево. Структура данных представляет собой:
1.Задание………………………………………….……………...…………………3
2.Структурное описание разработки……………………………...……………...4
3.Функциональное описание………………………………………..……………..8
4.Описание работы программы на контрольном примере и выводы……….…9
5.Литература…………………………..………………………………………..…12
if(thi
{
}
else
}
define
}
// функция для создания копии строки из текущей вершины
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(
balanse();
}
//
конструктор дерева с
tree(char* string)
{
this->bal = 0;
this->pu = 0;
head = new elem;
head->p = new char[strlen(string) + 1];
strncpy(
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->
else
head = new elem(mas);//если нет то выделяем память
if(!prov_
balans
}
// функция распечатки дерева
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->
a = head->left->count;//то в а записываем кол-во вершин в поддереве слева
if(head->
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)
{
}
for(int i = 0; i < sz*3; i++)
ready_
put_to_
for(int i = 0; i < sz*3; i++)
if(
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)
{
}
}
//
функция выбора индекса
int med(int min, int max)