From 9fe033ea88c2f705ec18c232873d056e0c229d72 Mon Sep 17 00:00:00 2001 From: Gaspard Coulet Date: Wed, 28 Apr 2021 23:05:53 +0200 Subject: Initial commit --- sem_4/Algo/TP5/Arbo.cpp | 235 ++++++++++++++++++++++++++++++++++++++++++++++ sem_4/Algo/TP5/Arbo.h | 115 +++++++++++++++++++++++ sem_4/Algo/TP5/TPArbo.pdf | Bin 0 -> 61606 bytes sem_4/Algo/TP5/main.cpp | 6 ++ sem_4/Algo/TP5/prog | Bin 0 -> 14506 bytes 5 files changed, 356 insertions(+) create mode 100644 sem_4/Algo/TP5/Arbo.cpp create mode 100644 sem_4/Algo/TP5/Arbo.h create mode 100644 sem_4/Algo/TP5/TPArbo.pdf create mode 100644 sem_4/Algo/TP5/main.cpp create mode 100644 sem_4/Algo/TP5/prog (limited to 'sem_4/Algo/TP5') diff --git a/sem_4/Algo/TP5/Arbo.cpp b/sem_4/Algo/TP5/Arbo.cpp new file mode 100644 index 0000000..18305d8 --- /dev/null +++ b/sem_4/Algo/TP5/Arbo.cpp @@ -0,0 +1,235 @@ +#include "Arbo.h" + +/******* Liste doublement chainee Début *******/ + +Cellule::Cellule (ContCellule A){ + fils=A; + Apres=NULL; +} + + + + +ListeCellules Cellule::EstDansListeP(ContCellule A){ + if (fils==A) return this; + if (Apres==NULL) return NULL; + return Apres->EstDansListeP(A); +} + + + +ListeCellules Cellule::AjouterSuccesseur(ContCellule A){ + if (!EstDansListeP(A)) { + ListeCellules ptCell=new Cellule(A); + ptCell->Apres=this; + return ptCell; + } + return this; +} + + + +ListeCellules Cellule::RetirerSuccesseur(ContCellule A){ + if (fils==A) return Apres; + if (!Apres) return this; + Apres=Apres->RetirerSuccesseur(A); return this; +} + + + + +/******* Liste doublement chainee Fin *******/ + + +/************Arborescence Debut*************/ + + +Sommet::Sommet(Valeur v){ + racine=v; + ListeSuccesseurs= NULL; +} + + +ListeCellules Sommet::EstSuccesseurP(Arbo A){ + if (ListeSuccesseurs){ + return (ListeSuccesseurs->EstDansListeP(A)); // à completer et decommenter + } + return NULL; +} + + + +void Sommet::AjouterSuccesseur(Arbo A){ + if ( ListeSuccesseurs && !(ListeSuccesseurs->EstDansListeP(A))){ + ListeSuccesseurs = ListeSuccesseurs->AjouterSuccesseur(A); + } + else { + ListeSuccesseurs = new Cellule (A); + } + return; +} + + + +void Sommet::RetirerSuccesseur(Arbo A){ + if (ListeSuccesseurs && ListeSuccesseurs->EstDansListeP(A)) { + ListeSuccesseurs= ListeSuccesseurs->RetirerSuccesseur(A); // à completer et decommenter + } + return; +} + +ostream& operator<<(ostream& os, Sommet& S){ + os<ListeSuccesseurs; L!=NULL;L=L->Apres){ + TraverseePrefixeRec(L->fils); + } ; // à completer et decommenter + return; +} + +/************Traversee recursive Fin*************/ + +/**********Pile Début*********/ + +Pile::Pile(){ + Sommet=NULL; +} + + +bool Pile::VideP(){ + return Sommet==NULL; +} + + +void Pile::Empiler(ContCellule A){ + Cellule* ptCellule=new Cellule(A); + ptCellule->Apres=Sommet; + Sommet=ptCellule; + return; +} + + +ContCellule Pile::Depiler(){ + Cellule* ptCellule=Sommet; + Sommet=Sommet->Apres; + return ptCellule->fils; +} + +/**********Pile Fin*********/ + +/************Traversee prefixe iterative Debut*************/ + +void TraverseePrefixeIt(Arbo A){ + Pile* P=new Pile; + P->Empiler(A); + while (!(P->VideP())){ + Arbo tmp = P->Depiler(); + cout<< *tmp; + for (ListeCellules L = tmp->ListeSuccesseurs; L!=NULL; L=L->Apres){ + P->Empiler(L->fils); + } + } + cout<Apres=ptCellule; + Entree=ptCellule; + if (! Sortie) Sortie=ptCellule; + return; +} + + +ContCellule File::Defiler(){ + Cellule* ptCellule=Sortie; + Sortie=Sortie->Apres; + return ptCellule->fils; +} + +/**********File Fin*********/ + +/************Traversee Largeur Debut*************/ + +void TraverseeLargeur(Arbo A){ + File * f= new File; + f->Enfiler(A); + while (!f->VideP()){ + A = f->Defiler(); + cout<<(*A); + for (ListeCellules tmp = A->ListeSuccesseurs; tmp != NULL; tmp=tmp->Apres){ + f->Enfiler(tmp->fils); + } + + } +} // à completer + +/************Traversee Largeur Fin*************/ + + +int main(){ + + Arbo A0 = new Sommet(0); + Arbo A1 = new Sommet(1); + Arbo A2 = new Sommet(2); + Arbo A3 = new Sommet(3); + Arbo A4 = new Sommet(4); + Arbo A5 = new Sommet(5); + Arbo A6 = new Sommet(6); + + A3->AjouterSuccesseur(A6); + A1->AjouterSuccesseur(A5); + A3->AjouterSuccesseur(A4); + A2->AjouterSuccesseur(A3); + A0->AjouterSuccesseur(A2); + A0->AjouterSuccesseur(A1); + + cout<<" rec A0 "; + TraverseePrefixeRec(A0); + cout<< endl; + cout<<" iter A0 "; + TraverseePrefixeIt(A0); + cout<< endl; + cout<<" largeur "; + TraverseeLargeur(A0); + cout<< endl; + + + A3->RetirerSuccesseur(A4); + A3->RetirerSuccesseur(A6); + //Alors, pourquoi ? pourquoi essaie t'on de retirer A5 et A2 (respectivement + //fils de A1 et de A0 ?) il y a comme un soucis... + cout<<"rec A0 apres retrait "; + TraverseePrefixeRec(A0); + cout<< endl; + cout<<" iter A0 "; + TraverseePrefixeIt(A0); + cout<< endl; + return 1; +} +//g++ -Wall Arbo.cpp -o prog diff --git a/sem_4/Algo/TP5/Arbo.h b/sem_4/Algo/TP5/Arbo.h new file mode 100644 index 0000000..4658710 --- /dev/null +++ b/sem_4/Algo/TP5/Arbo.h @@ -0,0 +1,115 @@ +#ifndef ARBO_H +#define ARBO_H + +#include +#include + +using namespace std; + +typedef int Valeur; + +struct Sommet; +typedef Sommet* Arbo; + + + +typedef Arbo ContCellule; + +/******* Liste chainee Début *******/ +struct Cellule; + +typedef Cellule* ListeCellules; + +struct Cellule{ + ContCellule fils; + ListeCellules Apres; + + Cellule (ContCellule A); + + ListeCellules EstDansListeP(ContCellule A); +// Si A apparait dans la liste, renvoie un pointeur sur la sous liste commençant par A; sinon renvoie NULL + + ListeCellules AjouterSuccesseur(ContCellule A); +// si A appartenait déjà à la liste renvoie la liste +// sinon rajoute A en tete et renvoie le nouvelle liste + + + ListeCellules RetirerSuccesseur(ContCellule A); +// renvoie la liste d'où a été retirée A s'il lui appartenait (sinon renvoie la liste initiale) +}; + +/******* Liste chainee Fin *******/ + +/************Arborescence Debut*************/ +struct Sommet { + Valeur racine; + ListeCellules ListeSuccesseurs; + + + Sommet(Valeur v); + + ListeCellules EstSuccesseurP(Arbo A); +// Si A apparait dans la liste ListeSuccesseurs, renvoie un pointeur sur la sous liste de ListeSuccesseurs commençant par A; sinon renvoie NULL + + void AjouterSuccesseur(Arbo A); +//rajoute A comme fils ainé + + void RetirerSuccesseur(Arbo A); +// si A était un fils, il cesse de l'être +}; + +ostream& operator<<(ostream& os, Sommet& S); + +/************Arborescence Fin*************/ + +/************Traversee recursive Debut*************/ + +void TraverseePrefixeRec(Arbo); + +/************Traversee recursive Fin*************/ + +/**********Pile Début*********/ +struct Pile { + ListeCellules Sommet; + + Pile(); + + bool VideP(); + void Empiler(ContCellule); + ContCellule Depiler(); // pas défini si la pile est vide +}; + +/**********Pile Fin*********/ + +/************Traversee prefixe iterative Debut*************/ + +void TraverseePrefixeIt(Arbo); + +/************Traversee prefixe iterative Fin*************/ + +/**********File Début*********/ +struct File { + ListeCellules Sortie; + ListeCellules Entree; + + File(); + + bool VideP(); + void Enfiler(ContCellule); + ContCellule Defiler(); // pas défini si la pile est vide +}; + +/**********File Fin*********/ + +/************Traversee Largeur Debut*************/ + +void TraverseeLargeur(Arbo); + +/************Traversee Largeur Fin*************/ + + + + + + +#endif diff --git a/sem_4/Algo/TP5/TPArbo.pdf b/sem_4/Algo/TP5/TPArbo.pdf new file mode 100644 index 0000000..c2b4758 Binary files /dev/null and b/sem_4/Algo/TP5/TPArbo.pdf differ diff --git a/sem_4/Algo/TP5/main.cpp b/sem_4/Algo/TP5/main.cpp new file mode 100644 index 0000000..494e997 --- /dev/null +++ b/sem_4/Algo/TP5/main.cpp @@ -0,0 +1,6 @@ +#include +#include"Arbo.h" + +int main (int argc, char ** argv){ + +} diff --git a/sem_4/Algo/TP5/prog b/sem_4/Algo/TP5/prog new file mode 100644 index 0000000..5e468bb Binary files /dev/null and b/sem_4/Algo/TP5/prog differ -- cgit v1.2.3