CSC 4103 – Programmation système

Portail informatique

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.