GPA665 PDF Ainsi cette méthode aide à

PILES FILES ET LISTES CHAÎNÉES

- top():. Retourne l'objet du dessus de la pile sans le retirer; si la pile est vide

Exercices avec Solutions

Si Non FDF(G) Alors Ecrire(F0) Fsi ;. Fait ;. Fermer(G) ; Fermer(F) ;. Fin ;. Page 65. Les Listes Chainées. Exercices Corrigés d'Algorithmique – 1ére Année MI

Corrigé de lexamen de Structures de données Session Ordinaire

Exercice 1. 1. Quatre exemples de structures de données linéaires : les tableaux les listes chaînées

Langage C : énoncé et corrigé des exercices IUP GéniE

1.2 CHAINES DE CARACTERES . Liste - Entier- > prem=Liste - Entier- > der=Liste - Entier- > co u r = E l ...

Algorithmes et structures de données : TD 8 Corrigé - Tableaux

Algorithmes et structures de données : TD 8 Corrigé. Tableaux dynamiques - Listes linéaires simplement chaınées - Complexité Comparer avec l'exercice ...

Talib24

1.4 LISTE CHAINEE. Le premier exercice est corrigé. Exercice 33 Ecrire un programme qui gère les listes chainées. Pour cela vous créerez un type de structure

Questionnaire dexamen+Corrigé - INF1101 Algorithmes et structure

INF1101 --- Examen final +Corrigé--- Automne 1999. Page 7 de 16 La classe LChaindc représente une liste doublement chaînée circulaire avec élément factice.

Solutionnaire pour les exercices sur les listes chaînées et les files

Voici une méthode pour insérer un élément au début d'une liste simplement chaînée. On garde le pointeur de la Tête dans un pointeur temporaire.

Exercices des chapitres 9 10 et 11 Sommaire

On considérera dans les exercices sauf cas contraire une liste chaînée de ce type : Corrigés. Algorithmique. Exercices ch. 9

Exercices des chapitres 9 10 et 11 Sommaire

07-**- Procédure de suppression d'un élément d'une liste chaînée à une position donnée . Corrigés. 01-**- Fonction de comptage dans une liste chaînée .

Algorithmes et structures de données : TD 8 Corrigé - Tableaux

Algorithmes et structures de données : TD 8 Corrigé. Tableaux dynamiques - Listes linéaires simplement cha?nées - Complexité asymptotique. Rappel :.

Langage C : énoncé et corrigé des exercices IUP GéniE

Langage C : énoncé et corrigé des exercices 1.2 CHAINES DE CARACTERES . ... Les exercices 1 à 1 6 20 à 2 5

PSD 2015/2016 Corrigé type série 4- Listes chainées 1 Exercice 1

Corrigé type série 4- Listes chainées Ecrire un sous algorithme qui inverse une liste chaînée dont la tête est tête. Procedure invers (Var tete : P) ;.

Exercices avec Solutions

Les Tableaux (Vecteurs – Matrices) et Chaines de caractères . Les Listes Chainées . ... Exercices Corrigés d'Algorithmique – 1ére Année MI 5. EXERCICE 1.

SUJET + CORRIGE

Liste doublement chainée. 9. Total: 30. Exercice 1 : Mise en bouche. (7 points). (a) (1 point) Deux nombres sont opposés si leur somme est égale `a 0.

Exercices corrigés

Affichez chaque élément d'une liste en utilisant une boucle for. Écrire une fonction compterMotsayant un argument (une chaîne de caractères) er qui.

Corrigé E.D. Algorithmes et Structures de Données n° 2 Thème : Les

Corrigé E.D. Algorithmes et Structures de Données n° 2. Thème : Les Listes. Exercice II.1 Manipulation d'une liste chaînée circulaire r.valeur = d3.

TD n 9 - Correction

Une liste est donc une chaine d'élément (d'o`u le terme liste chainée). Dans toute la suite du TD nous allons travailler avec les 2 classes suivantes :.

TD 7 - Les listes II Structures de données (IF 122) Comme la

Dans une liste doublement chaînée chaque cellule contient à la fois un pointeur vers l'élément suivant (suiv) et un pointeur vers l'élément précédent ( p re c )

Solutionnaire pour les exercices sur les listes chaînées et les files

>Solutionnaire pour les exercices sur les listes chaînées et les filesWebVoici une méthode pour insérer un élément au début d’une liste simplement chaînée On garde le pointeur de la Tête dans un pointeur temporaire On fait ensuite pointer le début de la liste au nouveau nœud à insérer Puis on met le suivant de cet objet au pointeur temporaire gardé Temporaire := Tête Tête := Nouveau Tête

TD : LES LISTES CHAINEES

>TD : LES LISTES CHAINEESWebP a g e 2 4 typedef struct { Etudiant info; struct Classe *suiv; }Classe ; //La fonction Ajout_Etudiant permet d'ajouter un nouvel étudiant dans la tête de la classe

École de technologie supérieure

Département de génie de la production automatisée

GPA665 Structures de données et algorithmes

Solutions du cahier d'exercices

Série d'exercices no. 3 : Les listes élémentaires (les listes chaînées) Session : Automne 2002 Responsable du cours : Mohamed Cheriet, ing., Ph. D. Locaux : Cours : 3740 Chargé de cours : Jean-Christophe Demers Laboratoire : 3324 Chargé de laboratoire : Nicolas Morency Exercice 1 Le programme montré pour cet exercice est incomplet, donc ne compile pas. En fait, vous devez le considérer comme du pseudo-code. Par exemple la fonction new n'est pas définit en langage C (mais elle existe en langage C++). Voici le code de ce programme corrigé : #include #include #include #define maxname 8 #define maxfamily 100 typedef struct { char Name[maxname]; int age; } Person; void NewPerson(Person** P); void main(void) { int i;

Person *personptr, *family[maxfamily]; NewPerson(&personptr); personptr->age = 25; strcpy(personptr->Name, "Fred "); for (i = 0; i < maxname; i++) printf("%c", personptr->Name[i]); printf("\test age de \t%d\n", personptr->age); family[10] = personptr; for (i = 0; i < maxname; i++) printf("%c", personptr->Name[i]); printf("\test age de \t%d\n", personptr->age); }

void NewPerson(Person** P) { *P = (Person*)malloc(sizeof(Person)); }

La sortie de ce programme est :

Fred ??? est âgé de 25 Fred ??? est âgé de 25 Exercice 2 Fonction qui compte le nombre de noeuds dans une liste chaînée. int count(node *head) { node* current = head; int n = 0; while (current != NULL) { n++; current = current->next; } return n; }

Exercice 3 Fonction qui libère toute la mémoire allouée pour une liste chaînée. Voici deux exemples

différents pour une même fonction. Premier exemple : void FreeLinkedList1(node *head) { node *First = head, *Temp; while (First != NULL) { Temp = First; First = First->next; free(Temp); } } Deuxième exemple : void FreeLinkedList2(node **head) { node *Temp; while (*head != NULL) { Temp = *head; *head = (*head)->next; free(Temp); } } L'avantage du deuxième exemple est qu'après l'exécution de la fonction le pointeur head vaut nul. Ainsi, cette méthode aide à ne pas faire d'accès mémoire incorrect. Exercice 4 Fonction qui copie entièrement une liste chaînée dans une autre.

void CopyLinkedList(node *HeadSource, node** HeadTarget) { node *CurrentSource = HeadSource; node *CurrentTarget;

/* S'assure qu'il y ait au moins 1 élément */ if (HeadSource == NULL) { *HeadTarget = NULL; } else { /* Affectation du premier noeud de la liste chaîné */ CurrentTarget = (node*)malloc(sizeof(node)); CurrentTarget->data = CurrentSource->data; *HeadTarget = CurrentTarget; CurrentSource = CurrentSource->next;

/* Affectation de tout les noeuds suivants */ while (CurrentSource != NULL) { CurrentTarget->next = (node*)malloc(sizeof(node)); CurrentTarget->next->data = CurrentSource->data; CurrentSource = CurrentSource->next; CurrentTarget = CurrentTarget->next; } CurrentTarget->next = NULL; } }

Exercice 5 Fonction qui copie le contenu d'une liste chaînée en ordre inverse. Voici deux exemples

différents pour cette fonction.

Premier exemple : void CopyBackward1(node *HeadSource, node** HeadTarget) { if (HeadSource != NULL) { CopyBackward1(HeadSource->next, HeadTarget); InsertLast(HeadTarget, HeadSource->data); } }

void InsertLast(node** Head, int Data) { node *Cur = *Head, *New = (node*)malloc(sizeof(node));

New->data = Data; New->next = NULL;

if (*Head == NULL) { *Head = New; } else { while (Cur->next != NULL) Cur = Cur->next; Cur->next = New; } } Deuxième exemple : void CopyBackward2(node *HeadSource, node** HeadTarget) { static node* LastTargetNode = *HeadTarget;

if (HeadSource != NULL) { CopyBackward2(HeadSource->next, HeadTarget); if (LastTargetNode == NULL) { *HeadTarget = (node*)malloc(sizeof(node)); (*HeadTarget)->data = HeadSource->data; (*HeadTarget)->next = NULL; LastTargetNode = *HeadTarget; } else { LastTargetNode->next = (node*)malloc(sizeof(node)); LastTargetNode->next->data = HeadSource->data; LastTargetNode->next->next = NULL; LastTargetNode = LastTargetNode->next; } } }

Le premier exemple possède le désavantage important de parcourir toute la nouvelle liste lors de chaque insertion. Le deuxième exemple parcours la nouvelle liste chaînée en utilisant habilement une variable static qui permet d'identifier le dernier noeud de la nouvelle liste pour chaque nouvelle insertion.

Exercice 6a Fonction déterminant si deux listes chaînées circulaires sont identique en considérant les

duplications interdites. On suppose une liste chaînée circulaire ordonnée avec un pointeur de liste pointant sur le dernier élément. int IsEqual1(node *L1, node *L2) { node *Cur1 = L1, *Cur2 = L2; int Equal = 1; do { Cur1 = Cur1->Next; Cur2 = Cur2->Next;

if (Cur1 && Cur2 && (Cur1->data == Cur2->data) && ((Cur1->data != Cur1->next->data) || (Cur1 == Cur1->next))) Equal = 0; } while (Equal && (Cur1 != L1));

if (Equal && (Cur2 == L2)) return 1; /* EQUAL */ else return 0; /* NOT EQUAL OR DUPLICATE */ }

Exercice 6b Fonction déterminant si deux listes chaînées circulaires sont identique en considérant les

duplications interdites. On suppose une liste chaînée circulaire ordonnée avec un pointeur de liste pointant sur le dernier élément. int IsEqual2(node *L1, node *L2) { node *Cur1 = L1, *Cur2 = L2; int Equal = 1; do { Cur1 = Cur1->Next; Cur2 = Cur2->Next; if (Cur1 && Cur2 && (Cur1->data == Cur2->data)) Equal = 0; } while (Equal && (Cur1 != L1)); if (Equal && (Cur2 == L2)) return 1; /* EQUAL */ else return 0; /* NOT EQUAL */ }

Exercice 7 Pour l'implantation d'une chaîne de caractères sous forme de liste chaînée, on suppose

que : · chaque noeud possède un char pour chaque caractère; · la fin de la liste chaînée (pointant vers nul) indique la fin de la chaîne de caractères (ainsi, le caractère \0 n'est plus utilisé pour indiquer la fin de la chaîne de caractères).

Voici la déclaration du type utilisé :

typedef struct _LinkedListStringNode { char Character; _LinkedListStringNode *Next; } LinkedListStringNode;

La fonction de concaténation peut être utilisée à l'aide de la fonction qui a été définie au

numéro 4 (CopyLinkedList). Évidemment, les types de données ne concordent pas (node* et LinkedListStringNode*). Mais il suffit d'adapter ce nouveau type à la même logique et la fonction est utilisable.

void StringConcatenation( LinkedListStringNode **StringSource, LinkedListStringNode *StringToConcatenate) { LinkedListStringNode* CurSource = *StringSource;

if (CurSource == NULL) { CopyLinkedList(StringToConcatenate, StringSource); } else { while (CurSource->next != NULL) { CurSource = CurSource->next; } CopyLinkedList(StringToConcatenate, &(CurSource->next)); } }

La fonction de calcul de la longueur est :

int StringLength(LinkedListStringNode* HeadString) { LinkedListStringNode* Current = HeadString; int n = 0;

while (Current != NULL) { n++; Current = Current->next; } return n; } Pour implanter la chaîne de caractères sans avoir à parcourir toute la chaîne pour connaître sa longueur, il suffit de garder cette information dans une variable. Ainsi, à chaque insertion on incrémente cette variable et à chaque suppression on décrémente la variable. Une technique élégante et pratique pour implanter une telle technique consiste à

définir une structure d'entête contenant à la fois le pointeur de tête mais aussi le nombre

de caractère. Voici la déclaration d'un tel type de donnée : typedef struct { _LinkedListStringNode *Head; int Length; } LinkedListString;

Exercice 8 ...

quotesdbs_dbs2.pdfusesText_2

[PDF] GPA665 Ainsi cette méthode aide à