diff options
Diffstat (limited to 'sem_3/algo')
29 files changed, 1478 insertions, 0 deletions
diff --git a/sem_3/algo/TP3/FichiersTP3.tgz b/sem_3/algo/TP3/FichiersTP3.tgz Binary files differnew file mode 100644 index 0000000..2986ae0 --- /dev/null +++ b/sem_3/algo/TP3/FichiersTP3.tgz diff --git a/sem_3/algo/TP3/enonceTP3.pdf b/sem_3/algo/TP3/enonceTP3.pdf Binary files differnew file mode 100644 index 0000000..887d4cb --- /dev/null +++ b/sem_3/algo/TP3/enonceTP3.pdf diff --git a/sem_3/algo/TP3/fichierTP3.cpp b/sem_3/algo/TP3/fichierTP3.cpp new file mode 100644 index 0000000..1b804ed --- /dev/null +++ b/sem_3/algo/TP3/fichierTP3.cpp @@ -0,0 +1,127 @@ +#include <iostream> +#include <fstream> +#include <string> +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> +#include "progListeSC.h" +#include "fichierTP3.h" +using namespace std; + + + +bool estTrieeLSC(ListeSC L){ + // Res : Renvoie true si L est une ListeSC tri�e, false sinon + + if (estVideLSC(L) || estVideLSC(L->succ)) + return true; + else + return (L->info < (L->succ)->info) && estTrieeLSC(L->succ); +} + +bool estListeIntervalle(ListeSC L){ + // Res : renvoie true si L est une Liste intervalle, renvoie false sinon + // A COMPLETER + while ( L->succ != NULL) { + if (L->succ->info - L->info != 1) return false; + L=L->succ; + } + return true; +} + +ListeSC consListeIntervalle1(int l, int p){ + // Donn�e : l>0 + // Res : renvoie une liste intervalle de longueur l et dont le premier �l�ment a pour valeur p + // Complexit� : Complexité dans le pire cas : O(N^2) ( boucle for + complexité de base de insererFinLC) + assert(l>0); + + int i; ListeSC L; + L=NULL; + for(i=0;i<l;i++) + insererFinLSC(L,p+i); + return L; +} + +ListeSC consListeIntervalle2(int l, int p){ + // Donn�e : l>0 + // Res : renvoie une liste intervalle de longueur l et dont le premier �l�ment a pour valeur p + // Complexit� : O(N) + // Version iterative + p=p+l-1 ; //valeur du dernier element + ListeSC L = NULL; + while ( l>0) { + L=creerLSC(p, L); + p--; + l--; + } + return L; +} + +ListeSC consListeIntervalle3(int l, int p){ + // Donn�e : l>0 + // Res : renvoie une liste intervalle de longueur l et dont le premier �l�ment a pour valeur p + // Complexit� : O(N-1) + // Version r�cursive + ListeSC L=NULL; + if ( l == 0) return L; + else { + L = creerLSC(p,consListeIntervalle3(l-1,p+1)); + return L; + } +} + +void transfListeIntervalle(ListeSC L){ + // Donn�e : L est une liste tri�e non vide + // Res : modifie L en y inserant des �l�ments de sorte qu'elle soit une Liste Intervalle + // Complexit� : ???? + while ( L->succ != NULL) { + if (L->succ->info - L->info != 1) { + insererApresLSC(L,L,L->info+1); + } + L=L->succ; + } + return; +} + +ListeSC intersectionListesIntervalles(ListeSC l1, ListeSC l2){ + // Donn�e : l1 et l2 2 listes intervalles + // Res : Renvoie l'intersection de l1 et l2; les �l�ments de la liste r�sultat sont recopi�s + // Complexit� : ordre O(N) une premiere partie au moins inferieure a la somme + // de la longueur des listes, plus un appel lineaire a consListeIntervalle2 + assert(estListeIntervalle(l1)); + assert(estListeIntervalle(l2)); + while (l1 != NULL && l2 != NULL && l1->info != l2->info){ + if (l1->info<l2->info){ + l1= l1->succ; + } + else { + l2=l2->succ; + } + } + int p= l1->info; + int l =0; + while ( l1 != NULL && l2 != NULL && l1->info == l2->info){ + l1=l1->succ; + l2=l2->succ; + l++; + } + return consListeIntervalle2(l,p); +} + +void plusLgSsLiInterv(ListeSC &L){ + // Donn�e : L liste + // Res : L est modifiee, elle est la plus longue sous-liste intervalle de la liste en entr�e + // Complexit� : ???? + // ListeSC ret = L; + // ListeSC ancien = NULL; + // int lenght = 0; + // while ( ret->succ != NULL){ + // if (ret->succ->info - ret->info != 1){ + // lenght=0; + // ret=ret->succ; + // } + // else { + // ancien + // } + // } +} diff --git a/sem_3/algo/TP3/fichierTP3.h b/sem_3/algo/TP3/fichierTP3.h new file mode 100644 index 0000000..17cf091 --- /dev/null +++ b/sem_3/algo/TP3/fichierTP3.h @@ -0,0 +1,43 @@ + +#ifndef FicTP3_H +#define FicTP3_H + + +bool estTrieeLSC(ListeSC L); + // Res : Renvoie true si L est une ListeSC triée, false sinon + +bool estListeIntervalle(ListeSC L); + // Res : renvoie true si L est une Liste intervalle, renvoie false sinon + +ListeSC consListeIntervalle1(int l, int p); + // Donnée : l>0 + // Res : renvoie une liste intervalle de longueur l et dont le premier élément a pour valeur p + +ListeSC consListeIntervalle2(int l, int p); + // Donnée : l>0 + // Res : renvoie une liste intervalle de longueur l et dont le premier élément a pour valeur p + +ListeSC consListeIntervalle3(int l, int p); + // Donnée : l>0 + // Res : renvoie une liste intervalle de longueur l et dont le premier élément a pour valeur p + + +void transfListeIntervalle(ListeSC L); + // Donnée : L est une liste triée non vide + // Res : modifie L en y inserant des éléments de sorte qu'elle soit une Liste Intervalle + +ListeSC intersectionListesIntervalles(ListeSC l1, ListeSC l2); + // Donnée : l1 et l2 2 listes intervalles + // Res : Renvoie l'intersection de l1 et l2; les éléments de la liste résultat sont recopiés + + +void plusLgSsLiInterv(ListeSC &L); + // Donnée : L liste + // Res : L est modifiee, elle est la lus longue sous-liste intervalle de la liste en entrée + + +#endif + + + + diff --git a/sem_3/algo/TP3/mainTP3.cpp b/sem_3/algo/TP3/mainTP3.cpp new file mode 100644 index 0000000..a0fb341 --- /dev/null +++ b/sem_3/algo/TP3/mainTP3.cpp @@ -0,0 +1,84 @@ +#include <iostream> +#include <fstream> +#include <string> +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> +#include "progListeSC.h" +#include "fichierTP3.h" + +using namespace std; + + +int main(int argc, char *argv[]){ + ListeSC l1,l2,l3; + int q, lg, prem; + clock_t t1,t2,t3, t4; + + cout << "Numero de la question traitee (1/2/3/4/5/6) ? "; + cin >> q ; + switch (q){ + case 1 : + l1=lireLSC(); + if (estListeIntervalle(l1)) + cout << "Cette liste est une liste intervalle \n"; + else + cout << "Cette liste n'est pas une liste intervalle \n"; + break; + + case 2 : + cout << "Donnez 2 entiers strictement positifs (longueur et premier element de la liste intervalle) : "; + cin >> lg >> prem; + l1=consListeIntervalle1(lg,prem); + afficherLSC(l1); + l2=consListeIntervalle2(lg,prem); + afficherLSC(l2); + l3=consListeIntervalle3(lg,prem); + afficherLSC(l3); + break; + case 3 : + cout << "Donnez 2 entiers strictement positifs (longueur et premier element de la liste intervalle) : "; + cin >> lg >> prem; + t1=clock(); + l1=consListeIntervalle1(lg,prem); + t2=clock(); + l2=consListeIntervalle2(lg,prem); + t3=clock(); + l3=consListeIntervalle3(lg,prem); + t4=clock(); + + cout << " Construction d'une Liste de taille " << lg + << "\n version 1 " <<(double) (t2-t1)/CLOCKS_PER_SEC + << " sec\n version 2 " <<(double) (t3-t2)/CLOCKS_PER_SEC + << " sec\n version 3 "<<(double) (t4-t3)/CLOCKS_PER_SEC<< " sec\n"; + break; + case 4 : // Transformation d'une liste triee en liste Intervalle + cout << "Entrez une Liste Triee : "; + l1=lireLSC(); + transfListeIntervalle(l1); + cout << "Liste Intervalle construite "; + afficherLSC(l1); + break; + case 5 : // intersection de 2 listes intervalle + cout << "Liste intervalle : "; + l1=lireLSC(); + cout << "Liste intervalle : "; + l2=lireLSC(); + l3=intersectionListesIntervalles(l1,l2); + cout << "Intersection : \n"; + afficherLSC(l3); + break; + case 6 : + cout << "Entrez une Liste : "; + l1=lireLSC(); + plusLgSsLiInterv(l1); + cout << "Plus longue sousListe Intervalle : "; + afficherLSC(l1); + } + return 0; +} + + + + + diff --git a/sem_3/algo/TP3/progListeSC.cpp b/sem_3/algo/TP3/progListeSC.cpp new file mode 100644 index 0000000..40efb3e --- /dev/null +++ b/sem_3/algo/TP3/progListeSC.cpp @@ -0,0 +1,105 @@ +// progListeSC.c +#include <iostream> +#include <fstream> +#include <assert.h> +#include <stdlib.h> +#include <stdio.h> +#include "progListeSC.h" + +using namespace std; + + +int 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); + return;} + +void insererApresLSC(ListeSC &l, ListeSC p, int val){ + assert((l)!=NULL); assert(p!=NULL); + (p->succ)=creerLSC(val,(p->succ)); + return;} + +void insererFinLSC(ListeSC &p, int val){ + if (p==NULL) + p=creerLSC(val,NULL); + else + insererFinLSC(p->succ,val); + return; +} + +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; + return;} + +void supprimerDebutLSC(ListeSC &L){ + ListeSC P; + assert(L!=NULL); + + P=L; + L=L->succ; + delete P; + + return;} + + +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;} + return;} + + + +void afficherLSC(ListeSC l){ + cout << "ListeSC : "; + while (! estVideLSC(l)){ + cout << l->info << " "; + l=l->succ;} + cout << endl; + return;} + +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; +} + diff --git a/sem_3/algo/TP3/progListeSC.h b/sem_3/algo/TP3/progListeSC.h new file mode 100644 index 0000000..e35deed --- /dev/null +++ b/sem_3/algo/TP3/progListeSC.h @@ -0,0 +1,56 @@ + +//* 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; + + +// Res : renvoie 1 si L est la liste vide, renvoie 1 sinon +int estVideLSC(ListeSC L ); + +// Res : renvoie une ListeSC dont le premier élément est e et la suite de la liste L +ListeSC creerLSC(int e, ListeSC L); + +// Res : modifie la ListeSC L en y insérant en première place l'élément e +void insererDebutLSC(ListeSC &L, 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 insererApresLSC(ListeSC &L, ListeSC P, int e); + +// Res : modifie la listeSC L en y insérant en dernière place l'élément e +void insererFinLSC(ListeSC &L, int e); + +// 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 +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 +// Res : modifie L en supprimant de L la cellule pointée pas P +void supprimerLSC(ListeSC &L, ListeSC P); + +// Donnée : L est une ListeSC non Vide ; +// Res : modifie L en supprimant son dernier élément +void supprimerFinLSC(ListeSC &L); + +// Donnée : L est une ListeSC non Vide ; +// Res : modifie L en supprimant son premier élément +void supprimerDebutLSC(ListeSC &L); + +// Res : affiche la liste L +void afficherLSC(ListeSC L); + +// Res : renvoie la ListeSC des éléments saisis au clavier +ListeSC lireLSC(); + +#endif //LISTESC_H diff --git a/sem_3/algo/TP3/tp3 b/sem_3/algo/TP3/tp3 Binary files differnew file mode 100644 index 0000000..527995d --- /dev/null +++ b/sem_3/algo/TP3/tp3 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 Binary files differnew file mode 100644 index 0000000..fde8e51 --- /dev/null +++ b/sem_3/algo/TP4/tpIN301_4.pdf diff --git a/sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp b/sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp new file mode 100644 index 0000000..18d30ab --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/mainTP1.cpp @@ -0,0 +1,65 @@ +#include <iostream> +#include <fstream> +#include <string> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include "outilsTab.h" + +using namespace std; + + +int main(int argc, char ** argv) +{ + int* Tab; + struct triplet res; + int sm, taille, q; + clock_t t1, t2; + + srand(time(NULL)); + printf("Numero de la question traitee (1/2/3/4) ? "); + scanf("%d",&q); + switch (q){ + case 1 : + taille=1000; + Tab=genTab(taille); + t1=clock(); sm=ssTabSomMax1(Tab,taille); t2=clock(); + cout << "\n Somme Max1 : " << sm << " tps : " << (double) (t2-t1)/ (double) CLOCKS_PER_SEC << endl; + t1=clock(); sm=ssTabSomMax2(Tab,taille); t2=clock(); + cout << "\n Somme Max2 : " << sm << " tps : " << (double) (t2-t1)/ (double) CLOCKS_PER_SEC << endl; + t1=clock(); sm=ssTabSomMax3(Tab,taille); t2=clock(); + cout << "\n Somme Max3 : " << sm << " tps : " << (double) (t2-t1)/ (double) CLOCKS_PER_SEC << endl; + t1=clock(); sm=ssTabSomMax4(Tab,taille); t2=clock(); + cout << "\n Somme Max4 : " << sm << " tps : " << (double) (t2-t1)/ (double) CLOCKS_PER_SEC << endl; + + break; + case 2 : + fichierTemps("sm1.dat", 1000, 100, ssTabSomMax1); + fichierTemps("sm2.dat", 1000, 100, ssTabSomMax2); + fichierTemps("sm3.dat", 1000, 100, ssTabSomMax3); + fichierTemps("sm4.dat", 1000, 100, ssTabSomMax4); + system("gnuplot trace1.gnu"); + fichierTemps("sm2.dat", 20000, 1000, ssTabSomMax2); + fichierTemps("sm3.dat", 20000, 1000, ssTabSomMax3); + fichierTemps("sm4.dat", 20000, 1000, ssTabSomMax4); + system("gnuplot trace2.gnu"); + fichierTemps("sm3.dat", 1000000, 100000, ssTabSomMax3); + fichierTemps("sm4.dat", 10000000, 1000000, ssTabSomMax4); + system("gnuplot trace3.gnu"); + break; + case 3 : + Tab=genTab(20); + afficheTab(Tab,20); + res=indSsTabSomMax(Tab,20); + cout << "\n somme Max : " << res.somMax << "\n debut souTab : " << res.deb << "\n fin SouTab : " << res.fin << endl; + break; + case 4 : + Tab=genTab(20); + afficheTab(Tab,20); + rangerElemNeg(Tab,20); + afficheTab(Tab,20); + break; + } + return 0; +} + diff --git a/sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp new file mode 100644 index 0000000..6643b13 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.cpp @@ -0,0 +1,131 @@ +#include <iostream> +#include <fstream> + +#include <stdlib.h> // pour rand +#include <assert.h> +#include "outilsTab.h" +using namespace std; + +int* genTab(int n){ + int* t; int i; + t=new int[n]; + for (i=0;i<n;i++) t[i]=-100+rand()%200; + return t; +} + +void afficheTab(int* T, int taille){ + int i; + cout << "\n[ "; + for (i=0;i<taille;i++) cout << T[i] << " "; + cout << "]\n"; + } + +void fichierTemps(const char* nomFic, int tMaxTab, int pas, int (*f)(int*, int)){ + int taille; + int* Tab; + clock_t t1, t2; + ofstream fichier(nomFic,ios::out); + + if (fichier) + { + for (taille=pas; taille<=tMaxTab; taille=taille+pas){ + Tab=genTab(taille); + t1=clock(); + (*f)(Tab,taille); + t2=clock(); + fichier << taille <<" "<< (double)(t2-t1)/ CLOCKS_PER_SEC << endl; + } + fichier.close(); + } + else cerr << " Problème ouverture fichier"<< endl; + + return ; +} + +int ssTabSomMax1(int* T, int taille){ + int somMax, som, i, j, k; + somMax=0; + for (i=0;i<taille;i++){ + for (j=i; j<taille; j++){ + som=0; + for (k=i; k<=j; k++) { + som = som + T[k]; + } + if (som > somMax) somMax = som; + } + } + return somMax; +} + +int ssTabSomMax2(int* T, int taille){ + int somMax, som, i, j; + somMax=0; + for (i=0;i<taille;i++){ + som=0; + for (j=i; j<taille; j++){ + som = som + T[j]; + if (som > somMax) somMax = som; + } + } + return somMax; +} + +int sTSM3(int* T,int g,int d){ + int m, som, i, smgd, smdg, smm, smg, smd; + assert(g<=d); + if (g==d){ + if (T[g]>0) return T[g]; else return 0; + } + else { + m = (d+g)/2; + smg=sTSM3(T,g,m); + smd=sTSM3(T,m+1,d); + smgd=0; som=0; + for (i=m;i>=g;i--){ + som=som+T[i]; + if (som > smgd) smgd=som; + } + smdg=0; som=0; + for(i=m+1;i<=d;i++){ + som=som+T[i]; + if (som>smdg) smdg=som; + } + smm=smgd+smdg; + if ((smg>=smd) && (smg>=smm)) return smg; + else { + if (smd>=smm) return smd; + else return smm; + } + } +} + +int ssTabSomMax3(int* T, int taille){ + return sTSM3(T,0,taille-1); +} + +int ssTabSomMax4(int* T, int taille){ + int ancienplusgrand = 0; + int somme =0; + for (int i =0; i < taille; i ++) { + somme+=T[i]; + if (somme < 0 ){ + somme= 0; + } + ancienplusgrand= ancienplusgrand> somme ? ancienplusgrand : somme; + } + return ancienplusgrand; +} + +struct triplet indSsTabSomMax(int* T, int taille){ +/* A COMPLETER */ + struct triplet res; + res.somMax=0; res.deb=0; res.fin=0; + return res; +} + + +void rangerElemNeg(int* T,int taille){ +/* A COMPLETER */ + return; + +} diff --git a/sem_3/algo/tp1-done/PROG_TP1/outilsTab.h b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.h new file mode 100644 index 0000000..9576c28 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/outilsTab.h @@ -0,0 +1,74 @@ +#ifndef OUTILSTAB_H_INCLUDED +#define OUTILSTAB_H_INCLUDED + +struct triplet { + int deb, fin, somMax;} ; + +int* genTab(int t); +// Renvoie un tableau de taille t, dont les éléments sont des entiers aléatoires compris entre -100 et 100 + + +void afficheTab(int* T, int t); +// Affiche les éléments de T, tableau d'entiers de taille t + + +void fichierTemps(const char* nomFic, int tMaxTab, int pasTaille, int (*fssTabSomMax)(int*, int)); +// Données nomFic une chaîne de caractères, tMaxTab et pasTaille 2 entiers positifs pasTaille < tMaxTab +// fssTabSomMax nom d'une fonction dont les données sont 1 tableau d'entiers et la taille de ce tableau et renvoyant 1 entier +// Resultat : crée un fichier de nom nomfic et pour chaque taille comprise entre pasTaille et tMaxTab (avec un pas de pasTaille), +// génère un tableau de cette taille +// execute la fonction ssTabSomMax sur ce tableau +// ajoute au fichier de nom nomfic la taille du tableau et le temps d'execution de ssTabSomMax + + +int ssTabSomMax1(int* Tab, int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n^3) +*/ + +int ssTabSomMax2(int*, int); + +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n^2) +*/ + +int ssTabSomMax3(int* Tab, int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n log n) +*/ + +int ssTabSomMax4(int* Tab, int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie la somme max des sous-tableaux de tab, algo de complexite O(n) + FONCTION A COMPLETER +*/ + +struct triplet indSsTabSomMax(int* Tab,int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : renvoie une structure contenant + la somme max des sous-tableaux de tab, + l'indice de début d'un sous-tableau de somme max + l'indice de fin d'un sous-tableau de somme max + algo de complexite O(n) + FONCTION A COMPLETER + +*/ + + +void rangerElemNeg(int* Tab,int n); +/* + Données : Tab un tableau d'entiers de taille n + Resultat : modifie le tableau Tab de sorte que tous les éléments négatifs soient placés avant tous les éléments positifs + algo de complexite O(n) + FONCTION A COMPLETER + +*/ + + + +#endif /* OUTILSTAB_H_INCLUDED */ diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm1.dat b/sem_3/algo/tp1-done/PROG_TP1/sm1.dat new file mode 100644 index 0000000..6fe54af --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/sm1.dat @@ -0,0 +1,10 @@ +100 0 +200 0 +300 0.03125 +400 0.03125 +500 0.046875 +600 0.09375 +700 0.15625 +800 0.21875 +900 0.3125 +1000 0.4375 diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm2.dat b/sem_3/algo/tp1-done/PROG_TP1/sm2.dat new file mode 100644 index 0000000..79cda5f --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/sm2.dat @@ -0,0 +1,7 @@ +1000 0 +2000 0 +3000 0.015625 +4000 0.015625 +5000 0.03125 +6000 0.046875 +7000 0.0625 diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm3.dat b/sem_3/algo/tp1-done/PROG_TP1/sm3.dat new file mode 100644 index 0000000..811f1f9 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/sm3.dat @@ -0,0 +1,10 @@ +100 0 +200 0 +300 0 +400 0 +500 0 +600 0 +700 0 +800 0 +900 0 +1000 0 diff --git a/sem_3/algo/tp1-done/PROG_TP1/sm4.dat b/sem_3/algo/tp1-done/PROG_TP1/sm4.dat new file mode 100644 index 0000000..811f1f9 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/sm4.dat @@ -0,0 +1,10 @@ +100 0 +200 0 +300 0 +400 0 +500 0 +600 0 +700 0 +800 0 +900 0 +1000 0 diff --git a/sem_3/algo/tp1-done/PROG_TP1/tp1 b/sem_3/algo/tp1-done/PROG_TP1/tp1 Binary files differnew file mode 100644 index 0000000..8cce618 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/tp1 diff --git a/sem_3/algo/tp1-done/PROG_TP1/trace1.gnu b/sem_3/algo/tp1-done/PROG_TP1/trace1.gnu new file mode 100644 index 0000000..a7f446a --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/trace1.gnu @@ -0,0 +1,5 @@ +set ylabel "secondes" +plot "sm4.dat" with lines, "sm3.dat" with lines, "sm2.dat" with lines, "sm1.dat" with lines +pause -1 "Appuyez sur RETURN pour continuer" +exit + diff --git a/sem_3/algo/tp1-done/PROG_TP1/trace2.gnu b/sem_3/algo/tp1-done/PROG_TP1/trace2.gnu new file mode 100644 index 0000000..ba4de89 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/trace2.gnu @@ -0,0 +1,5 @@ +set ylabel "secondes" +plot "sm4.dat" with lines, "sm3.dat" with lines, "sm2.dat" with lines +pause -1 "Appuyez sur RETURN pour continuer" +exit + diff --git a/sem_3/algo/tp1-done/PROG_TP1/trace3.gnu b/sem_3/algo/tp1-done/PROG_TP1/trace3.gnu new file mode 100644 index 0000000..1907656 --- /dev/null +++ b/sem_3/algo/tp1-done/PROG_TP1/trace3.gnu @@ -0,0 +1,5 @@ +set ylabel "secondes" +plot "sm4.dat" with lines, "sm3.dat" with lines +pause -1 "Appuyez sur RETURN pour continuer" +exit + diff --git a/sem_3/algo/tp1-done/énoncéTP1.pdf b/sem_3/algo/tp1-done/énoncéTP1.pdf Binary files differnew file mode 100644 index 0000000..bdd788a --- /dev/null +++ b/sem_3/algo/tp1-done/énoncéTP1.pdf diff --git a/sem_3/algo/tp2/fichierTP2.cpp b/sem_3/algo/tp2/fichierTP2.cpp new file mode 100644 index 0000000..3a73196 --- /dev/null +++ b/sem_3/algo/tp2/fichierTP2.cpp @@ -0,0 +1,214 @@ +#include <iostream> +#include <fstream> +#include <string> +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> +#include "progListeSC.h" +using namespace std; + +// DERNIERLSC ET ESTTRIEELSC +// Res : Renvoie l'adresse de la derniere cellule de la liste non vide L +ListeSC dernierLSC(ListeSC L){ + while ( L->succ != NULL){ + L=L->succ; + } + return L; +} + +// Res : Renvoie 1 si L est une ListeSC triee, 0 sinon +int estTrieeLSC(ListeSC L){ + while(L->succ != NULL){ + if (L->info > L->succ->info) { + return 0; + } + L=L->succ; + } + return 1; +} + + +// OTERREPETITION +// Res : Supprime de la ListeSC L tous les elements consecutifs egaux +// Opere en modifiant le chainage de la ListeSC L +// version iterative +void oterRepetitionLSC(ListeSC L){ + if (L->succ==NULL || L== NULL) return; + while ( L->succ != NULL){ + if (L->info == L->succ->info ) { + ListeSC tmp= L->succ; + L->succ=L->succ->succ; + delete tmp; + } + if ( L->succ != NULL ) L=L->succ; + } +} + +// Res : Supprime de la ListeSC L tous les elements consecutifs egaux +// Opere en modifiant le chainage de la ListeSC L +// version recursive +void oterRepetitionLSCR(ListeSC L){ + if ( L -> succ == NULL || L== NULL) return; + if ( L->succ->info==L->info){ + ListeSC tmp = L; + L->succ=L->succ->succ; + delete tmp; + } + oterRepetitionLSC(L->succ); + return; +} + + +// CONCATENATION DE 2 LISTES +// Res : Modifie la liste L1 en la concatenant avec la liste l2 +// Opere en modifiant le chainage de la listeSC L1 +// Version utilisant la fonction dernierLSC +void concatLSC(ListeSC L1,ListeSC L2){ + ListeSC tmp = dernierLSC(L1); + tmp->succ = L2; + return; +} + +// Res : Renvoie la ListeSC obtenue par concatenation des ListeSC L1 et L2 +// Opere en recopiant les elements des 2 listeSC L1 et L2 +// complexite : ??? +ListeSC concatLSCCopie(ListeSC L1,ListeSC L2){ + ListeSC L3=NULL; + while ( L1 != NULL) { + insererFinLSC(L3, L1->info); + L1 = L1->succ; + } + while (L2 != NULL){ + insererFinLSC(L3,L2->info); + L2=L2->succ; + } + return L3; +} + + +int main(int argc, char *argv[]){ + ListeSC l1,l2,l3; + int q; + + cout << "Numero de la question traitee (1/2/3/4/5) ? "; + cin >> q; + switch (q){ + case 1 : // Test des operations de base sur les listes + l1 = lireLSC(); + + // insertion d'un element de valeur 11 en derniere position de la liste l1 + // en utilisant insererFinLSC + // Completez + insererFinLSC(l1, 11); + + + cout << "Insertion de 11 en derniere position "; afficherLSC(l1); + + // insertion d'un element de valeur 22 en 2eme position de la liste l1 + // en utilisant insererApresLSC + // Completez + insererApresLSC(l1, l1,22); + + + cout << "Insertion de 22 en 2eme position ";afficherLSC(l1); + + // insertion d'un element de valeur 33 en 2eme position de la liste l1 + // sans utiliser insererApresLSC + // Completez + l1=creerLSC(l1->info, creerLSC(33, l1->succ)); + + + cout << "Insertion de 33 en 2eme position ";afficherLSC(l1); + + // Suppression du 2eme element de la liste en utilisant supprimerLSC + // Completez + supprimerLSC(l1, l1->succ); + + + cout << "Suppression du 2eme element "; afficherLSC(l1); + + // Suppression du 2eme element de la liste sans utiliser supprimerLSC + // Completez + if ( l1->succ!=NULL){ + ListeSC templist = l1->succ; + l1->succ = l1->succ->succ; + delete templist; + } + + cout << "Suppression du 2eme element "; afficherLSC(l1); + + // Inversion des valeurs des 2 premiers elements + // en modifiant les champs info (sans modifier le chainage) + // Completez + if (l1->succ != NULL){ + int tmp = l1->succ->info; + l1->succ->info=l1->info; + l1->info= tmp; + } + + + cout << "Inversion des valeurs des 2 premiers elements " ; afficherLSC(l1); + + // Inversion des 2 premiers elements + // en modifiant les champs succ (le chainage) + // Completez + if ( l1->succ != NULL) { + ListeSC templist; + templist = l1; + l1 = l1->succ; + templist->succ = l1->succ; + l1->succ= templist; + } + + + cout << "Inversion des 2 premiers elements "; afficherLSC(l1); + break; + + case 2 : // Test des fonctions estTrieeLSC et dernierLSC + l1 = lireLSC(); + if (estTrieeLSC(l1)) cout << "Cette liste est triee\n"; + else cout << "Cette liste n'est pas triee\n"; + if (l1 != NULL) + cout << "La valeur de son dernier element est " << dernierLSC(l1)->info << endl; + break; + + case 3: // Test des fonctions oterRepetitionLSC + l1 = lireLSC(); + oterRepetitionLSC(l1); + cout << "Liste sans repetition (version iterative) :\n"; + afficherLSC(l1); + l1 = lireLSC(); + oterRepetitionLSCR(l1); + cout << "Liste sans repetition (version recursive) :\n"; + afficherLSC(l1); + break; + + case 4 : // Test de la premiere fonction de concatenation de listes + l1 = lireLSC(); + l2 = lireLSC(); + concatLSC(l1,l2); + cout << "Concatenation des 2 listes (en modifiant le chainage) :\n"; afficherLSC(l1); + if ((l1 != NULL) && (l2 != NULL) ) + cout << "Adresse derniere cellule de l1 : " << (void *) dernierLSC(l1) << ", de l2 : "<< (void *) dernierLSC(l2) << endl; + cout << " Ajout de 44 en fin de la liste l1\n"; + insererFinLSC(l1,44); + cout << "Nouvelle valeur de l1:"; afficherLSC(l1); cout << endl; + cout << "Nouvelle valeur de l2: "; afficherLSC(l2); cout << endl; + break; + + case 5 : // Test des fonctions de concatenation de listes + l1 = lireLSC(); + l2 = lireLSC(); + l3 = concatLSCCopie(l1,l2); + cout << "Concatenation des 2 listes (par recopie des listes) : "; afficherLSC(l3); cout << endl; + if ((l1 != NULL) && (l2 != NULL) ) + cout << "Adresse derniere cellule de l1 : " << (void *) dernierLSC(l1) << " , de l2 : " << (void *) dernierLSC(l2) << ", de l3 : " << (void *) dernierLSC(l3) << endl; + cout << " Ajout de 55 en fin de la liste l1\n"; + insererFinLSC(l1,55); + cout << "Nouvelle valeur de l1: "; afficherLSC(l1); cout << endl; + cout << "Nouvelle valeur de l2: "; afficherLSC(l2); cout << endl; + cout << "Nouvelle valeur de l3: "; afficherLSC(l3); cout << endl; + break; + } + return 0; +} diff --git a/sem_3/algo/tp2/prog b/sem_3/algo/tp2/prog Binary files differnew file mode 100644 index 0000000..f4f6684 --- /dev/null +++ b/sem_3/algo/tp2/prog diff --git a/sem_3/algo/tp2/progListeSC.cpp b/sem_3/algo/tp2/progListeSC.cpp new file mode 100644 index 0000000..dd81a27 --- /dev/null +++ b/sem_3/algo/tp2/progListeSC.cpp @@ -0,0 +1,104 @@ +// progListeSC.c +#include <iostream> +#include <fstream> +#include <assert.h> +#include <stdlib.h> +#include <stdio.h> +#include "progListeSC.h" + +using namespace std; + + +int 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); + return;} + +void insererApresLSC(ListeSC &l, ListeSC p, int val){ + assert((l)!=NULL); assert(p!=NULL); + (p->succ)=creerLSC(val,(p->succ)); + return;} + +void insererFinLSC(ListeSC &p, int val){ + if (p==NULL) + p=creerLSC(val,NULL); + else + insererFinLSC(p->succ,val); + return; +} + +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; + return;} + +void supprimerDebutLSC(ListeSC &L){ + ListeSC P; + assert(L!=NULL); + + P=L; + L=L->succ; + delete P; + + return;} + + +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;} + return;} + + + +void afficherLSC(ListeSC l){ + cout << "ListeSC : "; + while (! estVideLSC(l)){ + cout << l->info << " "; + l=l->succ;} + cout << endl; + return;} + +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; +} diff --git a/sem_3/algo/tp2/progListeSC.h b/sem_3/algo/tp2/progListeSC.h new file mode 100644 index 0000000..c259352 --- /dev/null +++ b/sem_3/algo/tp2/progListeSC.h @@ -0,0 +1,56 @@ + +//* 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; + + +// Res : renvoie 1 si L est la liste vide, renvoie 1 sinon +int estVideLSC(ListeSC L ); + +// Res : renvoie une ListeSC dont le premier élément est e et la suite de la liste L +ListeSC creerLSC(int e, ListeSC L); + +// Res : modifie la ListeSC L en y insérant en première place l'élément e +void insererDebutLSC(ListeSC &L, 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 insererApresLSC(ListeSC &L, ListeSC P, int e); + +// Res : modifie la listeSC L en y insérant en dernière place l'élément e +void insererFinLSC(ListeSC &L, int e); + +// 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 +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 +// Res : modifie L en supprimant de L la cellule pointée pas P +void supprimerLSC(ListeSC &L, ListeSC P); + +// Donnée : L est une ListeSC non Vide ; +// Res : modifie L en supprimant son dernier élément +void supprimerFinLSC(ListeSC &L); + +// Donnée : L est une ListeSC non Vide ; +// Res : modifie L en supprimant son premier élément +void supprimerDebutLSC(ListeSC &L); + +// Res : affiche la liste L +void afficherLSC(ListeSC L); + +// Res : renvoie la ListeSC des éléments saisis au clavier +ListeSC lireLSC(); + +#endif //LISTESC_H diff --git a/sem_3/algo/tp2/énoncé TP2.pdf b/sem_3/algo/tp2/énoncé TP2.pdf Binary files differnew file mode 100644 index 0000000..9d961dc --- /dev/null +++ b/sem_3/algo/tp2/énoncé TP2.pdf |