pdf - e-book - archive - github.com

2.12  Listes Chaînées

2.12.1  Pointeurs et structures

Exercice 1

Créer un type st contenant un champ i de type int et un champ c de type char. Déclarez une variable p de type st*, allouez dynamiquement une variable de type st et faites pointer p dessus. Affectez à cette variable les valeurs 5 et 'a'. Affichez-les, libérez la mémoire.

2.12.2  Maniement du chaînage

Exercice 1 prise en main

Etant donné le programme

#include<stdio.h>

/**************************************************************/

typedef struct maillon
{
        int data;
        struct maillon* next;
}maillon;

/**************************************************************/

int main()
{
  maillon m, p;
  maillon* ptr;
  m.data = 1;
  m.next = &p;
  p.data = 2;
  p.next = NULL;
  for (ptr = &m ; ptr != NULL ; ptr = ptr->next)
    printf("data = %d\n", ptr->data);
  return 0;
}

Télécharger le fichier

Reprennez ce programme : créez deux maillons q et r en renseignant les champ data aux valeurs respectives 3 et 4, renseignez les valeurs next des maillons de sorte que la boucle for affiche

data = 1
data = 2
data = 3
data = 4

Exercice 2 tableaux

Reprennez le programme

#include<stdio.h>
#include<stdlib.h>

#define N 10

/**************************************************************/

typedef struct maillon
{
        int data;
        struct maillon* next;
}maillon;

/**************************************************************/

void printData(maillon* ptr)
{
  for( ; ptr != NULL ; ptr = ptr->next)
    printf("data = %d\n", ptr->data);
}

/**************************************************************/

int main()
{
  maillon* l;
  int i;
  l = (maillon*)malloc(N * sizeof(maillon));
  if (l == NULL)
    return -1;
  l->data = 0;
  for(i = 1 ; i < N ; i++)
    {
      (l + i)->data = i;
      (l + i - 1)->next = l + i;
    }
  (l + N - 1)->next = NULL;
  printData(l);
  free(l);
  return 0;
}

Télécharger le fichier

Modifiez le chaînage de sorte que les maillons soient disposés dans l’ordre inverse et que, par conséquent, ce programme affiche :

data = 9
data = 8
data = 7
data = 6
data = 5
data = 3
data = 4
data = 2
data = 1
data = 0

2.12.3  Opérations sur les listes chaînées

Pour les exercices suivants, vous utiliserez ce fichier source :

#include<stdio.h>
#include<stdlib.h>

#define N 10

/**************************************************************/

typedef struct maillon
{
  int data;
  struct maillon* next;
}maillon;

/**************************************************************/

void printLL(maillon* ptr)
{
  for( ; ptr != NULL ; ptr = ptr->next)
    printf("data = %d\n", ptr->data);
}

/**************************************************************/

maillon* creeMaillon(int n)
{
  maillon* l;
  l = (maillon*)malloc(sizeof(maillon));
  if(l == NULL)
    exit(0);
  l->data = n;
  l->next = NULL;
  return l;
}

/**************************************************************/

maillon* insereFinLL(maillon* l, int n)
{
  return NULL;
}

/**************************************************************/

maillon* copyLL(maillon* source)
{
  return NULL;
}

/**************************************************************/

maillon* reverseLL(maillon* l)
{
  return NULL;
}

/**************************************************************/

maillon* insereDebutLL(maillon* l, int n)
{
  maillon* first = creeMaillon(n);
  first->next = l;
  return first;
}

/**************************************************************/

maillon* initLL(int n)
{
  maillon* l = NULL;
  int i;
  for(i = n - 1 ; i >= 0 ; i--)
    l = insereDebutLL(l, i);
  return l;
}

/**************************************************************/

void freeLL(maillon* l)
{
  maillon* n;
  while(l != NULL)
    {
      n = l->next;
      free(l);
      l = n;
    }
}

/**************************************************************/

int main()
{
  return 0;
}

Télécharger le fichier

Exercice 3 ajout d’un élément à la fin

Erire le corps de la fonction suivante :

maillon* insereFinLL(maillon* l, int n)

Vous insérerez un maillon contenant la valeur n à la fin de la liste dont le premier élément est pointé par l. Vous retournerez un pointeur vers le premier élément de la liste.

Exercice 4 copie d’une liste chaînée

Erire le corps de la fonction suivante :

maillon* copyLL(maillon* source)

Vous copierez la liste l et retournerez un pointeur vers le premier élément de la copie. Vous avez le droit d’utiliser insereFinLL.

Exercice 5 inversion de l’ordre des éléments

Ecrivez un sous-programme qui inverse l’ordre des éléments d’une liste chaînée, et qui retourne un pointeur sur le premier élément de la liste nouvellement formée.

2.12.4  Listes doublement chaînées

Pour les exercices suivants, vous pouvez utiliser ce fichier source :

#include<stdio.h>
#include<stdlib.h>

#define N 10

/**************************************************************/
typedef struct dmaillon
{
  int data;
  struct dmaillon* previous;
  struct dmaillon* next;
}dmaillon;

/**************************************************************/

typedef struct dLinkedList
{
  struct dmaillon* first;
  struct dmaillon* last;
}dLinkedList;

/**************************************************************/

/*
  Affiche les elements d'une liste chainee.
 */

void printDLL(dLinkedList* dl)
{
}

/**************************************************************/

/*
  Libere tous les maillons, puis libere dl.
 */

void freeDLL(dLinkedList* dl)
{
}

/**************************************************************/

/*
  Alloue la memoire pour une dLinkedList, 
  initialise les pointeurs a NULL   
*/

dLinkedList* makeDLL()
{
  return NULL;
}

/**************************************************************/

/*
  Cree un maillon contenant la valeur n.
 */

dmaillon* makeDMaillon(int n)
{
  return NULL;
  
}

/**************************************************************/

/*
  Accroche le maillon m a la fin de la liste chainee dl
 */

void appendDMaillonDLL(dLinkedList* dl, dmaillon* m)
{
}

/**************************************************************/

/*
  Accroche le maillon m au debut de la liste chainee dl
 */

void pushDMaillonDLL(dLinkedList* dl, dmaillon* m)
{
}

/**************************************************************/

/*
  Ajoute a la fin de dl un maillon contenant la valeur n.
 */

void appendIntDLL(dLinkedList* dl, int n)
{
}

/**************************************************************/

/*
  Ajoute au debut de dl un maillon contenant la valeur n.
 */

void pushIntDLL(dLinkedList* dl, int n)
{
}

/**************************************************************/

/*
  Place dans la liste doublement chainee 
  les valeurs {0, ..., n}
 */

void initDLL(dLinkedList* dl, int n)
{
}

/**************************************************************/

/*
  Inverse l'ordre des elements de dl.
 */

void reverseDLL(dLinkedList* dl)
{
}

/**************************************************************/

/*
  Retourne une copie de source.
 */

dLinkedList* copyDLL(dLinkedList* source)
{
  return NULL;
}

/**************************************************************/

/*
  Concatene fin a la suite de debut, vide la liste fin.
 */

void concatDLL(dLinkedList* debut, dLinkedList* fin)
{
}

/**************************************************************/

int main()
{
  return 0;
}

Télécharger le fichier

Nous définissons comme suit une liste doublement chaînée

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define N 10

/**************************************************************/

typedef struct dmaillon
{
  int data;
  struct dmaillon* previous;
  struct dmaillon* next;
}dmaillon;

/**************************************************************/

typedef struct dLinkedList
{
  struct dmaillon* first;
  struct dmaillon* last;
}dLinkedList;

Implémentez les fonctions suivantes :

  1. void printDLL(dLinkedList* dl) affiche les éléments d’une liste chaînée.
  2. void freeDLL(dLinkedList* dl) libère tous les maillons, puis libère dl.
  3. dLinkedList* makeDLL() alloue la mémoire pour une dLinkedList, initialise les pointeurs à NULL
  4. dmaillon* makeDMaillon(int n) crée un maillon contenant la valeur n.
  5. void appendDMaillonDLL(dLinkedList* dl, dmaillon* m) accroche le maillon m à la fin de la liste chaînée dl
  6. void pushDMaillonDLL(dLinkedList* dl, dmaillon* m) accroche le maillon m au début de la liste chaînée dl
  7. void appendIntDLL(dLinkedList* dl, int n) ajoute à la fin de dl un maillon contenant la valeur n.
  8. void pushIntDLL(dLinkedList* dl, int n) ajoute au début de dl un maillon contenant la valeur n.
  9. void initDLL(dLinkedList* dl, int n) place dans la liste doublement chaînée les valeurs {0, ..., n−1}
  10. void reverseDLL(dLinkedList* dl) inverse l’ordre des éléments de dl.
  11. dLinkedList* copyDLL(dLinkedList* source) retourne une copie de source.
  12. void concatDLL(dLinkedList* debut, dLinkedList* fin) concatène fin à la suite de debut, vide la liste fin .

2.12.5  Fonctions récursives et listes chaînées

Complétez le code sources suivant. Les boucles sont interdites !

#include<stdio.h>
#include<stdlib.h>

/*
  Dans toutes les fonctions à partir d'insere, il est interdit de
  creer des maillons, toutes ces operations doivent se faire 
  par modification du chainage et non par recopie.
*/

typedef struct lls
{
  int data;
  struct lls* next;
}ll;

/********************************************************/

/*
  Alloue dynamiquement et initialise un maillon avec les 
  valeurs data et next, retourne son adresse.
*/

ll* cree(int data, ll* next)
{
  ll* maillon = (ll*)malloc(sizeof(ll));
  if (maillon == NULL)
  {
    printf("Plus de mémoire");
    exit(1);
  }
  maillon->data = data;
  maillon->next = next;
  return maillon;
}

/********************************************************/

/*
  Affiche le maillon l
*/

void affiche(ll* l)
{
  printf("%d -> ", l->data);
}

/********************************************************/

/*
  Affiche, dans l'ordre, tous les maillons de la liste l.
*/

void afficheTout(ll* l)
{ 
  if (l != NULL)
    {
      affiche(l);
      afficheTout(l->next);
    }
  else
    printf("\n");
}

/********************************************************/

/*
  Affiche en partant de la fin tous les maillons 
  de la liste l.
*/

void afficheALEnvers(ll* l)
{
  if (l != NULL)
    {
      afficheALEnvers(l->next);
      affiche(l);
    }
}

/********************************************************/

/*
  Detruit tous les maillons de la liste *l, met ce pointeur 
  a NULL.
*/

void detruit(ll* l)
{
  if (l != NULL)
    {
      detruit(l->next);
      free(l);
    }
}

/********************************************************/

/*
  Retourne la liste n -> n-1 -> ... -> 2 -> 1
*/

ll* entiersALEnvers(int n)
{
  if (n < 1)
    return NULL;
  return cree(n, entiersALEnvers(n - 1));
}

/********************************************************/

/*
  Retourne la liste 1 -> 2 -> ... -> n
*/

ll* entiers(int n)
{
  return NULL;
}

/********************************************************/

/*
  Insere le maillon x dans la liste l, supposee triee.
*/

ll* insere(ll* l, ll* x)
{
  return NULL;
}

/********************************************************/

/*
  Tri la liste l avec la methode du tri par insertion, retourne
  l'adresse du premier element de la liste triee.
*/

ll* triInsertion(ll* l)
{
  return NULL;
}

/********************************************************/

/*
  Repartit les elements de l entre les listes l1 et l2. 
  ex : l = 1 -> 2 -> 3 -> 4 -> 5 nous donne
  l1 = 5 -> 3 -> 1et l2 = 4 -> 2
*/

void split(ll* l, ll** l1, ll** l2)
{
}

/********************************************************/

/*
  Retourne l'interclassement des listes l1 et l2, supposees triees.
*/

ll* interclasse(ll* l1, ll* l2)
{
  return NULL;
}

/********************************************************/

/*
  Trie l avec la methode du tri fusion, retorune l'adresse
  du premier element de la liste triee.
*/

ll* triFusion(ll* l)
{
  return NULL;
}

/********************************************************/

/*
  Pour tester les fonctions...
*/

int main()
{
  ll* maillon = entiersALEnvers(10);
  afficheTout(maillon);
  afficheALEnvers(maillon);
  detruit(maillon);
  return 0;
}

Télécharger le fichier