codice:
/*
* 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;
}
Rispondi quotando