Programma non funzionante

di
pdor
il
2 risposte
P
pdor
Pochi posts
Iscritto da
giu, 2019
Messaggi:
3

Programma non funzionante

Ciao a tutti. Vi allego il codice della mia soluzione al seguente problema, purtroppo però il programma NON gira. Sapete dirmi dov'è l'errore?? Grazie

"Dati due alberi binari (non necessariamente uguali) e una chiave k si vuole determinare se la sequenza dei nodi incontrati nei due alberi durante la ricerca della chiave k sia uguale oppure no. Si scriva una funzione in C che verifichi tale proprietà"

Nel mio programma ho scomposto il problema in più sotto-problemi:
1) "visita_abr" e "_visita_abr" che visitano l'albero a partire dalla radice e aggiungono le chiavi nel vettore;
2) "aggiungi" che aggiunge i vari elementi al vettore dinamico;
3) "confronta" che confronta i due vettori
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "array.h"
#include "alberi.h"

void visita_abr(albero_binario_ricerca a, int k, vettore_dinamico* v);
void _visita_abr(nodo_albero_binario_ricerca* r, int k, vettore_dinamico* v);
void aggiungi(int dato, vettore_dinamico* v);
bool confronta(vettore_dinamico v, vettore_dinamico t);

int main()
{
   albero_binario_ricerca a, b;
   vettore_dinamico v, t;
   int chiave;
   
   a = crea_abr();
   b = crea_abr();
   
   inserisci_abr(&a, 20, 2.5);
   inserisci_abr(&a, 13, 2.5);
   inserisci_abr(&a, 24, 2.5);
   inserisci_abr(&a, 8, 2.5);
   inserisci_abr(&a, 16, 2.5);
   inserisci_abr(&a, 30, 2.5);
   inserisci_abr(&a, 9, 2.5);
   inserisci_abr(&a, 14, 2.5);
   
   inserisci_abr(&b, 20, 2.5);
   inserisci_abr(&b, 13, 2.5);
   inserisci_abr(&b, 30, 2.5);
   inserisci_abr(&b, 5, 2.5);
   inserisci_abr(&b, 16, 2.5);
   inserisci_abr(&b, 24, 2.5);
   inserisci_abr(&b, 14, 2.5);
   inserisci_abr(&b, 26, 2.5);
   
   v = crea_vettore_dinamico(9);
   t = crea_vettore_dinamico(9);
   
   printf("Inserire chiave: ");
   scanf ("%d", &chiave);
   
   visita_abr(a, chiave, &v);
   visita_abr(b, chiave, &t);
   
   stampa_vettore_dinamico(v);
   stampa_vettore_dinamico(t);
   
   if (confronta(v, t))
      printf("La proprietà è verificata\n");
   else
      printf("La proprietà NON è verificata\n");
   
   return EXIT_SUCCESS;
}

void visita_abr(albero_binario_ricerca a, int k, vettore_dinamico* v)
{
   _visita_abr(a.radice, k, v);
}

void _visita_abr(nodo_albero_binario_ricerca* r, int k, vettore_dinamico* v)
{
   if (r == NULL) /* caso di base: puntatore a NULL */
      return;
      
   if (k == r->chiave) /* caso di base: la chiave della radice e k coincidono */
   {
      aggiungi(r->chiave, v);
      return;
   }
   
   if (k < r->chiave) /* passo ricorsivo: k è minore della chiave della radice */
   {
      aggiungi(r->chiave, v);
      return _visita_abr(r->sinistro, k, v);
   }
   
   if (k > r->chiave) /* passo ricorsivo: k è minore della chiave della radice */
   {
      aggiungi(r->chiave, v);
      return _visita_abr(r->destro, k, v);
   }
}

void aggiungi(int dato, vettore_dinamico* v)
{
   /* se necessario, ridimensiona il vettore */
   ridimensione_vettore_dinamico(v, v->dimensione + 1);
   
   /* inserisci il contenuto nel vettore */
   v->dati[v->dimensione - 1] = dato;
}

bool confronta(vettore_dinamico v, vettore_dinamico t)
{
   int i;
   
   if (v.dimensione != t.dimensione) /* se le due dimensioni logiche non coincidono */
      return false;

   for (i = 0; i < v.dimensione; i++) /* scandisci entrambe le sequenze elemento per elemento ed esegui i confronti */
   {
      if (v.dati[i] != t.dati[i])
         return false;
   }
   
   return true;
}

2 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Programma non funzionante

    Non hai messo tutto il codice ma GIA' nel codice postato ci sono ERRORI abbastanza gravi.
    Tra l'altro, il codice non ha senso! Ma e' inutile mettersi a dettagliare i singoli punto.
    Praticamente va riscritto tutto!

    Descrivi a parole, ma in modo preciso, o se vuoi in pseudocodice, come dovrebbe funzionare.

    Lo sai che un nodo di un albero, oltre ai link verso i nodi dei figli, potrebbe avere anche un link verso il nodo padre?

    In questo modo, ti semplificheresti la vita?

    PERCHE' in alcune funzioni passi il parametro PER VALORE?

    Che differenza c'e' tra passare un parametro per valore e passare un puntatore?

    Non devi rispondere a me, ovviamente. Io lo so
  • P
    pdor
    Pochi posts
    Iscritto da
    giu, 2019
    Messaggi:
    3

    Re: Programma non funzionante

    Ciao, grazie per la risposta.

    Mi par di capire dal tuo messaggio che, oltre agli errori di sintassi e di semantica, il ragionamento che ho svolto (sia la scomposizione in sottoproblemi che i sottoproblemi stessi) non porti a nessun risultato.....

    Non ho capito il ricorso al puntatore al nodo padre (tra l'altro non contemplato nel materiale del mio corso): se parto dalla radice ed esploro tutti i nodi fino a trovare quello contenente la chiave, mi devo muovere dall'alto verso il basso e quindi considerare, dato un nodo generico, i suo figli e non tornare indietro al padre. O mi sbaglio?

    I passaggi by value errati immagino siano quelli delle chiamate alle funzioni quando passo i puntatori ai "descrittori" delle mia strutture dati (vettore_dinamico). 
    typedef struct _nodo_albero_ricerca
{
   int chiave;
   float dato;
   struct _nodo_albero_ricerca* sinistro;
   struct _nodo_albero_ricerca* destro;
} nodo_albero_binario_ricerca;

typedef struct
{
   int nodi;
   nodo_albero_binario_ricerca* radice;
} albero_binario_ricerca;

typedef struct 
{
   float *dati;
   int dimensione;
   int capacita;
} vettore_dinamico;
Devi accedere o registrarti per scrivere nel forum
2 risposte