CSC 4103 – Programmation système

Portail informatique

Les pointeurs

L'objectif de cette session d'exercices est de manipuler des pointeurs.

Passage par pointeur (~ 20mn)

Le but de cet exercice est de manipuler vos premiers pointeurs.

Pour commencer, écrivez un programme qui définit deux variables a et b, initialisées respectivement aux valeurs 4 et 0, et qui affiche la valeur de ces variables ainsi que leurs adresses.
Voir le code donné à la fin de l'exercice.

Définissez maintenant deux variables nommées pa et pb, respectivement initialisées aux adresses de a et b. Affichez aussi la valeur de ces variables ainsi que leurs adresses.
Voir le code donné à la fin de l'exercice.

Affectez maintenant la valeur 9 à b en utilisant le pointeur pb. Affichez la valeur de a et de b.
Voir le code donné à la fin de l'exercice.

Écrivez une fonction nommées squares, prenant deux paramètres, et élevant au carré chacun de ces paramètres. Utilisez squares pour élever au carré les variables a et b, et affichez ensuite ces variables.

Des tableaux et des pointeurs (~ 30mn)

Le but de cet exercice est de comprendre les équivalences entre tableaux et pointeurs.

Pour commencer, dans votre fonction main, définissez un tableau d'entiers nommé tab1 de 4 éléments, initialisé aux valeurs 1, 2, 3 et 4. Ensuite, écrivez une fonction display prenant en paramètre un tableau d'entiers et la taille du tableau. Cette fonction doit afficher le tableau. Utilisez display dans main pour afficher les éléments de tab1.
Voir le code donné à la fin de l'exercice.

Écrivez une fonction nommée squares prenant en paramètre un tableau d'entiers et la taille du tableau. Cette fonction élève au carré les éléments du tableau. Appelez squares dans la fonction main et affichez les éléments du tableau ensuite. Pour quelle raison le tableau a-t-il été modifié par squares ?
Pour le code, voir à la fin de l'exercice. Le tableau est modifié car il est passé par pointeur.

En utilisant la fonction malloc, allouez un tableau de 4 entiers que vous placerez dans une variable nommée tab2 de type pointeur vers un entier. Affichez la valeur de tab2 avant de libérer la mémoire utilisée par tab2 avec la fonction free.
Voir le code donné à la fin de l'exercice.

Écrivez une fonction init prenant en paramètre un pointeur nommé tab vers un entier et une taille. Cette fonction doit initialiser à zéro tous les éléments du tableau d'entiers pointé par tab. Pour compliquer un peu la tâche, vous n'avez pas le droit d'utiliser les crochets ([ et ]) dans cette fonction. Appelez init avec comme paramètre tab2 et 4, puis affichez tab2 en utilisant display. Pour quelle raison, la signature de display est-elle cohérente alors que le paramètre est de type pointeur vers un entier ?
Pour le code, voir à la fin de l'exercice. La signature est valide car un paramètre de type tableau est simplement un pointeur vers un entier.

Appelez maintenant init avec comme paramètre tab1 et affichez tab1 avec display. Pour quelle raison la signature de la fonction init est-elle valide alors que tab1 est du type tableau d'entiers ?
Pour le code, voir à la fin de l'exercice. La signature est valide car une variable de type tableau comme tab1 est simplement un pointeur vers le tableau.

que le monde est étrange

Affichez les valeurs tab1, &tab1, tab2 et &tab2. Pour quelle raison tab1 est égal à &tab1 alors que ce n'est pas le cas pour tab2.
tab2 est une variable de type pointeur. Elle se trouve en mémoire et possède une adresse, qui est donc différente de l'adresse pointée. Pour tab1, l'explication est plus surprenante. tab1 est un pointeur vers le tableau, mais le C évalue &tab1 vers l'adresse de la première case du tableau. Comme la première case du tableau est à l'adresse du tableau, on a bien une identité.

finalement le monde est logique

En utilisant sizeof, affichez les tailles de tab1, &tab1, *&tab1, tab2, &tab2 et *&tab2. Une taille est de type unsigned long qui s'affiche avec %lu. Pour quelle raison l'affichage produit est 16, 8, 16, 8, 8 et 8 ?
tab1 est le tableau, il a une taille de 4 entiers faisant chacun 4 octets. &tab1 est, comme indiqué à la question précédente, un pointeur vers la première case du tableau, il a donc une taille de 8 octets sur une machine 64 bits. tab2 étant un pointeur, il a une taille de 8 octets. Un pointeur vers tab2 a aussi une taille de 8 octets.

Gestion des paramètres (~ 20mn)

Le but de cet exercice est de manipuler les paramètres d'un programme en C. La fonction main reçoit deux arguments, souvent nommés argc et argv, permettant d'accéder aux paramètres du programme. La signature de la fonction main est ainsi la suivante :
int main(int argc, char** argv); /* on déclare aussi parfois argv avec char* argv[] qui est équivalent */

L'argument argc est de type entier. L'argument argv est de type pointeur vers un pointeur vers un caractère. Techniquement, argv est un tableau de taille argc. Ce tableau contient des pointeurs vers des chaînes de caractères (i.e., un tableau de caractères terminé par un zéro). Ces chaînes de caractères sont les paramètres: la 0è est le nom du programme et les suivantes les paramètres qui suivent.

Par exemple, si on invoque $ ./mon-prog 1 2 3, alors :
  • le paramètre argc de la fonction main du programme ./mon-prog vaut 4.
  • le paramètre argv est un pointeur vers un tableau, tel que argv[0] pointe vers la chaîne de caractère "./mon-prog", argv[1] pointe vers "1", etc...

Écrivez un programme qui affiche chacun des paramètres. La sortie du programme doit donc être la suivante :
$ ./test-param a b c argv[0]: ./test-param argv[1]: a argv[2]: b argv[3]: c
Voir le code donné à la fin de l'exercice.

Enrichissez votre programme de façon à afficher aussi l'adresse de chacun des paramètres, c'est-à-dire, l'adresse de chacun des argv[i]. La sortie du programme doit être proche de celle-ci :
$ ./test-param a b c argv[0] is at 0x7fff5c357958: ./test-param argv[1] is at 0x7fff5c357965: a argv[2] is at 0x7fff5c357967: b argv[3] is at 0x7fff5c357969: c
Voir le code donné à la fin de l'exercice.

On va maintenant transformer notre programme en petite calculette capable d'additionner ses paramètres. Pour cela, vous allez devoir convertir les chaînes de caractères données en argument en entier avec la fonction atoi définie dans stdlib.h. Votre nouveau programme doit maintenant produire un affichage similaire à celui-ci :
$ ./test-param 1 2 3 argv[0] is at 0x7fff53db3958: ./test-param argv[1] is at 0x7fff53db3965: 1 argv[2] is at 0x7fff53db3967: 2 argv[3] is at 0x7fff53db3969: 3 Sum: 6

Manipuler des chaîne de caractères (~ 20mn)

Le but de cet exercice est de manipuler des chaînes de caractères en C. Pour rappel, une chaîne de caractère est un tableau de char dont les cases contiennent les différentes lettres de la chaîne. Le caractère nul ('\0') est utilisé pour terminer la chaîne de caratère.

Il s'agit ici d'implémenter une fonction retournant le nombre de caractères d'une chaîne de caractères. La signature de la fonction est la suivante:

int string_length(const char* string);
Ici, le paramètre string est de type const char*. Le mot-clé const signifie que la chaîne de caractère passée en argument n'est pas modifiée par la fonction.

Implémentez la fonction string_length et vérifiez qu'elle retourne le bon résultat.

On souhaite maintenant implémenter la fonction string_cpy dont le prototype est le suivant:

void string_cpy(char* dest, const char* src, size_t n);

Cette fonction copie au plus n caractères depuis src vers dest

Implémentez la fonction string_cpy et vérifiez son fonctionnement.

Il s'agit ici d'implémenter une fonction permettant de concaténer deux chaînes de caractères. La signature de la fonction à implémenter est la suivante:

void string_concatenate(char* dest, const char* src, size_t n);

La fonction string_concatenate ajoute les n premiers caractères de la chaîne src à la fin de la chaîne dest en écrasant le caractère nul ('\0'), puis en ajoutant un nouveau caractère nul final.

Par exemple, le programme suivant:

devrait afficher:

$ ./exemple_code Final destination string : |Bonjourà tous !|

Implémentez la fonction string_concatenate en vous servant des fonctions string_length et string_cpy.

Pour implémenter cette fonction, calculez la taille de la chaîne dest (en utilisant string_length). Cette taille correspond à l'indice du tableau dest où copier la chaîne src. Vous pouvez donc calculer l'adresse à passer en argument à string_cpy.
Félicitation ! Vous venez d'implémenter une partie des fonctions de la bibliothèque standard (les fonctions strlen, strncpy et strncat)!

Une liste chaînée (~ 80mn, exercice difficile, mais essentiel dans ce cours)

Le but de cet exercice est de mettre en œuvre une structure de donnée classique, à savoir la liste chaînée. Une liste chaînée permet de stocker des valeurs sans savoir au préalable le nombre de valeurs qu'il faudra stocker.

Une liste chaînée est constituée de nœuds, chaque nœud stockant une valeur. Dans notre exercice, les nœuds vont stocker des chaînes de 256 caractères. Dans une liste chaînée, chaque nœud contient l'adresse du nœud successeur, sauf le dernier de la liste, qui pointe vers NULL (on vous rappelle que NULL est défini dans stdlib.h).
Tout au long de cet exercice, n'hésitez pas à faire, sur un brouillon, des dessins représentant les données manipulées par votre programme

Écrivez un programme nommé list.c et définissant une structure nommée node permettant de stocker un nœud de la liste chaînée. Comme expliqué en introduction, un nœud possède deux champs :
  • un pointeur nommé next pointant vers le nœud suivant de la liste,
  • et un élément nommé element, c'est à dire un tableau de 256 caractères dans notre cas.
Voir le code donné à la fin de l'exercice.

Écrivez une fonction nommée create prenant en argument une chaîne de caractères et renvoyant l'adresse d'un struct node. Cette fonction doit allouer et initialiser un nouveau nœud et le renvoyer. Initialiser un nœud revient à affecter son champ next à la valeur NULL et à copier la chaîne de caractères passée en argument dans le champ element. Pour copier une chaîne de caractères, vous pourrez utiliser au choix la fonction strncpy ou la fonction memcpy.

Dans la fonction main, créez deux nœuds nommés n1 et n2, respectivement initialisés aux valeurs "bonjour" et "monde". Chaînez n2 à la suite de n1, puis affichez les champs éléments de n1 et de n2 pour vérifier que votre fonction create est correcte.

Écrivez une fonction display prenant en argument une liste chaînée. Cette fonction doit afficher les champs element de chacun des nœuds de la liste chaînée. Vérifiez que display fonctionne correctement en affichant la liste n1. Votre programme devrait afficher "bonjour" suivi de "monde".

Nous mettons maintenant en œuvre une fonction nommée insert d'insertion dans la liste chaînée. Cette fonction doit insérer une chaîne de caractères de façon à ce que la liste soit triée dans l'ordre lexicographique. Nous mettons en œuvre cette fonction progressivement étape par étape.

Commencez par écrire une fonction insert prenant deux paramètres :

  • un pointeur vers un nœud, nommé list (struct node* list),
  • une chaîne de caractères nommée str à insérer dans la liste.
La fonction retourne un pointeur sur un nœud.

La fonction commence par créer un nœud new_node en appelant la fonction create. Ensuite, trois cas sont à prendre en compte:

  • insertion dans une liste vide: dans ce cas, le nœud suivant new_node est NULL, et la liste débute à new_node
  • insertion avant le début de la liste: dans ce cas, le nœud suivant new_node est le premier nœud de la liste, et la liste débute à new_node
  • insertion après le premier nœud: dans ce cas, new_node est inséré entre 2 nœuds notés cur_node et next_node: le suivant de cur_node est new_node, et le suivant de new_node est next_node.

Dans un premier temps, implémentez la fonction insert de sorte qu'elle gère les deux premiers cas. Testez votre code en créant une liste vide, et en y insérant les nœuds "ccc", "bbb", et "aaa". Vérifiez avec la fonction display que le résultat est correct.

Pour comparer deux chaînes de caractères, vous pouvez utiliser la fonction strcmp.

Maintenant que nous pouvons parcourir la liste, nous cherchons l'emplacement auquel il faut insérer la chaîne de caractères str.

Pour cela, nous allons utiliser deux pointeurs cur_node et next_node. cur_node est initialisé au premier élément de la liste, et next_node est le successeur de cur_node.

Modifiez la fonction pour parcourir la liste. Le parcours doit s'arrêter si:

  • next_node atteint la fin de la liste,
  • ou si l'élément suivant (next_node->element) est plus grand que str en utilisant l'ordre lexicographique.
Lors du parcours de la liste, veillez à ce que next_node soit toujours le successeur de cur_node.

Lorsque la boucle se termine, cur_node désigne le nœud précédent str (dans l'ordre lexicographique), et next_node le nœud suivant str (ou NULL si aucun élément n'est plus grand que str). Il ne vous reste plus qu'à insérer new_node entre cur_node et next_node.

Dans la fonction main, créez une nouvelle variable de type pointeur vers un nœud nommée list et initialisée à la valeur NULL. Avec la fonction insert, ajoutez à cette liste les mots de la phrase suivante  "que la force soit avec toi". Ensuite, affichez la liste list avec display. Expliquez comment se passe l'insertion du premier nœud "que" et celle du quatrième nœud "soit".
Pour le premier nœud, list pointe vers NULL. Le nouveau nœud new_node a un pointeur next initialisé à list, c'est à dire NULL. C'est bien le dernier nœud de la liste.

Avant la quatrième insertion, la liste est constituée des nœuds "force", "la", "que". Comme "soit" est plus grand que tous ces mots, le parcours va finalement s'arrêter quand next_node vaut NULL. Le nouveau nœud aura donc son pointeur next initialisé à NULL puisque next_node vaut NULL. Ensuite, en affectant ce nouveau nœud à cur_node->next, on modifie le suivant de du nœud"que". Au résultat, le nœud "soit" est bien chaîné après le nœud "que".

défi

En utilisant un procédure similaire à insert, écrivez une procédure destroy, prenant un pointeur sur nœud et une chaîne de caractères en paramètres, et retournant un pointeur sur nœud, qui supprime un nœud de la liste. Pensez à libérer votre nœud avec free. Pour comparer deux chaînes de caractères, vous aurez besoin de la fonction strcmp.
Félicitation ! Vous avez réussi l'un des exercices classiques les plus difficiles sur les pointeurs.