TP N°2

 

Les Listes Chainées Simples

 

 

Exercice 1 :

 

Ecrire les fonctions suivantes pour les listes chainées simples :

  1. "ajoutTete" qui ajoute  un élément en tête de liste.
  2. "ajoutAprès"  qui ajoute un élément  après une adresse donnée.
  3. "creerListeFiFo" qui crée une liste de n entiers en FIFO (utiliser "ajoutTete" et "ajoutAprès" ).
  4. "creerListeLiFo" qui crée une liste de n entiers en LIFO (utiliser "ajoutTete").
  5. "creerListeFiFo2" qui crée une liste de n entiers en FIFO (utiliser uniquement "ajoutAprès" ).
  6. "afficherListe" qui parcourt une liste de n entiers et affiche tous les éléments de la liste.
  7.  "supprimtete" qui supprime l’élément en tête de liste.
  8. "supprimApres" qui supprime l’élément après une adresse donnée.
  9. "supprimNeg" qui supprime les valeurs négatives de la liste (utiliser  "supprimtete" et "supprimAprès").
  10. "rechercheAdrsMin" qui retourne l’adresse de l’élément le plus petit (minimum).
  11. "TrierListe" qui trie une liste par ordre croissant (utiliser "rechercheAdrsMin").
  12. "recherchePrecTrie"  qui étant donne la tête d’une liste triée par ordre croissant  et un entier  v retourne l'adresse du précédent ou l’entier v doit être insérer dans la liste.
  13.  "InsererListeTrie" qui étant donne la tête d’une liste triée par ordre croissant  demande à l’utilisateur de donner un entier v et l’insert à la bonne position dans la liste (utiliser "recherchePrecTrie" ).
  14. "rechercheTrieMaxOcc" qui étant donné la tête d’une liste triée par ordre croissant retourne l’adresse de l’ élément le plus fréquent (c.a.d l’ élément dont le nombre d’occurrences est le plus grand).
  15. "suppressionTrieDoublons" qui étant donne la tête d’une liste triée par ordre croissant supprime les doublons (exemple si la liste est 1, 2, 2, 2, 5, 5, 8 la liste devient 1, 2, 5, 8).
  16. "rechercheAdrsMax" qui retourne l’adresse de l’élément le plus grand (maximum), cette fonction aura aussi comme résultat l’adresse de l’élément précédent du maximum (sera égale a NULL si le maximum est le premier de la liste).
  17. "TrierListe2" qui recherche le maximum d’une liste quelconque (première liste), l’enlève de la liste (sans le supprimer) et l’ajoute en tête de liste d’une 2eme liste ; ainsi on obtient une liste triée (utiliser "rechercheAdrsMax"). On bouclera tant que la première liste est non vide. Modifier le main() pour utiliser TrierListe2.
  18. "entList  *sortedInsert(entList *tete, entList *new_node)": fonction sortedInsert() qui etant donne une liste triee de tete tete triee par ordre croissant et un noeud new_node insert new_node dans la liste a la bonne position pour avoir la liste toujours triee par ordre croissant.
  19. "entList *insertionSort(entList *tete)": fonction qui implemente le tri par insertion d'une liste. Utiliser la fonction precedente sortedInsert(). La fonction retourne la tete de la liste triee.
  20. Ecrire la fonction main en utilisant les fonctions précédentes en appelant dans cet ordre : creerListeFifo, afficherList, enleverNeg, afficherList, trieList,  afficherList, InsererListeTrie suivi de afficherList  (l’appeler dans une boucle 5 fois), rechercheTrieMaxOcc, suppressionTrieDoublons et afficherList

 Solution

 

 

Exercice 2 :

 

Ecrire les fonctions suivantes pour les listes chainées simples :

  1. "Deplacertete"  qui étant donné  2 têtes de liste (passées par adresse) tête de liste destination et tête de liste source, enlève le 1er élément de la liste source et le met en tête de liste de la liste destination
  2. "diviserAlternatif"  qui étant donné  une liste simple crée 2 plus petites listes sans allocation de mémoire composées de manière alternative des éléments de la liste initiale et inversées (si liste initiale est 1, 5, 8, 12, 3, 9 alors les 2 listes crées seront 3, 8, 1 et 9, 12, 5. Utiliser "Deplacertete"
  3. "fusion2ListesTries" qui fait la fusion de deux listes triées d’entiers L1 et L2 en une liste triée L3
  4. "listeMemoire" qui fait la création de la liste miroir de L (sans allocation d’espace mémoire, en changeant uniquement les chainages) 
  5. "listesTrieesIntersect" qui étant donné deux listes triées d’entiers L1 et L2 crée une nouvelle liste qui contient l’intersection des 2 listes ; la nouvelle liste sera elle aussi triée
  6. "entList    *somme2Listes(entList *list1, entList *list2)" fonction qui fait la somme de 2 listes de chiffres entiers qui representent chacun un nombre en creant une liste qui represente la somme des 2 nombres. Si List 1: 5->1->2   represente nbr 215 et List 2: 8->3->1  represente nbr 138 alors cette fonction cree list: 3->5->3  qui represente le nbr 353 (egale a 215 + 138). Cette fonction doit d'abord convertir chacune des 2 listes en son nombre correspondant.
  7.  "entList    *somme2ListesDirect(entList *list1, entList *list2)" fonction qui fait la somme de 2 listes de chiffres entiers qui representent chacun un nombre en creant une liste qui represente la somme des 2 nombres. Si List 1: 5->1->2   represente nbr 215 et List 2: 8->3->1  represente nbr 138 alors cette fonction cree list: 3->5->3  qui represente le nbr 353 (egale a 215 + 138). Cette fonction doit faire la somme des 2 listes sans convertir les listes en leur nombre correspondant.
  8. Tester dans la fonction main chacune des fonctions ci-dessus après avoir ajouté la fonction afficherListe

 

Solution

 

 

Exercice 3 :

 

Ecrire les fonctions suivantes pour les listes chainées simples :

 

  1. "void pairSwapData(entList *tete)" fonction qui permute les donnees de chaque noeud avec le noeud suivant et ce pour chaque paire de la liste. Par example, si la liste est 1->2->3->4->5 alors la liste devient to 2->1->4->3->5 et si la liste est 1->2->3->4->5->6 alors elle devient  2->1->4->3->6->5.
  2. "entList  *pairSwapLinks(entList *tete)" fonction qui permute le chainage de chaque noeud avec le noeud suivant et ce pour chaque paire de la liste. Par example, si la liste est 1->2->3->4->5 alors la liste devient to 2->1->4->3->5 et si la liste est 1->2->3->4->5->6 alors elle devient  2->1->4->3->6->5.
  3.  "entList *deplacerPairImpair(entList *tete)" fonction qui deplace les nombres pairs en avant de la liste et les nombres impairs apres, garder l'ordre des nombres pairs et des nombres impairs le meme.
  4. "void deplacerPosPairImpair(entList *tete)" fonction qui deplace les noeuds de position impair en avant de la liste et les noeuds de position pair apres. Si la liste est 10->32->20->43->40->70->65->88 alors elle devient 10->20->40->65->32->43->70->88 et si la liste est: 10->32->20->43->40->70->65 alors elle devient 10->20->40->65->32->43->70
  5. Tester dans la fonction main chacune des fonctions ci-dessus après avoir ajouté la fonction afficherListe

 

 

Solution