C liste double liée avec le type de données abstraites

Question

J'ai besoin dans la liste double liée en C, mais il doit être pour différents types. En C++, nous utilisons des modèles pour cela. Où puis-je trouver un exemple en C pour une liste double liée avec des items de types abstraits.

Merci

Answer 1

Il existe plusieurs approches possibles, dont l'une consiste à stocker un void* dans votre terminal ADT.

J'ai toujours trouvé que c'est un peu pénible dans une liste chaînée puisque vous devez gérer son allocation séparément à la liste elle-même. En d'autres termes, pour allouer un nœud, vous devez alimenter le nœud et sa charge utile séparément (et n'oubliez pas de les nettoyer tous les deux lors de la suppression).

Une approche que je l'ai utilisé dans le passé est d'avoir une structure « taille variable » comme:

typedef struct _tNode { 
    struct _tNode *prev; 
    struct _tNode *next; 
    char payload[1]; 
} tNode; 

Maintenant, cela ne regarder taille variable mais nous allons allouer une structure ainsi:

typedef struct { 
    char Name[30]; 
    char Addr[50]; 
    char Phone[20]; 
} tPerson; 
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson)); 

maintenant vous avez un nœud qui, à toutes fins utiles, ressemble à ceci:

typedef struct _tNode { 
    struct _tNode *prev; 
    struct _tNode *next; 
    char Name[30]; 
    char Addr[50]; 
    char Phone[20]; 
} tNode; 

ou, sous forme graphique (où [n] signifie n octets):

+------------+ 
| prev[4] | 
+------------+ 
| next[4] | 
+------------+ +-----------+ 
| payload[1] | | Name[30] | <- overlap 
+------------+ +-----------+ 
       | Addr[50] | 
       +-----------+ 
       | Phone[20] | 
       +-----------+ 

qui est, en supposant savez comment traiter correctement la charge utile. Cela peut se faire comme suit:

node->prev = NULL; 
node->next = NULL; 
tPerson *person = &(node->payload); // cast for easy changes to payload. 
strcpy (person->Name, "Richard Cranium"); 
strcpy (person->Addr, "10 Smith St"); 
strcpy (person->Phone, "555-5555"); 

CAST ligne jette simplement l'adresse du être une adresse du type de charge utile tPerson réelle caractère payload (dans le type tNode).

En utilisant cette méthode, vous pouvez transporter tout type de charge utile que vous voulez dans un nœud, même différents types de charge utile dans chaque noeud, si vous faites la structure plus comme:

typedef struct _tNode { 
    struct _tNode *prev; 
    struct _tNode *next; 
    int payloadType;  // Allows different payload type at each node. 
    char payload[1]; 
} tNode; 

et utiliser payloadType pour stocker un indicateur de la charge utile.

Ceci a l'avantage sur une union en ce qu'elle ne gaspille pas d'espace, comme on peut le voir avec les éléments suivants:

union { 
    int fourBytes; 
    char oneHundredBytes[100]; 
} u; 

où 96 octets sont gaspillées chaque fois que vous stockez un type entier dans la liste (pour un entier de 4 octets). Le type de charge utile dans le tNode vous permet de détecter facilement le type de charge utile que ce nœud est en train de transporter, afin que votre code puisse décider comment le traiter. Vous pouvez utiliser quelque chose le long des lignes de:

#define PAYLOAD_UNKNOWN  0 
#define PAYLOAD_MANAGER  1 
#define PAYLOAD_EMPLOYEE 2 
#define PAYLOAD_CONTRACTOR 3 

ou (probablement mieux):

typedef enum { 
    PAYLOAD_UNKNOWN, 
    PAYLOAD_MANAGER, 
    PAYLOAD_EMPLOYEE, 
    PAYLOAD_CONTRACTOR 
} tPayLoad; 

La seule chose que vous devez surveiller est d'assurer que l'alignement de la charge utile est correcte. Étant donné que mon espace réservé de charge utile et la charge utile sont tous les types char, ce n'est pas un problème. Cependant, si votre charge utile est composée de types avec des exigences d'alignement plus strictes (comme quelque chose de plus strict que les pointeurs, vous devrez peut-être ajuster pour cela).

Bien que je n'ai jamais vu un environnement avec des alignements plus stricts que les pointeurs, est possible selon la norme ISO C.

Vous pouvez généralement obtenir le simple alignement requis en utilisant un type de données pour l'espace réservé de charge utile qui a l'exigence d'alignement strict tels que:

long payload; 

---

Avec le recul, il me semble que vous avez probablement ne pas besoin un tableau en tant que placeholder de la charge utile. C'est assez simple pour avoir quelque chose dont vous pouvez prendre l'adresse. Je soupçonne que mon idiome particulier remonte à l'époque où je stockais juste un tableau de personnages (plutôt qu'une structure) et les référenciez directement. Dans ce cas, vous pouvez utiliser payload[] seul sans utiliser un autre type.

Answer 2

Manipulation des données arbitraires dans C se fait habituellement à l'aide des pointeurs - spécifiquement void * dans la plupart des cas.

Answer 3

Le point de vue le plus proche de C vers une classe de base "objet" ou type typé est un pointeur void. Un void * représente un pointeur vers quelque chose, mais il ne spécifie pas le type de données pointées. Si vous voulez accéder aux données, vous devez utiliser une distribution.

Un nœud de liste doublement chaînée pourrait ressembler à ceci:

struct DoubleLinkedListNode { 
    struct DoubleLinkedListNode *previous, *next; 
    void *data; 
}; 

Pour attribuer un nœud une chaîne, par exemple, vous pouvez faire:

char myString[80] = "hello, world"; 
struct DoubleLinkedListNode myNode; 
myNode.data = myString; 

Pour obtenir la chaîne de retour d'un noeud , vous utilisez un casting:

char *string = (char *)myNode.data; 
puts(string); 

pour stocker un pointeur non, vous devez faire un pointeur à partir des données. Pour les structures, vous pouvez simplement déréférencer l'instance si sa durée de vie est suffisamment longue (similaire à l'exemple ci-dessus). Si ce n'est pas le cas, ou si vous avez affaire à un type primitif (par exemple int ou float), vous devez ajouter malloc un peu d'espace. Assurez-vous de libérer la mémoire lorsque vous avez terminé.

Answer 4

Vous pouvez utiliser des macros comme illustré here (cet exemple particulier implémente des tables de hachage génériques).

Answer 5

De toute évidence, le noyau Linux utilise des listes chaînées à de nombreux endroits, à la fois dans le noyau lui-même et dans les nombreux modules de pilotes de périphériques. Presque tous ces éléments sont implémentés en utilisant le même ensemble de macros défini dans linux/list.h

Voir http://isis.poly.edu/kulesh/stuff/src/klist/ ou http://kernelnewbies.org/FAQ/LinkedLists pour une bonne explication.

Les macros semblent un peu étranges au début, mais sont faciles à utiliser et deviennent rapidement une seconde nature. Ils peuvent être facilement adaptés pour être utilisés dans l'espace utilisateur (voir list.h).