Discussion :

[Sve@r]

Si il y a une chance même infime qu'un bug se produise, alors ...

... alors tu peux être certain que le bug se produira au pire moment de ta vie de dev

Par contre, il faut, soit le faire exprès (auquel cas on utilisera memcpy()), soit manquer cruellement de chance pour que la zone-source et la zone destinataire se chevauchent.

Hum, compter sur la chance (et la malchance) en prog... Bon bien entendu ça dépend de la criticité de ton truc mais si on se laisse trop aller, tôt ou tard "crouich"

[VivienD]

À obsidian :

Si tu arrives à ne pas t'en dégoûter, c'est de cette façon que tu progresseras le plus vite.

Ne t'inquiète pas : quand on a fait partie d'un groupe qui vénérait le pinaillage et les subtilités, ça laisse des traces et des habitudes indélébiles (c'est même pour ça que j'ai fait du grec ancien, langue avec laquelle on est princièrement servi question pinaillage et subtilités).

— Le premier est un pointeur sur un tableau d'entiers ;
— Le second est un tableau de pointeurs d'entiers.

Ça se voit d'ailleurs aux accolades « { » et « } » que tu es obligé de mettre. Elles indiquent que tu initialises un tableau. Dans le premier cas, on déclare bien un pointeur seul, quoi qu'il pointe. C'est pour cela que je peux directement lui affecter NULL, sans autre artifice.

Je comprends mieux. D'ailleurs, j'ai modifié mon programme avec cette déclaration, puis j'ai revêtu le rôle d'apprenti sorcier. Au final je suis arrivé à cette déclaration const int (*pTab)[NB_ORDONNEES] = calloc (NB_ABSCISSES,sizeof (int[NB_ORDONNEES])); qui me permet d'avoir un pointeur constant pointant sur un tableau bidimensionnel alloué et initialisé via calloc(). Après pour travailler le tableau j'ai dû utilisé un second pointeur initialisé comme suit : int *p = (int*) pTab;

Cela dit, les structures sont extrêmement utilisées en C, pour des choses similaires. Le seul inconvénient à vectoriser des structures est l'éventuel padding que le compilateur peut ajouter et qu'il faut annuler explicitement le cas échéant, avec des directives qui ne sont pas toujours portables.

En fait, je vois les structures plus pour les listes chaînées et les champs de bits que pour de « bêtes » tableaux multidimensionnels ou de « bêtes » vecteurs.

Ce n'est pas tout-à-fait vrai.

D'abord on préfère avoir des programmes déterministes ! :-) Si il y a une chance même infime qu'un bug se produise, alors le problème doit être corrigé avant d'être mis en production. En plus, ces cas improbables lorsqu'on fonctionne en mono-tâche se révèlent redoutables une fois mis en parallèle dans un environnement multi-thread. Ils deviennent des races conditions, très difficiles à débuguer.

Je remplis des tas de cahiers et de feuilles volantes à cause de ça.

À Sve@r :

... alors tu peux être certain que le bug se produira au pire moment de ta vie de dev



Hum, compter sur la chance (et la malchance) en prog... Bon bien entendu ça dépend de la criticité de ton truc mais si on se laisse trop aller, tôt ou tard "crouich"

Le pire moment de ma vie de développeur amateur a eu lieu quand j'ai donné par inadvertance une rasade de café noir à mon précédent ordinateur portable ; il ne s'en est jamais remis.

[VivienD]

Bonjour,
j'ai essayé d'adapter la syntaxe d'obsidian pour le tableau bidimensionnel afin de lui ajouter une troisième dimension, mais en vain.
Vous pourriez m'indiquer la méthode, s'il vous plaît.

Je rappelle le code d'obsidian.

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdlib.h>
#include <stdio.h>
 
#define ABSCISSES 11
#define ORDONNEES 15
 
int main (void)
{
    int i,j;
    int (*ptr)[ORDONNEES] = NULL;
    int * ptr2 = NULL;
 
    ptr = calloc (ABSCISSES,sizeof (int[ORDONNEES));
 
    ptr2 = ptr;
    for (i=0;i<ABSCISSES*ORDONNEES;++i) *ptr2++=i;
 
    for (i=0;i<ABSCISSES;++i)
    for (j=0;j<ORDONNEES;++j) printf ("%d ",ptr[i][j]);
 
    free (ptr);
 
    puts ("");
    return 0;
}

[Obsidian]

En fait, c'est facile : un pointeur peut être utilisé comme un tableau à une dimension parce qu'on est censé connaître la taille de ce qu'il pointe et, ce faisant, on peut incrémenter le pointeur avec la bonne « distance » pour passer à l'élément suivant. Ça permet de faire fonctionner « ptr++ » et, par extension, toute l'arithmétique des pointeurs.

Donc, un tableau tridimensionnel, c'est un tableau de tableaux bidimensionnels.

Quelque soit le nombre de dimensions de ton tableau, il suffit juste de faire disparaître la « plus grande » (la plus à gauche, donc) derrière l'étoile « * », pour pouvoir ensuite la ré-indexer quand tu en as besoin.

Donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdlib.h>
#include <stdio.h>
 
int main (void)
{
    int i,j,k;
    int  * ptr        = NULL;
    int (* tab)[4][5] = NULL;
 
    ptr = malloc (sizeof (int) * 3 * 4 * 5);
 
    for (i=0;i<(3*4*5);++i) ptr[i]=i;
 
    tab = (int(*)[4][5])ptr;
 
    for (i=0;i<3;++i)
    for (j=0;j<4;++j)
    for (k=0;k<5;++k) printf ("%d ",tab[i][j][k]);
 
    puts ("");
 
    return 0;
}

[VivienD]

Je vois. Donc, si je veux déclarer un tableau à quatre dimensions, je fais comme ci-dessous.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <stdlib.h>
 
#define NB_ABSCISSES 10
#define NB_ORDONNEES 10
#define NB_COTES 10
#define NB_DIMENSION4 10 //J'ai oublié son nom, parce qu'il en a un, le bougre.
 
int main(int argc, char *argv[])
{
    int i = 0;
    int iAbscisseVoulue = 4;
    int iOrdonneeVoulue = 0;
    int iCoteVoulue = 3;
    int iDimension4Voulue = 2;
    int *p = NULL;
    const int (*pTab)[NB_ORDONNEES][NB_COTES][NB_DIMENSION4] = calloc(NB_ABSCISSES, sizeof(int[NB_ORDONNEES][NB_COTES][NB_DIMENSION4]));
 
    p = (int*) pTab;
    for (i = 0 ; i < NB_ABSCISSES * NB_ORDONNEES * NB_COTES * NB_DIMENSION4 ; ++i)
        *p++ = i;
    p = NULL;
 
    printf("Abscisse: %i\tOrdonnee: %i\tCotes: %i\tDimension 4: %i\tValeur: %d\n",
        iAbscisseVoulue, iOrdonneeVoulue, iCoteVoulue, iDimension4Voulue,
        pTab[iAbscisseVoulue][iOrdonneeVoulue][iCoteVoulue][iDimension4Voulue]);
 
    free(pTab);
 
    return 0;
}

[Obsidian]

Tout-à-fait !

Allez, quelques remarques insignifiantes histoire de faire un commentaire :

• Ligne 7, tu utilises « // ». Il n'y a rien de mal à cela, si ce n'est que c'était du C++ au départ et que cela a été re-transposé au C avec C99. Rien ne t'oblige aujourd'hui à te conformer à une version plus ancienne, mais si tu veux faire du code C vraiment strict, tu peux t'habituer à utiliser « /* » et « */ » ;
  
• Je suppose que tu as fait exprès de mettre toutes tes dimensions à « 10 ». Ça tombe bien parce que ça permet de voir tout de suite si la valeur extraite de la cellule est bien la bonne puisqu'elle correspond forcément aux différents indices, concaténés :
  
  

  Code SHELL :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  $ ./test
  Abscisse: 4	Ordonnee: 0	Cotes: 3	Dimension 4: 2	Valeur: 4032

  
  Tu peux également essayer avec d'autres valeurs ;
  
  
  
  
• Enfin, je suppose que là aussi tu le sais, mais tu n'es pas du tout obligé d'initialiser ton tableau de manière linéaire avec ptab. Tu peux très bien utiliser directement les indices entre crochets comme tu le fais pour le lire. Je n'ai utilisé les deux approches que pour montrer que, justement, en déposant une suite de chiffres réputés consécutifs en mémoire, je retombais bien sur mes pieds ensuite en les indexant.

[VivienD]

• Ligne 7, tu utilises « // ». Il n'y a rien de mal à cela, si ce n'est que c'était du C++ au départ et que cela a été re-transposé au C avec C99. Rien ne t'oblige aujourd'hui à te conformer à une version plus ancienne, mais si tu veux faire du code C vraiment strict, tu peux t'habituer à utiliser « /* » et « */ » ;

En fait j'utilise // pour les commentaires temporaires, c'est-à-dire quel code je dois entrer à l'endroit de ces commentaires, et /* ... */ pour les commentaires définitifs.

• Je suppose que tu as fait exprès de mettre toutes tes dimensions à « 10 ». Ça tombe bien parce que ça permet de voir tout de suite si la valeur extraite de la cellule est bien la bonne puisqu'elle correspond forcément aux différents indices, concaténés :
  
  

  Code SHELL :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  $ ./test
  Abscisse: 4	Ordonnee: 0	Cotes: 3	Dimension 4: 2	Valeur: 4032

  
  Tu peux également essayer avec d'autres valeurs ;

En fait je n'étais pas très inspiré pour trouver des valeurs bidons.

• Enfin, je suppose que là aussi tu le sais, mais tu n'es pas du tout obligé d'initialiser ton tableau de manière linéaire avec ptab. Tu peux très bien utiliser directement les indices entre crochets comme tu le fais pour le lire. Je n'ai utilisé les deux approches que pour montrer que, justement, en déposant une suite de chiffres réputés consécutifs en mémoire, je retombais bien sur mes pieds ensuite en les indexant.

Euh... je crois que j'ai de la relecture qui m'attend pour comprendre ce que tu m'exposes.

[Obsidian]

Euh... je crois que j'ai de la relecture qui m'attend pour comprendre ce que tu m'exposes.

Non, rien de compliqué, heureusement. :-)

Je veux dire par là que tu peux très bien remplir ton tableau de la même façon que tu le lis :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>
 
#define ABSCISSES 5
#define ORDONNEES 6
#define COTES 7
 
int main (void)
{
    int i=0,j=0,k=0;
    int (*ptr)[ORDONNEES][COTES] = NULL;
 
    ptr = calloc (ABSCISSES,sizeof (int[ORDONNEES][COTES]));
 
    /* Remplissage */
    for (i=0;i<ABSCISSES;i++)
    for (j=0;j<ORDONNEES;j++)
    for (k=0;k<COTES;k++) ptr[i][j][k] = i * 100 + j * 10 + k;
 
    /* Relecture */
    for (i=0;i<ABSCISSES;i++)
    for (j=0;j<ORDONNEES;j++)
    for (k=0;k<COTES;k++) printf ("%03d ",ptr[i][j][k]);
 
    puts ("");
 
    return 0;
}

J'avais jusque là rempli mon tableau en utilisant une boucle unique pour deux raisons : déposer des données en mémoire de façon complètement indépendante de la déclaration de mon pointeur de tableau, et montrer qu'elles étaient bien déposées consécutivement, dans l'ordre croissant. Ceci pour bien montrer dans quel ordre on les retrouvait ensuite. Mais rien ne t'oblige, bien sûr, à toujours procéder de cette façon.

[VivienD]

Ah ! OK. J'avais juste sévèrement bogué.

J'ai utilisé le remplissage linéaire juste pour l'exemple. Dans mes programmes je procéderai évidemment en utilisant la méthode que tu viens de montrer.

[VivienD]

J'ai étudié rapidement les différents codes pour les listes simplement chaînées disponibles sur internet. La syntaxe qui revient le plus souvent est la suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct SLL_Element { 
  TYPE Data; 
  struct SLL_Element *pNext; 
}SLL_NODE;

Parfois, à la place de TYPE Data;, on peut trouver TYPE *pData;.
Toutefois la déclaration struct SLL_Element *pNext; ne me plaît guère. Est-ce qu'il serait possible de définir cet élément de la manière suivante, quitte à s'infliger de nouvelles contorsions algorithmiques ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct { 
  TYPE Data; 
  TYPE *pNext; 
}SLL_NODE;

Dans ce cas, on aurait:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SLL_NODE Element1, Element2;
Element1.pNext = &Element2.Data;
*(Element1.pNext + 1) = NULL;

[Obsidian]

Non, parce que pNext a vocation à pointer le prochain maillon, pas la donnée elle-même. Si, depuis le premier maillon, tu pointes la première donnée (ça, d'accord) et directement la deuxième donnée plutôt qu'accéder à son maillon, comment fais-tu pour atteindre la troisième et les suivantes ?

[VivienD]

Mon idée du *(ElementN.pNext + 1) ne fonctionne pas ? Tant pis...

[matafan]

Tu ne peux pas être sûr que le compilateur va mettre pNext immédiatement après Data. Pour des questions d'alignement il pourrait décider d'insérer du padding, et dans ce cas ta méthode ne marcherait pas.

Edit : tiens d'ailleurs si tu voulais vraiment tu pourrais faire un truc fiable en castant en char *, en ajoutant offsetof(SLL_NODE, pNext) - offsetof(SLL_NODE, Data) et en recastant le tout en TYPE **. Mais je ne le recommande pas

[Obsidian]

Non, parce que c'est justement le principe de la liste chaînée.

Le principe est d'associer des éléments répartis n'importe où en mémoire, en faisant en sorte que chacun transporte avec lui l'adresse du prochain. Donc, par principe, les éléments ne sont pas consécutifs. Tu ne peux donc pas utiliser l'arithmétique des pointeurs pour déduire leur position.

L'intérêt majeur des listes chaînées est de pouvoir facilement faire évoluer la taille d'une liste en allouant, par exemple, chaque maillon avec un malloc.

Avantage : il est très facile d'insérer ou supprimer un élément dans la liste. Lorsque tu as un maillon « 1 » qui pointe le maillon « 2 », tu « intercales » le nouveau maillon en faisant pointer « 1 » vers « nouveau » et « nouveau » vers « 2 ».

Inconvénient : tu perds l'accès dit « direct » ou « aléatoire », te permettant d'accéder directement à un élément de la liste par son index pour basculer vers un accès dit « séquentiel » dans le sens où tu es obligé de parcourir la liste depuis le début et dans l'ordre pour être certain d'atteindre ton élément. On utilise d'ailleurs la même terminologie avec les fichiers.

À noter également que c'est la signification du mot RAM « Random Access Memory » puisque tu peux accéder directement à n'importe lequel des milliards d'octets qu'elle propose aujourd'hui, et ce en temps constant O(1), ce qui est quand même un avantage remarquable du point de vue algorithmique. La Machine de Turing, dont l'architecture est la mère de celles de tous les ordinateurs, ne l'impose même pas…

[Sve@r]

Avantage : il est très facile d'insérer ou supprimer un élément dans la liste. Lorsque tu as un maillon « 1 » qui pointe le maillon « 2 », tu « intercales » le nouveau maillon en faisant pointer « 1 » vers « nouveau » et « nouveau » vers « 2 ».

Pour des questions de sécurité, il est plutôt conseiller de commencer par faire pointer « nouveau » vers « 2 » avant de briser le lien « 1 » vers « 2 » et le remplacer par « 1 » vers « nouveau ». Car si le programme plante entre les 2 étapes, la liste est toujours complète.

J'ai étudié rapidement les différents codes pour les listes simplement chaînées disponibles sur internet. La syntaxe qui revient le plus souvent est la suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct SLL_Element { 
  TYPE Data; 
  struct SLL_Element *pNext; 
}SLL_NODE;

Parfois, à la place de TYPE Data;, on peut trouver TYPE *pData;.

La seconde écriture dissocie le maillon de son contenu. Ca permet une plus grande souplesse dans l'évolution de « TYPE ».

Toutefois, c'est indiqué moins souvent mais tu auras aussi un gros avantage à définir une structure spécifique à la liste elle-même. Style

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
typedef struct { 
  SLL_NODE *tete; 
}SLL_LIST;

Ca peut paraitre idiot de définir une structure pour un seul pointeur mais ça offre différents avantages

• plus tard, si besoin, tu pourras facilement rajouter d'autres éléments de gestion comme par exemple le dernier maillon, un maillon de lecture, le nombre d'éléments, etc.
  
• tu peux facilement manipuler un tableau de liste
  

  Code c :

  Sélectionner tout - Visualiser dans une fenêtre à part

  SLL_LIST tab[100];

  Alors que si tu te contentes de n'avoir que le pointeur de tête, tu es obligé de passer par des écritures moins agréables
  

  Code c :

  Sélectionner tout - Visualiser dans une fenêtre à part

  SLL_NODE *tete[100];

• dans le cas où tu utilises une fonction d'insertion, tu es obligé, dans la version simple, de lui passer un double pointeur. Uniquement parce que la fonction doit avoir le droit d'insérer en début et donc modifier la tête. Style
  

  Code c :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  void insert_maillon(SLL_NODE **tete, SLL_NODE *elem)
  {
      if (elem doit s insérer au début)
      {
           elem->next=(*tete)->next;
           (*tete)=elem;
      }
      else
      {
              ...
      }
  }
   
  int main()
  {
      SLL_NODE *tete;
      insert_maillon(&tete, ...);
  }

  
  Ca t'amène à une écriture lourde et, à force, désagréable. Alors qu'avec une structure appropriée, tu passes juste l'adresse de la structure (un simple pointeur) et ta fonction peut l'utiliser pour manipuler la tête comme elle le sent, style...
  

  Code c :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  void insert_maillon(SLL_LIST *liste, SLL_NODE *elem)
  {
      if (elem doit s insérer au début)
      {
           elem->next=liste->tete;
           liste->tete=elem;
      }
      else
      {
              ...
      }
  }
   
  int main()
  {
      SLL_LIST liste;
      insert_maillon(&liste, ...);
  }

• ça t'ouvre facilement la porte vers l'orienté objet, style
  

  Code c :

  Sélectionner tout - Visualiser dans une fenêtre à part

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  void list_init(SLL_LIST *liste)
  {
      liste->tete=NULL;
  }
   
  void list_free(SLL_LIST *liste)
  {
      SLL_NODE *current, *next;
   
      current=liste->tete;
      next=current->next;
      while (1)
      {
            free(current);
            if (next == NULL) break;
   
            current=next;
            next=current->next;
      }
  }
   
  int main()
  {
      SLL_LIST liste;
      list_init(&liste);
   
      ...
      ...
      ...
   
      list_free(&liste);
  }

Bref pour résumer, petite analogie pratique: tu peux tenir tes chemises par le col mais tu les manipules mieux si tu les mets sur un cintre...

[VivienD]

@Svear :
J'avais déjà pensé à créer une sorte de registre par liste chaînée ; pour les listes simplement chaînées, ça donnait une structure comme suit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct{
     SLL_NODE *pFirst;
     int iSize;
}SLL_REGISTER;

Lorsque l'on crée un liste simplement chaînée, cela revient grosso modo à ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SLL_REGISTER *sll_pRegistre = malloc(sizeof(SLL_REGISTER));
(*sll_pRegistre).iSize = 0;
(*sll_pRegistre).pFirst = NULL;

Ensuite lors d'un ajout d'élément dans la liste, il faudra penser à incrémenter ou décrémenter (*sll_pRegistre).iSize.

[Sve@r]

@Svear :
J'avais déjà pensé à créer une sorte de registre par liste chaînée ; pour les listes simplement chaînées, ça donnait une structure comme suit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct{
     SLL_NODE *pFirst;
     int iSize;
}SLL_REGISTER;

Lorsque l'on crée un liste simplement chaînée, cela revient grosso modo à ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SLL_REGISTER *sll_pRegistre = malloc(sizeof(SLL_REGISTER));
(*sll_pRegistre).iSize = 0;
(*sll_pRegistre).pFirst = NULL;

Tu avais quasiment trouvé tout seul l'idée. Accessoirement (*pt).membre s'écrit plus facilement pt->membre et ça fait un peu riche de passer par un pointeur + malloc pour gérer une liste

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SLL_REGISTER sll_registre;
sll_registre.iSize = 0;
sll_registre.pFirst = NULL;

Ensuite lors d'un ajout d'élément dans la liste, il faudra penser à incrémenter ou décrémenter (*sll_pRegistre).iSize.

D'où l'approche objet avec une fonction dédiée à chaque opération. Ainsi, tu centralises les actions et tu répercutes plus facilement les modifications de structure sans risquer d'en oublier. Exemple: je veux rajouter un compteur d'éléments dans ma structure

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
typedef struct { 
  SLL_NODE *tete; 
  unsigned long cpt;
}SLL_LIST;
 
void list_init(SLL_LIST *liste)
{
    liste->tete=NULL;
    liste->cpt=0;
}

Et je ne touche pas au main qui reste inchangé

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    SLL_LIST liste;
    list_init(&liste);
 
    ...
    ...
    ...
 
    list_free(&liste);
}

[VivienD]

Je récapitule.

Pour une liste simplement chaînée, il faut d'abord créer deux structures – la première pour les éléments et l'autre pour le registre. Pour les éléments on aura :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct sll_element{
    TYPE Data; /* ou TYPE *pData; */
    struct sll_element *pNext;
}SLL_NODE;

et pour le registre ce sera :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct {
    unsigned int iSize;
    SLL_NODE *pFirst;
}SLL_REGISTER;

Ensuite il faut coder tout un chapelet de fonctions pour gérer cette liste : création de la liste, initialisation de la liste, ajout d'un élément, suppression d'un élément et suppression de la liste.

En ce qui concerne les listes doublement chaînées, les structures deviennent :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
typedef struct dll_element{
    TYPE Data; /* ou TYPE *pData; */
    struct dll_element *pPrevious;
    struct dll_element *pNext;
}DLL_NODE;
 
typedef struct{
    unsigned int iSize;
    DLL_NODE *pFirst;
    DLL_NODE *pLast;
}DLL_REGISTER;

Ensuite, il faut adapter la « harde » de fonctions de gestion des listes simplement chaînées aux listes doublement chaînées.

J'ai bon ?

[Sve@r]

Je récapitule.

Pour une liste simplement chaînée, il faut d'abord créer deux structures – la première pour les éléments et l'autre pour le registre. Pour les éléments on aura :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct sll_element{
    TYPE Data; /* ou TYPE *pData; */
    struct sll_element *pNext;
}SLL_NODE;

et pour le registre ce sera :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct {
    unsigned int iSize;
    SLL_NODE *pFirst;
}SLL_REGISTER;

Ensuite il faut coder tout un chapelet de fonctions pour gérer cette liste : création de la liste, initialisation de la liste, ajout d'un élément, suppression d'un élément et suppression de la liste.

En ce qui concerne les listes doublement chaînées, les structures deviennent :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
typedef struct dll_element{
    TYPE Data; /* ou TYPE *pData; */
    struct dll_element *pPrevious;
    struct dll_element *pNext;
}DLL_NODE;
 
typedef struct{
    unsigned int iSize;
    DLL_NODE *pFirst;
    DLL_NODE *pLast;
}DLL_REGISTER;

Ensuite, il faut adapter la « harde » de fonctions de gestion des listes simplement chaînées aux listes doublement chaînées.

J'ai bon ?

Exactement. Plus tu fais ce travail pénible de conception très en amont, plus tout te sera plus facile ensuite pour maintenir et faire évoluer le projet.

Accessoirement, on préfère réserver les majuscules aux macros et nommer les types "t_..."

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
typedef struct s_element{
    TYPE Data; /* ou TYPE *pData; */
    struct s_element *pPrevious;
    struct s_element *pNext;
} t_node;
 
typedef struct{
    unsigned int iSize;
    t_node *pFirst;
    t_node *pLast;
}t_register;

[VivienD]

Je poursuis sur mes listes simplement chaînées, car j'ai choisi de créer une bibliothèque les concernant : je n'ai guère envie que recopier tous les typedef et toutes les fonctions de gestion dès que je souhaite m'en servir. Par ailleurs, j'en ferai de même pour les autres types de liste. Voici ce que ça donne :

Code : singlylinkedlist.h :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#ifndef SINGLYLINKEDLIST_H_INCLUDED
#define SINGLYLINKEDLIST_H_INCLUDED
 
/*
##############################
##### Nouveaux types #########
##############################
*/
 
typedef int t_slldata;
 
typedef unsigned int t_sllsize;
 
typedef struct sll_element{
    t_slldata *pData;
    struct sll_element *pNext;
}t_sllnode;
 
typedef struct{
    t_sllsize Size;
    t_sllnode *pFirst;
}t_sllreg;
 
/*
##############################
##### Gestion ################
##############################
*/
t_sllreg* newSLL(void);
void delSLL(t_sllreg *Reg);
t_sllnode* sllGoTo(t_sllreg *Reg, t_sllsize Target);
void sllAddNode(t_sllreg *Reg, t_sllsize Target);
void sllDelNode(t_sllreg *Reg, t_sllsize Target);
 
#endif

Code : singlylinkedlist.c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>
#include "singlylinkedlist.h"
 
t_sllreg* newSLL(void) /* Créer et initialiser une nouvelle liste */
{
    t_sllreg New = {0, NULL};
    return &New;
}
 
void delSLL(t_sllreg *Reg) /* Vider et supprimer une liste */
{
    (*Reg).Size = 0;
    (*Reg).pFirst = NULL;
}
 
t_sllnode* sllGoTo(t_sllreg *Reg, t_sllsize Target) /* Sélectionner un élément */
{
    if(Target > (*Reg).Size)
        return sllGoTo(Reg, (*Reg).Size);
    else
    {
        t_sllsize Pos = 1;
        t_sllnode *p = (*Reg).pFirst;
        for(Pos = 2 ; Pos <= Target ; Pos++)
            p = (*p).pNext;
        return p;
    }
}
 
void sllAddNode(t_sllreg *Reg, t_sllsize Target) /*Ajouter un élément */
{
    t_sllnode New{NULL, NULL};
    if(Target <= 1)
    {
        New.pNext = (*Reg).pFirst;
        (*Reg).pFirst = &New;
    }
    else
    {
        t_sllnode *p = sllGoTo(Reg, Target - 1);
        New.pNext = (*p).pNext;
        (*p).Next = &New;
    }
    (*Reg).Size++;
}
 
void sllDelNode(t_sllreg *Reg, t_sllsize Target) /* Supprimer un élément */
{
    t_sllnode *p[2] = {NULL};
    if(Target <= 1)
    {
        p[0] = (*Reg).pFirst;
        p[1] = (*p[0]).pNext;
        (*Reg).pFirst = p[1];
    }
    else
    {
        p[0] = sllGoTo(Reg, Target - 1);
        p[1] = (*p[0]).pNext;
        p[1] = (*p[1]).pNext;
        (*p[0]).pNext = p[1];
    }
    (*Reg).Size--;
}

Des améliorations sont à prévoir, vu que c'est un premier jet. Par exemple, la fonction t_sllreg* newSLL(void) renvoie l'adresse d'une variable locale et il en va à peu près de même pour void sllAddNode(t_sllreg *Reg, t_sllsize Target). D'autre part, j'utilise le vecteur t_sllnode *p[] dans la fonction void sllDelNode(t_sllreg *Reg, t_sllsize Target), alors que j'aurais préféré avoir à faire avec un simple pointeur comme t_sllnode *p des fonctions t_sllnode sllGoTo(t_sllreg *Reg, t_sllsize Target) et void sllAddNode(t_sllreg *Reg, t_sllsize Target).
Savez-vous comment résoudre ces problèmes ?