liste chaînée « polyvalent » mise en œuvre dans le plus pur C

Question

Ce n'est pas exactement une question technique, car je sais C genre de assez pour faire les choses que je dois (je veux dire, en termes de ne pas «laisser la langue dans votre chemin), cette question est essentiellement une question «quelle direction prendre.

Situation est: Je suis actuellement un cours d'algorithmes avancés, et pour des raisons de « grandir en tant que programmeurs », je suis obligé d'utiliser pur C pour mettre en œuvre les travaux pratiques (il fonctionne bien: à peu près toute petite erreur que vous faites vous force à comprendre complètement ce que vous faites pour le fixer). Au cours de la mise en œuvre, je lance évidemment le problème d'avoir à mettre en œuvre les structures de données « de base » à partir de la base:. Listes effectivement non seulement liés, mais aussi des piles, des arbres, etc.

Je me concentre sur les listes dans ce sujet car il est généralement une structure que je finis à l'aide beaucoup dans le programme, soit comme une structure « principale » ou comme une structure « d'aide » pour d'autres plus grands (par exemple, un hachage arbre qui résout les conflits en utilisant une liste chaînée).

Cela exige que les éléments liste des magasins de lots de différents types. Je suppose ici comme prémisse que je ne veux pas recoder la liste pour chaque type. Donc, je peux venir avec ces alternatives:

• Faire une liste de pointeurs vides (un peu inélégante, plus difficile à déboguer)
• Faire une seule liste, mais ayant une union comme « type d'élément », contenant tous les types d'éléments que je vais utiliser dans le programme (plus facile à déboguer, l'espace des déchets si les éléments ne sont pas tous de la même taille )
• En utilisant une macro préprocesseur pour régénérer le code pour chaque type, dans le style de SGLIB , l 'imitation' C ++ ' STL (solution créative, les éléments ont le type explicite, ils sont en fait quand ils sont retournés,, ne gaspillez pas un espace tout changement dans le code de la liste peut être vraiment dramatique )
• Votre idée / solution

Pour la question claire: que l'on de ce qui précède est le meilleur

PS: Depuis que je suis essentiellement dans un contexte académique, je suis aussi très intéressé par la vue des personnes qui travaillent avec C pur là-bas dans l'industrie. Je comprends ceux qui sont dans la zone des systèmes embarqués la plupart des programmeurs purs C, où je ne pense pas que ce genre de problème que je suis confronté est commun. Cependant, si quelqu'un sait là-bas comment faire « dans le monde réel », je serais très intéressé par votre avis.

Answer 1

A void * est un peu d'une douleur dans une liste, puisque vous devez gérer l'allocation est séparément à la liste elle-même. 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;
    int payloadType;
    char payload[1];  // or use different type for alignment.
} tNode;

Maintenant, je me rends compte que ne pas Rechercher de taille variable mais nous allons allouer une structure ainsi:

typedef struct {
    char Name[30];
    char Addr[50];
} 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;
    int payloadType;
    char Name[30];
    char Addr[50];
} tNode;

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

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

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

node->prev = NULL;
node->next = NULL;
node->payloadType = PLTYP_PERSON;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Bob Smith");
strcpy (person->Addr, "7 Station St");

Cette ligne de coulée jette simplement l'adresse du caractère payload (dans le type de tNode) soit une adresse du type réel de la charge utile de tPerson.

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 , sans l'espace perdu d'un syndicat. Ce gaspillage peut être vu avec ce qui suit:

union {
    int x;
    char y[100];
} u;

où 96 octets sont gaspillées chaque fois que vous stockez un type entier dans la liste (pour un nombre entier de 4 octets).

Le type de charge utile dans le tNode vous permet de détecter facilement ce type de charge utile ce noeud est en train, de sorte que votre code peut 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;

Answer 2

Mon .002 $:

• Faire une liste de pointeurs vides (un peu diselegant, plus difficile à déboguer)

Ce n'est pas un mauvais choix, à mon humble avis, si vous devez écrire en C. Vous pouvez ajouter des méthodes de l'API pour permettre l'application de fournir une méthode d'impression () pour faciliter la mise au point. Des méthodes similaires pourraient être invoquées lorsque (par exemple) éléments sont ajoutés ou supprimés de la liste. (Pour les listes chaînées, ce qui est généralement pas nécessaire, mais pour les structures de données plus complexes - tables de hachage, par exemple) -. Il peut parfois être une bouée de sauvetage)

• Faire une seule liste, mais ayant une union comme « type d'élément », contenant tous les types d'éléments que je vais utiliser dans le programme (plus facile à déboguer, l'espace des déchets si les éléments ne sont pas tous de la même taille)

J'éviter cela comme la peste. (Eh bien, vous avez demandé.) Avoir une dépendance, à la compilation configurée manuellement à partir de la structure de données à ses types contenus est le pire de tous les mondes. Encore une fois, à mon humble avis.

• En utilisant une macro préprocesseur pour régénérer le code pour chaque type, dans le style de SGLIB (sglib.sourceforge.net), « imitation » C ++ de STL (solution créative, les éléments ont le type explicite qu'ils en fait, ne perd pas l'espace sont quand ils sont retournés, tout changement dans le code de la liste peut être vraiment dramatique)

idée Intriguant, mais comme je ne sais pas SGLIB, je ne peux pas dire beaucoup plus que cela.

• Votre idée / solution

Je vais avec le premier choix.

Answer 3

Je l'ai fait dans le passé, dans notre code (qui a depuis été converti en C ++), et à l'époque, décidé sur le vide * approche. Je viens de faire cela pour la flexibilité -. Nous étions presque toujours le stockage d'un pointeur dans la liste de toute façon, et la simplicité de la solution, et la facilité d'utilisation de celui-ci l'emportaient sur (moi) les inconvénients aux autres approches

Cela étant dit, il y avait un temps où il a causé un bug méchant qui était difficile à déboguer, il est donc certainement pas une solution parfaite. Je pense qu'il est toujours celui que je prendrais, bien que, si je faisais cela à nouveau maintenant.

Answer 4

En utilisant une macro préprocesseur est la meilleure option. noyau Linux liste chaînée est une excellente mise en œuvre d'une eficient d'un circulairement lié liste C. est très portable et facile à utiliser. Voici une version autonome d'en-tête du noyau linux 2.6.29 de list.h .

Le FreeBSD / OpenBSD sys / file d'attente est une autre bonne option pour une liste liée à base macro générique

Answer 5

Je n'ai pas codé C au cours des années, mais GLib prétend fournir « un grand un ensemble de fonctions d'utilité pour les chaînes et les structures de données communes », parmi lesquels sont des listes liées.

Answer 6

Bien qu'il soit tentant de penser à résoudre ce genre de problème en utilisant les techniques d'une autre langue, par exemple, les génériques, dans la pratique, il est rarement une victoire. Il y a probablement des solutions qui obtiennent en conserve tout de la plupart du temps (et vous disent dans leur documentation quand ils se trompent), à l'aide qui pourrait manquer le point de la mission, donc je pense que deux fois. Pour un très petit nombre de cas, il pourrait être feasable de rouler votre propre, mais pour un projet de toute taille raisonnable, sa ne sera probablement pas en valeur l'effort de débogage.

Au contraire, lors de la programmation en langage x, vous devez utiliser les expressions idiomatiques de la langue x. Ne pas écrire java lorsque vous utilisez python. Ne pas écrire C lorsque vous utilisez système. Ne pas écrire C ++ lorsque vous utilisez C99.

Moi-même, je finirais probablement utiliser quelque chose comme la suggestion de Pax, mais en fait utiliser une union de char [1] et void * et int, pour rendre les cas communs pratique (et un drapeau de type enumed)

(Je voudrais aussi probablement finir par mettre en place un arbre de fibonacci, juste cause que cela semble soigné, et vous ne pouvez mettre en œuvre RB Les arbres tant de fois avant qu'il ne perde sa saveur, même si cela est mieux pour les cas les plus courants que ça être utilisé.)

modifier en fonction de votre commentaire, il semble que vous avez un très bon cas pour l'utilisation d'une solution en conserve. Si votre moniteur permet, et la syntaxe qu'il offre est à l'aise, lui donner un tourbillon.

Answer 7

Ceci est un bon problème. Il y a deux solutions J'aime:

• Dave Hanson C Interfaces et Implémentations utilise une liste de void * pointeurs, ce qui est assez bon pour moi.

• Pour ma étudiants , j'ai écrit un script awk pour générer des fonctions de liste spécifique de type . Par rapport aux macros préprocesseur, il nécessite une étape supplémentaire de construction, mais le fonctionnement du système est beaucoup plus transparent pour les programmeurs sans beaucoup d'expérience. Et cela aide vraiment faire le cas pour le polymorphisme paramétrique, qu'ils voient plus loin dans leur programme.

  Voici ce qu'un ensemble de fonctions ressemble à:

  int      lengthEL (Explist *l);
  Exp*     nthEL    (Explist *l, unsigned n);
  Explist *mkEL     (Exp *hd, Explist *tl);
  

  Le script awk est une horreur 150 en ligne; il recherche code C pour typedefs et génère un ensemble de fonctions de la liste pour chacun d'eux. Il est très vieux; Je pourrais sans doute faire mieux maintenant: -)

Je ne donnerais pas une liste des syndicats le temps de la journée (ou de l'espace sur mon disque dur). Ce n'est pas sûr, et ce n'est pas extensible, vous pouvez tout aussi bien utiliser void * et faire avec elle.

Answer 8

Une amélioration par rapport à ce qui en fait une liste de vide * serait en fait une liste de struct qui contiennent un vide * et une méta-données sur ce que le vide * souligne, y compris le type, la taille, etc.

D'autres idées:. Incorporer un interpréteur Perl ou Lisp

Ou aller à mi-chemin: lien avec la bibliothèque Perl et en faire une liste de Perl ou quelque chose SVs

.

Answer 9

Je serais probablement aller avec le vide * me approche, mais il m'a semblé que vous pouvez stocker vos données XML. Ensuite, la liste peut juste avoir un char * pour les données (qui vous analyser la demande pour tous les éléments que vous avez besoin sous) ....