[C]inserire e cancellare nodi in una lista collegata

[boll85]

Ciao a tutti!
sto cercando di implementare in c un dizionario mediante una tavola hash con liste collegate, ma i metodi insert e delete per inserire e cancellare un nodo nella lista mi danno qualche problema....la insert mi sovrascrive sempre il primo elemento puntato dalla lista, nonostante io penso di aver giustamente incrementato il puntatore, mentre la delete in realtà non mi cancella il nodo, la print continua a stampare il nodo anche quando la lista dovrebbe risultare vuota.
Mi potete aiutare a vedere dov'è il problema?..vi posto il codice... sbaglio sicuramente qualcosa nel gestire i puntatori e la free.
Spero in una vostra risposta, grazie!!!

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

#define M 10
#define DIM_ELEM 20

struct nodo {
	int key;
	char* val;
	struct nodo* next;
} typedef nodo;

struct hashMap{
	nodo* lista[M];
}typedef hashmap;

typedef int (*HashFunz)(int k);//puntatore a funzione 

int hash1(int k);
int hash2(int k);

void insert(hashmap* h, char* e, int k, HashFunz hf);
void delete(hashmap* h, int k, HashFunz hf);
char* search(hashmap* h, int k, HashFunz hf);
void print(hashmap* h);
int menu();


int main(){
	hashmap tavola={NULL};
	int metodo;
	HashFunz funzHash;
	printf("Funzione hash da utilizzare per implementare la tavola:\n");
	printf("1)Metodo delle divisioni\n");
	printf("2)Metodo del ripiegamento(con chiavi aventi più di una cifra)\n");
	scanf("%d",&metodo);
	switch(metodo){
		case 1:
			funzHash=hash1;
			break;
		case 2:
			funzHash=hash2;
			break;
		default:
			printf("Valore inserito non valido. Il programma verrà terminato\n");
			return 0;
	}
	
	int chiave;
	while(1){
		int scelta= menu();
		char* elemento = (char*)malloc(DIM_ELEM * sizeof (char));
		switch (scelta){
			case 1: 
				printf("Inserisci chiave:\n");
				scanf("%d", &chiave);
				printf("Inserisci elemento:\n");
				scanf("%s", elemento);
				insert(&tavola,elemento,chiave,funzHash);
				break;
			case 2:	
				printf("Cerca chiave:\n");
				scanf("%d", &chiave);
				elemento=search(&tavola,chiave,funzHash);	
				if(elemento==NULL)
					printf("Chiave non trovata.\n");
				else
					printf("Elemento trovato: %s\n", elemento);
				break;
			case 3:
				printf("Cancella chiave:\n");
				scanf("%d", &chiave);
				delete(&tavola,chiave,funzHash);
				break;
			case 4:
				print(&tavola);
				break;	
			default:
				return 0;
		}
	}
	
	return 0;
}

int hash1(int k){
	return k%M;
}

int hash2(int k){
	int r=0,q=k;
	k=0;
	while(q>0){
		r=q%10;
		q=q/10;
		k+=r;
	}
	return k%M;//Inserisco il modulo perchè la somma delle cifre potrebbe essere superiore ad m
}

void insert(hashmap* h, char* e, int k, HashFunz hf){
	int indice= (*hf)(k);
	nodo* nuovo=(nodo*)malloc(sizeof(nodo));
	nuovo->key=k;
	nuovo->val=e;
	nuovo->next=NULL;
	nodo* temp=h->lista[indice];
	if(temp!=NULL){
		while(temp->next!=NULL){
			temp=temp->next;
		}
		temp->next=nuovo;
	}
	h->lista[indice]= nuovo;
	if(h->lista[indice]!=NULL){
	        printf("Valore h->lista[indice]->key %d\n", h->lista[indice]->key);
	        printf("Valore h->lista[indice]->val %s\n", h->lista[indice]->val);
	}else{
		printf("lista ancora vuota\n");
	}
	printf("Voce inserita nel dizionario.\n");
	return;
}

void delete(hashmap* h, int k, HashFunz hf){
	int indice= (*hf)(k);
	nodo* temp=h->lista[indice];
	while(temp!=NULL){
		if(temp->key==k){
			nodo* n=temp->next;
			free(temp);
			temp=n;
			printf("Voce cancellata dal dizionario.\n");
			return;
		}else{
			temp=temp->next;
		}
	}
	printf("Chiave non presente.\n");
	return;
}

char* search(hashmap* h, int k, HashFunz hf){
	int indice= (*hf)(k);
	nodo* temp=h->lista[indice];
	while(temp!=NULL){
		if(temp->key==k){
			return temp->val;
		}else{
			temp=temp->next;
		}
	}
	return NULL;
}

void print(hashmap* h){
	printf("\n\n********************************\n");
	printf("Voci dizionario:\n");
	printf("Indice\t\tChiave\t\tElemento\n");
	int i;
	nodo* temp;
	for(i=0;i<M;i++){
		temp=h->lista[i];
		while(temp!=NULL){
			printf("%d\t\t%d\t\t%s\n",i,temp->key,temp->val);
			temp=temp->next;
		}
	}
	printf("\n********************************\n\n");
	return;
}

int menu(){
	int scelta;
	printf("\nMENU' DIZIONARIO");
	printf("\n1) Aggiungi voce (con chiavi distinte)");
	printf("\n2) Cerca chiave");
	printf("\n3) Elimina chiave");
	printf("\n4) Visualizza dizionario");
	printf("\n5) Esci");
	printf("\nScelta: ");
	scanf("%d", &scelta);
	
	return scelta;
}

[jaso]

guarda:

struct list
{
int value;
struct list* nextPtr;
};
..
main()
{
..
struct list* listPtr;
..
preInsert(&listPtr,value);
..
preInsert(struct list** ptrPtr, int value) //inserisce un elemento
{

struct list* tmpPtr;

tmpPtr=*ptrPtr;
*ptrPtr=(struct list*)malloc(sizeof(struct list));
(*ptrPtr)->value=value;
(*ptrPtr)->nextPtr=tmpPtr;
}

scritto al volo.. lol che casino con il tab..
ciao

[boll85]

Ciao...grazie della risposta, ma con il metodo che dici tu dovrei cambiare completamente tutto il codice..
Un consiglio per cambiare il metodo insert e delete mantenendo le mie strutture?

[menphisx]

Non pensi che 10 sia un po' piccolo per M ?
Controlla i valori di ritorno delle malloc

[boll85]

il valore di M secondo me non c'entra nulla....sulle malloc, invece forse ne manca una in insert per assegnare il valore del parametro e al nuovo nodo, così non lo sovrascrivo ogni volta....ma comunque non mi scorre lo stesso la lista...è un macello questo programma..

[menphisx]

Basta metter una assert dopo ogni malloc:

assert(puntatore != NULL);

per essere sicuro che ogni allocazione avvenga correttamente.
Questa è solo buona pratica di programmazione ...

[Vincenzo1968]

È bene usare un numero primo per dimensionare la hashtable. Per cancellare un nodo da una lista, si deve prima far puntare il nodo precedente al nodo successivo.

Così dovrebbe andare:

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

#define M 4093
#define DIM_ELEM 89

typedef struct tagNodo
{
	int key;
	char* val;
	struct tagNodo* next;
} nodo;

typedef struct tagHashMap
{
	nodo* lista[M];
}hashmap;

typedef int (*HashFunz)(int k);//puntatore a funzione 

int hash1(int k);

void hm_free_list(nodo* first);
void hm_insert(hashmap* h, char* e, int k, HashFunz hf);
nodo* hm_delete_node(nodo *first, int k);
void hm_delete(hashmap* h, int k, HashFunz hf);
char* hm_search(hashmap* h, int k, HashFunz hf);
void print(hashmap* h);
int menu();


int main()
{
	hashmap tavola;
	int metodo;
	HashFunz funzHash;
	int chiave;
	int scelta;
	char* elemento;
	int k;

	funzHash = hash1;

	for (k = 0; k < M; k++)
		tavola.lista[k] = NULL;

	while(1)
	{
		scelta = menu();
		elemento = (char*)malloc(DIM_ELEM * sizeof(char) + 1);
		if ( !elemento )
		{
			printf("Memoria insufficiente.\n");
			break;
		}

		switch (scelta)
		{
			case 1: 
				printf("Inserisci chiave:\n");
				scanf("%d", &chiave);
				printf("Inserisci elemento:\n");
				scanf("%s", elemento);
				hm_insert(&tavola,elemento,chiave,funzHash);
				break;
			case 2:	
				printf("Cerca chiave:\n");
				scanf("%d", &chiave);
				elemento = hm_search(&tavola,chiave,funzHash);	
				if(elemento==NULL)
					printf("Chiave non trovata.\n");
				else
					printf("Elemento trovato: %s\n", elemento);
				break;
			case 3:
				printf("Cancella chiave:\n");
				scanf("%d", &chiave);
				hm_delete(&tavola,chiave,funzHash);
				break;
			case 4:
				print(&tavola);
				break;	
			default:
				for (k = 0; k < M; k++)
					hm_free_list(tavola.lista[k]);
				return 0;
		}
	}
	
	return 0;
}

int hash1(int k)
{
	return k%M;
}

void hm_free_list(nodo* first)
{
	nodo *n1 = first, *n2;
	while ( n1 != NULL )
	{
		free(n1->val);
		n2 = n1->next;
		free(n1);
		n1 = n2;
	}
}

void hm_insert(hashmap* h, char* e, int k, HashFunz hf)
{
	nodo *temp, *nuovo;
	int indice;

	if ( hm_search(h, k, hf) != NULL )
	{
		printf("La chiave inserita, %d, e' gia' presente nel dizionario.\n", k);
		return;
	}

	indice = (*hf)(k);

	nuovo = (nodo*)malloc(sizeof(nodo));
	if ( !nuovo )
	{
		printf("Memoria insufficiente.\n");
		return;
	}

	nuovo->key = k;
	nuovo->val = e;
	nuovo->next = NULL;
	temp = h->lista[indice];
	if(temp != NULL)
	{
		while(temp->next != NULL)
		{
			temp = temp->next;
		}
		temp->next = nuovo;
	}
	else
	{
		h->lista[indice] = nuovo;
	}

	printf("Voce inserita nel dizionario.\n");
}

nodo* hm_delete_node(nodo *first, int k)
{
	nodo *n1 = first, *n2;
	nodo *prev = NULL;

	if ( first == NULL )
		return NULL;

	while ( n1 != NULL )
	{
		if ( n1->key == k )
		{
			if ( !prev ) /* Se prev è NULL, stiamo cancellando il primo nodo della lista */
			{
				n1 = n1->next;
				free(first);
				return n1;
			}
			else
			{
				n2 = n1->next;
				free(n1);
				prev->next = n2;
				return first;
			}
		}
		else
		{
			prev = n1;
			n1 = n1->next;
		}
	}

	return first;
}

void hm_delete(hashmap* h, int k, HashFunz hf)
{
	int indice = (*hf)(k);
	nodo* temp = h->lista[indice];

	h->lista[indice] = hm_delete_node(temp, k);
}

char* hm_search(hashmap* h, int k, HashFunz hf)
{
	int indice = (*hf)(k);
	nodo* temp = h->lista[indice];
	while(temp != NULL)
	{
		if(temp->key == k)
		{
			return temp->val;
		}
		else
		{
			temp = temp->next;
		}
	}
	return NULL;
}

void print(hashmap* h)
{
	int i;
	nodo* temp;

	printf("\n\n********************************\n");
	printf("Voci dizionario:\n");
	printf("Indice\t\tChiave\t\tElemento\n");

	for(i = 0; i < M; i++)
	{
		temp = h->lista[i];
		while(temp != NULL)
		{
			printf("%d\t\t%d\t\t%s\n",i,temp->key,temp->val);
			temp = temp->next;
		}
	}
	printf("\n********************************\n\n");
	return;
}

int menu()
{
	int scelta;

	printf("\nMENU' DIZIONARIO");
	printf("\n1) Aggiungi voce (con chiavi distinte)");
	printf("\n2) Cerca chiave");
	printf("\n3) Elimina chiave");
	printf("\n4) Visualizza dizionario");
	printf("\n5) Esci");
	printf("\nScelta: ");
	scanf("%d", &scelta);
	
	return scelta;
}

[boll85]

Ciao, grazie per le correzioni del codice...Funziona perfettamente!!!
Mi sei stato veramente di un aiuto enorme, ho capito finalmente dove sbagliavo...ormai avevo perso le speranze di vederlo funzionante, invece...
Grazie tante ancora!!!