Le document décrit les listes simplement chaînées comme une structure de données où chaque élément pointe vers le suivant. Il présente les opérations de base sur les listes telles que la création, le parcours, l'insertion et la suppression d'éléments.
0 évaluation0% ont trouvé ce document utile (0 vote)
51 vues14 pages
Le document décrit les listes simplement chaînées comme une structure de données où chaque élément pointe vers le suivant. Il présente les opérations de base sur les listes telles que la création, le parcours, l'insertion et la suppression d'éléments.
Le document décrit les listes simplement chaînées comme une structure de données où chaque élément pointe vers le suivant. Il présente les opérations de base sur les listes telles que la création, le parcours, l'insertion et la suppression d'éléments.
Le document décrit les listes simplement chaînées comme une structure de données où chaque élément pointe vers le suivant. Il présente les opérations de base sur les listes telles que la création, le parcours, l'insertion et la suppression d'éléments.
Les pointeurs Variables dynamiques, pointeurs et prise d'adresse
Variables dynamiques, pointeurs et adresse
Un objet P de type pointeur sert à désigner des objets : les valeurs q'il prend sont des références (adresses en mémoire) à ces objets. Une variable dynamique (ou objet pointé ) est un objet crée pendant l'exécution d'un programme. Elle a un type et une valeur variable mais n'a pas de nom.
L'opérateur de prise d'adresse &, est un opérateur unaire qui s'applique à
une identi cation de variable ; il ne s'applique pas à des constantes. Exemple :
int x; int t[N]; /* &x a pour valeur, l'adresse de x &t[3] a pour valeur l'adresse du 4e élément de t &t est interdit (t est une constante) */ Rodrigue DJEUMEN Listes simplement chaînées 2 / 14 Les pointeurs Déclarateur de pointeur et adressage indirect
Déclarateur de pointeur et adressage indirect
Comme pour les tableaux, il n'existe pas de type pointeur. Une variable pointeur est dé nie par un déclarateur de pointeur. Exemple :
int *p; //déclare une variable p qui pointe sur les objets int *p[N]; //déclare un tableau de N pointeurs; int (*p)[N]; //déclare un pointeur sur un tableau; Le pointeur va servir à faire des indirections, et à obtenir des valeurs par indirection ; considérons : int x = 4, y = 5; int *p = &x; p est le pointeur d'adresse initialisé à l'adresse de x ∗p est la variable pointée de p , qui correspond à x *p = y; //affecte à x la valeur y Rodrigue DJEUMEN Listes simplement chaînées 3 / 14 Les pointeurs Opérateurs de pointeurs
Les opérateurs
Un pointeur qui ne pointe sur rien a pour valeur NULL (constante dé nie dans stdio .h) ;
Les aectations entre les pointeurs ayant des objets pointés de même types sont possibles. Les opérations arithmétiques suivantes sont dé nies sur les pointeurs : addition : Correspond à un déplacement dans le type pointé
soustraction d'un entier : -//-
soustraction de deux pointeurs : fournit le nombre d'éléments situés entre deux pointeurs
comparaisons :
void ∗ pu est appelé pointeur universel.
Rodrigue DJEUMEN Listes simplement chaînées 4 / 14 Les pointeurs Pointeurs et tableaux
Pointeurs et tableaux
Les déclarations suivantes char t [] et char ∗ p sont équivalentes, en ce
sens que t et p sont des variables de type chaîne. si t = ”une ” et p = ”deux , alors t [1] vaut 0 n0 , ∗t vaut 0 u 0 ; p [2] vaut 0 u 0 tandis que ∗p vaut 0 d 0 .
L'opérateur d'indexation sur les tableaux est une forme particulière
d'indirection pour les pointeurs : id [expr ] équivaut à ∗(id + (expr )) Le parcours d'un tableau peut s'écrire : for(i = 0; i <= N-1; i++) scanf(%c,*(t+i));
typedef struct{ short j,m; int a; } Date; et la déclaration d'un pointeur sur cette structure : Date *d; L'accès à un champ du pointeur d ce fait par : (*d).j = 2; (*d).m = 12; (*d).a = 2015; On peut également se servir de l'opérateur − > pour simpli er l'écriture et obtenir le même résultat : d->j = 2; d->m = 12; d->a = 2015; Rodrigue DJEUMEN Listes simplement chaînées 6 / 14 Les listes simplement chaînées Structures de données
Structure de donnée liste
Une liste est une suite d'un nombre variable d'objets de même type, appelés éléments de la liste. On dira donc qu'une liste simplement chaînée est une liste dans laquelle chaque élément, sauf le dernier, pointe vers son successeur. Pour dé nir une liste simplement chaînée, il faut : Décrire le type de ses éléments, qui est généralement un enregistrement constitué de deux parties, une partie information et un pointeur qui référence l'élément suivant, Dé nir un pointeur de tête qui permette d'accéder au premier élément de la liste. Exemple : Dé nir une liste simplement chaînée de nombres entiers. typedef struct Cellule{ int info; struct Cellule *suivant; }*ListeEntier;
Les listes simplement chaînées Opérations sur les listes simplement chaînées
Parcours d'une liste
void parcours(ListeEntier liste){
ListeEntier ptr; ptr = liste; //Sauvegarde de la tête de liste while (ptr != NULL){ printf("%d ",ptr->info); //Traitement à effectuer ptr = ptr->suivant; } }
Les listes simplement chaînées Opérations sur les listes simplement chaînées
Création en tête
Pour la création en tête, deux cas sont à considérer :
La liste est vide, dans ce cas, la création en tête revient simplement à ajouter un nouvel élément. La liste contient au moins un élément, dans ce cas, il faudrait insérer le nouvel élément en tête. ListeEntier creerTete(int t[],int n){ ListeEntier ptr,p; int i; ptr = NULL; for(i=0;i<n;i++){ p = malloc(sizeof(ListeEntier)); p->info = t[i]; p->suivant = ptr; ptr = p; p=NULL; } return ptr; }
Les listes simplement chaînées Opérations sur les listes simplement chaînées
Insertion en queue
Pour la création en queue, deux cas sont à considérer :
La liste est vide, dans ce cas, la création en queue revient simplement à ajouter un nouvel élément. La liste contient un ou plusieurs éléments, dans ce cas, il faudrait procéder au parcours de la liste jusqu'à la n avant de rajouter l'élément. ListeEntier insererQueue(int val,ListeEntier ptr){ ListeEntier p0; if (ptr == NULL){ ptr = malloc(sizeof(ListeEntier)); ptr->info = val; ptr->suivant = NULL; return ptr; } else{ p0 = ptr; while (p0->suivant != NULL) p0 = p0->suivant; p0->suivant = malloc(sizeof(ListeEntier)); p0->suivant->info = val; p0->suivant->suivant = NULL; return ptr; } } Rodrigue DJEUMEN Listes simplement chaînées 10 / 14 Les listes simplement chaînées Opérations sur les listes simplement chaînées
Suppression en tête
void supprimerTete(ListeEntier ptr){
ListeEntier p; p = ptr; ptr = ptr->suivant; free(p); }
Les listes simplement chaînées Opérations sur les listes simplement chaînées
Exercices
Dans le cadre de la manipulation des listes, proposer des algorithmes
(fonctions) pour : 1 Créer une liste en ajoutant les éléments en queue, 2 Insérer un élément à une position k quelconque de la liste, 3 supprimer un élément à une position k quelconque.
