VPF::Дерево - Форум программистов

amfisat

Дата 27.5.2010, 06:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 3.5.2010
Где: СПб

Репутация: нет
Всего: нет

Всем привет! Я ОЧЕНЬ новичок в проге, но я упорно занимаюсь ... smile

Вот, собссна, мое затруднение ... - на парах мы как-то очень быстро пробежали материал, и, не успев закрепить предыдущий, полезли уже в бинарные деревья ... - пытаюсь теперь осваивать самостоятельно...
И вот такая задача:

Надо написать программу, которая содержит динамическую информацию налоговой инспеции. Сведения о каждом лице включают в себя: имя, список налогов, для каждого налога - его размер, признак, юридическое лицо или нет.
Программа должна обеспечивать:1) Формирование базы данных инспекции в виде бинарного дерева. 2) при уплате всех налогов (сумма и имя вводятся с консоли) лицо удаляется из базы. 3) По запросу выводятся сведения о физ. и юрид. лицах отдельно.

У меня есть шаблон, который хотелось бы подогнать под эту задачку:

Код


#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <iostream>

using namespace std;

struct list
{
char* name;
int count;
list* next;
};

struct btree
{
int sort;
list* data;
btree* left;
btree* right;
};

list *addToList(list* l, char* str, int count)
{
if (l == NULL)
{
l = new list();
l->name = new char[strlen(str) + 1];
strcpy(l->name, str);
l->count = count;
l->next = NULL;
return l;
}
else if (strcmp(l->name, str) == 0)
{
l->count += count;
return l;
}
else
{
l->next = addToList(l->next, str, count);
return l;
}
}

list *deleteInList(list* l, char* str, int count)
{
if (l == NULL)
{
return NULL;
}
else if (strcmp(l->name, str) == 0)
{
l->count -= count;
if (l->count == 0)
{
list* temp = l->next;
delete [] l->name;
delete l;
return temp;
}
return l;
}
else
{
l->next = deleteInList(l->next, str, count);
return l;
}
}

void printList(list* l)
{
if (l == NULL)
return;

cout<<l->name<<l->count;
printList(l->next);
}

btree* add(btree *tree, int sort, char* str, int count)
{
if (tree == NULL)
{
btree* tree = new btree();
tree->data = NULL;
tree->left = NULL;
tree->right = NULL;
tree->sort = sort;
tree->data = addToList(tree->data, str, count);
return tree;

}
else if (tree->sort == sort)
{
tree->data = addToList(tree->data, str, count);
return tree;
}
else if (tree->sort > sort)
{
tree->left = add(tree->left, sort, str, count);
}
else if (tree->sort < sort)
{
tree->right = add(tree->right, sort, str, count);
}

return tree;
}



btree* find(btree *tree, int sort)
{
if (tree == NULL)
{
return NULL;
}

if (tree->sort == sort)
{
printList(tree->data);
return tree;
}

if (sort < tree->sort)
{
return find(tree->left, sort);
}
else if (sort > tree->sort)
{
return find(tree->right, sort);
}
}

btree* min(btree *tree)
{
if (tree->left == NULL)
{
return tree;
}

return min(tree->left);
}

btree* del(btree *tree, int sort, char* str, int count)
{
if (tree == NULL)
{
return NULL;
}

btree *temp;
if (tree->sort == sort)
{
tree->data = deleteInList(tree->data, str, count);

if (tree->data == NULL)
{
if (tree->left == NULL && tree->right == NULL)
{
delete tree;
return NULL;
}
else if (tree->left == NULL)
{
temp = tree->right;
delete tree;
return temp;
}
else if (tree->right == NULL)
{
temp = tree->left;
delete tree;
return temp; 
}
else 
{
temp = min(tree->right);
tree->sort = temp->sort;
tree->data = temp->data;
temp->data = NULL;
tree->right = del(tree->right, tree->sort, str, count);
return tree;
}
}
}

if (sort < tree->sort)
{
tree->left = del(tree->left, sort, str, count);
}
else if (sort > tree->sort)
{
tree->right = del(tree->right, sort, str, count);
} 

return tree;
}



void destroyList(list* l)
{
list* temp;
while (l != NULL)
{
temp = l;
l = l->next;
delete [] temp->name;
delete temp;
}
}

void destroyTree(btree* tree)
{
if (tree == NULL)
return;
btree* left = tree->left;
btree* right = tree->right;
destroyList(tree->data);
delete tree;
destroyTree(left);
destroyTree(right);

}

int main()
{
cout<<"Input element of tree or empty string to end : ";

btree* tree = NULL;
char str[100]; 
char sort[100];
char count[100];
while (strlen(gets(str)) > 0)
{
gets(sort);
gets(count);
tree = add(tree, atoi(sort), str, atoi(count));

cout<<"Input element of tree or empty string to end : ";

}

cout<<"\nInput element to delete or empty string to end : ";

while (strlen(gets(str)) > 0)
{
gets(sort);
gets(count);
tree = del(tree, atoi(sort), str, atoi(count));

cout<<"\nInput element to delete or empty string to end : ";

}

cout<<"\nInput sort to print or empty string to end : ";

while (strlen(gets(str)) > 0)
{
find(tree, atoi(str));

cout<<"\nInput sort to print or empty string to end : ";

}

destroyTree(tree);

return 0;
}

Посмотрите, пжлст ...

xvr

Дата 27.5.2010, 11:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Цитата(amfisat @ 27.5.2010, 06:26

)

Посмотрите, пжлст ...

Посмотрели - ужас. Нет, ужас ужас ужас smile

Оформите дерево и пр в виде классов, с методами, как полагается. Если классов еще не проходили, то зачем насовали в исходник операторов new?

В качестве ключа в дереве должно использоваться имя, а не то, что у вас там написанно (какой то целый sort)

Если вам нужно именно бинарное дерево, то все остальное лучше взять готовое, что бы не засорять исходник (std::string и std::list)

yeputons

Дата 27.5.2010, 16:37 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 77
Регистрация: 1.4.2009
Где: Санкт-Петербург

Репутация: 2
Всего: 5

xvr,

Цитата

Посмотрели - ужас. Нет, ужас ужас ужас smile

Оформите дерево и пр в виде классов, с методами, как полагается. Если классов еще не проходили, то зачем насовали в исходник операторов new?

В институте же. А там, судя по рассказам друзей, прогать учат не очень хорошо.

amfisat, попробуйте сначала хранить не данные, а просто пары чисел - ID лица и какие-то данные.
Плюс - да, используйте STL:

Код


#include <string>
#include <list>

...

string s ="fff";
s += "abacaba";
printf("%s\n", s.c_str()); // fffabacaba

...
list<int> l;
l.push_back(1);
l.push_back(2);
for (list<int>::iterator it = l.begin(); it != l.end(); it++)
  printf("%d\n", *it);
...

toxx

Дата 27.5.2010, 17:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 4
Всего: 13

Цитата

В институте же. А там, судя по рассказам друзей, прогать учат не очень хорошо.

как стараешься, так и "прогаешь"

yeputons

Дата 29.5.2010, 10:14 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 77
Регистрация: 1.4.2009
Где: Санкт-Петербург

Репутация: 2
Всего: 5

toxx, а если по-другому не то что не учат, а запрещают?
P.S. по-моему, я развожу холивар. Нехорошо.

amfisat

Дата 29.5.2010, 18:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 3.5.2010
Где: СПб

Репутация: нет
Всего: нет

Ну нам эта тема давалась на самост. изучение - учебных часов не хватило ... - и это задание дали на дом ... с метод. указанием в виде того шаблона, который приведен в первом сообщении ...

А что ... он совсем не подходит ... ?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »