TP 4 - 5

On s'intéresse à deux façon possible de représenter une matrice donnant les distances entre des villes.

Prenons une région au hasard : le nord. On s'intéresse à un ensemble de 9 villes dans la région nord pas-de-calais, représenté par la structure suivante :

Nous allons proposer plusieurs façon différentes de représenter les distances entre ces villes et comparer ces solutions en terme d'occupation mémoire et de temps d'exécution.

    PARTIE 1

  1. Proposer une structure de donnée pour représenter l'ensemble des villes donné ci-dessus.
  2. Commençons par représenter les distances entre les villes sous la forme d'une matrice. Quel serait le code pour représenter la matrice suivante en C ?
  3. Donner une fonction qui, à partir du nom d'une ville, permet de retrouver son indice dans le tableau définit à la première question. Utiliser pour cela la fonction strcmp
  4. Proposer une fonction permettant, pour deux villes données, de donner la distance entre elles.
  5. Utilisez la fonction précédente pour écrire une fonction permettant de calculer la distance totale d'un circuit parcourant un ensemble de villes. Les villes du circuits seront stockées ligne par ligne dans un fichier texte qui sera redirigé en entrée lorsque vous exécuterez votre programme.

    6. PARTIE 2

  6. On veut maintenant faire en sorte que l'utilisateur puisse entrer autant de villes qu'il souhaite. En utilisant la fonction realloc et une boucle while qui demande des villes tant que l'utilisateur n'a pas entré "fin", proposer un code pour la fonction void entrer_villes(char*** villes, int* nb_ville) qui permette à l'utilisateur de remplir un tableau avec toutes les villes entrées (on supposera qu'il y en a au moins une).
  7. Créez une fonction void remplir_matrice(char** villes, int*** distances, int nb_ville) qui, à partir d'une liste de villes passées en paramètre, va allouer et remplir une matrice de distance en demandant les informations à l'utilisateur.
  8. Donnez la fonction qui permet de libérer les variables ainsi allouées.

    9. Correction jusqu'à ce point : tp4-5.c.

    PARTIE 3

  9. On constate que la matrice est symétrique. On propose donc de représenter les distance avec des listes chaînées, comme sur le schéma ci-dessous. Définissez les structures de données permettant cette représentation.
  10. Donnez une fonction qui prend en paramètre un pointeur sur une liste et la matrice précédente et qui rempli la liste à partir de la matrice.
  11. Sachant qu'un pointeur occupe 8 octets en mémoire et un entier 4 octets, calculez l'occupation mémoire des deux solutions.
  12. Avec la deuxième solution, écrire la fonction qui détermine la distance entre deux villes données par leur nom.
  13. Donnez une fonction permettant de calculer la distance totale d'un circuit avec cette solution.
  14. À l'aide de la fonction time(), comment pourrait-on mesurer le temps d'exécution du calcul de la longueur totale d'un même circuit avec les deux solutions?

    15. PARTIE 4

    Un circuit touristique est décrit par la ville de départ/arrivée et la liste des villes étapes (le circuit part d'une ville, passe par des villes étapes et revient à cette ville). L'ensemble des villes visitées comprend donc la ville départ/arrivée plus les villes étapes. La ville de départ/arrivée et les villes étapes sont désignées par l'indice où elles sont rangées dans le vecteur villes. Pour l'exemple, l'entier 4 désigne Lille. On utilise dans cette partie la première solution de modélisation des distances.

  15. Proposez une structure de liste chaînée pour représenter un circruit touristique.
  16. Ecrire un algorithme qui, étant donnés un circuit c et un tableau distance calcule la distance totale à parcourir pour effectuer le circuit complet.
  17. Écrire un algorithme qui pour un circuit c, un tableau distance et une étape e donnés détermine le nombre de kilomètres économisés si on ne passe pas par l'étape e.