VPF::Небинарное дерево - Форум программистов

Hanja

Дата 9.11.2014, 19:36 (ссылка)

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

Загрузка ...

Новичок

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

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

Имеется такая задача:
Трассировка  программы,   не   содержащей   рекурсивных
вызовов  и  повторяющихся  имен  процедур,  распечатана в виде
списка выполняемых процедур. Процедура попадает в список, если
к ней произошло обращение из вызывающей процедуры либо возврат
управления из  вызванной  ей  процедуры.  Структура  программы
такова,  что  каждая вызываемая процедура вложена в вызывающую
ее процедуру.  Начало и  окончание  программы  должны  быть  в
головной процедуре.  Известен объем памяти,  который требуется
для  загрузки  каждой  процедуры.  При  выходе  из   процедуры
занимаемая ей память освобождается.  Построить и выдать дерево
вызовов процедур.  Определить размер памяти,  необходимый  для
работы  программы,  и цепочку вызовов,  требующую максимальной
памяти.

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

Код


#include <iostream>
 
#include <stdlib.h>
 
using namespace std;
 
//using namespace system
 
struct Tree {
 
int id; //уникальное значение
 
int level; //уровень в иерархии
 
int count_son; //количество сыновей
 
struct Tree** son; //массив указателей на сыновей
 
};
 
/*---------Создание дерева----------*/
 
struct Tree *createTree(struct Tree *node, int id, int level){
 
//node = new Tree;
 
node->id = id;
 
node->level = level;
 
cout << "\nKol. sons (" << (node->level) << "-" << (node->id) << "): ";
 
cin >> (node->count_son);
 
node->son = new struct Tree *[node->count_son];
 
 
 
level++;
 
for(int i = 0; i < ( node->count_son); i++){
 
node->son[i] = new Tree;
 
node->son[i]->id = id + i;
 
node->son[i]->level = level;
 
}
 
for(int i = 0; i < (node->count_son); i++)
 
createTree(node->son[i], id + i, level);
 
return node;
 
}
 
/*---------Вывод дерева----------*/
 
void printTree(struct Tree *node){
 
if(node){
 
for(int i = 0; i < (node->level); i++)
 
cout << "| ";
 
if(node->son != NULL)
 
cout << "[+]";
 
cout << "(" << (node->level) << "-" << (node->id) << ")" << endl;
 
if((node->count_son) != 0)
 
for(int i = 0; i < (node->count_son); i++)
 
printTree(node->son[i]);
 
}
 
}
 
 
 
int main()
 
{
 
Tree *root;
 
root = new Tree;
 
root = createTree(root, 0, 0);
 
printTree(root);
system("pause"); 
return 0;
 
 
}

xvr

Дата 10.11.2014, 12:52 (ссылка)

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

Загрузка ...

Эксперт

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

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

Ваша программа - готовый пример на тему 'Как не надо писать на С++'. Верните каку тому, кто ее написал smile

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

Для хранения потомков используйте массив std::vector<Tree*> внутри Tree

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