Discussion :

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

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

[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

[picodev]

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 :

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

[Médinoc]

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 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
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 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
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 C :

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

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 C :

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

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

En queue:

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

[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

[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?

[mido1951]

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

[Médinoc]

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

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

[mido1951]

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 :

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

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 :

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
 
/* 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.

[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 C mauvais :

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

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!

[mido1951]

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 :

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

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.

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

[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

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

[mido1951]

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

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

[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

[mido1951]

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 :

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

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 :

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

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

[Médinoc]

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