PDA

Visualizza la versione completa : [C] Alberi Ricerca Binaria con STACK


RoxLover
05-03-2009, 19:31
Buonasera a tutti,
mi ritrovo a sbattere allegramente la testa contro qualsivoglia spigolo mi si presenti per risolvere il seguente problema(due punti a capo)
stò implementando un albero di ricerca binario molto semplice e perlappuntoporcacciamiseria non funzionante.
Le operazioni da implementare sono le semplici find,add,altezza etc...Finchè le ho dovute implementare ricorsivamente nessun problema tutte funzionanti, ma al momento di passare alla versione iterativa sono arrivati i problemi.Dopo qualche ricerca ho provato a implementare la funzione add con l'aiuto di uno stack che però non ha nessuna intenzione di funzionare.Posto il codice per qualche anima pia..

//----------------------METODI X STACK
#define SIZE 50
Tree *tos, *p1, stack[SIZE];

void push(Tree* i)
{
p1++;
if(p1 == (tos+SIZE)) {
printf("Stack Overflow.\n");
exit(1);
}
p1 = i;
}

Tree* pop(void)
{
if(p1 == tos) {
printf("Stack Underflow.\n");
exit(1);
}
p1--;
return (p1+1);
}

//---------------------------------------------------------------------
void addIt(int x, Tree * T){
tos = stack;
p1 = stack;
if (findIt(x,*T)==1) return;
printf("L'elemento non è stato trovato.Procedo all'inserimento.\n");
int flag=0;
push(T);
Node *node;
do{
&node=(pop());
//printf("Elemento considerato:%d\n",cursor->element);
if (node->element >x){
printf("node->element >x");
if (node->left!=NULL) push((*node)->left);
else flag=1;

}else{
printf("node->element <x");
if (node->right!=NULL) push((*node)->left);
else flag=1;
}
}while (flag==0)
if (node->element > x) node->left=newNode(x);
else node->right=newNode(x);
}

Ah scusate non ho avvertito se qualche vero programmatore C lo legge potrebbe morire per l'uso dei puntatori..Beware!Ringrazio dell'attenzione e spero in qualche replica perchè sono un tantinello nella m.

MItaly
05-03-2009, 20:51
Ma nello stack vuoi memorizzare dei puntatori a Tree oppure dei Tree?

YuYevon
05-03-2009, 20:51
Ciao,

scusa ma se anche qualcuno trovasse il tempo per aiutarti, da dove dovrebbe cominciare?

1) non hai specificato dove hai l'errore, e non hai nemmeno detto semplicemente se si tratta di un errore run-time o compile-time, limitandoti a dire che "non ha alcuna intenzione di funzionare";

2) il codice è illegibile, non lo hai riportato con gli appositi tag che sono a disposizione, non è indentato e non ci sono spazi tra le righe e tra le parole (che lo renderebbero più leggibile) nemmeno a pagarli;

3) il codice non è compilabile dato che non c'è main();

4) bisogna praticamente andare ad intuito sulla natura di variabili come p1, tos e il tipo "Tree", visto che non hai detto nulla in merito, nonché sulla funzione findIt(), che non è stata definita nel codice che hai riportato, pur essendo richiamata;

Non è per fare la predica, ma è perché in queste condizioni diventa praticamente impossibile aiutarti :)

RoxLover
05-03-2009, 22:24
Voglio memorizzare il puntatore a Tree in modo da,arrivando alla fine del ramo corretto, poter memorizzare nell' albero passato come parametro il nuovo nodo con parte elemento=x.

x YuYevon:chiedo venia è la prima volta che provo la strada del forum e non sono pratico cerco di essere più chiaro.


typedef struct Node* Tree;
typedef struct Node {

int element;

Tree left; // sinistro

Tree right; // destro

}Node;

Tree newNode(int el) {

Tree pnode = (Node *)malloc(sizeof(Node));


pnode->element = el;


pnode->left = NULL;


pnode->right = NULL;


return pnode;

}

int find(int x, Tree t) {


int el; // usando una variabile in più si evita ogni


if(t) { // volta il doppio calcolo della chiave del nodo

el = t->element;


if(x < el) return find(x,t->left);


else if(x > el) return find(x,t->right);


else return 1;

}


else return 0;

}


//----------------------METODI X STACK

#define SIZE 50

Tree *tos, *p1, stack[SIZE];

void push(Tree* i)
{

p1++;

if(p1 == (tos+SIZE)) {

printf("Stack Overflow.\n");

exit(1);

}

p1 = i;
}

Tree* pop(void)
{

if(p1 == tos) {

printf("Stack Underflow.\n");

exit(1);

}

p1--;

return (p1+1);
}

//---------------------------------------------------------------------
void addIt(int x, Tree * T){

tos = stack;
p1 = stack;
if (findIt(x,*T)==1) return;
printf("L'elemento non è stato trovato.Procedo all'inserimento.\n");

int flag=0; //settato a 1 quando trovo posizione corretta

push(T);
Node *node;
//Tree cursor=T;
do{
&node=pop(); error: lvalue required as left operand of assignment

if (node->element >x){

printf("node->element >x");
if (node->left!=NULL) push(&(node)->left);
else flag=1;

}else{

printf("node->element <x");
if (node->right!=NULL) push(&(node)->right);
else flag=1;

}

}while (flag==0);

if (node->element > x) node->left=newNode(x);
else node->right=newNode(x);
}

int main() {


Tree t=newTree();
addIt(5,&t);

}

MItaly
05-03-2009, 22:44
Be', l'errore che dici deriva dall'& che ci hai messo davanti; se non lo metti non si dovrebbe verificare.

RoxLover
05-03-2009, 22:51
togliendolo mi dice
warning: assignment from incompatible pointer type
sempre alla stessa linea...

KrOW
05-03-2009, 23:07
Ciao . . . Hai provato


node = *(pop());

???

YuYevon
06-03-2009, 08:45
Originariamente inviato da RoxLover
togliendolo mi dice
warning: assignment from incompatible pointer type
sempre alla stessa linea...

Non potrebbe mai funzionare quell'assegnazione perché nella function in cui si verifica l'errore "node" è un puntatore alla struttura "Node", mentre pop() restituisce

p1 + 1

ma la dichiarazione di p1 (che non capisco perché la fai globale) è

Tree *p1;

dove Tree (secondo la typedef che hai scritto) è già un tipo "puntatore alla struttura Node", quindi dichiarando p1 come puntatore ad un dato di tipo Tree, stai dicendo che p1 è un "puntatore a puntatore alla struttua Node", e quindi c'è un incongruenza tra i tipi del valore di ritorno di pop() e della variabile a cui lo vuoi assegnare (node).

Prova a fare semplicemente questa dichiarazione a posto dell'ultima

Node *p1;

oppure (dal momento che hai definito Tree)

Tree p1;

ovviamente fai attenzione che anche "tos" e "stack" sono dichiarati come puntatori a puntatori... e non so se questo può darti problemi perché non ho letto ancora tutto il codice.

RoxLover
06-03-2009, 12:02
Ciao . . . Hai provato codice: node = *(pop()); ???

Grande KrOW sembra che così funzioni!Ora lo provo un pò però perchè YuYevon ha ragione ci dev'essere qualcosa che non va però per ora inserisce senza problemi..in scioltezza azzarderei!Grazie a tt dell'aiuto vi faccio sapere!

YuYevon
06-03-2009, 12:08
Infatti la soluzione di KrOW consiste nel dereferenziare il valore restituito da pop() (che è appunto un puntatore a puntatore a Node) che a quel punto diviene un semplice puntatore a Node, e quindi compatibile con il dato node che all'interno della funzione è proprio anch'esso un puntatore a Node.

(sembra uno scioglilingua)

Loading