Allocation Dynamique

Soit le programme suivant :
  1. #include <stdio.h>
  2.  
  3. int* creerTab(int n){
  4. int tab[n]; /* non conforme mais passons... */
  5. int i;
  6. for(i=0;i<n;i++)
  7. tab[i] = 0 ;
  8. return tab;
  9. }
  10. int main(){
  11. int tab[] = creerTab(10);
  12. int i;
  13. for(i=0;i<10;i++)
  14. printf("%d ",tab[i]);
  15. printf("\n");
  16. return 0;
  17. }
  18.  
  • Compile-t-il ?
  • Remplassez dans le main
    int tab[] =
    par
    int* tab =
  • Le code compile-t-il ? Quelle est la difference ?
  • Que veulent dire les warnings ?
  • Le code fonctionne-t-il correctement ? pourquoi ?
  • Modifiez la fonction creerTab pour qu'il fonctionne correctement.
  • Si vous avez utilisez la fonction malloc, modifiez le code pour utiliser calloc.

Listes simplement chaînées

On se donne une structure de liste chaînée de données de type int définie ainsi :
  1. typedef struct _cell {
  2. int v;
  3. struct _cell * next;
  4. }Cell;
  5. typedef Cell * List;
  6.  

Exercice 1

Écrire une fonction List empty_list () qui renvoie la valeur de pointeur que vous aurez choisie pour représenter la liste vide, puis la fonction Boolean is_empty (List l) qui teste si une liste est vide (vous devrez définire le type Boolean, avec une enum).

Exercice 2

Écrire deux fonctions d'affichage des éléments d'une liste. L'une itérative, l'autre récursive.

Exercice 3

Écrire une fonction List add_first(int data, List l) qui renvoie une liste ayant comme premier élément data et dont la suite est constituée par la liste l ainsi que la fonction List remove_first(List l) qui prend une liste non vide l, lui enlève sa tête et renvoie la suite de la liste. Assurez vous que toute la mémoire allouée par X appels à add_first soit libérée par X appels à remove_first.
Ecrire une fonction main() pour tester votre code.

Exercice 4

Changez les signatures de add_first et remove_first pour que le code suivant (à completer) fonctionne comme attendu :
  1. List l = empty_list();
  2. int i;
  3. for(i=5;i>0;i--)
  4. add_first(i,/* a completer */);
  5. print_list(l); /* affiche 1 2 3 4 5*/
  6. for(i=0;i<5;i++)
  7. remove_first(/* a completer */);
  8. if(is_empty(l)) printf("la liste est vide\n");
  9.  

Exercice 5

Écrire une fonction void free_list(List * l) qui libère toute la mémoire occupée par une liste l. Pourquoi la liste est-elle passée par adresse ? en remplacant la boucle du code précédant par un appel à free_list, le comportement du programme ne doit pas changer.

Exercice 6

Écrire une fonction Cell* get(int v, List * l) qui enlève la première occurrence de v dans la liste l passée par adresse. La mémoire associée au maillon enlevé ne doit pas être libéré, en revanche un pointeur vers ce maillon est renvoyé. Ecire ensuite une fonction List add_cell(Cell* c, List * l); qui ajoute le maillon c passé par addresse à la fin de la liste l passée par adresse. Testez le code :
  1. List l = empty_list();
  2. List l2 = empty_list();
  3. int i;
  4. for(i=5;i>0;i--)
  5. add_first(i,/* a completer */);
  6. print_list(l); /* affiche 1 2 3 4 5*/
  7. for(i=1;i<=5;i++)
  8. add_cell(get(1,&l),&l2);
  9. if(is_empty(l)) printf("la liste l est vide\n");
  10. print_list(l2);
  11.