Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Lista multipla per simulare un albero! Sto impazzendo!
Forum - C/C++ - Lista multipla per simulare un albero! Sto impazzendo!

Avatar
Ghost_M91W (Ex-Member)
Newbie


Messaggi: 5
Iscritto: 10/05/2011

Segnala al moderatore
Postato alle 17:52
Domenica, 22/05/2011
Ragazzi ho bisogno di aiuto! In pratica ho un esercizio da svolgere, che richiede questo: dato un array di struct in input struct lista {char nome_nodo; int padre} contenenti rispettivamente il nome del nodo e l'indice del nodo padre di quel dato nodo, devo restituire in output una tabella contenente il nome del nodo, il grado (ovvero il numero dei figli) e l'indice dei figli. Tramite array non ci ho messo nulla, ma con le liste dinamiche (richiesto!) ho messo giù qualcosa, e infatti nel mio codice nome e grado vengono aggiornati, ma gli indici dei figli no!

Per farvi capire meglio, la tabella che ho in input è tipo questa:

Nome   Padre
A            -1(-1 indica che è il nodo radice)
B             2
C             0
D             0

Mentre in output devo restituire questa tabella:

Nome   Grado   Figli
A          2         3 4
B          0      
C          1         2
D          0      

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define LEN 4
  4. struct albero{char nome_nodo;
  5.               int grado;
  6.               int padre;
  7.               int indice;
  8.               struct albero *pt_figli;
  9.               struct albero *p_next;
  10.              };
  11. struct lista{char nome_nodo;
  12.              int padre;
  13.             };
  14. struct coda{struct albero *info;
  15.             struct coda *p_next;
  16.            };
  17. void main()
  18. {struct albero *head=calloc(1,sizeof(struct albero)),*punt=head, *radice, *p_figli, *el_da_ins, *p_albero; //puntatori per creare la lista
  19.  struct coda *top, *bottom; struct albero *nodo; //puntatori per la coda per l'accesso all'albero
  20.  struct lista input[]={'A',-1,
  21.                        'B', 2,
  22.                        'C', 0,
  23.                        'D', 0,
  24.                       };
  25.  
  26.  int i;
  27.  //CARICO TUTTO L'ARRAY IN UNA LISTA//
  28.  for(i=0; i<LEN; i++)
  29.         {if(i<LEN-1)
  30.             punt->p_next=calloc(1,sizeof(struct albero)); //evito che mi venga generato un elemento in più
  31.          punt->nome_nodo=input[i].nome_nodo;
  32.          punt->padre=input[i].padre;
  33.          punt->indice=i;
  34.          punt=punt->p_next;
  35.         }
  36.  punt=head;
  37.  while(punt!=NULL)
  38.         {if(punt->padre==-1)
  39.                 {radice=punt;//cerco il nodo radice
  40.                  printf("Radice trovata\n\n");
  41.                  printf("Nome radice: %c\n",radice->nome_nodo);
  42.                 }
  43.          else
  44.                 {el_da_ins=punt;
  45.                  p_albero=head; //scorro la lista per cercare il padre di quel nodo
  46.                  while(p_albero!=NULL && p_albero->indice!=el_da_ins->padre)
  47.                         {p_albero=p_albero->p_next;
  48.                          printf("Cerco...\n");
  49.                         }
  50.                  if(p_albero->indice==el_da_ins->padre)
  51.                         {printf("Trovato! in posizione: %d\n",p_albero->indice);
  52.                          p_figli=p_albero;
  53.                          while(p_figli->pt_figli!=NULL)
  54.                                 {p_figli=p_figli->pt_figli;
  55.                                  printf("Verifica: %c\n",p_figli->nome_nodo);
  56.                                  printf("Cerco primo nodo figlio libero\n");
  57.                                 }
  58.                          p_figli->pt_figli=el_da_ins;
  59.                          printf("Memoria allocata per il primo nodo figlio\n");
  60.                          p_figli=p_figli->pt_figli;
  61.                          printf("Puntatore figli in posizione\n");
  62.                          // p_figli=el_da_ins;
  63.                          printf("Inserisco un nodo:");
  64.                          printf(" %c  ",p_figli->nome_nodo);
  65.                          printf("di indice: %d ",p_figli->indice);
  66.                          printf("al padre: %c \n",p_albero->nome_nodo);
  67.                          p_albero->grado++;
  68.                         }
  69.                  }
  70.         punt=punt->p_next;
  71.        }
  72.  punt=head;
  73.  
  74.  while(punt!=NULL)
  75.         {printf("Nome: %c    ",punt->nome_nodo);
  76.          printf("Grado: %d   ",punt->grado);
  77.          p_figli=punt->pt_figli;
  78.          printf("Figli: ");
  79.          while(p_figli!=NULL)
  80.                 {printf("%c", p_figli->nome_nodo);
  81.                  p_figli=p_figli->pt_figli;
  82.                 }
  83.          printf("\n\n");
  84.          punt=punt->p_next;
  85.         }
  86. }

  

Ripeto: il problema è negli indici dei figli: è come se non scrivessi le informazioni nella lista multipla... secondo me il problema dipende da el_da_ins ma non so come ovviare. Per favore datemi una mano, mi affido a voi.
PS: vi conviene fare copia e incolla perchè purtroppo ho perso l'indentatura

Ultima modifica effettuata da Ghost_M91W il 22/05/2011 alle 19:04
PM