probleme de suppression des element de la table de hachage

**étoile de mer** · 01/10/2008, 19h12

bonjour à tous,
jai construit une table de hachage qui contient des mots et pour chaque mot sa frequence.
jai fait une focntion qui supprime les element de la table de hachage qui supprime les mot qui ont ne frequence egale à 1.
le probleme c'est que j'ai decouvert que meme apres cette operation de suppression ya encore de element qi persistent encore dans la table de hachage et qui ont une frequence ==1
je vois pas pourquoi?
help svp
merci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void clean_table(Liste **TableHash, int NombreLigne )
{
    int boucle;
    float suup=0;
 
    for ( boucle = 0; boucle < TAILLEHASH; boucle++)
    {
        Liste *premier_valide = NULL;
        Liste *q = TableHash[boucle];
        while (q != NULL)
        {
            printf ("%d", q->freq);
            //suup = (float)(q->freq) / (float)(NombreLigne);
 
           // printf("%f", suup);
            //
            //if (suup <= Seuil)
            if(q->freq==1)
            {
                /* supprime l'element */
                Liste *tmp = q->suivant;
                /* -mo- libere(q); n'est pas déclarée */
                q = tmp;
            }
            else
            {
                if (premier_valide == NULL)
                {
                    premier_valide = q;
                }
                q = q->suivant;
            }
        }
        TableHash[boucle] = premier_valide;
    }
}

le probleme c'est que quand je remplie cette table d'un ptit nombre de mots: cette fonction marche nikel
et dans le cas contraire ca donne pas de bon resultats

**tchize_** · 01/10/2008, 19h41

ton algorithme ne fait que supprimer le premier élément de chaque liste si il a un fréquence de 1. Tu travaille correctement pour les premiers éléments (tant que fréquence de 1, on supprime et on marque le suivant comme premier), mais tu dois aussi gérer correctement les cas ou tu n'est plus en tete de liste. Là tu dois récupérer l'élément précédent et changer son ->suivant (voir algorithmique, suppression d'éléments dans une liste chainée).

**étoile de mer** · 02/10/2008, 11h11

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
void clean_table(Liste **TableHash, int NombreLigne )
{
    int boucle;
    float suup=0;
    Liste  *next;
 
    for ( boucle = 0; boucle < TAILLEHASH; boucle++)
    {
        Liste *premier_valide = NULL;
        Liste *q = TableHash[boucle];
        while (q != NULL)
        {
            printf ("%d", q->freq);
            //suup = (float)(q->freq) / (float)(NombreLigne);
 
           // printf("%f", suup);
            //
            //if (suup <= Seuil)
            if(q->freq==1)
            {
                if(premier_valide==NULL)
                {
                    TableHash[boucle]=q->suivant;
 
 
                }
                else
                premier_valide->suivant=q->suivant;
                // nettoyage
                next = q->suivant;
                free(q);  // libère la mémoire de 'p'
                q = next;
 
 
 
 
            }
            else
            {
                if (premier_valide == NULL)
                {
                    premier_valide = q;
                }
                q = q->suivant;
            }
        }
        TableHash[boucle] = premier_valide;
    }
}

**étoile de mer** · 03/10/2008, 09h03

j'ai fait une fonction qui supprime les element de la liste chaine qui ont une frequence<1
quand je l'ai testé tous les element sont supprimés seul l'elemnt .
j'ai fait ce code,
bizarre a l'aide de dubugger je vois bien qu'il supprime bien les elemnt voulus, mais dans l'affichage des element restant de la liste, je vois qu'il ya un element diqparu , or normallement il n'est pas supprimé
bizarre non???

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Liste* filtrer_liste(Liste *seq, int a )
{
 
    Liste  *next;
 
       Liste *premier_valide = NULL;
        Liste *q = seq;
        while (q != NULL)
        {
            //printf ("%d", q->freq);
            //suup = (float)(q->freq) / (float)(NombreLigne);
 
           // printf("%f", suup);
            //
            //if (suup <= Seuil)
            if(q->freq<=1)
            {
                if(premier_valide==NULL)
                {
                    seq=q->suivant;
 
 
                }
                else
                premier_valide->suivant=q->suivant;
                // nettoyage
                next = q->suivant;
                free(q);  // libère la mémoire de 'p'
                q = next;
 
 
 
 
            }
            else
            {
                if (premier_valide == NULL)
                {
                    premier_valide = q;
                }
                q = q->suivant;
            }
        }
        seq = premier_valide;
        return seq;
 
}

**3DArchi** · 03/10/2008, 09h38

Envoyé par cyrine

j'ai fait une fonction qui supprime les element de la liste chaine qui ont une frequence<1
quand je l'ai testé tous les element sont supprimés seul l'elemnt .
j'ai fait ce code,
bizarre a l'aide de dubugger je vois bien qu'il supprime bien les elemnt voulus, mais dans l'affichage des element restant de la liste, je vois qu'il ya un element diqparu , or normallement il n'est pas supprimé
bizarre non???

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Liste* filtrer_liste(Liste *seq, int a )
{
 
    Liste  *next;
 
       Liste *premier_valide = NULL;
        Liste *q = seq;
        while (q != NULL)
        {
            //printf ("%d", q->freq);
            //suup = (float)(q->freq) / (float)(NombreLigne);
 
           // printf("%f", suup);
            //
            //if (suup <= Seuil)
            if(q->freq<=1)
            {
                if(premier_valide==NULL)
                {
                    seq=q->suivant;
 
 
                }
                else
                premier_valide->suivant=q->suivant;
                // nettoyage
                next = q->suivant;
                free(q);  // libère la mémoire de 'p'
                q = next;
 
 
 
 
            }
            else
            {
                if (premier_valide == NULL)
                {
                    premier_valide = q;
                }
                q = q->suivant;
            }
        }
        seq = premier_valide;
        return seq;
 
}

Non, regarde dans ton autre poste et déroule l'exemple à la main. Tu comprendras mieux pourquoi il te manque des éléments.

**étoile de mer** · 03/10/2008, 10h53

merci 3DArchi
mais je vois bien qu'il supprime bien les mots avec le debugger

peut etre j'ai tort?...

**Médinoc** · 03/10/2008, 11h37

Pour supprimer "n'importe quel élément d'une liste chaînée, y compris le premier", tu dois pouvoir modifier le pointeur qui pointe vers le premier chaînon.

Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef struct s_chainon
{
	int valeur;
	struct s_chainon *pSuivant;
} Chainon;
 
typedef struct s_liste
{
	Chainon *pPremier;
} Liste;
 
void SupprimerInferieurs(Liste *pListe, int seuil)
{
	Chainon **ppChainon = &pListe->pPremier;
	Chainon *pChainon = pListe->pPremier;
	while(pChainon != NULL)
	{
		if(pChainon->valeur < seuil)
		{
			/* Supprime l'élément courant sans modifier ppChainon */
			Chainon *pDel = pChainon;
			*ppChainon = pDel->pSuivant;
			pChainon = pDel->pSuivant;
			DetruireChainon(pDel);
		}
		else
		{
			/* Passe au suivant, modifie ppChainon */
			ppChainon = &pChainon->pSuivant;
			pChainon = pChainon->pSuivant;
		}
	}
}

**étoile de mer** · 03/10/2008, 11h56

merci Medinoc,
je suis bloquéé là, me reste 1journéé , et je peux pas refaire tt le travail avec ce principe des liste chainéé, les nouvelles structure se donnée que tu a defini

je me sens que je suis perdue

**Médinoc** · 03/10/2008, 11h58

Et si tu prenais directement l'équivalent d'un Chainon** en paramètre de ta fonction de suppression ?

**3DArchi** · 03/10/2008, 12h21

Envoyé par cyrine

merci 3DArchi
mais je vois bien qu'il supprime bien les mots avec le debugger

peut etre j'ai tort?...

Cyrine,
Comme je te l'ais signalé dans le post, ton problème est dans la gestion de premier_valide dès que tu as des séquences N 1 N 1 N. Tu vas faire disparaître le N du milieu de ta liste.
Des fois, faut pas vouloir trop en faire d'un seul coup.
Essayes-ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void clean_table(Liste **TableHash, int NombreLigne )
{
    int boucle;
 
    for ( boucle = 0; boucle < TAILLEHASH; boucle++)
    {
        Liste *precedent;
        Liste *q = TableHash[boucle];
        /* Il vaut mieux couper la boucle en deux! */
        /* Dans un premier temps, on s'occupe de chercher le premier élément valide: */
        while((q!=NULL)&&(q->freq==1))
        {
           printf ("%d", q->freq);
           TableHash[boucle] = q->suivant;
           q = q->suivant;
        }
        precedent = TableHash[boucle];/* forcement non nul si q est non nul! */
        q= (NULL!=precedent)?precedent->suivant:NULL;
        /* Dans un second temps, on supprimer les élément de fréquence 1: */
        while(q!=NULL){
           printf ("%d", q->freq);
           if(q->freq==1){// on dechaine l'element:
              precedent->suivant = q->suivant;
              free(q);
              q = precedent->suivant;
           }
           else{
              precedent = q;
              q = q->suivant;
           }
        }
    }
}

**Médinoc** · 03/10/2008, 12h31

Déjà, c'est la fonction qu'il faut couper : On peut extraire le corps de la boucle de clean_table pour en faire un clean_liste...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void detruire_chainon(Liste * pChainon)
{
	free(pChainon);
}
 
void clean_liste(Liste ** const ppPremier, int NombreLigneMin)
{
	Liste **ppChainon = ppPremier;
	Liste *pChainon = *ppPremier;
	while(pChainon != NULL)
	{
		if(pChainon->freq < NombreLigneMin)
		{
			/* Supprime l'élément courant sans modifier ppChainon */
			Liste *pDel = pChainon;
			*ppChainon = pDel->suivant;
			pChainon = pDel->suivant;
			detruire_chainon(pDel);
		}
		else
		{
			/* Passe au suivant, modifie ppChainon */
			ppChainon = &pChainon->suivant;
			pChainon = pChainon->suivant;
		}
	}
}
 
void clean_table(Liste **TableHash, int NombreLigne )
{
	size_t index;
 
	for ( index = 0; index < TAILLEHASH; index++)
	{
		clean_liste(&TableHash[index], NombreLigne);
	}
}

**Médinoc** · 03/10/2008, 13h57

Et voici le même code, plus à mon goût et commenté:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/* Fonction qui fait ce qu'il faut pour détruire proprement un chaînon.
   Par exemple, il peut y avoir des trucs à faire avant le free()... */
void detruire_chainon(Liste * pChainon)
{
	free(pChainon);
}
 
/* Modifie le pointeur, pour le faire pointer sur le chaînon
   qui suit celui à détacher. Retourne le chaînon détaché. */
Liste * detacher_chainon(Liste **ppChainon)
{
	Liste *pRet = *ppChainon;
	if(pRet==NULL)
		return NULL;
 
	*ppChainon = pRet->suivant;
	pRet->suivant = NULL;
	return pRet;
}
 
/* À partir d'un pointeur de pointeur, 
   donne le pointeur de pointeur pour le chaînon suivant */
Liste ** get_ptr_chainon_suivant(Liste **ppChainon)
{
	if(ppChainon==NULL || *ppChainon==NULL)
		return NULL;
	else
	{
		Liste* pChainon = *ppChainon;
		return &pChainon->suivant;
	}
}
 
void clean_liste(Liste ** const ppPremier, int NombreLigneMin)
{
	/* Utilise un pointeur de pointeur, pour modifier plus facilement.
	   Quand on supprime un élément, on modifie le pointeur qui pointait dessus. */
	Liste **ppChainon = ppPremier;
	while((*ppChainon) != NULL)
	{
		if((*ppChainon)->freq < NombreLigneMin)
		{
			/* Supprime l'élément courant sans modifier ppChainon */
			Liste *pDel = detacher_chainon(ppChainon);
			detruire_chainon(pDel);
		}
		else
		{
			/* Passe au suivant, modifie ppChainon */
			ppChainon = get_ptr_chainon_suivant(ppChainon);
		}
	}
}
 
/* Je n'ai pas l'habitude d'utiliser la notation "tableau" pour les paramètres,
   Mais là je trouve ça pratiquement indispensable pour éviter la confusion
   avec les autres fonctions. */
void clean_table(Liste *TableHash[], int NombreLigne )
{
	size_t index;
 
	/*Parcoure la table, et nettoie chaque liste.*/
	for ( index = 0; index < TAILLEHASH; index++)
	{
		clean_liste(&TableHash[index], NombreLigne);
	}
}

Si j'ai le temps, j'y joindrai un schéma explicatif.

**3DArchi** · 03/10/2008, 14h26

Envoyé par Médinoc

Et voici le même code, plus à mon goût et commenté:

Plus à mon goût:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Liste* clean_liste(Liste * const pPremier, int NombreLigneMin)

Bref, plutôt que de passer un pointeur de pointeur, on passe un pointeur et la fonction retourne le résultat. Mais, là c'est juste une question de style.

**Médinoc** · 03/10/2008, 14h48

Le fait d'utiliser un pointeur de pointeur permet de rester cohérent sur tout le parcours, vu qu'en interne aussi, on utilise un pointeur de pointeur.

Voir schéma joint pour la façon dont je parcoure la liste simplement chaînée pour insérer et supprimer facilement des éléments.

**étoile de mer** · 03/10/2008, 15h38

merci

mais ca cause une erreur de segmentation ici

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if((*ppChainon)->freq < NombreLigneMin)

une idéé svp?
merci

**Médinoc** · 03/10/2008, 15h45

Réussis-tu à comprendre mon code et mon schéma ?

**Médinoc** · 06/10/2008, 13h44

Envoyé par cyrine

ca cause une erreur de segmentation ici

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if((*ppChainon)->freq < NombreLigneMin)

une idéé svp?
merci

Cela ne peut pas être une erreur de pointeur nul car la valeur de (*ppChainon) est testée juste avant.
Tu dois donc avoir un pointeur "suivant" non-initialisé quelque part dans ta liste.

probleme de suppression des element de la table de hachage

C

Discussions similaires

Partager

Partager