Initial commit

1 files changed, 214 insertions, 0 deletions

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