conseils pour les listes chainées

Version imprimable

13/05/2016, 15h27
mido1951

conseils pour les listes chainées

Bonjour,
Je compte créer une liste chainée et après je dois insérer les éléments dans les trois places possibles(Début, Milieu, Fin).
Alors je voulais savoir, est-ce que c'est possible de créer une seule fonction qui ajoute à la liste dans ces trois places au lieu de créer chaque fonction comme les cours qui existent pour les listes chainées? parce que moi je ne sais pas à l'avance ou l'élément se place(il faut faire une condition).
Merci pour vos réponse.
13/05/2016, 15h43
Médinoc

Si tu utilises un parcours indirect (où au lieu de pointer sur les chaînons eux-mêmes, tu pointes sur leur pointeurs) pour ta liste chaînée, tu peux te faire une fonction InsererAvant() qui marchera aussi bien au début qu'au milieu ou à la fin. Après, c'est juste une histoire de trouver les endroits où l'on veut insérer (pointeur sur le premier pointeur pour insérer en tête, pointeur sur le pointeur nul pour insérer en queue, etc.)
13/05/2016, 16h03
mido1951

merci pour ton aide Médinoc mais je n'ai pas bien compris l'idée parce-que je ne connais pas très bien le parcours indirect.
mais si c'est efficace je veux bien la comprendre.
est-ce qu'il existe un exemple ou un exemple sur net?
parce-que une seule fonction c'est mieux que créer 3 fonctions"insererDebut(), insererMilieu(), insrerFin()"!
Merci

Citation:

Envoyé par mido1951

Bonjour,
Je compte créer une liste chainée et après je dois insérer les éléments dans les trois places possibles(Début, Milieu, Fin).
Alors je voulais savoir, est-ce que c'est possible de créer une seule fonction qui ajoute à la liste dans ces trois places au lieu de créer chaque fonction comme les cours qui existent pour les listes chainées? parce que moi je ne sais pas à l'avance ou l'élément se place(il faut faire une condition).
Merci pour vos réponse.

Bonjour,
il «suffit» d'encapsuler :)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 typedef enum { LP_HEAD, LP_MIDDLE, LP_TAIL } list_pos_t; void insert( list_t *list, value_t value, list_pos_t insertion_pos ) { switch (insertion_pos) { case LP_HEAD: insert_head(list, value); break; case LP_MIDDLE: insert_middle(list, value); break; case LP_TAIL: insert_tail(list, value); break; default: // on gère l'erreur break; } }
Ensuite ta liste devra gérer 3 pointeurs «fixes» : un pour la tête, un pour le milieu, un pour la queue. Remarque que deux insertions en tête provoque le déplacement du pointeur milieu vers la gauche, et deux insertions à la fin un déplacement vers la droite. Il te faut un compteur entier valant 0 au départ, chaque insertion en tête le décrémente, chaque insertion en fin l'incrémente, arrivé à 2 ou -2 il faut déplacer le pointeur milieu.. Insérer après milieu est équivalent à insérer en fin, de la même manière insérer avant milieu revient à insérer en tête du point de vue incrémentation/décrémentation. Il faudra gérer aussi les cas limites.

Citation:

Envoyé par mido1951

merci pour ton aide Médinoc mais je n'ai pas bien compris l'idée parce-que je ne connais pas très bien le parcours indirect.
mais si c'est efficace je veux bien la comprendre.
est-ce qu'il existe un exemple ou un exemple sur net?
parce-que une seule fonction c'est mieux que créer 3 fonctions"insererDebut(), insererMilieu(), insrerFin()"!
Merci

Le parcours indirect, c'est qu'au lieu de parcourir ta liste comme ceci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
chainon * GetSuivant(chainon *pChainon)
{
	assert(pChainon != NULL);
	return pChainon->pSuivant;
}
 
void Parcours(chainon *pPremier)
{
	chainon *pCourant;
	/*Note: pPremier a le droit d'être NULL, mais dans ce cas on n'appellera jamais GetSuivant dessus*/
 
	for(pCourant=pPremier ; pCourant!=NULL ; pCourant=GetSuivant(pCourant))
	{
		/*Faire un truc avec pCourant*/
	}
}

Tu la parcoures comme ceci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
chainon ** GetPtrSuivant(chainon **ppChainon)
{
	assert(ppChainon != NULL);
	assert(*ppChainon != NULL);
	return &( (*ppChainon)->pSuivant );
}
 
void ParcoursPtr(chainon **ppPremier)
{
	chainon **ppCourant;
 
	/*Note: ppPremier n'a PAS le droit d'être NULL.*/
	/*Note: *ppPremier a le droit d'être NULL, mais dans ce cas on n'appellera jamais GetPtrSuivant dessus*/
 
	assert(ppPremier != NULL);
	for(ppCourant=ppPremier ; *ppCourant!=NULL ; ppCourant=GetPtrSuivant(ppCourant))
	{
		chainon *pCourant = *ppCourant;
		/*Faire un truc avec ppCourant ou pCourant*/
	}
}

L'avantage, c'est que si tu te fais une fonction InsererAvant():

Code:

1
2
3
4
5
6
7
8
9
void InsererAvant(chainon **ppChainonRef, chainon *pNouveau)
{
	assert(ppChainonRef != NULL);
	assert(pNouveau != NULL);
	assert(pNouveau->pSuivant == NULL); /*pNouveau doit être isolé pour qu'on puisse l'insérer*/
 
	pNouveau->pSuivant = (*ppChainonRef)->pSuivant;
	(*ppChainonRef)->pSuivant = pNouveau;
}

Tu peux alors l'utiliser pour insérer n'importe où dans ta liste!
En tête:

Code:

1
2
3
4
5
void InsererEnTete(chainon **ppPremier, chainon *pNouveau)
{
	assert(ppPremier != NULL);
	InsererAvant(ppPremier, pNouveau);
}

En queue:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
chainon ** GetPtrNull(chainon **ppDansListe)
{
	chainon **ppCourant;
 
	/*Note: ppDansListe n'a PAS le droit d'être NULL.*/
	/*Note: *ppDansListe a le droit d'être NULL, mais dans ce cas on n'appellera jamais GetPtrSuivant dessus*/
 
	assert(ppDansListe != NULL);
	for(ppCourant=ppDansListe ; *ppCourant!=NULL ; ppCourant=GetPtrSuivant(ppCourant))
	{ }
	return ppCourant; /*Ici, ppCourant pointeur sur le pointeur nul terminal*/
}
void InsererEnQueue(chainon **ppPremier, chainon *pNouveau)
{
	chainon **ppNull;
	assert(ppPremier != NULL);
	ppNull = GetPtrNull(ppPremier);
	InsererAvant(ppPremier, pNouveau);
 
}

Ou une fonction qui fait les deux:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
enum position { POS_TETE, POS_QUEUE };
void InsererAPosition(chainon **ppPremier, chainon *pNouveau, position pos)
{
	chainon **ppInser;
	assert(ppPremier != NULL);
 
	switch(pos)
	{
	case POS_TETE:
		ppInser = ppPremier;
		break;
	case POS_QUEUE:
		ppInser = GetPtrNull(ppPremier);
		break;
	default:
		assert(strlen("Enum position inconnue")==0);
		return;
	}
	InsererAvant(ppInser, pNouveau);
}

(bon, trouver le milieu est plus fastidieux, mais pas insurmontable)

17/05/2016, 10h19
mido1951

mon truc c'est que j'ai des valeurs 1,2,3,4,...,n et chaque valeur est liée à des positions(des valeurs aussi).
par exemple:
1 est liée aux positions 1000,3000,5000.
2 est liée aux positions 2000,4000,9000.
3 est liée aux positions 2500,6000,7000.
4 est liée aux positions 1000,3000,5000.
5 est liée aux positions 500,3500,8000.

ce que je veux faire de mettre ces valeurs dans une liste chainée et les triés de façon à avoir:

(5,500)--> (1,4,1000) -->(2,2000) --> (3,2500) --> (1,4,3000)-->(5,3500)-->(2,4000)-->(1,4,5000)-->(3,6000)-->(3,7000)-->(5,8000)-->(2,9000).

comme vous voyez pour les positions juste on met les deux valeurs dans un même nœud de la liste c'est pour ça que je vais faire une liste dans une liste chainée.
dans la deuxième étape ce que je veux faire c'est les fonctions d'insertions dans la liste (tête, milieu, queue).

voilà c'est pour ça que je veux avoir vos conseils avant.
qu'est ce que vous pensez?
Merci
17/05/2016, 10h59
Médinoc

En gros, tu cherches à faire une liste chaînée triée par "position", d'objets contenant chacun une liste chaînée de nombres?
17/05/2016, 11h02
mido1951

Citation:

Envoyé par Médinoc

En gros, tu cherches à faire une liste chaînée triée par "position", d'objets contenant chacun une liste chaînée de nombres?

oui c'est ça.
c'est pour ça que je veux avoir vos conseils avant de coder.
Merci

Dans ce cas, vois-tu la fonction ParcoursPtr() que j'avais écrite?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ParcoursPtr(chainon **ppPremier)
{
	chainon **ppCourant;
 
	/*Note: ppPremier n'a PAS le droit d'être NULL.*/
	/*Note: *ppPremier a le droit d'être NULL, mais dans ce cas on n'appellera jamais GetPtrSuivant dessus*/
 
	assert(ppPremier != NULL);
	for(ppCourant=ppPremier ; *ppCourant!=NULL ; ppCourant=GetPtrSuivant(ppCourant))
	{
		chainon *pCourant = *ppCourant;
		/*Faire un truc avec ppCourant ou pCourant*/
	}
}

On peut s'en servir pour créer une fonction qui recherche un élément dans la liste triée, et retourne l'élément s'il existe, ou l'endroit où l'insérer s'il n'existe pas.
Puisque tu as deux types de listes différents, il va falloir dupliquer le code un peu (c'est là que le C++ montre tout son avantage sur le C). Deux listes et deux structures Chainon, qu'on va appeler chainonPosition et chainonChiffre. La liste de positions est trié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
chainonPosition** position_TrouverPtrChainonTrie(chainonPosition **ppPremier, long valeurPosition)
{
	chainonPosition **ppCourant;
 
	/*Note: ppPremier n'a PAS le droit d'être NULL.*/
	/*Note: *ppPremier a le droit d'être NULL, mais dans ce cas on n'appellera jamais GetPtrSuivant dessus*/
 
	assert(ppPremier != NULL);
	for(ppCourant=ppPremier ; *ppCourant!=NULL ; ppCourant=GetPtrSuivant(ppCourant))
	{
		if((*ppCourant)->valeurPosition >= valeurPosition)
		{
			/*Soit on a trouvé la valeur (égalité), 
			soit ppCourant pointe sur le pointeur vers l'élément suivant
			(donc pile là où il faut insérer)*/
			return ppCourant;
		}
	}
	/*Si on a parcouru la liste jusqu'au bout,
	c'est que la position n'est pas dans la liste 
	ET est supérieure à toutes les autres positions de la liste;
	il faut donc insérer le nouveau chaînon en queue de liste.
	Ça tombe bien, ppCourant pointe sur le pointeur nul de queue.*/
	return ppCourant;
}

Ainsi, on peut se faire une fonction qui trouve le bon chaînon ou l'insère s'il n'est pas là:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
chainonPosition* position_InsererTrie(chainonPosition **ppPremier, long valeurPosition)
{
	chainonPosition **ppTrouve = position_TrouverPtrChainonTrie(ppPremier, valeurPosition);
	assert(ppTrouve != NULL /*position_TrouverPtrChainon ne retourne jamais un pointeur nul*/);
	if((*ppTrouve) != NULL && (*ppTrouve)->valeurPosition == valeurPosition)
	{
		/*Le chaînon existe déjà, on le retourne*/
		return *ppTrouve;
	}
	else
	{
		/*Il faut créer un chaînon et l'insérer juste avant la position actuelle*/
		chainonPosition* pNouveau = position_CreerChainon(valeurPosition); /*Cette fonction fait le malloc(), etc.*/
		InsererAvant(ppTrouve, pNouveau);
		return pNouveau;
	}
}

salut medinoc,
Merci pour ton aide.
j'utilise une stratégie différente.
j'ai quelques problèmes pour l'instant. si t'as le temps pour m'aider sur des trucs.

pour l'instant j'ai crée une fonction qui retourne un noeud précis dans la liste.
voici le code.
Code:

1 2 3 4 5 6 7 8 9 10 11 listepos_l * currentnode(listepos_l *p_head,int pos) { listepos_l *p=p_head; while(p->vposition < pos) //les vposition de chaque noeud dans la liste sont inférieur à pos alors il avance et enfin il récupère la position du noeud demandé. { p= p->suivant; } return p; // le noeud demandé }
puis j'utilise ce noeud pour insérer après lui un nouveau noeud.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 /* insertion à la position demandée */ listepos_l * ins_milieu(listepos_l *pListe,pos_t *lindexKmer,unsigned short int indexKmer,int vpos) { listepos_l * newelem= malloc(sizeof(listepos_l)); listepos_l * courant= malloc(sizeof(listepos_l)); courant= currentnode(pListe,vpos); // le noeud demandé newelem->lindexKmer=ajouteFin(lindexKmer,indexKmer); //c'est une liste dans la liste chainée principale newelem->vposition=vpos; newelem->suivant=courant->suivant; courant->suivant=newelem; return newelem; }
j'ai essayé ce code mais pour l'instant il me génère une erreur de type "Segmentation fault (core dumped)".
Je continue à voir le problème mais j'ai voulu avoir votre avis avant.
Merci.

18/05/2016, 11h16
Médinoc
Ton problème le plus visible, c'est que currentnode() n'a pas de condition d'arrêt si la position n'est pas trouvée.
Le deuxième problème de cette fonction, c'est qu'à cause de son parcours direct, elle ne peut pas te retourner l'emplacement où il convient d'insérer un nouveau chaînon listepos_l s'il n'est pas trouvé.

Ensuite, dans ins_milieu(), qu'est-ce que c'est que ce cirque?
Code:

1 2 3 listepos_l * courant= malloc(sizeof(listepos_l)); courant= currentnode(pListe,vpos); // le noeud demandé
Pourquoi ce malloc()? c'est une fuite de mémoire!

Oui c'est ça le problème j'ai une fuite de mémoire même j'ai éliminé le malloc() (c'est une faute de ma part) j'ai encore une fuite de mémoire. Le même problème Segmentation fault (core dumped).

pour la condition d'arrêt j'ai mis le main() une condition dans s'il entre dans la fonction c'est que forcément p->vposition < pos mais il faut trouver la position.
J'ai même essayé de localiser un petit problème:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 listepos_l * currentnode(listepos_l *p_head,long int pos) { listepos_l *p=p_head; printf("pos : %ld\n",pos); //ici il m'affiche pos printf("p->vposition de P: %ld",p->vposition); // aussi c'est bon. while(p->vposition < pos) { p= p->suivant; } //normalement à la fin de cette boucle on aura le pointeur qui pointe vers l'insertion du nouvel élément. if(p->suivant == NULL){printf("Pointeur egale à null\n");} return p; }
Est-ce c'est logique medinoc?
Merci pour ton aide.

18/05/2016, 12h01
Médinoc

Franchement, tant que tu n'es pas en phase d'optimisation, tu peux remonter ton dernier printf() (et le test de nullité qui va avec) dans la boucle.
Et rajouter les \n qui manquent dans tes printf().
18/05/2016, 17h30
mido1951

J'ai fait quelque retouche pour l'instant il marche..
Mais de cette façon:
(5,500)--> (1,1000)-->(4,1000) -->(2,2000) --> (3,2500) --> (1,3000)-->(4,3000)-->(5,3500)-->(2,4000)-->(1,5000)-->(4,5000)-->(3,6000)-->(3,7000)-->(5,8000)-->(2,9000).

Mais pas de cette façon:
(5,500)--> (1,4,1000) -->(2,2000) --> (3,2500) --> (1,4,3000)-->(5,3500)-->(2,4000)-->(1,4,5000)-->(3,6000)-->(3,7000)-->(5,8000)-->(2,9000).

Comment accéder à un élément à la liste chainée pour lui ajouter de nouvelles valeurs dans un même nœud?
Merci
18/05/2016, 17h39
Médinoc

Il faut que l'appelant de la fonction currentNode() ait le moyen de voir si le nœud retourné est le nœud recherché (celui avec exactement la bonne valeur) ou le suivant (celui avant lequel il faudrait insérer un nouveau nœud).

d'accord, Medinoc .
Je vais essayer de comprendre comment faire.
voici mon code:

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
listepos_l * currentnode(listepos_l *p_head,long int pos)
{    
	listepos_l *p=p_head;unsigned int compteur=0; unsigned int i=0;
	while(p->vposition <= pos && p->suivant != NULL)
    {  
		p= p->suivant;
		compteur++;
	}
 
	listepos_l *courant=p_head;
	for(i=1;i<compteur;i++)
		courant=courant->suivant;
	return courant;
}
 
/* insertion à la position demandée */ 
listepos_l * ins_milieu(listepos_l *pListe,pos_t *lindexKmer,unsigned short int indexKmer,long int vpos)
{
		listepos_l * newelem= malloc(sizeof(listepos_l));
		listepos_l * courant;
 
	courant= currentnode(pListe,vpos);
 
	newelem->lindexKmer=ajouteFin(lindexKmer,indexKmer);
	newelem->vposition=vpos;
 
	newelem->suivant=courant->suivant;
	courant->suivant=newelem;
	return pListe;
 
}

donc ici c'est dans la currentnode() qu'il faut ajouter à liste dans le noeud de la liste?
Merci

18/05/2016, 19h18
Médinoc

Non, tu dois séparer les tâches.
Contente-toi de te débrouiller pour que le retour de currentNode() soit plus utile. Au pire, tu peux garder en mémoire un pointeur vers le nœud précédent, et retourner celui-ci (ou NULL si c'était la tête de liste) si le nœud exact n'est pas trouvé...

Et ensuite dans l'appelant, tu n'aura qu'à comparer le vposition du nœud retourné (s'il n'est pas NULL) avec le vposition que tu cherches, et ainsi tu sauras si tu dois insérer un nouveau nœud ou bien ajouter le chiffre au nœud trouvé...

Ou bien, tu peux te rendre compte que c'est encore plus une usine à gaz que mon idée, et passer à celle-ci:mouarf:

merci pour ton aide.
j'ai une petite question pour retourner le résultat du premier nœud de la liste. Il faut juste pointer sur le premier noeud n'est-ce pas?
voici un code:
Code:

1 2 3 4 5 6 long int displayfirstnode(listepos_l *p_head) { listepos_l *p = p_head; //printf("vposition: %ld \n",p->vposition); return p->vposition; //j'ai besoin du vposition de type long int du premier noeud. }
dans la fonction main cette fonction ne veut pas faire un retour.
voici se qui existe dans le main.
Code:

1 2 listepos_l *p1; p1->vposition=displayfirstnode(listepos); //listepos est la liste deja plaine parce que j'ai vérifié qu'il au moins un noeud.
voila.
je pense que p1->vposition ne veut pas accepter le retour de la fonction. malgré que vposition est de même type.
Merci

20/05/2016, 11h53
Médinoc

Dans ton main, p1 n'est pas initialisé.