PDA

Visualizza la versione completa : Aiuto : Implementazione Dizionario in C


deimos88
30-12-2013, 12:17
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;
}



:dhò::dhò::dhò::messner::messner::messner:

oregon
30-12-2013, 13:05
Di quali errori parli?

Scara95
30-12-2013, 13:31
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
30-12-2013, 14:06
Innanzi tutto grazie mille per la risposta :D ...
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


typedef char * 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.. :confused:

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
30-12-2013, 14:27
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.. :confused:
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
30-12-2013, 14:54
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 :(:confused:

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
30-12-2013, 15:14
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
30-12-2013, 15:18
D'accordo, grazie mille per tutto.. pomeriggio provo a sistemare tutto e ti faccio sapere! Adesso vado a magnare ahahahah buon pranzoo :)

Loading