// ==================================================================
// Auteur : Jean-Michel RICHER
// Email : jean-michel.richer@univ-angers.fr
// Institution : Université d'Angers, Faculté des Sciences
// Département : Informatique
// ==================================================================
//
// Objectif : Implantation itérative de liste simplement chaînée
//
// Spécificité : On passe en paramètre des sous-programmes qui
// agissent sur les listes, la liste à modifier. Pour les sous-
// programmes qui modifie la liste (comme l'ajout d'un élément)
// on retourne la tête de la nouvelle liste modifiée.
//
// Lors de l'appel de ces sous-programmes il faut donc passer
// la liste en paramètre mais éventuellement récupérer la liste
// modifiée
//
// L'implantation donnée ici utilise des macro-instructions afin
// de rendre la lecture du code plus aisée.
// ==================================================================
#include <iostream>
#include <sstream>
using namespace std;
// ==================================================================
// structures communes
// ==================================================================
// définition du type de la valeur stockée par un élément de la liste
using type_valeur = int;
// définition d'un élément (maillon) de la liste
struct type_element_de_liste
{
// pointeur sur l'élément suivant
type_element_de_liste *suivant;
// valeur stockée par cet élément
type_valeur valeur;
};
// définition d'une liste comme un pointeur sur un élément
using liste = type_element_de_liste *;
// définition de la liste vide
const liste liste_vide = nullptr;
// ==================================================================
// structures spécifiques à cette implantation
// ==================================================================
#define le_suivant_de(l) l->suivant
#define la_valeur_de(l) l->valeur
// ==================================================================
// Sous-programmes qui agissent sur une liste
// ==================================================================
// Initialisation de la liste
liste liste_initialiser()
{
return liste_vide;
}
// Ajout en tête de la liste
liste liste_ajouter_en_tete(liste l, int valeur)
{
type_element_de_liste *nouvel_element = new type_element_de_liste;
le_suivant_de(nouvel_element) = l;
la_valeur_de(nouvel_element) = valeur;
return nouvel_element;
}
// Ajout en queue de la liste
liste liste_ajouter_en_queue(liste l, int valeur)
{
type_element_de_liste *nouvel_element = new type_element_de_liste;
le_suivant_de(nouvel_element) = liste_vide;
la_valeur_de(nouvel_element) = valeur;
if (l == liste_vide)
{
return nouvel_element;
}
else
{
// rechercher le dernier élément
liste dernier = l;
while (le_suivant_de(dernier) != liste_vide)
{
dernier = le_suivant_de(dernier);
}
le_suivant_de(dernier) = nouvel_element;
return l;
}
}
// créer une liste à partir de données stokées
// dans une chaîne de caractères
liste liste_creer(string data)
{
liste l = liste_vide;
istringstream iss(data);
type_valeur valeur;
while (iss >> valeur)
{
l = liste_ajouter_en_queue(l, valeur);
}
return l;
}
// Vider une liste : supprimer tous ses éléments
liste liste_vider(liste l)
{
liste courant = l;
liste suivant;
while (courant != liste_vide)
{
suivant = le_suivant_de(courant);
delete courant;
courant = suivant;
}
return liste_vide;
}
// Affichage de la liste
void liste_afficher(liste l)
{
liste courant = l;
while (courant != liste_vide)
{
cout << la_valeur_de(courant) << " ";
courant = le_suivant_de(courant);
}
cout << endl;
}
// Tri de la liste sous forme de tri à bulle
void liste_trier(liste l)
{
liste courant1 = l;
while (courant1 != liste_vide)
{
liste courant2 = le_suivant_de(courant1);
while (courant2 != liste_vide)
{
if (la_valeur_de(courant1) > la_valeur_de(courant2))
{
swap(la_valeur_de(courant1), la_valeur_de(courant2));
}
courant2 = le_suivant_de(courant2);
}
courant1 = le_suivant_de(courant1);
}
}
liste liste_supprimer_doublons(liste l)
{
liste courant = l;
// on parcourt la liste initiale à la recherche d'un doublon
// pour chaque élément
while (courant != liste_vide)
{
liste doublon = le_suivant_de(courant);
// parcours des éléments restants dans la liste
liste precedent_doublon = courant;
while (doublon != liste_vide)
{
// a t-on trouvé un doublon ?
if (la_valeur_de(courant) == la_valeur_de(doublon))
{
// si oui, supprimer le doublon
liste suivant_doublon = le_suivant_de(doublon);
delete doublon;
le_suivant_de(precedent_doublon) = suivant_doublon;
doublon = suivant_doublon;
}
else
{
// sinon, passer à l'élément suivant
precedent_doublon = doublon;
doublon = le_suivant_de(doublon);
}
}
courant = le_suivant_de(courant);
}
return l;
}
// ==================================================================
// Programme principal
// ==================================================================
// On insère des élément dans la liste (en tête, puis en queue) et
// on affiche le résultat : 11 4 3 2 1 5 6 7 8 9 10 -1
// on tri ensuite la liste : -1 1 2 3 4 5 6 7 8 9 10 11
// ==================================================================
int main()
{
liste l;
l = liste_initialiser();
for (int i = 1; i < 5; ++i)
{
l = liste_ajouter_en_tete(l, i);
}
for (int i = 5; i < 11; ++i)
{
liste_ajouter_en_queue(l, i);
}
l = liste_ajouter_en_tete(l, 11);
l = liste_ajouter_en_queue(l, -1);
cout << "liste initiale = ";
liste_afficher(l);
liste_trier(l);
cout << "liste triée = ";
liste_afficher(l);
l = liste_vider(l);
l = liste_creer("1 2 1 2 2 3 2 1");
cout << "liste avec doublons = ";
liste_afficher(l);
l = liste_supprimer_doublons(l);
cout << "liste sans doublons = ";
liste_afficher(l);
l = liste_vider(l);
return EXIT_SUCCESS;
}