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

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

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