Initial commit

1 files changed, 127 insertions, 0 deletions

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
+  //   }
+  // }
+}