Aiuto : Implementazione Dizionario in C

[deimos88]

Salve a tutti, dovrei implementare un dizionario in C, con le tre operazioni di inserimento, cancellazione e ricerca.
Ho provato a farlo da solo ma credo h ci siano un po' di errori e siccome non so dove mettere le mani confido in un vostro aiuto!!!
Vi ringrazio anticipatamente e vi allego il mio codice con gli errori inlclusi...

/*
* Dizionario realizzato mediante struttura circolare doppiamente collegata.
* 
*       classe StrutturaCollegata implementa Dizionario:
*        dati:                                                                  S(n) = @(n)
*             una collezione di n record contenenti ciascuno una quadrupla
*             (prev, elem, chiave, next), dove prev e next sono puntatori
*             al precedente e successivo record della collezione.
*             Manteniamo inoltre un puntatore list che contiene l'indirizzo
*             di un record se la collezione non è vuota e null altrimenti.
*        operazioni:
*             insert(elem e, chiave k)                                          T(n)=O(1)
*                         viene creato un record p con elemento e e chiave k.
*                         Se list=null, si effettua p->next=p, p->prev=p e
*                         list=p . Altrimenti si collega il record p tra
*                         list e list->next effettuando p->next=list->next,
*                         list->next->prev=p, p->prev=list e list->next=p.
*             delete(chiave k)                                                  T(n)=O(n)
*                         si trova il record P con chiave k come nella
*                         search; poi si effettua p->prev->next=p->next e
*                         p->next->prev=p->prev; infine viene distrutto
*                         il record p.
*             search(chiave k)-> elem                                           T(n)=O(n)
*                         se list=null si restituisce null. Altrimenti si
*                         scandisce la struttura saltando di record in
*                         record con p=p->next fino a quando non diventa
*                         p=list, verificando se qualche p ha chiave k.
*                         In caso positivo si restituisce l'elemento
*                         trovato e null altrimenti.
*/

#include <stdio.h>
typedef char* STRINGA;
typedef struct dato {
        struct dato* prec;
        int elemento;
        STRINGA chiave;
        struct dato* succ;
} DATO;

typedef struct dizionario {
        DATO* list;
        inserisci(int el, STRINGA ch);
        cancella(STRINGA ch);
        cerca(STRINGA ch);
} DIZIONARIO;


void creadiz(DIZIONARIO diz)
{
     diz = malloc(sizeof(DIZIONARIO));
     diz.list = NULL;
}
void inserisci(int el, STRINGA ch)
{
     DATO p;
     p = malloc(sizeof(DATO));
     
     p.elemento = el;
     p.chiave = ch;
     
     if (list == NULL) {
              p.prec = p;
              p.succ = p;
     } else {
            p.succ = list.succ;
            list.succ.prec = p;
            p.prec = list;
            list.next = p;
     }
}

void cancella(STRINGA ch)
{
     if (list == NULL) {
              return NULL;
     } else {
            while ( p != list ) {
                  if( p.chiave == ch ) {
                      p.prec.succ = p.succ;
                      p.succ.prec = p.prec;
                      
                      free(p);
                  } else {
                         p = p.succ;
                  }
            } 
     }
     return 0;
}

void cerca(STRINGA ch)
{
     if (list == NULL) {
              return NULL;
     } else {
            while ( p != list ) {
                  if( p.chiave == ch ) {
                      return p.elemento;
                  } else {
                         p = p.succ;
                  }
            } 
     }
     
     return NULL;
}

[oregon]

Di quali errori parli?

[Scara95]

Ho commentato il codice spiegando gli errori e correggendolo.
Ci sono ancora alcuni errori logici, ho scritto dove sono.

Edit: al momento non libera tutta la memoria. E' un errore anche questo.

/*
* Dizionario realizzato mediante struttura circolare doppiamente collegata.
* 
*       classe StrutturaCollegata implementa Dizionario:
*        dati:                                                                  S(n) = @(n)
*             una collezione di n record contenenti ciascuno una quadrupla
*             (prev, elem, chiave, next), dove prev e next sono puntatori
*             al precedente e successivo record della collezione.
*             Manteniamo inoltre un puntatore list che contiene l'indirizzo
*             di un record se la collezione non è vuota e null altrimenti.
*        operazioni:
*             insert(elem e, chiave k)                                          T(n)=O(1)
*                         viene creato un record p con elemento e e chiave k.
*                         Se list=null, si effettua p->next=p, p->prev=p e
*                         list=p . Altrimenti si collega il record p tra
*                         list e list->next effettuando p->next=list->next,
*                         list->next->prev=p, p->prev=list e list->next=p.
*             delete(chiave k)                                                  T(n)=O(n)
*                         si trova il record P con chiave k come nella
*                         search; poi si effettua p->prev->next=p->next e
*                         p->next->prev=p->prev; infine viene distrutto
*                         il record p.
*             search(chiave k)-> elem                                           T(n)=O(n)
*                         se list=null si restituisce null. Altrimenti si
*                         scandisce la struttura saltando di record in
*                         record con p=p->next fino a quando non diventa
*                         p=list, verificando se qualche p ha chiave k.
*                         In caso positivo si restituisce l'elemento
*                         trovato e null altrimenti.
*/

/*stdio non ti è necessaria se non usi funzioni di IO*/
#include <stdio.h>

/*Usi malloc, strcmp e strcpy, queste sono necessarie*/
#include <string.h>
#include <stdlib.h>

/*Devi sempre allocare spazio per i caratteri.
  Io qui ho supposto che una chiave sia lunga al massimo 50 caratteri,
  se vuoi puoi ridurli o aumentarli o utilizzare l'allocazione dinamica*/
typedef char STRINGA[50];

typedef struct dato {
        struct dato* prec;
        int elemento;
        STRINGA chiave;
        struct dato* succ;
} DATO;

/*Stiamo lavorando in C, non esistono i metodi*/
typedef DATO* DIZIONARIO; 

void creadiz(DIZIONARIO *diz)
{
     *diz = NULL;
}

void inserisci(DIZIONARIO *d, int el, STRINGA ch)
{
     /*ti serve un puntatore, non la struttura*/
     DATO *p;
     p = malloc(sizeof(DATO));
     
     p->elemento = el;
    /*le strinche si copiano con strcpy in C,
      studia da un libro il perché, troppo lungo*/
     strcpy(p->chiave, ch);
     
     if ((*d) == NULL) {
              p->prec = p;
              p->succ = p;
              (*d) = p;
     } else {
            p->succ = (*d)->succ;
            (*d)->succ->prec = p;
            p->prec = (*d);
            (*d)->succ = p;
     }
}

/*la logica è scorretta se il dizionario contiene solo 1 elemento
  o se cancella il primo elemento inserito*/
int cancella(DIZIONARIO* d, STRINGA ch)
{
     /*devi dichiarare che cos'è p*/
     DATO *p = *d;
     /*Non puoi ritornare NULL perché di tipo int.
       Potresti ritornare (int)NULL ma questo è equivalente a 0.
       In ogni caso una cancellazione va sempre a buon fine,
       percui non ti servirebbe un valore di ritorno*/
     if (p == NULL) {
              return 0;
     } else {
            /*do {} while(); altrimenti viene subito interrotto*/
            do {
                  /*le strinche si comparano con strcmp in C,
                    studia da un libro il perché, troppo lungo*/
                  if( strcmp(p->chiave, ch) == 0 ) {
                      p->prec->succ = p->succ;
                      p->succ->prec = p->prec;                      
                      free(p);
                      return 1;
                  } else {
                         p = p->succ;
                  }
            } while ( p != (*d) );
     }
     return 0;
}

/*il ritornare uno 0 non è corretto se elemento può valere 0*/
int cerca(DIZIONARIO* d, STRINGA ch)
{
     /*devi dichiarare che cos'è p*/
     DATO *p = *d;
     /*Non puoi ritornare NULL perché di tipo int.
       Potresti ritornare (int)NULL ma questo è equivalente a 0.*/ 
     if (p == NULL) {
              return 0;
     } else {
            /*do {} while(); altrimenti viene subito interrotto*/
            do {
                  /*le strinche si comparano con strcmp in C,
                    studia da un libro il perché, troppo lungo*/
                  if( strcmp(p->chiave, ch) == 0 ) {
                      return p->elemento;
                  } else {
                         p = p->succ;
                  }
            } while ( p != (*d) );
     }
     
     return 0;
}

/* test main. Non presenta i casi in cui cancella è sbagliato. */
int main(void) {
    DIZIONARIO d;
    creadiz(&d);
    printf("pere: %d\n", cerca(&d, "pere")); 
    inserisci(&d, 5, "mele");
    inserisci(&d, 3, "pere");
    printf("pere: %d\n", cerca(&d, "pere"));
    cancella(&d, "pera");
    printf("pere: %d\n", cerca(&d, "pere"));
    cancella(&d, "pere");
    printf("pere: %d\n", cerca(&d, "pere"));
    return 0;
}

[deimos88]

Innanzi tutto grazie mille per la risposta ...
Visto che mi hai praticamente corretto tutto volevo chiederti alcune delucidazioni se non ti dispiace.. anche per capire meglio tutto!
A parte le inclusioni (ok stdlib, string mi hai illuminato ero convinto si potessero copiare le stringhe tranquillamente, ri-grazie)
coomunque ricapitolando:

1) Ho visto che mi hai corretto la definizione di STRINGA ... ma se io uso

typedefchar * STRINGA;

non dovrebbe in automatico creare un array di caratteri della lunghezza della stringa che di volta in volta vado a passare?

2) Hai ragione non ci avevo pensato che idiota. Niente metodi in C!!! Quindi mi tocca passare ogni volta l'elemento su cui operare alle funzioni... e ovviamente trasformare tutto in puntatori (fin qui ci sono)
Ma così facendo dove lo metto il puntatore "list" che dovrebbe puntare al primo record se esistente o a null altrimenti..

3) Perchè la logica è scorretta se vi è solo un elemento? o se si cancella il primo elemento inserito? (sempre per via della sparizione del puntatore "list" o non c'entra? )

4) ok i ritorni li sistemavo dopo grazie comunque!

5) Un ultima domanda, se all'interno delle funzioni invece di creare un altro "Dato *p" potrei utilizzare direttamente il "*d" che passo come argomento alla funzione o questo andrebbe a creare casini???

[Scara95]

1) Ho visto che mi hai corretto la definizione di STRINGA ... ma se io uso

typedefchar * STRINGA;

non dovrebbe in automatico creare un array di caratteri della lunghezza della stringa che di volta in volta vado a passare?

Forse intendi

typedef char *STRINGA;

In ogni caso no: char * è solo un puntatore a carattere che contiene un indirizzo di memoria, questa memoria devi allocarla tu. Il metodo più semplice è usare un array al posto di un puntatore, il metodo più difficile è quello di aggiungere un po' di funzioni che ti gestiscano la memoria e allacorla dinamicamente.

2) Hai ragione non ci avevo pensato che idiota. Niente metodi in C!!! Quindi mi tocca passare ogni volta l'elemento su cui operare alle funzioni... e ovviamente trasformare tutto in puntatori (fin qui ci sono)
Ma così facendo dove lo metto il puntatore "list" che dovrebbe puntare al primo record se esistente o a null altrimenti..

Puoi creare una struttura e che non è altro la parte di non-metodi che utilizzeresti in un linguaggio ad oggetti, tuttavia nel tuo codice hai un solo elemento per cui il creare una struttura con un solo elemento è (per dire) un surplus, quindi ti basta un puntatore all'elemento.

3) Perchè la logica è scorretta se vi è solo un elemento? o se si cancella il primo elemento inserito? (sempre per via della sparizione del puntatore "list" o non c'entra? )

Perché l'elemento della lista da cui tu accedi agli altri è sempre il primo che hai inserito, quindi se cancelli il primo elemento inserito non sarai più in grado di accedere agli altri.
Perché se la lista ha un solo elemento e lo cancelli la "testa" della lista non sarà impostata a NULL.

4) ok i ritorni li sistemavo dopo grazie comunque!

Ti avrebbero dato errore o warning in compilazione.

5) Un ultima domanda, se all'interno delle funzioni invece di creare un altro "Dato *p" potrei utilizzare direttamente il "*d" che passo come argomento alla funzione o questo andrebbe a creare casini???

Sì e no, cerca di capire da solo il perché

[deimos88]

1) Sisi intendevo quello, non è la prima volta che utilizzo questa definizione di stringa e non ho mai avuto problemi con l'allocazione, mi fa tutto in automatico..

2) Sisi infatti non riuscivo a capire come creare il dizionario, cioè mi sembrava inutile un solo elemento.. ma in questo modo in pratica ho un doppio puntatore a un elemento dato.. giusto?

4) sisi lo so, ma avevo altri problemi piu gravi ahahahahha

3/5) Si io accedo sempre dal primo elemento inserito, ma in teoria quando cancello un elemento (se non è il primo non ho problemi) se è il primo o l'unico dovrei aggiornare il puntatore dal quale accedo (il famoso "list" che adesso è sparito ed è diventato *p) ... quindi se nella funzione cancella io aggiorno il puntatore dal quale accedo dovrebbe risolversi il problema... ma qui si ripone il problema dell'usare direttamente l'argomento che passo alla funzione e non un altro puntatore!)
Sto entrando in un tunnel di confusione dal quale prevedo non usciro facilmente... :S

Comunque ti allego il codice rivisto grazie alle tue correzioni.. (ho lasciato invariata la definizione di stringa.. volevo vedere se dava problemi ma come puoi vedere va bene lo stesso)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef char * STRINGA;




typedef struct dato {
        struct dato* prec;
        int elemento;
        STRINGA chiave;
        struct dato* succ;
} DATO;




typedef DATO * DIZIONARIO;




void creadiz(DIZIONARIO *diz)
{
     *diz = NULL;
}




void inserisci(DIZIONARIO *d, int el, STRINGA ch)
{
     DATO *p;
     p = malloc(sizeof(DATO));
     
     p->elemento = el;
     p->chiave = ch;
     
     if ( (*d) == NULL) {
              p->prec = p;
              p->succ = p;
              (*d) = p;
     } else {
            p->succ = (*d)->succ;
            (*d)->succ->prec = p;
            p->prec = (*d);
            (*d)->succ = p;
     }
}




int cancella(DIZIONARIO *d, STRINGA ch)
{
     DATO *p = *d;
     
     if (p == NULL) {
              return -1;
     } else {
            do {
                if( strcmp(p->chiave, ch) == 0 ) {
                    p->prec->succ = p->succ;
                    p->succ->prec = p->prec;                      
                    free(p);
                    return -10;
                } else {
                       p = p->succ;
                }
            } while ( p != (*d) );
     }
     
     return -1;
}


int cerca(DIZIONARIO *d, STRINGA ch)
{
     DATO *p = *d;
     
     if (p == NULL) {
           return -1;
     } else {
            do {
                if( strcmp(p->chiave, ch) == 0 ) {
                    return p->elemento;
                } else {
                       p = p->succ;
                }
            } while ( p != (*d) );
     }
     
     return -1;
}

e del main tanto per XD

int main(){
    
    DIZIONARIO d;
    
    creadiz(&d);
    
    printf("Ciao, come stai?\n");
    
    inserisci(&d, 1, "Ciao");
    
    inserisci(&d, 2, "come");
    
    inserisci(&d, 3, "stai");
    
    printf("La parola \"Ciao\" si trova nella posizione: %d\n", cerca(&d, "Ciao"));
    printf("La parola \"come\" si trova nella posizione: %d\n", cerca(&d, "come"));
    printf("La parola \"stai\" si trova nella posizione: %d\n", cerca(&d, "stai"));
    printf("La parola \"tutto\" si trova nella posizione: %d\n", cerca(&d, "tutto"));
    printf("La parola \"bene\" si trova nella posizione: %d\n", cerca(&d, "bene"));
    printf("La parola \"grazie\" si trova nella posizione: %d\n", cerca(&d, "grazie"));
    
    printf("Ciao, tutto bene grazie.\n");
    
    cancella(&d, "come");
    inserisci(&d, 4, "tutto");
    
    cancella(&d, "stai");
    inserisci(&d, 5, "bene");
    
    inserisci(&d, 6, "grazie");
    
    printf("La parola \"Ciao\" si trova nella posizione: %d\n", cerca(&d, "Ciao"));
    printf("La parola \"come\" si trova nella posizione: %d\n", cerca(&d, "come"));
    printf("La parola \"stai\" si trova nella posizione: %d\n", cerca(&d, "stai"));
    printf("La parola \"tutto\" si trova nella posizione: %d\n", cerca(&d, "tutto"));
    printf("La parola \"bene\" si trova nella posizione: %d\n", cerca(&d, "bene"));
    printf("La parola \"grazie\" si trova nella posizione: %d\n", cerca(&d, "grazie"));


    system("pause");
    return 0;
}

[Scara95]

1) Sisi intendevo quello, non è la prima volta che utilizzo questa definizione di stringa e non ho mai avuto problemi con l'allocazione, mi fa tutto in automatico..

E' undefined behavior, il fatto che funzioni è un puro caso.

2) Sisi infatti non riuscivo a capire come creare il dizionario, cioè mi sembrava inutile un solo elemento.. ma in questo modo in pratica ho un doppio puntatore a un elemento dato.. giusto?

E' diverso avere un puntatore ad un oggetto e un puntatore ad un puntatore ad un oggetto.

4) sisi lo so, ma avevo altri problemi piu gravi ahahahahha

Si parte sempre da quello che si può correggere e si sa come correggere

3/5) Si io accedo sempre dal primo elemento inserito, ma in teoria quando cancello un elemento (se non è il primo non ho problemi) se è il primo o l'unico dovrei aggiornare il puntatore dal quale accedo (il famoso "list" che adesso è sparito ed è diventato *p) ... quindi se nella funzione cancella io aggiorno il puntatore dal quale accedo dovrebbe risolversi il problema... ma qui si ripone il problema dell'usare direttamente l'argomento che passo alla funzione e non un altro puntatore!)

A dire il vero list è diventato (*d), p è rimasto p (concettualmente), ha solo cambiato tipo.
Il Sì e No voleva dire: si puoi farlo, ma devi stare attento alle modifiche che apporti nelle variabili di main e comunque nel tuo caso non potresti farlo perché (*d) ti serve per tenere traccia della testa della lista circolare.
Sì ti basta cambiare il valore di (*d).

Prova a correggere cancella alla luce di quello che ho detto e quello che hai capito da te.

[deimos88]

D'accordo, grazie mille per tutto.. pomeriggio provo a sistemare tutto e ti faccio sapere! Adesso vado a magnare ahahahah buon pranzoo