Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

106 512 Problèmes corrigés - Pascal CHAPITRE 7 FICHIERS, POINTEURS ET LISTES Fi

106 512 Problèmes corrigés - Pascal CHAPITRE 7 FICHIERS, POINTEURS ET LISTES Fichiers à acces direct en turbo-pascal En turbo-pascal sur PC le type "file of ... " permet les fichiers de longueur variable, il faut pour utiliser des fichiers sur disquette connaître les ordres de création "rewrite", d'ouverture "reset" de fermeture "close" etc... On se limite volontairement dans le programme de carnet d'adresses, aux opérations élémentaires sur un fichier à accès direct (chaque élément se trouve à une adresse précise), aller chercher une fiche, en créer une nouvelle, et lire la totalité. Les différentes instructions de manipulation de fichiers sont commentées au fur et à mesure dans le programme. program adresses ; { Fichier à accès direct } type individu = record nom, prenom : string [20]; adresse : string [80]; telephone: string [12] end; fichier = file of individu; {On définit deux types d'objets, les individus et les fichiers} var G : fichier; X : integer ; procedure creation (var F : fichier); { ne servira qu'une seule fois } begin rewrite (F); close (F) end; procedure ecriture (var F : fichier); { Ecrit une ou plusieurs nouvelles fiches dans F } var A : individu ; C : char; begin reset (F); C := 'O'; seek (F, filesize (F)); { permet de se positionner sur la fin du fichier en cherchant (seek) dans F la dernière position (filesize(F) donne le nombre de fiches)."filesize" est inconnu sur Macintosh} with A do while C = 'O' do begin write ('NOM: '); readln (nom); write ('PRENOM: '); readln (prenom); write ('ADRESSE: '); readln (adresse); write ('TEL: '); readln (telephone); write (F, A);{ Ecriture dans le fichier F et non sur l'écran} write ('AUTRE ? (O/N) ') ; readln (C) end; { With A do... est une instruction dont il n'a pas été question jusqu'à présent, elle permet de ne pas répéter à chaque fois A.nom, A.prenom etc...} close (F) end; { fin de la procédure d'écriture } procedure edition (A : individu); {réalise une édition à l'écran de l'individu A } var I : integer; begin writeln (A.nom,' ', A.prenom,' ', A.adresse, ' TEL:', A.telephone); for I := 1 to 80 do write ('-') {Place une ligne séparatrice de tirets} end; procedure lecture (var F : fichier); {Lecture complète du fichier F} var A : individu ; begin reset (F); repeat read (F,A); {lecture depuis F sur la disquette et non depuis le clavier, "read" et "write" avancent toujours d'un cran la position courante dans le fichier, après leur exécution, cela est très commode pour la procédure présente } write ( filepos (F),' ') ; edition (A) until eof ; { répéter jusqu'à la fin du fichier (end of file)} writeln ('Il y a ', filesize (F), ' fiches.'); close (F) end; Chapitre 7 - Fichiers, pointeurs et listes. 107 begin assign (G, 'ADRESSES.DAT'); { Permet d'assigner à la variable globale G le nom précis du fichier on peut prévoir de demander le nom (commande propre au turbo-pascal sur PC)} writeln (' Fichier d adresses. '); write (' 0: Création 1: Lecture complète 2: Nouvelle fiche '); readln (X); case X of 0 : creation (G); 1 : lecture (G); 2 : ecriture (G) end; { "recherche" et "destruc" restent à écrire } end. Ce programme ne fournit donc qu'une initiation, naturellement les gros fichiers posent bien d'autres problèmes mais on trouvera en exercice des idées d'améliorations. Variables dynamiques ou pointeurs Jusqu'à présent lorsqu'on définissait une variable X entière en l'affectant de la valeur 3, on avait de façon "statique" durant toute l'éxecution du programme, une place déterminée en mémoire où étaient rangés le nom X et la valeur 3 (éventuellement modifiée). Pour une variable dynamique, sa création ou destruction pourra être faite durant l'éxecution suivant les besoins, on ne pourra y accéder que par une "variable pointeur" contenant son adresse en mémoire. Un pointeur est défini par exemple par var Y : ^integer; pour un pointeur sur un entier, et le contenu de ce vers quoi elle pointe sera accessible par Y^ qui est donc un entier. La procedure de création d'un pointeur est new (Y), cette nouvelle variable Y est alors rangée dans une pile spéciale appelée "tas". Sa destruction est opérée par dispose (Y), en ce cas sa place dans le tas est récupérée. Le fait de ne pointer sur rien est décidé (quelquesoit le type du pointeur) par Y := nil Exemple, si var X, Y : ^integer ; a été déclaré, Les trois séquences d'instructions new (X); X^ := 5; Y := X; write (Y^) new (X); new (Y); X^ := 5; Y := X; write (Y^) new (X); X^ := 5; Y := X; dispose (X); write (Y^) donneront toutes 5, par contre : new (X); X^:= 5; Y := X; Y^:= 3; write (X^); donnera 3. Utilisation pour la construction d'une liste chaînée On devra pour un exemple minimal parler de "doublets" c'est à dire d'une partie information et d'une partie "pointeur" pour aller chercher le doublet suivant. Ainsi pour une liste d'entiers on définiera deux types (se définissant récursivement) : type ptr = ^doublet ; doublet = record numero : integer; suivant : ptr ; Exemple : tenue à jour d'une course On souhaite en temps réel, à chaque arrivée de coureur, entrer ce coureur (son numéro de dossard, son nom et le temps qu'il vient de faire), l'insérer dans la liste de ceux qui sont déjà arrivés et réafficher le classement provisoire. On dispose donc en permanence de la liste des coureurs ayant concouru, triée par ordre de temps croissant. type ptr = ^doublet; {doit être défini avant} coureur = record num : integer; nom : string[12]; temps : real end; doublet = record individu : coureur; suivant : ptr end; var tete, nouveau : ptr; procedure arrivee (var nouveau : ptr); {crée un nouvel individu à son arrivée} begin nouveau^.suivant := nil; write (' Quel numéro ') ; readln (nouveau^.individu.num); write (' Quel temps ') ; readln (nouveau^.individu.temps); write (' Quel nom ') ; readln (nouveau^.individu.nom) end; 108 512 Problèmes corrigés - Pascal procedure insertion (var tete : ptr; nouveau : ptr); {suivre la figure ci-dessus} var courant : ptr; {pointeur local servant à parcourir la liste} begin courant := tete; if tete = nil then tete := nouveau {cas du tout premier concourant} else begin while (courant^.suivant <> nil) and (courant^.suivant^.individu.temps < nouveau^.individu.temps) do courant := courant^.suivant; if courant = tete then begin nouveau^suivant := tete ; tete := nouveau end else begin nouveau^.suivant := courant^.suivant ; courant^.suivant := nouveau end end {nouveau a été intercalé entre courant et le suivant du courant} end; Autre version : procedure insertion (var liste : ptr; nouv : ptr) ; var pred : ptr; {on s'intéresse au précédent "pred"} begin new (pred); pred^.suivant := liste; liste := pred; while (pred^.suivant <> nil) and (nouv^.temps > pred^.suivant^.temps) do pred := pred^.suivant ; nouv^.suivant := pred^.suivant; pred^.suivant := nouv; liste := liste^.suivant {on rétablit les choses} end; procedure resultat (tete : ptr); var courant : ptr; begin courant := tete; writeln ('Voici la liste des coureurs arrivés '); while courant <> nil do begin writeln (courant^.individu.num, ' ', courant^.individu.nom, ' ', courant^.individu.temps); courant := courant^.suivant end end; Le programme sera (avec les déclarations d'usage) : new (tete); while fini = 'n' do begin arrivee (nouveau); insertion (tete, nouveau); resultat (tete); write ('fini ? (o/n) '); readln (fini) end Exemple de construction d'un arbre binaire Pour définir une arborescence de caractères où chaque noeud possède un fils droit et un fils gauche, il suffit de déclarer : type ptr = ^triplet; triplet = record noeud : char; filsdroit, filsgauche : ptr end; Sa construction pourra se faire (dans l'ordre racine-gauche-droite) par : procedure consrtuc (var A : ptr); var chg, chd : char; begin write ('Pour ', A^.noeud, ' Fils gauche '); read (chg); new (A^.filsgauche); if chg = chr(13) then A^.filsgauche := nil else A^.filsgauche^.noeud := chg ; write (' Fils droit '); readln (chd); new (A^.filsdroit) ; if chd = chr (13) then A^.filsdroit := nil else A^.filsdroit^.noeud := chd; if chg <> chr(13) then construc (A^.filsgauche); if chd <> chr(13) then construc (A^.filsdroit) end; begin new(A); write ('Donnez la racine '); readln (A^.noeud); construc (A) end. Chapitre 7 - Fichiers, pointeurs et listes. 109 Le parcours racine-gauche-droite d'une arborescence se fera par : procedure parcours (A : ptr); begin if A <> nil then begin write (A^.noeud); parcours (A^.filsgauche); parcours (A^.filsdroit) end end; Problème général du parcours avec retour en arrière Dans une arborescence de racine n (en fait à chaque noeud n se pose le même problème), les paramètres intervenant sont le chemin ch suivi au dessus de n (donc la liste vide si n est vraiment la racine), l'ensemble des solutions sol déjà obtenues, l'ensemble "fr" des frères de droite de n et la liste "efr" des ensembles de frères non encore explorés correspondant à chacune des étapes du chemin ch. (Ici n n'est pas dans ch, par n&ch, nous uploads/Litterature/ ch7-fichiers-pointeurs-et-listes.pdf