TD No 5
from http://vernier.frederic.free.fr/Teaching/PimpA

Les listes chainées

Questions sans code à écrire

1. Dans une liste simple chainée, combien y a t-il de pointeurs a mettre a jour pour inserer-en-tete, inserer-au milieu et insere-en-queue ?
2. Lorsqu'on crée une structure supplémentaire pour manipuler une liste chainée que met-on dedans en plus du pointeur vers le premier/dernier élément ?
3. Quelle structure (Tableaux ou Liste chainée) est mieux adaptée aux suppressions d'un élément en tête ?

// compile avec g++ main.cpp -o main.out
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <stdlib.h>
using namespace std;

struct Ville{
  string *Insee;
  int dep;
  string *Nom;
  int Altitude;
  string *code_postal;
  float longitude_radian;
  float latitude_radian;
  int pop99;
  float surface;
};
vector<Ville*> liste;

struct Departement{
  string *nom;
  int No;
  int pop99;
  float surface;
  struct Departement *next;
};

Departement *first = NULL;


void lire_fichier(string s){
  ifstream f(s.c_str());
  string line;

  getline(f,line);
  while(getline(f,line)) {
    Ville *v = (Ville*)malloc(sizeof(Ville)) ;
    int ind = line.find(";");
    v->Insee = new string (line.substr(0, ind));;
    string code_dep = v->Insee->substr(0, v->Insee->size()-3);
    if (code_dep == "2A" || code_dep == "2B")
      v->dep = 20;
    else
      v->dep   =  atoi(code_dep.c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v->Nom = new string(line.substr(0, ind));

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v->Altitude = atoi(line.substr(0, ind).c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v->code_postal = new string(line.substr(0, ind));

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v->longitude_radian = atof(line.substr(0, ind).c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v->latitude_radian = atof(line.substr(0, ind).c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v->pop99 = atoi(line.substr(0, ind).c_str());

    line = line.substr(ind+1, line.size()-1);
    ind = line.find(";");
    v->surface = atof(line.substr(0, ind).c_str());

    struct Departement *ptr = first;
    //recherche si le departement existe deja
    while(ptr!=NULL && ptr->No != v->dep){
      ptr = ptr->next;
    }
    // a la sortie de la boucle le pointeur est null si il n'existe pas
    // alors on le cree
    if (ptr==NULL){
      ptr = (Departement*)malloc(sizeof(Departement));
      ptr->pop99=0;
      ptr->surface = 0;
      ptr->next = first;
      first = ptr;
      ptr->No = v->dep;
    }
    // qu'il soit trouve ou nouvelle cree on met a jour les infos du departement
    ptr->surface = ptr->surface + v->surface;
    ptr->pop99   = ptr->pop99   + v->pop99;

    liste.push_back(v);
  }
  f.close();
}


int main(int, char*[]) {
  lire_fichier("villes.csv");
  cout << *liste[0]->Nom << " a une population de " << liste[0]->pop99 << " personnes" << endl;

  struct Departement *ptr = first;
  //affiche la population de tous les departements
  while(ptr!=NULL){
    cout << " le departement No " << ptr->No << " a une population de " << ptr->pop99 << " personnes" << endl;
    ptr = ptr->next;
  }
}

Implémentation

Le but de l'implementation sera d'insérer les departements dans une liste double-chainée en garantissant l'ordre des numeros en inserant les départements au bon endroit au fur et a mesure de leur découverte.

4. Trouver le code de recherche si le departement existe dans le code ci-dessus. De quelle recherche s'agit-il ?
5. Dans le code ci-dessus, quelle difference y a t-il entre l'affichage et la recherche (si le departement existe)
7. Rajouter au code (ci-dessus) le double chainage
8. Créer des fonctions insertion_en_tete et insertion_numero. Modifier le code ci-dessus pour utiliser d'abord la fonction insertion_en_tete puis la fonction insertion_numero qui insere dans le bon ordre des numeros de departement.
9. Creer une fonction de duplication de la liste chainée
10. Implementer une algo de tri fusion pour trier les departements par population