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