probleme de suppression des element de la table de hachage

Version imprimable

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:

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

01/10/2008, 19h41
tchize_

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).

Code:

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;
    }
}

supprimer element liste chainee

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:

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;
 
}

Citation:

Envoyé par cyrine

Code:

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.

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

merci 3DArchi
mais je vois bien qu'il supprime bien les mots avec le debugger
:aie:
peut etre j'ai tort?...

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:

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;
		}
	}
}

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

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
:aie:
je me sens que je suis perdue
03/10/2008, 11h58
Médinoc

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

Citation:

Envoyé par cyrine

merci 3DArchi
mais je vois bien qu'il supprime bien les mots avec le debugger
:aie:
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:

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;
           }
        }
    }
}

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:

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);
	}
}

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

Code:

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.

03/10/2008, 14h26
3DArchi

Citation:

Envoyé par Médinoc

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

:king:
Plus à mon goût:

Code:

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.
03/10/2008, 14h48
Médinoc

1 pièce(s) jointe(s)

Avec un schéma!

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.
03/10/2008, 15h38
étoile de mer

erreur de segmentation

merci :king:
mais ca cause une erreur de segmentation ici

Code:

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

une idéé svp?
merci
03/10/2008, 15h45
Médinoc

Réussis-tu à comprendre mon code et mon schéma ?
06/10/2008, 13h44
Médinoc

Citation:

Envoyé par cyrine

ca cause une erreur de segmentation ici

Code:

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.