summaryrefslogtreecommitdiff
path: root/sem_3/algo/TP4
diff options
context:
space:
mode:
Diffstat (limited to 'sem_3/algo/TP4')
-rw-r--r--sem_3/algo/TP4/fichierTP4.cpp194
-rw-r--r--sem_3/algo/TP4/progListeSC.cpp114
-rw-r--r--sem_3/algo/TP4/progListeSC.h59
-rw-r--r--sem_3/algo/TP4/tpIN301_4.pdfbin0 -> 94341 bytes
4 files changed, 367 insertions, 0 deletions
diff --git a/sem_3/algo/TP4/fichierTP4.cpp b/sem_3/algo/TP4/fichierTP4.cpp
new file mode 100644
index 0000000..9b90ad7
--- /dev/null
+++ b/sem_3/algo/TP4/fichierTP4.cpp
@@ -0,0 +1,194 @@
+#include <iostream>
+#include <sstream>
+#include <fstream>
+#include <string>
+//#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include "progListeSC.h"
+using namespace std;
+
+typedef struct noeud {
+ int info;
+ struct noeud *sag;
+ struct noeud *sad;} NoeudSC;
+typedef NoeudSC *ArbreBin;
+
+ArbreBin creerArbreBin(int e, ArbreBin G, ArbreBin D){
+ /* Res : renvoie une ArbreBin dont la racine vaut e, le sag G et le sad D */
+ ArbreBin A = new NoeudSC;
+ A->info=e; A->sag=G; A->sad=D;
+ return A;}
+
+void codageABdot(ofst ream& fichier, ArbreBin A){
+ if (A != NULL){
+ fichier << (long) A << " [label=\"" << A->info << "\" ] ;\n";
+ if (A->sag != NULL) {
+ fichier << (long)A << " -> " << (long)(A->sag) << " [color=\"red\",label=\"g\" ] ;\n";
+ codageABdot(fichier,A->sag);}
+ if (A->sad != NULL) {
+ fichier << (long)A << " -> " << (long)(A->sad) << " [color=\"blue\",label=\"d\" ] ;\n";
+ codageABdot(fichier,A->sad);}
+ }
+ return;}
+
+
+void dessinerAB(ArbreBin A, const char * nomFic, string titre){
+ ofstream f(nomFic);
+ if (!f.is_open()){
+ cout << "Impossible d'ouvrir le fichier en �criture !" << endl;
+ }
+ else {
+ f<< "digraph G { label = \""<< titre << "\" \n";
+ codageABdot(f,A);
+ f << "\n }\n" ;
+ f.close();}
+ return;}
+
+
+/* A COMPLETER */
+int sommeNoeuds(ArbreBin A){
+ /* renvoie la somme des etiquettes des noeuds de l arbre binaire A */
+ /* A COMPLETER */
+ return A == NULL ? 0: A->info+sommeNoeuds(A->sag)+sommeNoeuds(A->sad);
+}
+
+int profMinFeuille(ArbreBin A){
+ /* renvoie la profondeur minimum des feuilles de l'arbre A ; A est non vide */
+ assert(A!=NULL);
+ /* A COMPLETER */
+ return A==NULL ? 0: A->info + ( profMinFeuille(A->sag)<= profMinFeuille(A->sad)) ? profMinFeuille(A->sag):profMinFeuille(A->sad));
+}
+
+ListeSC parcoursInfixe(ArbreBin A){
+ /* renvoie la liste composee des etiquettes des noeuds de l'arbre A ordonn�e
+ selon l'ordre infixe */
+ /* A COMPLETER */
+ return A==NULL ? NULL: concatLSC(concatLSC(parcoursInfixe((A->sag), A->info),A->sad));
+}
+
+void effeuiller(ArbreBin& A){
+ /* modifie l'arbre A en supprimant ses feuilles */
+ /* A COMPLETER */
+ return;}
+
+void tailler(ArbreBin& A, int p){
+ /* modifie l'arbre A, en supprimant ses noeuds de profondeur au moins p ; p est un entier positif ou nul */
+ /* A COMPLETER */
+ return;}
+
+void tronconner(ArbreBin& A){
+ /* modifie l'arbre A, en supprimant les noeuds dont un seul sous-arbre est vide */
+ /* A COMPLETER */
+ return;}
+
+ArbreBin genereAB(int n){
+ /* A COMPLETER */
+ return NULL;}
+
+
+bool estParfait(ArbreBin A){
+ // V�rifie si A est un arbre binaire parfait
+ return true;
+}
+
+/*****************************************************************************/
+/* */
+/* main */
+/* */
+/*****************************************************************************/
+int main(int argc, char *argv[]){
+ int q,i;
+ ArbreBin A,B,C;
+ ostringstream stre;
+ ListeSC L;
+ string chaine;
+ A=creerArbreBin(8,
+ creerArbreBin(7,
+ creerArbreBin(4,NULL,NULL),
+ creerArbreBin(9,NULL,NULL)),
+ creerArbreBin(3,NULL,NULL));
+
+ B=creerArbreBin(8,
+ creerArbreBin(2,
+ creerArbreBin(4,NULL,NULL),
+ creerArbreBin(9,
+ NULL,
+ creerArbreBin(1,
+ NULL,
+ creerArbreBin(7,
+ creerArbreBin(11,NULL,NULL),
+ creerArbreBin(5,
+ NULL,
+ NULL))))),
+ creerArbreBin(3,
+ creerArbreBin(12,
+ creerArbreBin(6,NULL,NULL),
+ NULL),
+ creerArbreBin(9,NULL,NULL)));
+ C=NULL;
+ C= creerArbreBin(1,C,C);
+ cout << "Numero de la question traitee (1/2/3/4/5/6/7) ? ";
+ cin >> q;
+ switch (q){
+ case 1 :
+ dessinerAB(A,"arbre.dot","Arbre Bin");
+ cout << "Somme des noeuds de l'arbre :"<< sommeNoeuds(A) << endl;
+ cout << "Profondeur minimum des feuilles de l'arbre : " << profMinFeuille(A) << endl;
+ system("dotty arbre.dot");
+ break;
+ case 2 :
+ dessinerAB(A,"arbre.dot","Arbre Bin");
+ L=parcoursInfixe(A);
+ cout << "Liste des noeuds de l'arbre en ordre infixe : ";
+ afficherLSC(L);
+ system("dotty arbre.dot");
+ break;
+ case 3 :
+ dessinerAB(B,"arbre.dot","Arbre Bin");
+ system("dotty arbre.dot&");
+ effeuiller(B);
+ dessinerAB(B,"arbre2.dot","Arbre Bin effeuille");
+ system("dotty arbre2.dot");
+ break;
+ case 4 :
+ dessinerAB(B,"arbre.dot","Arbre Bin");
+ system("dotty arbre.dot&");
+ cout << " Donner une profondeur (entier positif) :";
+ cin >> i;
+ tailler(B,i);
+ stre << i;
+ chaine = stre.str();
+ chaine = "Arbre Bin taille a la profondeur " + chaine;
+ dessinerAB(B,"arbre2.dot",chaine);
+ system("dotty arbre2.dot&");
+ break;
+ case 5 :
+ cout << " Donner un entier positif :";
+ cin >> i;
+ stre << i;
+ chaine = "Arbre Bin " + stre.str();
+ dessinerAB(genereAB(i),"arbre.dot", "Arbre Bin " + stre.str());
+ system("dotty arbre.dot&");
+ break;
+ case 6 :
+ dessinerAB(B,"arbre.dot","Arbre Bin");
+ system("dotty arbre.dot&");
+ tronconner(B);
+ dessinerAB(B,"arbre2.dot","Arbre tronconne");
+ system("dotty arbre2.dot&");
+ break;
+ case 7 :
+ A=genereAB(7);
+ chaine= estParfait(A) ? "Arbre parfait" : "Arbre non parfait";
+ dessinerAB(A,"arbre.dot",chaine);
+ system("dotty arbre.dot");
+
+ B=genereAB(8);
+ chaine= estParfait(B) ? "Arbre parfait" : "Arbre non parfait";
+ dessinerAB(B,"arbre2.dot",chaine);
+ system("dotty arbre2.dot&");
+ break;
+ }
+ return 0;
+}
diff --git a/sem_3/algo/TP4/progListeSC.cpp b/sem_3/algo/TP4/progListeSC.cpp
new file mode 100644
index 0000000..0a88c29
--- /dev/null
+++ b/sem_3/algo/TP4/progListeSC.cpp
@@ -0,0 +1,114 @@
+/**************************** progListeSC.c **********************************/
+
+#include <iostream>
+#include <fstream>
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include "progListeSC.h"
+
+using namespace std;
+
+
+bool estVideLSC(ListeSC l)
+{ return (l==NULL);}
+
+ListeSC creerLSC(int val, ListeSC succ){
+ ListeSC l = new CelluleSC;
+ l->info=val;
+ l->succ=succ;
+ return l;}
+
+void insererDebutLSC(ListeSC& p, int val){
+ p=creerLSC(val,p);
+}
+
+void insererApresLSC(ListeSC& l, ListeSC p, int val){
+ assert((l)!=NULL); assert(p!=NULL);
+ (p->succ)=creerLSC(val,(p->succ));
+}
+
+void insererFinLSC(ListeSC& p, int val){
+ if ((p)==NULL)
+ p=creerLSC(val,NULL);
+ else
+ insererFinLSC(p->succ,val);
+}
+
+ListeSC predecesseurLSC(ListeSC L, ListeSC P){
+ assert(L!=NULL);
+ assert(P!=NULL);
+
+ if (L->succ==P){return L;}
+ else {return predecesseurLSC(L->succ,P);}
+}
+
+void supprimerLSC(ListeSC& L, ListeSC P){
+ assert(L!=NULL);
+ assert(P!=NULL);
+
+ if (L==P){L=L->succ;}
+ else {
+ predecesseurLSC(L,P)->succ=P->succ;
+ }
+ delete(P);
+}
+
+void supprimerDebutLSC(ListeSC& L){
+ ListeSC P;
+
+ assert(L!=NULL);
+
+
+ P=L;
+ L=L->succ;
+ delete(P);
+}
+
+
+void supprimerFinLSC(ListeSC& L){
+ assert(L!=NULL);
+
+ if (L->succ==NULL){
+ delete(L);
+ L=NULL;}
+ else {
+ ListeSC P=L,Q;
+ while ((P->succ)->succ!=NULL){
+ P=P->succ;}
+ Q=P->succ;
+ P->succ=NULL;
+ delete(Q);}
+}
+
+
+
+void afficherLSC(ListeSC l){
+ cout<< "ListeSC : ";
+ while (! estVideLSC(l)){
+ cout << " " << l->info <<" ";
+ l=l->succ;}
+ cout << endl;
+}
+
+ListeSC lireLSC(){
+ ListeSC l;
+ int i;
+ cout << "Entrez les éléments d'une liste d'entiers (0 pour finir)\n";
+ l=NULL;
+ cin >> i;
+ while (i!=0) {
+ insererFinLSC(l,i);
+ cin >>i ;
+ }
+ return l;
+}
+
+ListeSC concatLSC(ListeSC L1, ListeSC L2){
+ ListeSC P;
+ if (L1==NULL) return L2;
+ else {
+ P= L1;
+ while (P->succ != NULL) P=P->succ;
+ P->succ = L2;
+ return L1;}}
diff --git a/sem_3/algo/TP4/progListeSC.h b/sem_3/algo/TP4/progListeSC.h
new file mode 100644
index 0000000..f60d8f4
--- /dev/null
+++ b/sem_3/algo/TP4/progListeSC.h
@@ -0,0 +1,59 @@
+
+/**************************** ListeSC.h **************************************/
+/* Implantation du type Liste d'entiers Simplement Chainée */
+
+#ifndef LISTESC_H
+#define LISTESC_H
+
+typedef struct cellule {
+ int info;
+ struct cellule *succ;} CelluleSC;
+
+typedef CelluleSC *ListeSC;
+
+
+bool estVideLSC(ListeSC L );
+/* Res : renvoie 1 si L est la liste vide, renvoie 1 sinon */
+
+ListeSC creerLSC(int e, ListeSC L);
+/* Res : renvoie une ListeSC dont le premier élément est e et la suite de la liste L */
+
+void insererDebutLSC(ListeSC & L, int e);
+/* Res : modifie la ListeSC L en y insérant en premiere place l'élément e */
+
+void insererApresLSC(ListeSC & L, ListeSC P, int e);
+/* Donnée : L est une ListeSC non vide, P l'adresse d'un élément de L, e un entier */
+/* Res : insère dans la liste L après l'élément d'adresse P 1 élément de valeur e */
+
+void insererFinLSC(ListeSC & L, int e);
+/* Res : modifie la listeSC L en y insérant en dernière place l'élément e */
+
+ListeSC predecesseurLSC(ListeSC L, ListeSC P);
+/* Donnée : L est une ListeSC non Vide ; */
+/* P est un pointeur non vide vers une cellule de la liste L */
+/* L != P */
+/* Res : renvoie l'adresse de la cellule précédant dans L celle pointée pas P */
+
+void supprimerLSC(ListeSC & L, ListeSC P);
+/* Donnée : L est une ListeSC non Vide ; */
+/* P est un pointeur non vide vers une cellule de la liste L */
+/* Res : modifie L en supprimant de L la cellule pointée pas P */
+
+void supprimerFinLSC(ListeSC & L);
+/* Donnée : L est une ListeSC non Vide ; */
+/* Res : modifie L en supprimant son dernier élément */
+
+void supprimerDebutLSC(ListeSC & L);
+/* Donnée : L est une ListeSC non Vide ; */
+/* Res : modifie L en supprimant son premier élément */
+
+void afficherLSC(ListeSC L);
+/* Res : affiche la liste L */
+
+ListeSC lireLSC();
+/* Res : renvoie la ListeSC des éléments saisis au clavier */
+
+ListeSC concatLSC(ListeSC L1, ListeSC L2);
+/* Res : renvoie la ListeSC, concaténation des listes L1 et L2, en modifiant le chaînage de L1*/
+
+#endif /*LISTESC_H*/
diff --git a/sem_3/algo/TP4/tpIN301_4.pdf b/sem_3/algo/TP4/tpIN301_4.pdf
new file mode 100644
index 0000000..fde8e51
--- /dev/null
+++ b/sem_3/algo/TP4/tpIN301_4.pdf
Binary files differ
generated by cgit v1.2.3 (git 2.46.0) at 2026-04-22 14:43:41 +0000