TP N°3

Les Listes Chainées Bidirectionnelles

Exercice :

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

1. "ajoutete"  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. "creerFiFo" qui crée une liste bidirectionnelle de n entiers en FIFO (utiliser "ajoutete" et "ajoutAprès" )
4. "creerFiFo2" qui crée une liste bidirectionnelle de n entiers en FIFO (utiliser uniquement "ajoutAprès" )
5. "afficherListeTete" qui parcourt une liste bidirectionnelle a partir de la tete et affiche tous les éléments de la liste
6. "afficherListeQueue" qui parcourt une liste une liste bidirectionnelle a partir de la  queue et affiche tous les élément s de la liste

6. "supprimerTete" qui supprime le premier élément d’une liste bidirectionnelle

7. "supprimerAutreQueTete" qui supprime l’ élément après un élément d’adresse donne p d’une liste bidirectionnelle

8. "rechercherVal" qui recherche la valeur val dans une liste bidirectionnelle et retourne son adresse si val existe ; retourne NULL si val n’existe pas dans la liste
9. "supprimerVal" qui supprime l’élément dont la valeur est val dans une liste bidirectionnelle (utiliser "rechercherVal", "supprimerTete" et "supprimerAutreQueTete")
10. "reverseListBD" qui inverse une liste bidirectionnelle.
11. "permuterNListBD" qui permute le n eme noeud a partir de tete avec le n eme noeud a partir de la queue (en changeant les chainages - il faut que n ne soit pas plus grand que le nombre de noeuds dans la liste).
12. "void   sortedInsert(BDList *plistTrie, entList *new_node)": fonction sortedInsert() qui etant donne une liste BD triee par ordre croissant de tete et queue donnes dans le parametre list de type BDList et un noeud new_node insert new_node dans la liste a la bonne position pour avoir la liste toujours triee par ordre croissant.
13. "BDList insertionSort(BDList bdlist)": fonction qui implémente le tri par insertion d'une liste BD. Utiliser la fonction précédente sortedInsert(). La fonction retourne la tête et la queue de la liste triée dans BDList.
14. "void afficherSommePair(BDList list, int som)": Fonction qui etant donné une liste BD triée par ordre croissant affiche toutes les paires des noeuds dont la somme des éléments est égale à som. Utiliser l'idée suivante: avoir un pointeur pTete qui pointe vers le 1er noeud de la liste et pQueue qui pointe vers le dernier noeud de la liste; si la somme des éléments des noeuds pointés par pTete et pQueue est plus petite que som alors pTete doit avancer vers le suivant, si cette somme est plus grande que som alors pQueue doit se déplacer vers le précédent, si cette somme est égale à som alors on a trouve une paire et pTete avance vers le suivant et pQueue vers le précédent et on refait la même chose avec les nouveaux noeuds.
15. "void     partitionner(BDList *pbdlist, int x)": Fonction qui étant donné une liste BD et un entier x partitionne cette liste en mettant les valeurs < x à l'avant de la liste et les valeurs >= x à l'arriere de la liste. On garde le même ordre des éléments qu'ils soit mis en avant de la liste ou à l'arriere de la liste. Par exemple si la liste initiale est:  13<->11<->5<->29<->6<->12<->17<->10 et X est 13 alors la liste devient: 11<->5<->6<->12<->10<->13<->29<->17. Utiliser l'idée suivante: créer 2 listes (sans allouer de l'espace mais en changeant les chainages de la liste originale). Une liste qui contient les éléments plus petit que x et une liste qui contient les éléments superieurs ou égales à x; ensuite fusionner les 2 listes. Noter qu'on peut avoir une des 2 listes vide si x est plus petite ou bien plus grande que toutes les valeurs dans la liste originale.
16. "void     partitionner2(BDList *pbdlist, int x)": Fonction qui fait la même chose que la fonction précédente partitionner() mais en utilisant l'idée suivante: chercher à partir du premier élément de liste le premier élément de la liste dont la valeur est superieur ou égale à x. A partir de cet élément parcourir la liste jusqu'au dernier élément et enlever les éléments qui sont inférieur à x de leur position courante et les insérer juste avant le premier élément superieur ou egale à x.
17. "void  supprimerDupliquerTrie(BDList *pbdlist)": Fonction qui supprime les dupliqués d'une liste BD triée (utiliser la fonction supprimerAutreQueTete). Si la liste est: 1<->1<->2<->2<->2<->2<->4<->6<->12<->12<->12 alors la liste devient: 1<->2<->4<->6<->12
18. "void diviseListBD2(BDList list, BDList *pliste1, BDList *pliste2)": Fonction qui divise la liste list en 2 listes liste1 et liste2, liste1 contenant la 1ere moitié de la liste et liste2 contenant la 2eme moitié de la liste. S'il y'a un nombre impair d'éléments dans la liste alors liste1 contiendra un élément de plus que liste2. Si liste est: 1<->2<->3<->4<->5<->6 alors liste1 sera: 1<->2<->3 et liste2 sera: 4<->5<->6 et si liste est: 1<->2<->3<->4<->5 alors liste1 sera: 1<->2<->3 et liste2 sera: 4<->5. On veut faire un seul parcourt de la liste. Utiliser l'idée suivante: avoir un pointeur p1 qui parcourt la liste list d'un pas et un pointeur p2 qui parcourt la liste list de 2 pas. Lorsque p2 atteint la fin de la liste alors p1 sera au milieu de la liste.  Une autre maniere est d'avoir 2 pointeurs: un pointeur qui parcourt la liste a partir de la tete et un autre pointeur qui parcourt la liste a partir de la queue. On s'arrêtera lorsque les 2 pointeurs se rencontreront au milieu de la liste ou bien à une position prés dependemment si la liste a un nombre pair ou impair d'éléments.
19. "void somme2ListesBD(BDList list1, BDList list2, BDList *plist)" fonction qui fait la somme de 2 listes de chiffres entiers qui representent chacun un nombre en créant une liste qui represente la somme des 2 nombres. Si List 1: 5<->1<->2   represente nbr 512 et List 2: 8<->3<->1  represente nbr 831 alors cette fonction crée list: 1<->3<->4<->3  qui represente le nbr 1343 (egale a 512 + 831).
20. Ecrire la fonction main() et tester les differentes fonctions ci-dessus. Noter que pour verifier que les fonctions marchent. après appel de la fonction il faut afficher la liste à partir de la tête et aussi afficher la liste à partir de la queue pour verifier que les chainages des suivants sont corrects et aussi que les chainages des précédents sont corrects. Pour chaque fonction il faut tester plusieurs scénarios: le cas générale ainsi que les cas particulier.

Solution