Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Implementare BST in C
Forum - C/C++ - Implementare BST in C

Avatar
swet (Normal User)
Pro


Messaggi: 128
Iscritto: 01/01/2009

Segnala al moderatore
Postato alle 17:58
Sabato, 11/04/2015
Salve ragazzi, sto tentando di implementare un Binary search tree con una struct ma sto avendo problemi nell' implementare le primitive.

Il compilatore è minGW per windows .

di seguito il codice

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include<stdlib.h>
  3. struct nodo{
  4. int dato; // dato
  5. struct nodo *DX; // sottoalbero di dx
  6. struct nodo *SX;// sottoalbero di SX
  7.  
  8. } nodo;
  9.  
  10. typedef struct nodo* tree; // definisco l' albero
  11.  
  12. //prototipi delle funzioni
  13. tree alberovouto();
  14. tree costruiscialbero(int key, tree SX, tree DX);
  15.  
  16. int *vettore,dimensione ;
  17.  
  18. tree alberovouto(){
  19. //costruisce un albero vuoto)
  20.  
  21.  
  22. return NULL ;
  23. }
  24. tree costruiscialbero(int key, tree sx, tree dx){
  25.  
  26. tree radice;
  27.  
  28. // devo allocare dinamicamente la memmoria
  29. radice = malloc(sizeof(nodo));
  30. if (radice!=NULL){
  31. radice->dato=key;
  32. radice->DX=dx;
  33. radice->SX=sx;
  34.  
  35. return (radice);
  36. }
  37. printf("Non posso allocare la memoria\n");
  38. }
  39.  
  40.  
  41.  
  42. int main (void)
  43. {
  44.  
  45. printf("Benvenuto nel programma\n");
  46.  
  47. tree t1;
  48. t1=costruiscialbero(5,alberovuoto(),alberovuoto());
  49.  // metto il valore 5 nel mio albero vuoto
  50.  
  51.  
  52.  
  53.  
  54. }



il programma non viene compilato segnalando diversi warning sull' incopatibilità dei dati ( i cui motivi non so spiegarmeli, in quanto teoria , non vi sono incoerenze), e un problema di referenziazione di una funzione.
di seguito trovate l' output prodotto da minGW

Codice sorgente - presumibilmente Delphi

  1. C:\test>gcc main.c
  2. main.c: In function 'main':
  3. main.c:50:1: warning: passing argument 2 of 'costruiscialbero' makes pointer fro
  4. m integer without a cast [enabled by default]
  5.  t1=(tree*)costruiscialbero(5,alberovuoto(),alberovuoto());
  6.  ^
  7. main.c:26:6: note: expected 'tree' but argument is of type 'int'
  8.  tree costruiscialbero(int key, tree sx, tree dx){
  9.       ^
  10. main.c:50:1: warning: passing argument 3 of 'costruiscialbero' makes pointer fro
  11. m integer without a cast [enabled by default]
  12.  t1=(tree*)costruiscialbero(5,alberovuoto(),alberovuoto());
  13.  ^
  14. main.c:26:6: note: expected 'tree' but argument is of type 'int'
  15.  tree costruiscialbero(int key, tree sx, tree dx){
  16.       ^
  17. main.c:50:3: warning: assignment from incompatible pointer type [enabled by defa
  18. ult]
  19.  t1=(tree*)costruiscialbero(5,alberovuoto(),alberovuoto());
  20.    ^
  21. C:\Users\Davide\AppData\Local\Temp\ccwBnh7w.o:main.c:(.text+0x6e): undefined ref
  22. erence to `alberovuoto'
  23. C:\Users\Davide\AppData\Local\Temp\ccwBnh7w.o:main.c:(.text+0x75): undefined ref
  24. erence to `alberovuoto'
  25. c:/mingw/bin/../lib/gcc/mingw32/4.8.1/../../../../mingw32/bin/ld.exe: C:\Users\D
  26. avide\AppData\Local\Temp\ccwBnh7w.o: bad reloc address 0x20 in section `.eh_fram
  27. e'
  28. c:/mingw/bin/../lib/gcc/mingw32/4.8.1/../../../../mingw32/bin/ld.exe: final link
  29.  failed: Invalid operation
  30. collect2.exe: error: ld returned 1 exit status



Sapete darmi qualche indicazione


PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6116
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 18:27
Sabato, 11/04/2015
Codice sorgente - presumibilmente C/C++

  1. tree alberovouto(){
  2. //costruisce un albero vuoto)
  3.  
  4.  
  5. return NULL ;
  6. }



Questo non costruisce un albero vuoto, ritorna semplicemente 0 (NULL = 0).

Codice sorgente - presumibilmente C/C++

  1. tree alberovouto(){
  2. //costruisce un albero vuoto)
  3.  
  4.  
  5. return (tree)malloc(sizeof(nodo));
  6. }



Nota inoltre che non hai bisogno di struct per implementare un BST. Basta usare un array (molto più semplice, imo).

http://en.m.wikipedia.org/wiki/Binary_tree#Arrays


Seguimi su Twitter: http://www.twitter.com/pierotofy

Fai quello che ti piace, e fallo bene.
PM Quote
Avatar
swet (Normal User)
Pro


Messaggi: 128
Iscritto: 01/01/2009

Segnala al moderatore
Postato alle 12:39
Domenica, 12/04/2015
Hai ragione, avevo scelto la strada più difficile

Seguendo il tuo consiglio , sto cercando di implementarlo attraverso gli array:

Codice sorgente - presumibilmente C++

  1. // questo programma implementa il BST con array        
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. int inserimento(int T[],int k);
  6. int INORDER(int T[]);
  7.  
  8. void main (void){
  9.         int i=0;
  10.         int key=0;
  11. printf("Benvenuto nel programma\n");
  12. // riempio il vettore
  13. int vettore[18];
  14.  
  15. printf("Il tuo vettore e' cosi' riempito \n");
  16. for (i=0;i<18;i++){
  17.         //inizializzo il vettore
  18.         vettore[i]=0;
  19.         printf("%d",vettore[i]);
  20.        
  21. }
  22. // inserimento dei valori
  23.     printf("\nInserisci un valore radice\n");
  24.         scanf("%d",&key);
  25.         inserimento(vettore,key);
  26.         printf("\nValore radice inserito \n");
  27.        
  28.         for (i=0;i<8;i++){
  29.                 printf("\nInserisci ora un valore\n");
  30.         scanf("%d",&key);
  31.         inserimento(vettore,key);
  32.         }
  33.         printf("\nVettore pieno\n");
  34.         printf("\nInorder\n");
  35.         INORDER(vettore);
  36.  
  37. }
  38. int inserimento(int T[],int k){
  39.         printf("\nKey = %d ",k);
  40.         int y;
  41.         int x=T[0]; // valore radice
  42.         y=0;
  43.        
  44.         //cerco la posizione
  45. while(x!=0){
  46.        
  47.         if ( k< x){
  48.                         y=2*y+1;
  49.                 printf("\nEntrato a sx \n");
  50.         }
  51.                 if (k>x){
  52.                         y=2*y+2;
  53.                 printf("Entrato a dx \n");
  54.                 }
  55.                 x=T[y];
  56.                
  57.                
  58. }
  59. printf("\n X = %d ",x);
  60.  
  61.         if(x==0){ //nodo vuoto
  62.         printf("\n Y = %d ",y);
  63.                 T[y]=k;
  64.                 printf("\n T[y] = %d ",T[y]);
  65.                 return 1;
  66.         }
  67.         return 1;
  68.        
  69.        
  70. }
  71.  
  72. int INORDER(int T[]){
  73.         y=0;
  74.        
  75.         while(T[y]!=0){
  76.                
  77.                 //RAMO SX
  78.                 INORDER(T[2*y+1]);
  79.        
  80.                 printf("%d",T[y]);
  81.         // RAMO DX
  82.         INORDER(T[2*y+2]);
  83.        
  84.        
  85.         }
  86.        
  87. }


Ho problemi ad implementare la visita INORDER, programma va in OVERFLOW(suppongo), l' inserimento funziona bene .

Consigli?

Ultima modifica effettuata da swet il 12/04/2015 alle 12:51


PM Quote
Avatar
XBarboX (Member)
Guru


Messaggi: 945
Iscritto: 31/12/2008

Segnala al moderatore
Postato alle 22:10
Mercoledì, 15/04/2015
Se può tornarti utile qualche mese fa ho dovuto scrivere un ADT per gestire un bst. Penso sia interessante perché in questo esempio viene memorizzato tutto dinamicamente. Risulta più complicato in certi punti mentre in altri, invece, risulta più pratica la gestione della struttura dati. Ti riporto qualche pezzo di codice:

bst.h
Codice sorgente - presumibilmente C++

  1. #include "item.h"
  2.  
  3. typedef struct t_bst *BST;
  4.  
  5. BST bst_init();
  6. void bst_insert_leaf(BST bst, Item i);
  7. int  bst_tree_height(BST bst);
  8. void bst_destroy(BST bst);



bst.c
Codice sorgente - presumibilmente C++

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include "item.h"
  4. #include "bst.h"
  5.  
  6. typedef struct bst_node *link;
  7.  
  8. struct bst_node{
  9.         Item item;              //node item
  10.         link left;              //left child
  11.         link right;             //right child
  12.         int n;                  //size of sub-tree
  13. };
  14.  
  15. struct t_bst{
  16.         link root;
  17. };
  18.  
  19. BST bst_init()
  20. {
  21.         BST bst = malloc(sizeof(*bst));
  22.         bst->root = NULL;
  23.         return bst;
  24. }
  25.  
  26. link new_node(Item i, link l, link r, int n)
  27. {
  28.         link new = malloc(sizeof(*new));
  29.         new->item = i;
  30.         new->left = l;
  31.         new->right = r;
  32.         new->n = n;
  33.         return new;
  34. }
  35.  
  36. void bst_insert_leaf(BST bst, Item i)
  37. {
  38.         //if empty bst
  39.         if(bst->root == NULL)
  40.         {
  41.                 bst->root = new_node(i, NULL, NULL, 1);
  42.                 return;
  43.         }
  44.  
  45.         //if not empty bst
  46.         link p = bst->root;     //father
  47.         link x = p;             //actual pointer
  48.         while(x != NULL)
  49.         {
  50.                 p = x;
  51.                 x->n++;
  52.                 if(item_compare(i, x->item) < 0)
  53.                         x = x->left;
  54.                 else
  55.                         x = x->right;
  56.         }
  57.         x = new_node(i, NULL, NULL, 1);
  58.         if(item_compare(i, p->item) < 0)
  59.                 p->left = x;
  60.         else
  61.                 p->right = x;
  62. }
  63.  
  64. void pre_order(link p, FILE *fp)
  65. {
  66.         item_print(p->item, fp);
  67.         if(p->left != NULL)
  68.                 pre_order(p->left, fp);
  69.         if(p->right != NULL)
  70.                 pre_order(p->right, fp);
  71. }
  72.  
  73. void in_order(link p, FILE *fp)
  74. {
  75.         if(p->left != NULL)
  76.                 in_order(p->left, fp);
  77.         item_print(p->item, fp);
  78.         if(p->right != NULL)
  79.                 in_order(p->right, fp);
  80. }
  81.  
  82. void post_order(link p, FILE *fp)
  83. {
  84.         if(p->left != NULL)
  85.                 post_order(p->left, fp);
  86.         if(p->right != NULL)
  87.                 post_order(p->right, fp);
  88.         item_print(p->item, fp);
  89. }
  90.  
  91. void destroy(link p)
  92. {
  93.         if(p->left != NULL)
  94.                 destroy(p->left);
  95.         if(p->right != NULL)
  96.                 destroy(p->right);
  97.         item_free(p->item);
  98. }
  99.  
  100. void bst_destroy(BST bst)
  101. {
  102.         if(bst->root != NULL)
  103.                 destroy(bst->root);
  104.         free(bst);
  105. }



Se ti serve anche qualche altro pezzo di codice, come ad esempio l'inserimento in radice, dimmelo che te lo spedisco volentieri.
Come puoi vedere le visite in pre/in/post order sono molto chiare grazie a questa tipo di struttura dati, mentre e` più rognosa la parte di deallocazione e di inserimento.

Spero di essere stato utile :k:


The old lie: Dulce et decorum est pro patria mori
PM Quote
Avatar
swet (Normal User)
Pro


Messaggi: 128
Iscritto: 01/01/2009

Segnala al moderatore
Postato alle 18:30
Mercoledì, 22/04/2015
Grazie mille, ho optato per gli array perché purtroppo, per quanto più elegante fosse la soluzione con le struct , purtroppo in sede di esame, ho poco tempo per scrivere il programma.

Con gli array sembra funzionare tutto molto bene , appena avrò del tempo proverò sicuramente ad implementare la tua soluzione XBarboX

Grazie mille ancora.


PM Quote