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_3/algo/TP3/FichiersTP3.tgz | Bin 0 -> 2607 bytes sem_3/algo/TP3/enonceTP3.pdf | Bin 0 -> 125909 bytes sem_3/algo/TP3/fichierTP3.cpp | 127 +++++++++++++++++++++++++++++++++++++++++ sem_3/algo/TP3/fichierTP3.h | 43 ++++++++++++++ sem_3/algo/TP3/mainTP3.cpp | 84 +++++++++++++++++++++++++++ sem_3/algo/TP3/progListeSC.cpp | 105 ++++++++++++++++++++++++++++++++++ sem_3/algo/TP3/progListeSC.h | 56 ++++++++++++++++++ sem_3/algo/TP3/tp3 | Bin 0 -> 19624 bytes 8 files changed, 415 insertions(+) create mode 100644 sem_3/algo/TP3/FichiersTP3.tgz create mode 100644 sem_3/algo/TP3/enonceTP3.pdf create mode 100644 sem_3/algo/TP3/fichierTP3.cpp create mode 100644 sem_3/algo/TP3/fichierTP3.h create mode 100644 sem_3/algo/TP3/mainTP3.cpp create mode 100644 sem_3/algo/TP3/progListeSC.cpp create mode 100644 sem_3/algo/TP3/progListeSC.h create mode 100644 sem_3/algo/TP3/tp3 (limited to 'sem_3/algo/TP3') diff --git a/sem_3/algo/TP3/FichiersTP3.tgz b/sem_3/algo/TP3/FichiersTP3.tgz new file mode 100644 index 0000000..2986ae0 Binary files /dev/null and b/sem_3/algo/TP3/FichiersTP3.tgz differ diff --git a/sem_3/algo/TP3/enonceTP3.pdf b/sem_3/algo/TP3/enonceTP3.pdf new file mode 100644 index 0000000..887d4cb Binary files /dev/null and b/sem_3/algo/TP3/enonceTP3.pdf differ 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 +#include +#include +#include +#include +#include +#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;i0 + // 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->infoinfo){ + 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 +#include +#include +#include +#include +#include +#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 +#include +#include +#include +#include +#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 new file mode 100644 index 0000000..527995d Binary files /dev/null and b/sem_3/algo/TP3/tp3 differ -- cgit v1.2.3