CSC4103 -- CF2 Année 2017/2018
Durée: 1h30, tout document papier autorisé
Lorsque vous écrivez du code, essayez d'avoir une indentation à peu près correcte
(une indentation trop incorrecte vous ferait perdre des points).
Sauf si explicitement demandé, il n'est pas nécessaire de spécifier les fichiers inclus (directive #include).
Dans cet exercice, nous concevons un système permettant de retrouver les coordonnées
GPS de villes.
Les villes (∼ 5 points)
Dans un premier temps, nous nous focalisons sur la conception des villes.
Une ville est représentée par un nom (une chaîne de 256 caractères),
une latitude (un nombre à virgule flottante à double précision)
et une longitude (un nombre à virgule flottante à double précision).
0.5 points
Donnez la structure C permettant de représenter une ville.
Vous nommerez cette structure struct city.
3 points
On suppose que les villes sont stockées dans un fichier au format texte.
Chaque ville est représentée par 3 lignes.
La première contient le nom de la ville, la seconde la latitude et la troisième
la longitude.
Écrivez une fonction struct city* readCity(FILE* f) permettant
de lire une ville à partir du fichier f.
Cette fonction reçoit le flux f en paramètre et lit la ville
se trouvant à l'emplacement actuel du curseur dans le fichier.
Elle doit donc allouer une structure city et la remplir de façon adéquate.
Si f est positionné à la fin du fichier (c'est-à-dire si l'appel à fscanf
renvoie EOF) ou si la lecture échoue (c'est-à-dire si l'appel à fscanf renvoie 0),
readCity doit renvoyer NULL
1.5 points
Écrivez une fonction void printCities(char* fileName) permettant
d'afficher toutes les villes se trouvant dans le fichier fileName.
Pensez à gérer les cas d'erreurs.
La recherche rapide de ville (∼ 11 points)
Maintenant que nous avons mis en œuvre les villes, nous construisons
une structure permettant de retrouver rapidement une ville à partir de son nom.
La structure que nous allons utiliser se nomme une table de hachage.
Techniquement, une table de hachage est un tableau de pointeurs vers des listes chaînées.
Un nœud de la liste chaînée contient un pointeur vers une structure
city et un pointeur vers le nœud suivant.
Pour rechercher une ville ayant pour nom name dans une table de hachage, il faut :
- Calculer l'indice idx de la liste chaînée qui contient la ville name dans le tableau. Techniquement cet indice est égale à la somme des lettres de name modulo la taille du tableau.
- Rechercher la ville ayant pour nom name dans la liste chaînée se trouvant à l'indice idx dans le tableau.
0.5 point
Donnez le code de la structure struct node permettant de représenter un
nœud de la liste chaînée.
0.5 points
On suppose qu'on dispose d'une constante N donnant le nombre d'entrées dans
le tableau.
Donnez le code permettant de déclarer le tableau des listes chaînées.
Vous nommerez cette variable globale map.
1.5 points
Donnez le code de la fonction int getIndex(char* cityName).
Cette fonction renvoie l'indice idx de la liste chaînée qui contient
la ville name dans le tableau.
2 points
Donnez le code de la fonction struct city* getCity(char* cityName)
permettant de retrouver la ville de nom cityName dans la table de hachage.
Si la ville ne se trouve pas dans la table de hachage, getCity doit renvoyer NULL.
2.5 points
Donnez le code de la fonction void deleteCity(char* cityName)
permettant de supprimer la ville de nom cityName de la liste chaînée.
2.5 points
Donnez le code de la fonction void addCity(struct city* city)
permettant d'ajouter la ville city dans la table de hachage.
Si une ville de nom city->name est déjà dans la liste chaînée, votre méthode
doit supprimer l'ancienne ville avant d'ajouter la nouvelle.
1.5 points
Écrivez une méthode struct node* initCities(const char* fileName)
permettant de créer la table de hachage des villes associées aux villes stockées
dans le fichier fileName (au format texte tel que définit dans le premier exercice).
Les processus (∼ 4 points)
Écrivez un programme permettant de créer une chaîne de n processus
où n est un paramètre du programme.
Une chaîne de n processus signifie que le processus initial doit engendrer n - 1
processus (directement ou via sa descendance)
et que chaque père doit avoir au plus un fils.
Le dernier processus de la chaîne doit exécuter le programme /bin/ls avec
comme paramètre -al.
