summaryrefslogtreecommitdiff
path: root/sem_3/algo/tp2
diff options
context:
space:
mode:
Diffstat (limited to 'sem_3/algo/tp2')
-rw-r--r--sem_3/algo/tp2/fichierTP2.cpp214
-rw-r--r--sem_3/algo/tp2/progbin0 -> 19149 bytes
-rw-r--r--sem_3/algo/tp2/progListeSC.cpp104
-rw-r--r--sem_3/algo/tp2/progListeSC.h56
-rw-r--r--sem_3/algo/tp2/énoncé TP2.pdfbin0 -> 100541 bytes
5 files changed, 374 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;
+}
diff --git a/sem_3/algo/tp2/prog b/sem_3/algo/tp2/prog
new file mode 100644
index 0000000..f4f6684
--- /dev/null
+++ b/sem_3/algo/tp2/prog
Binary files differ
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
new file mode 100644
index 0000000..9d961dc
--- /dev/null
+++ b/sem_3/algo/tp2/énoncé TP2.pdf
Binary files differ
generated by cgit v1.2.3 (git 2.46.0) at 2026-04-22 14:43:12 +0000