PDA

Visualizza la versione completa : [C] Problema malloc?


dicaraf
21-08-2014, 18:12
Ciao a tutti, sto svolgendo un progetto che consiste in questo: dato un array di interi, non contenente elementi ripetuti, costruire un albero binario di ricerca bilanciato le cui chiavi siano elementi dell'array.
Ora la mia idea è stata quella di ordinare il vettore, prendere l'elemento mediano e metterlo nella radice dell'albero per poi agire ricorsivamente. Il codice sembra però non funzionare correttamente per problemi di allocazione dei nodi, almeno così è secondo me. Qualcuno riesce ad aiutarmi?
Grazie.
PS nell'originale la lista è letta da file ma qui ho inserito un esempio specifico.


#include <stdio.h>#include <stdlib.h>
typedef struct NODE {
int key;
struct NODE *left;
struct NODE *right;
struct NODE *up;
} NODE;


int pivot(int *A,int p,int r){
return p+rand()%(r-p+1);
}

void swap(int *A,int i, int j){
int tmp;
tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}

int partition(int *A,int p,int q,int r){
int i=p, j=r,pivot;
swap(A,q,p);
pivot=A[p];
while(i<j){
while(j>p && pivot<=A[j]){
j--;
}
while(i<r && pivot>A[i]){
i++;
}
if(i<j){
swap(A,i,j);
}
}
swap(A,p,j);
return j;
}


void quicksort(int *A,int p,int r){
if (p<r){
int q=pivot(A,p,r);
int i=partition(A,p,q,r);
quicksort(A,p,i);
quicksort(A,i+1,r);
}
}



NODE *NodeAlloc(int key) {
NODE *node = (NODE *)malloc(sizeof(NODE));
node ->key = key;
node ->left = NULL;
node->right = NULL;
node->up = NULL;
return node;
}


NODE* Alb(int* list, int j, int u){
int m;
NODE *nodo;
if (j<=u){
m = ((j + u) / 2);
nodo = NodeAlloc(list[m]);
nodo->left = Alb(list, j, m - 1);
nodo->right = Alb(list, m + 1, u);
return nodo;
}
else
return NULL;


}
NODE *BalancedBST(int *list, int n) {
NODE *T = NULL;
int k;


k = n - 1;
quicksort(list, 0, k);


T = Alb(list, 1, n);


return T;
}


void PreOrderPrint(NODE *T) {
if(T!=NULL){
printf("%d ",T->key);
PreOrderPrint(T->left);
PreOrderPrint(T->right);
}
}


void DeleteBST(NODE *T) {
if(T!=NULL){
DeleteBST(T->left);
DeleteBST(T->right);
free(T);
}
}


int main() {
int list[]={8, 5, 18, 15, 17, 9, 7, 16},n=8;
NODE *T;



T = BalancedBST(list,n);
PreOrderPrint(T);
DeleteBST(T);
return 0;
}

Loading