8 files changed, 415 insertions, 0 deletions

diff --git a/sem_3/algo/TP3/FichiersTP3.tgz b/sem_3/algo/TP3/FichiersTP3.tgz
new 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
new 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
new file mode 100644
index 0000000..527995d
--- /dev/null
+++ b/sem_3/algo/TP3/tp3