GEF 243BProgrammation informatique

appliquée

Listes chaînées II

§15.1 – 15.2

JGA Beaulieu4/11/23 2

Revue

• Où dans la mémoire est-ce que les listes chaînées sont stockées?

• Est-ce que chaque nœud dans la liste chaînée possède un nom symbolique (nom de variable)?

• Quelle est l’utilité du pointeur de tête?

JGA Beaulieu4/11/23 3

Synopsis

• Traverser/chercher dans une LC• Insérer un nœud

1. À la tête de la LC

2. Après la tête de la LC

• Effacer un nœud 1. À la tête de la LC

2. Après la tête de la LC

3. Utilisant l’indirection

JGA Beaulieu4/11/23 4

Traverser – chercher dans une LC

• Rappel cours Liste Chaìnée I:

typedef struct TAG_NOEUD_ETUDIANT

{

char prenom[15];

char surnom[25];

unsigned long numeroDeCollege;

float moyenne;

struct TAG_NOEUD_ETUDIANT* pProchainNoeud;

} NOEUD_ETUDIANT; //nom du type

JGA Beaulieu4/11/23 5

1. Déclarez un pointeur à la structure de type définit (disons pTraverse)NOEUD_ETUDIANT* pTraverse = NULL;

2. Met pTraverse à la tête de la liste pTraverse = pListeEtudiants;

3. Vérifie si le pointeur est NULL

4. Traite le nœud courrant

5. Met le pointeur au prochain nœud

pTraverse = pTraverse->pProchainNoeud;

6. Retourne à l’étape 3 jusqu’à fin

Traverser – chercher dans une LC

JGA Beaulieu4/11/23 6

Traverser – chercher dans une LC

…

int compte = 0;

NOEUD_ETUDIANT* pTraverse = pListeEtudiants;

while (pTraverse != NULL)

{

compte++; //traite le noeud courrant

pTraverse = pTraverse->pProchainNoeud;

}//fin while pTraverse

…

Allard20001

pProchainNoeud

Allen22456

pProchainNoeud

Baar20002

pProchainNoeud

Alpo22460

pProchainNoeud0

pListeEtudiants

pTraverse compte = 0

pTraverse = pListeEtudiants;

Allard20001

pProchainNoeud

Allen22456

pProchainNoeud

Baar20002

pProchainNoeud

Alpo22460

pProchainNoeud0

pListeEtudiants

pTraverse compte = 1

pTraverse = pTraverse->pProchainNoeud;

Allard20001

pProchainNoeud

Allen22456

pProchainNoeud

Baar20002

pProchainNoeud

Alpo22460

pProchainNoeud0

pListeEtudiants

pTraversecompte = 4

while (pTraverse->pProchainNoeud != NULL) {…}

JGA Beaulieu4/11/23 10

• Nous avons déjà vu comment insérer un nœud au début de la liste dans le cours précédent.

• Avant que nous voulions insérer un nœud dans la LC nous devons la traverser pour chercher le point d’insertion.

• La seule exception à cette règle est si nous utilisons une liste non-ordonnée. Dans ce cas nous ajoutons toujours les nœuds au début de la liste.

Ceci est un cas simple qui est couvert par les étapes pour l’insertion dans une liste ordonnée

Insertion d’un nœud dans une LC

JGA Beaulieu4/11/23 11

1. Déclarez un nœud temporaire (pTemp) et demander de la mémoire avec malloc

On vérifie si il y a assez de mémoire

2. Mettez touts les champs du nœud pointé par pTemp à leurs valeurs appropriées

3. Pour insérer un nœud au début de la liste:a. À la tête de la liste:

i. Pointe le nouveau nœud au premier nœud en utilisant le pointeur de tête: pTemp->pProchainNoeud = pListeEtudiants;

ii. Pointez le pointeur de tête au nouveau nœud (pTemp)pListeEtudiants = pTemp;

Insertion d’un nœud à la tête d’une LC

JGA Beaulieu4/11/23 12

Insertion d’un nœud à la tête d’une LC//1. créez un nouveau noeud

NOEUD_ETUDIANT* pTemp = NULL;

pTemp = (NOEUD_ETUDIANT *)malloc(sizeof(NOEUD_ETUDIANT));

//2. initialisez le nouveau noeud

strcpy(pTemp->prenom,"Jack");

strcpy(pTemp->surnom,"Rabbit");

pTemp->numeroDeCollege = 22222;

pTemp->moyenne = 99.9;

//3.a Insérez le nœud à la tête de la liste

pTemp->pProchainNoeud = pListeEtudiants;

pListeEtudiants = pTemp;

Allard20001

pProchainNoeud 0

pListeEtudiants

pTemp

Rabbit22222

pProchainNoeud ?

Insertion d’un nœud à la tête d’une LCÉtapes 1,2 – déclare et initialise le nœud

Allard20001

pProchainNoeud 0

pListeEtudiants

pTemp

Rabbit22222

pProchainNoeud

1. pTemp->pProchainNoeud = pListeEtudiants;2. pListeEtudiants = pTemp;

1

2

Insertion d’un nœud à la tête d’une LCÉtape 3a – déclare et initialise le nœud

JGA Beaulieu4/11/23 15

1. Créez un nouveau nœud

2. Initialisez le nouveau nœud

3. Pour insérer dans la LC:b. N’importe où d’autre que la tête dans la LC

i. Traversez la liste en utilisant pTraverse (ici nous assumons que nous voulons insérer après pTraverse)

ii. Pointez le nouveau nœud où pTraverse pointe (indirection)

pTemp->pProchainNoeud = pTraverse->pProchainNoeud;

i. Pointez pTraverse au nouveau nœud pTravers->pProchainNoeud = pTemp;

Insertion d’un nœud après la tête de la LC

JGA Beaulieu4/11/23 16

Insertion d’un nœud après la tête de la LC

//1. créez un nouveau noeud

NOEUD_ETUDIANT* pTemp = NULL;

pTemp = (NOEUD_ETUDIANT *)malloc(sizeof(NOEUD_ETUDIANT));

//2. initialisez le nouveau nœud

strcpy(pTemp->prenom,"Jack");

strcpy(pTemp->surnom,"Rabbit");

pTemp->numeroDeCollege = 22222;

pTemp->moyenne = 99.9;

//3.b. insérez le nœud n’importe où d’autre dans la LC

pTemp->pProchainNoeud = pTraverse->pProchainNoeud;

pTravers->pProchainNoeud = pTemp;

Allard20001

pProchainNoeud

0pListeEtudiants

pTemp

Rabbit22222

pProchainNoeud ?

All20001

pProchainNoeud

pTraverse

Insertion d’un nœud après la tête de la LCÉtapes 1,2 – Déclare et initialise le nouveau nœud

Allard20001

pProchainNoeud

0pListeEtudiants

pTemp

Rabbit22222

pProchainNoeud

1. pTemp->pProchainNoeud = pTravers->pProchainNoeud;2. pTravers->pProchainNoeud = pTemp;

Allen22456

pProchainNoeud

pTraverse

1

2

Insertion d’un nœud après la tête de la LCÉtape 3b – Déclare et initialise le nouveau nœud

JGA Beaulieu4/11/23 19

1. Déclarez un nouveau pointeur appelé pPred qui suit pTraverse mais un nœud en arrière

2. Vérifiez si la liste est vide et imprime une erreur si c’est le cas

3. Vérifiez si le nœud à être effacé est le premier (la tête)

a. nous mettons la tête au prochain nœud dans la liste.

pListeEtudiants = pListeEtudiants->pProchainNoeud; b. Libèrez la mémoire

Effacer un nœud à la tête de la LC

JGA Beaulieu4/11/23 20

Effacer un nœud à la tête de la LC

…//Condition spéciale si le noeud est la têteunsigned long numEfface = 0; //on obtiens cette valeur

//1. Déclarez deux pointeursNOEUD_ETUDIANT *pTraverse = pListeEtudiants;NOEUD_ETUDIANT *pPred = pListeEtudiants;

//2. check si la liste est videif (pListeEtudiants == NULL){…} //imprime erreur et sort

//3a. Efface la tête de la liste parce que c’est le bon nœud if (pListeEtudiants->numeroDeCollege == numEfface){

pListeEtudiants = pListeEtudiants->pProchainNoeud;free(pTraverse);

}else

pTraverse = pTraverse->pProchainNoeud; …//pTraverse est maintenant en avant de pPred

Allard20001

pProchainNoeud

Allen22456

pProchainNoeud

Baar20002

pProchainNoeud

Alpo22460

pProchainNoeud0

pListeEtudiants

pTraverse numEfface = 20001pPred

Effacer un nœud à la tête de la LCÉtapes 1,2 – trouve le nœud à effacer

Allard20001

pProchainNoeud

Allen22456

pProchainNoeud

Baar20002

pProchainNoeud

Alpo22460

pProchainNoeud0

pListeEtudiants

pTraverse numEfface = 20001pPred

Effacer un nœud à la tête de la LCÉtapes 3a,b – efface le nœud et libère la mémoire

JGA Beaulieu4/11/23 23

3. Voir si le nœud de tête doit être effacé

4. On fait une recherche pour le nœud à être effacé en testant pour la condition numeroDeCollege match dedans une boucle

a. Avance les deux pointeurs (pTraverse et pPred)

5. Efface le nœud qui suit pPred a. réglant le pointeur de prochain nœud de pPred comme suit:

pPred->pProchainNoeud = pTraverse->pProchainNoeud;b. Libère la mémoire où pTraverse pointe

Effacer un nœud après la tête de la LC

JGA Beaulieu4/11/23 24

Effacer un nœud dans une LC - général

…//étapes 1 – 3b diapo 20

//4. trouve le nœud à effacer

while (pTraverse->numeroDeCollege != numEfface)

{

pPred = pTraverse; //4a. Avance les pointeurs

pTraverse = pTraverse->pProchainNoeud;

if (pTraverse == NULL) {…} //check si fin de la LC

//si on arrive à la fin sans trouver le nœud

//il faut donner une erreur

}

//5. Efface le nœud et libère la mémoire

pPred->pProchainNoeud = pTraverse->pProchainNoeud;

free(pTraverse);

…

Allard20001

pProchainNoeud

Allen22456

pProchainNoeud

Baar20002

pProchainNoeud

Alpo22460

pProchainNoeud0

pListeEtudiants

pTraverse

numEfface = 20002

Avance des pointeurs pTraverse en avant de pPred

pPred

Allard20001

pProchainNoeud

Allen22456

pProchainNoeud

Baar20002

pProchainNoeud

Alpo22460

pProchainNoeud0

pListeEtudiants

pTraverse

numEfface = 20002

pPred->pProchainNoeud = pTraverse->pProchainNoeud;

free(pTraverse);

pPred

JGA Beaulieu4/11/23 27

Effacer un nœud dans une LC - général

• Vous pouvez aussi vous servir de l’indirection pour tenir le prédécesseur du nœud que vous voulez effacer

• Le code suivant est équivalent au code de la diapo 24

• Quand vous vous servez de ce genre d’indirection faites attention à ce que vous libérez (free)!

JGA Beaulieu4/11/23 28

while ((pTraverse->pProchainNoeud)->numeroDeCollege != numEfface)

{

pTraverse = pTraverse->pProchainNoeud;

if (pTraverse->pProchainNoeud == NULL) {…} //imprime une erreur et …

}

pTemp = pTraverse->pProchainNoeud;

pTraverse->pProchainNoeud = (pTraverse->pProchainNoeud)->pProchainNoeud;

free(pTemp); //Cette ligne est importante

…

JGA Beaulieu4/11/23 29

Quiz Time

• Décrivez les étapes pour traverser une LC• Décrivez les étapes pour faire une insertion

générale dans une LC