5 files changed, 356 insertions, 0 deletions
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<<S.racine<<" ";
+  return os;
+}
+
+/************Arborescence Fin*************/
+
+/************Traversee recursive Debut*************/
+
+void TraverseePrefixeRec(Arbo A){
+  if (!A) { return;};
+  cout<< *A;
+  for (ListeCellules L=A->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<<endl;
+  //  while // à completer et decommenter
+}
+
+/************Traversee  prefixe iterative Fin*************/
+
+
+/**********File Début*********/
+
+File::File(){
+  Sortie=NULL; Entree=NULL;
+}
+
+
+bool File::VideP(){
+  return Sortie==NULL;
+}
+
+
+void File::Enfiler(ContCellule A){
+  Cellule* ptCellule=new Cellule(A);
+  if (Entree) Entree->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 <iostream>
+#include <sstream>
+
+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
--- /dev/null
+++ b/sem_4/Algo/TP5/TPArbo.pdf
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<iostream>
+#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
--- /dev/null
+++ b/sem_4/Algo/TP5/prog