#include <conio.h>
#include <stdio.h>
struct node
{
int number;
int label;
node *ancestor;
};
int main(void)
{
int a=0,i,numb=0,lvl=0;
node *p=new node;
p->ancestor=0;
p->number=numb;
node *root=p;
printf("Skolko potomrkov u dannogo uzla? ");
scanf("%i",&a);
for(i=0;i<a;i++)
{
numb++;
node *p1=new node;
p1->number=numb;
printf("Vvedite metku uzla %i ",i+1);
scanf("%i",p1->label);
p1->ancestor=p;
}
...
Размер структуры.
Пишу программу которая создает дерево, у каждого узла произвольное число потомков, указываемое пользователем. Остановился на самом начале. Все должно быть реализовано с помощью указателей на родителей. Каждый узел - структура, содержащая метку, порядковый номер и указатель на родителя. sizeof() показывает, что размер структуры 12, и адресс увеличивается на 12 при p++, а адреса созданных одна за другой структур отличаются на 16. :confused: Почему? Изза этого я не могу перемещаться по структурам используя инкремент. Как быть?
Привожу кусочек кода:
а не [quote] . /* модератор */[/COLOR]
Привожу кусочек кода:
Код:
[QUOTE=Gorec]дерево, у каждого узла произвольное число потомков, указываемое пользователем. Остановился на самом начале. Все должно быть реализовано с помощью указателей на родителей[/QUOTE]
Почемй ты так решил организовать деоево. Если ты будешь хранить указатель на родителя, ты не сможешь перемешаться по дереву).
Примерно вот так нужно оформять код. Больше пробелов, пустых строк и отступов.
Ну и по коду. Ты же создаешь узел и на следующей итерации теряешь указатель на выделеную память безвозвратно, а это мусор.
З.Ы. В структуре могут быть "дыры". Покожи код перемещения по структуре.
Почемй ты так решил организовать деоево. Если ты будешь хранить указатель на родителя, ты не сможешь перемешаться по дереву).
Код:
for( i = 0; i < a; i ++ )
{
node *p1 = new node;
numb ++;
p1->number = numb;
printf( "Vvedite metku uzla %i ", i + 1 );
scanf( "%i", p1->label );
p1->ancestor = p;
}
{
node *p1 = new node;
numb ++;
p1->number = numb;
printf( "Vvedite metku uzla %i ", i + 1 );
scanf( "%i", p1->label );
p1->ancestor = p;
}
Примерно вот так нужно оформять код. Больше пробелов, пустых строк и отступов.
Ну и по коду. Ты же создаешь узел и на следующей итерации теряешь указатель на выделеную память безвозвратно, а это мусор.
З.Ы. В структуре могут быть "дыры". Покожи код перемещения по структуре.
Цитата:
Почемй ты так решил организовать деоево. Если ты будешь хранить указатель на родителя, ты не сможешь перемешаться по дереву).
Потому что так поставлена задача.
Как я понимаю это нужно решить:
Создаем дерево.
Запоминаем количество узлов.
Обходим так: от указателя на корень идем по памяти используя ++ и смотрим у какого узла поле ancestor указывает на корень и т.д.
насчет мусора:
цитата из книжки(проверенная)
Цитата:
Арифметические операции с указателями (сложение с константой, вычитание, инкремент и декремент) автоматически учитывают размер типа величин адресуемых указателями. Эти операции применимы только к указателям одного типа и имеют смысл в основном при работе со структурами данных, последовательно размещенных в памяти, например массивами. ... Фактически значение указателя изменяется на величену sizeof(тип).
Непонятно, почему адреса созданных последовательно структур отличаются на 16 а не на 12.
ЗЫ Кода дальше просто нет). Я дошел до этого момента, начал проверять как создаются структуры и нашел ошибку.
Цитата: Gorec
Непонятно, почему адреса созданных последовательно структур отличаются на 16 а не на 12.
Вообще говоря, если объект А создан сразу после объекта В, то это не означает, что в памяти они будут располагаться последовательно.
Хочешь, чтобы они последовательно располагались - используй массив.
Хм. я в курсе, но всегда работало)). А если делать массивом то нужно заранее спрашивать сколько узлов и как они расположены, потом сохранять эти данные(куда?) в файл наверное будет лучше всего, потом создавать массив структур и лишь потом их организовывать в дерево. Я подумал, что мой способ попроще.
А черт! Я действительно понял какую глупость придумал с подряд заведенными структурами: надо массивом. Всем спасибо )
Вассе-то, нормальные люди делают у каждого узла указатель на первого потомка и на след. "брата".
Я знаю, как делают нормальные люди. Ну а я делаю как указано в моей задаче.
ЗЫ. это для бинарного дерева, а для небинарного? У моего дерева у каждого узла может быть сколько угодно потомков.
ЗЫ. это для бинарного дерева, а для небинарного? У моего дерева у каждого узла может быть сколько угодно потомков.
2 Gorec
Как видно для узла1, что бы перебрать всех потомков достаточно знать указатель тока на первого(узел2), а там уже этот потомок(узел2), уже содержит указатель на следующего потомка узла1 узел3(для узла2 он являеться "бра - а - а -тиком"). Тоесть по указателю на сына мы фактически получаем указатель на список сыновей.
Для бинарных, как частного случая есть более лучшие способы. Например в массиве(двоичная куча), где потомками i-го узла являються узлы 2i и 2i+1, а узел 1 - корнень. Данный способ объясняется тем, что на i-ом уровне бинарных деревьев в 2-а раза больше вершин чем на i-1-ом.
Непонятно зачем тебе указатель на родителя, причем тока на него. Обычно по дереву спускаються "вниз"(отталкиваються от корня). Поэтому нужен указатель на потомка.
Если ты реализуешь через массив проблемы с добавлением будут. Тогда уж если я тебя правильно понял список нужен(если правильно понял идею). Но в любом случае "твой" способ экзотичен мягко говоря
Цитата:
Вассе-то, нормальные люди делают у каждого узла указатель на первого потомка и на след. "брата".
Это приведен один из способов хранения деревьев общего вида(т.е. любых) , а не тока бинарных.
Попробую прояснить ситуацию. Вот рисунок.
Код:
узел1(корень)
/ | \
v | \
узел2 -> узел3 -> узел 4
/ | \
v | \
узел5 ... ...
/ | \
v | \
узел2 -> узел3 -> узел 4
/ | \
v | \
узел5 ... ...
Как видно для узла1, что бы перебрать всех потомков достаточно знать указатель тока на первого(узел2), а там уже этот потомок(узел2), уже содержит указатель на следующего потомка узла1 узел3(для узла2 он являеться "бра - а - а -тиком"). Тоесть по указателю на сына мы фактически получаем указатель на список сыновей.
Для бинарных, как частного случая есть более лучшие способы. Например в массиве(двоичная куча), где потомками i-го узла являються узлы 2i и 2i+1, а узел 1 - корнень. Данный способ объясняется тем, что на i-ом уровне бинарных деревьев в 2-а раза больше вершин чем на i-1-ом.
Непонятно зачем тебе указатель на родителя, причем тока на него. Обычно по дереву спускаються "вниз"(отталкиваються от корня). Поэтому нужен указатель на потомка.
Если ты реализуешь через массив проблемы с добавлением будут. Тогда уж если я тебя правильно понял список нужен(если правильно понял идею). Но в любом случае "твой" способ экзотичен мягко говоря
Я понимаю всю экзотичность своего метода). Просто есть методичка, в ней по теме "деревья" 25 вариантов задачи.
Привожу свою задачу:
Привожу свою задачу:
Цитата:
Напишите программу, которая представляет операторы выполняемые над деревом - LABEL(n, T), root(T) и чето еше. Все должно быть реализовано с помощью указателей на родителей.
Все упирается в эти указатели на родителей.
Встречаются еще варианты задачи:
Цитата:
...Все должно быть реализовано с помощью списка сыновей.
и
Цитата:
...Все должно быть реализовано с помощью указателя на самого левого сына и на правого брата(как раз твой метод)
Так вот не я выбираю через что реализовывать дерво). Какая досталась, такую и делаю. Не нравится мне способ со списком, так как нада в каждую структуру еще по указателю и + в задаче ничего не сказано про список.
З.Ы. спасибо за пояснения, я сразу не догнал как можно сделать небинарное дерево.
А может вот так-------->>>>>>>>>
Если что не понятно, спрашивай. Остальное доделаешь сам, задолбался я это писать))) :D
Код:
#include <stdio.h>
#define LETTER 'A'
#define DIGIT '0'
#define MAXWORD 20
struct tnode{
char* word; //Указатель на слово
int count; //Счётчик слов
struct tnode* left; //Левый потомок
struct tnode* right; //Правый потомок
}
main() {
struct tnode* root,* tree();
char word[MAXWORD];
int t;
root=NULL;
while((t=getword(word,MAXWORD))!=EOF) {
if(t==LETTER) {
root=tree(root,word);
}
}
treeprint(root);
}
struct tnode* tree(p,w) {
struct tnode* p;
char* w;
struct tnode* talloc();
char* strsave();
int cond;
if(p==NULL) {
p=talloc();
p->word=strsave(w);
p->count=1;
p->left=p->right=NULL;
}
else if((cond=strcmp(w,p->word))==0) {
p->count++;
}
else if(cond<0) {
p->left=tree(p->left,w);
}
else {
p->right=tree(p->right,w);
}
return (p);
}
treeprint(p) {
struct tnode* p;
if(p!=NULL) {
treeprint(p->left);
printf("%4d%s\n",p->count,p->word);
treeprint(p->right);
}
}
struct tnode* talloc() {
char* calloc();
return((struct tnode*)calloc(1,sizeof(struct tnode)));
}
getword(w,lim) {
char* w;
int lim;
int c,t;
if(type(c=* w++=getch())!=LETTER) {
* w='\0';
return(c);
}
while(--lim>0) {
t=type(c=* w++=getch());
if(t!=LETTER && t!=DIGIT) {
ungetch(c);
break;
}
}
*(w-1)-'\0';
return(LETTER);
}
type(c) {
int c;
if(c>='A' && c<='Z' || c>='a' && c<='z') {
return(LETTER);
}
else if(c>='0' && c<='9') {
return(DIGIT);
}
else {
return(c);
}
}
#define LETTER 'A'
#define DIGIT '0'
#define MAXWORD 20
struct tnode{
char* word; //Указатель на слово
int count; //Счётчик слов
struct tnode* left; //Левый потомок
struct tnode* right; //Правый потомок
}
main() {
struct tnode* root,* tree();
char word[MAXWORD];
int t;
root=NULL;
while((t=getword(word,MAXWORD))!=EOF) {
if(t==LETTER) {
root=tree(root,word);
}
}
treeprint(root);
}
struct tnode* tree(p,w) {
struct tnode* p;
char* w;
struct tnode* talloc();
char* strsave();
int cond;
if(p==NULL) {
p=talloc();
p->word=strsave(w);
p->count=1;
p->left=p->right=NULL;
}
else if((cond=strcmp(w,p->word))==0) {
p->count++;
}
else if(cond<0) {
p->left=tree(p->left,w);
}
else {
p->right=tree(p->right,w);
}
return (p);
}
treeprint(p) {
struct tnode* p;
if(p!=NULL) {
treeprint(p->left);
printf("%4d%s\n",p->count,p->word);
treeprint(p->right);
}
}
struct tnode* talloc() {
char* calloc();
return((struct tnode*)calloc(1,sizeof(struct tnode)));
}
getword(w,lim) {
char* w;
int lim;
int c,t;
if(type(c=* w++=getch())!=LETTER) {
* w='\0';
return(c);
}
while(--lim>0) {
t=type(c=* w++=getch());
if(t!=LETTER && t!=DIGIT) {
ungetch(c);
break;
}
}
*(w-1)-'\0';
return(LETTER);
}
type(c) {
int c;
if(c>='A' && c<='Z' || c>='a' && c<='z') {
return(LETTER);
}
else if(c>='0' && c<='9') {
return(DIGIT);
}
else {
return(c);
}
}
Если что не понятно, спрашивай. Остальное доделаешь сам, задолбался я это писать))) :D