Les enregistrements Les enregistrements : Définition : Un enregistrement est

Les enregistrements Les enregistrements : Définition : Un enregistrement est un type de données défini par l'utilisateur et qui permet de grouper un nombre fini d'éléments (ou champs) de types éventuellement différents. Déclaration du type : type Nom_type = Enregistrement champ 1 : Type 1 - - - - champ n : Type n Fin Nom_Type Déclaration des objets (variables) utilisant ce type : var identificateur_objet : Nom_type Les enregistrements : Exemple type Fiche = enregistrement nom, prénom : Chaîne sexe : Caractère numéro : Entier non signé moyenne : Réel num_cin : Entier long Fin Fiche var etudiant : Fiche Les enregistrements : L'affectation de valeurs aux différents champs d'une variable de type enregistrement se fait par une opération de type : variable.champ ← valeur Exemple etudiant.nom ← " T ouati" etudiant.prénom ← " Amir" etudiant.sexe ← "H" etudiant.numéro ← 18 etudiant.moyenne ← 13.25 etudiant.num_cin ← 12345678 Les enregistrements : Action de lecture : Lire (variable.champ) Exemple : Ecrire ("Entrer le nom de l’étudinat : "), Lire (etudiant.nom) Les enregistrements : Application Dans cet exercice nous avons un enregistrement qui contient : le N° d’une phrase, la phrase elle-même et un tableau de 26 cases dont chaque case contient la fréquence d’apparition de chaque lettre de l’alphabet . ( la 1ère case concerne le ‘A’ , la 2ième le ‘B’,…). Le problème consiste donc à donner un N° à la phrase puis à lire la phrase elle même. Puis on calculera la fréquence d’apparition de chaque lettre de l’alphabet que l’on rangera dans un tableau. Lequel sera mis à son tour dans l’enregistrement. On affiche ensuite le N° et le tableau des fréquences qui se trouvent dans l’enregistrement. Les enregistrements en c Déclaration de structure Première méthode Déclaration du nouveau type typedef struct { Type champ 1; - - - - Type champ n; } Nom_type; Déclaration de variables Nom_type nom_var1[,nom_var2, ….,nom_varp]; Les enregistrements en c Déclaration de structure Deuxième méthode Déclaration de variables sans déclarer un nouveau type struct { Type champ 1; - - - - Type champ n; } nom_var1[,nom_var2, ….,nom_varp]; Les enregistrements en c Déclaration de structure Troisième méthode Déclaration de nouveau type et variables en même temps struct Nom_type { Type champ 1; - - - - Type champ n; } nom_var1[,nom_var2, ….,nom_varp]; on peut utiliser le nom de structure Nom_type pour déclarer d'autres variables struct Nom_type v1, v2, v3; Les enregistrements en c Exemple Première méthode typedef struct { char nom[20]; char prenom[20]; int no_employe; } personne; personne p1,p2; Deuxième méthode struct { char nom[20]; char prenom[20]; int no_employe; } p1,p2; Impossible de déclarer d’autres variables de même type Troisième méthode struct personne { char nom[20]; char prenom[20]; int no_employe; } p1,p2; struct personne pers1, pers2, pers3; Les enregistrements en c Initialisation de structure : Une structure peut être initialisée par une liste d'expressions constantes Nom_type nom_var = {val1, val2, val3,….}; Exemple : personne p = {"Jean", "Dupond", 7845}; Opérateurs sur les structures Accès aux membres des structures : l'opérateur de sélection de membre est le « . » (point) Affectation de structures : On peut affecter une structure à une variable structure de même type personne p1,p2; ... p1 = p2; Les enregistrements en c Tableaux de structures Une déclaration de tableau de structures se fait de la même façon que la déclaration d'un tableau dont les éléments sont de type simple. Nom_type nom_var[Taille] Exemple : - personne T[100]; - accéder au nom de la personne qui a l'index i dans t : T[i].nom Pointeurs vers une structure Déclaration : Nom_type *nom_var; Exemple : personne pers; //pers est une variable de type struct personne personne *p; //p est un pointeur vers une struct personne p = &pers; Allocation d'espace pour les structures : p = malloc(sizeof(struct personne)); Les enregistrements en c Application 1) Proposer une structure pour modéliser un nombre complexe . 2) Ecrire un programme en C qui lit deux nombres complexes C1 et C2 et qui affiche ensuite leur somme et leur produit. Les listes chaînées Les listes chaînées Une liste chaînée permet de stocker un ensemble de valeur du même type, comme un tableau. Contrairement au tableau, la taille de la liste chaînée peut varier au cours du temps. En effet, contrairement au tableau, la liste n'est pas allouée en une seule fois, mais chaque élément est alloué indépendamment, sous la forme d'un maillon. Notion de maillon L'élément de base d'une liste chaînée s'appelle le maillon. Il est constitué : d’un ou des champs de données et d'un pointeur vers un maillon. Les listes chaînées Notion de liste chaînée Dans une liste chaînée, chaque élément pointe, à l'aide d’un pointeur (suivant) vers l'élément suivant dans la liste ; le dernier élément, par définition, n'a pas de suivant, donc son pointeur suivant vaut NIL. Les listes chaînées Pour manipuler une liste chaînée, nous manipulons un pointeur sur le premier élément; comme chaque élément « connaît » l'élément suivant, on peut ainsi accéder à tous les éléments de la liste. Si le pointeur premier vaut NIL, on considérera naturellement que la liste est vide (elle ne contient aucun élément). Le premier maillon de la liste est appelé tête, le dernier maillon de la liste est appelé queue. Les listes chaînées Implémentation du type liste chaînée Un maillon est composé de deux champs de types hétérogènes, il est implémenté donc en utilisant les enregistrements de la manière suivante : Déclaration du maillon type maillon = Enregisterment valeur : type suivant : ^maillon Fin maillon ^maillon Les listes chaînées Autre modélisation du type liste chaînée Un maillon est composé de deux champs : Un champ de type enregistrement contenant les champs de données Un pointeur vers le maillon suivant Déclaration du maillon type data = Enregisterment val1 : type val2 : type … Fin data maillon = Enregisterment champ: data suivant : ^maillon Fin maillon Exemple En C typedef struct { int num; char nom[30]; char prenom[30]; }data; typedef struct maillon{ data champ; struct maillon*suiv; }liste; Les listes chaînées Définition du type liste type liste : maillon Déclaration d’une variable de type liste Une fois le type liste est défini on peut déclarer une variable de type pointeur sur liste de la manière suivante p : ^liste Accès aux champs d’un maillon d’une liste Si p est un pointeur sur une variable de type liste, p^ est la variable pointée par p. cette variable est un enregistrement, pour accéder à ses champs on utilise l’opérateur ". " p^. valeur p^. suivant Les listes chaînées Initialisation d’une liste à Nil Une liste est vide si le pointeur du premier maillon vaut Nil p ← Nil Insertion d’une valeur en tête d’une liste Ecrire la procédure InsertTete qui permet d’insérer une valeur val en tête d’une liste chaînée donnée par l’adresse de son premier élément (premier). Notons qu’après l’insertion la valeur du premier sera changée, donc le passage doit se faire par adresse. Les listes chaînées Principe 1. Créer un maillon d’adresse p1 contenant la valeur val  p1 ← nouveau(^liste) p1^.valeur ← val 2. Créer un lien entre le nouveau maillon et la tête de la liste de telle sorte que p soit le suivant de p1  p1^.suivant ← premier 3. Le maillon p1 devient le premier maillon de liste p  premier ← p1 Les listes chaînées Algorithmique PROCEDURE InsertTete(var premier : ^liste, val : entier) var nouvElt: ^liste Début nouvElt ← nouveau(^liste) nouvElt ^.valeur ← val nouvElt ^.suivant ← premier premier ← nouvElt Fin type maillon = Enregistrement valeur : entier suivant : ^maillon Fin maillon liste : maillon Les listes chaînées En C liste* InsertTete(liste *premier,int val){ liste *nouvElt; nouvElt =(liste*)malloc(sizeof(liste)); nouvElt->valeur=val; nouvElt->suivant=premier; return nouvElt; } typedef struct maillon{ int valeur; struct maillon*suivant; }liste; Les listes chaînées En C Appel : void main() { liste*lst; lst=(liste*)malloc(sizeof(liste)); lst->valeur=1; lst->suivant=NULL; lst=InsertTete(lst,0); } Les listes chaînées Exercice Soit la structure suivante : typedef struct student { char lastname[30]; char firstname[20]; int group; } Student_t; Construire un maillon d’une liste chainée en utilisant la structure précédente. Ecrire une fonction en C permettant d’insérer en tête dans cette liste chaînée. Déclarer une variable de type la liste chainée définie et la remplir. Ecrire une fonction en C permettant d’afficher les valeurs de tous les maillons d’une liste. uploads/Finance/ algorithmique-et-structures-de-donnees-part3.pdf

  • 30
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager
  • Détails
  • Publié le Jan 22, 2022
  • Catégorie Business / Finance
  • Langue French
  • Taille du fichier 0.3003MB