Spiegazione sui dizionari

di
Cristian02
il
11 risposte
C
Cristian02
Pochi posts
Iscritto da
ago, 2021
Messaggi:
7

Spiegazione sui dizionari

Buongiorno a tutti, sono uno studente universitario del corso di informatica del primo anno. Sto riscontrando alcuni problemi nell'ultima parte del programma, che riguarda i dizionari in C. A livello logico comprendo il funzionamento, ma a livello pratico ho delle difficoltà e vorrei chiedervi aiuto. Vorrei fare un semplice dizionario: come creare un dizionario vuoto, inserire liste con i valori, aggiornare e inserire una nuova lista all'interno del dizionario, e infine, come posso eliminarla.

//Il mio codice
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
//DIZIONARIO IN C NON è ALTRO UN ARRAY CHE ALL'INTERNO CONTIENE VARIE LISTE

//STRUTTURE
typedef struct {
	int valore;
	struct nodo *succ;
}nodo;

typedef struct{
	nodo **node;
	int dimList; 	//numero di liste
	int n;			//numero di elementi nel dizionario
}dic;

typedef struct{
	char *key;
	float value;
}d_item;

//PROTOTIPO
dic dic_input(int );
void mostraDic(dic );

dic dic_input(int dimList){ 
	dic d;
	d.node=malloc(dimList*sizeof(nodo*));
	d.dimList=dimList;
	d.n=0;
	for (int i=0;i<dimList;i++){
		d.node[i]=NULL;
	}
return d; //restituisco il dizionario appena creato 	
}

void mostraDic(dic d){
	for (int i=0;i<d.dimList;i++){
		printf("%d -\n",i);
	}
}


int main (){
	//Creo un dizionario VUOTO
	dic d;
	//Chiamo la funzione per inizializzare
	d=dic_input(3); //Sto dicendo di creare 3 liste

	mostraDic(d);
return 0;
}
//Il codice del professore:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


struct d_item {
	char *k;
	float v;
};
typedef struct d_item d_item;

struct nodo {
	d_item info;
	struct nodo *succ;
};
typedef struct nodo nodo;

struct dict {
	nodo **a;
	int m; // numero di liste (dimensione di a)
	int n; // numero di elementi nel dizionario
};
typedef struct dict dict;

int h(char*, dict);
dict dict_init(int);
dict dict_update(dict, d_item);
nodo *lista_cerca_k(nodo*, char*);
nodo *lista_in0(nodo*, d_item );
void dict_mostra(dict);
void lista_mostra(nodo*);


int main(int n, char *args[]){
	dict d = dict_init(3);
	int i;
	d_item e;
	
	for (i = 1; i < n; i++){
		e.k = args[i];
		e.v = i;
		d = dict_update(d, e); 
	}
	
	dict_mostra(d);
}


int h(char *x, dict d){
	int out = 0;
	int i = 0;
	
	while( x[i] != '\0'){
		out = x[i]^out;
		i++;
	}
	
	return out % d.m;
}

dict dict_init(int m){
	/*
	 * Ritorna un dizionario vuoto con m liste
	 * */
	dict d;
	int i;
	
	d.a = malloc(m*sizeof(nodo));
	d.m = m;
	d.n = 0;
	for(i = 0; i < m; i++){
		d.a[i] = NULL;
	}
	
	return d;
}

dict dict_update(dict d, d_item e){
/*
 * Se e.k e' nel dizionario ne modifica il valore in e.v.
 * Altrimenti inserisce in d la nuova coppia e
 * 
 * */
	nodo *p; 
	int lis = h(e.k, d);
	
	
	p = lista_cerca_k(d.a[lis], e.k);
	
	if ( p == NULL ) { // la chiave non è nel dizionario
		/*
		 * inseriamo e in d
		 * */
		 d.a[lis] = lista_in0(d.a[lis], e);
		 d.n++;
	} else {
		/*
		 * aggiorno il valore associato a e.k
		 * */
		p->info.v = e.v;
	}
	
	return d;
}


nodo *lista_cerca_k(nodo *x, char *k){
	/*
	 * Ritorna il puntatore al nodo contenente l'item con chiave k, 
	 * oppure NULL se k non e' una chiave del dizionario
	 * */
	nodo *p = x;
	
	while ( p != NULL ){
		if ( strcmp(p->info.k, k) == 0 ) {
			return p;
		}
		p = p->succ;
	}
	
	return NULL;
}


nodo *lista_in0(nodo* x, d_item e){
	nodo *n = malloc(sizeof(nodo));
	
	n->info = e; // un po' delicato, perche'? 
	n->succ = x;
	
	return n;
}

void dict_mostra(dict d){
	int i;
	
	for (i = 0; i < d.m; i++){
		printf("%d - ", i);
		lista_mostra(d.a[i]);
	}
}

void lista_mostra(nodo *x){
	nodo *p = x;
	
	while( p != NULL ){
		printf("(%s, %.2f) ", p->info.k, p->info.v);
		p = p->succ;
	}
	printf("\n");
}

Ho capito come creare un dizionario vuoto, ma non so come procedere con il resto delle operazioni.

11 Risposte

  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21266

    Re: Spiegazione sui dizionari

    Una richiesta troppo generica, non si fanno lezioni complete nel forum. Limitiamoci ad un singolo problema preciso.

  • C
    Cristian02
    Pochi posts
    Iscritto da
    ago, 2021
    Messaggi:
    7

    Re: Spiegazione sui dizionari

    09/02/2024 - oregon ha scritto:

    Una richiesta troppo generica, non si fanno lezioni complete nel forum. Limitiamoci ad un singolo problema preciso.

    Mi scusi se mi sono spiegato male. Il mio problema riguarda il modo in cui posso inserire liste all'interno di un dizionario. So come aggiungere valori a una lista, ma non so come inserire le liste all'interno del dizionario.
    comunque la ringrazio per la sua attenzione :)

  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21266

    Re: Spiegazione sui dizionari

    Qui ci diamo tutti del tu, come in qualsiasi forum.

    Hai provato a impostare la lista e scrivere il codice dell'inserimento?

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Spiegazione sui dizionari

    Da una lettura veloce del topic mi sembra di capire che l'intento sia quello di implementare un array di liste allocato dinamicamente.

    Detto ciò non capisco cosa c'entrano i “dizionari” in questo contesto. Il termine “dizionario” ha un significato specifico che ignoro in ambito informatico? In caso contrario perché non utilizzare una semplice lista?

    In ogni caso se sei in grado di popolare un semplice array di interi allocato dinamicamente, non dovresti avere problemi neanche con un array di liste, l'unica differenza è che gli elementi non sono dei numeri ma le “teste” delle singole liste.

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

    Re: Spiegazione sui dizionari

    @Nippolo
    deve implementare un dizionario di quelli “intelligenti” ;-)

    E' basato sull'utilizzo dell'hash della chiave per trovare la posizione nel vettore delle liste di “overflow” (in Italiano: “lista di trabocco”)
    La lista  di “overflow” serve per gestire le “collisioni” ;-)

    Poi, per fare le cose “fighe”, se una lista di overflow diventa troppo lunga, dovrebbe riallocare il tutto con un vettore delle liste PIU' GRANDE, e riorganizzare tutti gli elementi (coppia <chiave, valore>).

    Diciamo che se non lo sa fare, vuol dire che gli mancano un bel po' di concetti base !
    L'implementazione e' abbastanza “arzigogolata” ;-)

    https://www.sci.unich.it/~meo/didattica/courses/asdI/lucidi/hash.pdf

    Ma sono certo che il docente avra' fornito anche lui della documentazione.

    Come “aiutino”, le operazioni sono:

    1. dict_create() ->D    crea un dizionario con un numero PREDEFINITO di liste di overflo (ad esempio una soltanto)
    2. dict_set(D, chiave, valore) -> true|false   aggiunge una nuova entry <chiave, valore> al dizionario. Se esiste gia' una entry con la stessa chiave, AGGIORNA il valore (notare che ho usato ‘set’ e non ‘insert’ o ‘update’: DUE funzioni in UNA ;-) ) Ritorna true o false se ha inserito o aggiornato 
    3. dict_get(D, chiave, default_value) -> value   ritorna il valore associato a quella chiave. Se non c'e' nessuna entry con quella chiave, ritorna default_value (ci sarebbero altre possibili implementazioni, ma questa e' la piu' semplice e flessibile).
    4. dict_delete(D, chiave) -> true|false  elimina la entry con quella chiave. Se non c'e' nessuna entry con quella chiave, NON FA NULLA! Ritorna true se ha effettivamente cancellato qualcosa, false altrimenti

    .

    Poi ci sarebbereo diverse operazioni di servizio:

    1. dict_clear(D)   VUOTA l'intero dizionario, ma mantiene l'oggetto valido per un successivo riutilizzo
    2. dict_destroy(D)   DISTRUGGE il dizionario e tutte le strutture dati di servizio
    3. dict_reorganize(D, n)   RIORGANIZZA il contenuto del dizionario usando un nuovo vettore di ‘n’ liste di overflow. QUesto serve per ridurre la lunghezza massima delle liste di overflow
    4. dict_maxlen(D) -> int    ritorna la lunghezza massima delle liste di overflow. Serve per sapere quando riorganizzare il dizionario
    5. dict_size(D) -> int     ritorna la lunghezza del vettore delle liste di overflow
    6. dict_count(D) -> int     ritorna il numero totale di entry presenti nel dizionario
    7. dict_keys(D) ->  char**   ritorna un vettore contenente TUTTE le chiavi presenti nel dizionario

    .

    Poi, visto che piace un sacco stampare qualcosa a video ;-)

    1. dict_dump(D)    stampa a video il contenuto del dizionario

    .

    Si puo' notare che certe operazioni possono essere create a partire da altre ;-)

    Come dire: la lista di funzionalita' ipotizzate nel codice, non c'azzeccano minimamente :-(

  • A
    Alexv
    Molto attivo
    Iscritto da
    giu, 2018
    Messaggi:
    632

    Re: Spiegazione sui dizionari

    09/02/2024 - Cristian02 ha scritto:

    Mi scusi se mi sono spiegato male. Il mio problema riguarda il modo in cui posso inserire liste all'interno di un dizionario. So come aggiungere valori a una lista, ma non so come inserire le liste all'interno del dizionario.
    comunque la ringrazio per la sua attenzione :)

    Quindi hai un problema con gli array di puntatori, ovvero con i puntatori doppi?

    nodo* CreaLista(){
 // ...
}

nodo **a //array di puntatori a puntatori a nodo
nodo *p // puntatore a nodo

nodo *testa = a[3]; // Ottengo il puntatore al primo elemento della quarta lista (a partire da 0)

a[4] = testa;
int x = a[4]->valore;

a[3] = NULL; // sposto la lista dalla pozizione a[3] ad a[4]

a[5] = CreaLista();

    Se hai capito come funziona il dizionario, lascia perdere il codice del professore (a parte la funzione di hash) e realizza un pezzo per volta.

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Spiegazione sui dizionari

    09/02/2024 - migliorabile ha scritto:

    @Nippolo
    deve implementare un dizionario di quelli “intelligenti” ;-)

    E' basato sull'utilizzo dell'hash della chiave per trovare la posizione nel vettore delle liste di “overflow” (in Italiano: “lista di trabocco”)
    La lista  di “overflow” serve per gestire le “collisioni” ;-)

    Ipotizzo che per collisione si intenda il caso in cui elementi diversi condividono una stessa chiave e quindi a quella chiave si associa in qualche modo non un singolo elemento, ma una lista di elementi. E' più o meno così?

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

    Re: Spiegazione sui dizionari

    @Nippolo, non passeresti l'esame di ‘algoritmi e strutture dati’ ;-)

    la collisione avviene nel seguente caso:

    siano date 2 chiavi (ad esempio 2 stringhe) DIVERSE ovviamente: k1 e k2.

    Per ogni chiave applichi la funzione hash: hash(k1), hash(k2)

    E' possibile che hash(k1) sia uguale ad hash(k2) ma questo avviene con bassissima probabilita' se il numero delle chiavi e mooooolto piu' piccolo nel numero di bit usato per rappresentare il valore hash, che e' un intero. Supponi di usare interi a 32 o 64 bit. Certo, se usi interi a 8 (256 possibili valori) o 16 bit (65536 possibili valori), la probabilita' di collisione e' decisamente piu' alta (maggiore con 8 bit ovviamente)

    ora devi accedere al vettore delle liste di overflow di lunghezza N. Quello che fai e' accedere agli elementi

    i1=hash(k1) modulo N

    i2=hash(k2) modulo N

    Qui puoi avere una collisione perche N e' molto piccolo. Ad esempio supponi che N sia 1, valore ragionevole per un dizionario vuoto. La collisione e' assicurata al 100%. Con N=2, la collisione e' assicurata al 50%. Quindi perche' non partire con N=1000'? si puo' anche fare, ma se metti nel dizionario un milione di elementi, e' ovvio che avrai delle collisioni: almeno 999000!

    D'altra parte, fino a che ci sono pochi elementi nel dizionario, non serve avere N grande.

    Quindi, poiche' hai una collisione MA le chiavi sono diverse, che fai? Ecco dove entra in gioco la lista di overflow:  ti permette di gestire oggetti con chiavi DIVERSE ma che generano lo STESSO valore per

    hash(k) modulo N

    Dopo un po' le liste di overflow diventano molto lunghe e quindi fai una ricerca sequenziale (lenta). E' a questo punto che riorganizzi il dizionario con il vettore delle liste di overflow di lunghezza 2N. Questo ha come effetto quello di dimezzare, mediamente, la lunghezza delle liste.

    Il caso di due oggetti con la STESSA chiave NON ESISTE: e' lo STESSO oggetto a cui e' stato cambiato il valore!

    La chiave IDENTIFICA UNIVOCAMENTE l'oggetto: stessa chiave implica stesso oggetto!

    Come noti, avevi scritto una cosa ‘quasi giusta' ;-)

    Il concetto e': la funzione hash deve ritornare SEMPRE lo stesso valore se applicata alla STESSA chiave. Il problema delle collisioni lo si ha con

    hash(k) modulo N

    MA il valore di N puo' cambiare (e DEVE cambiare)

    L'altro problema e' come calcolare la funzione hash di una stringa. Ci sono un'infinita' di modi che uno si puo' inventare

    1. usando shift e xor
    2. usando moltiplicazioni per un numero primo e somma

    .

    String.hashCode di Java usa il metodo 2.

    Come dicevo, l'implementazione' abbastanza arzigogolata: ci sono un'infinita' di dettagli da tenere in considerazione

     ;-)

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Spiegazione sui dizionari

    Mea culpa, da profano ho utilizzato il termine “chiave” pensando di riferirmi all'output, quando invece di fatto mi stavo riferendo all'input.

    Comunque grazie, alla prossima seduta andrà sicuramente meglio!
    Scherzi a parte, la tua spiegazione mi ha aiutato ad inquadrare meglio il problema , ma ovviamente si tratta di argomenti che vanno studiati per bene.

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

    Re: Spiegazione sui dizionari

    Array, liste (uni e bidirezionale) dizionari (basati su tabella hash o albero bilanciato), alberi (binari e non, bilanciati e non) e grafi 

    sono le strutture dati che un programmatore DEVE conoscere come le sue tasche (anche se bucate). Le usa n milioni di volte al giorno ;-) 

  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: Spiegazione sui dizionari

    Ma io non sono un “programmatore”, mi limito ad utilizzare la programmazione come esercizio di logica. 
    E poi sarebbe un peccato studiare troppo col rischio di autospoilerarmi cose divertenti con cui “giocare”! =)

Devi accedere o registrarti per scrivere nel forum
11 risposte