implementazione lista collegata 'multiuso' in puro C

StackOverflow https://stackoverflow.com/questions/736307

Domanda

Questa non è esattamente una questione tecnica, dal momento che so C tipo di abbastanza per fare le cose che devo (voglio dire, in termini di non 'lasciare che la lingua ottenere nel vostro senso'), quindi questa domanda è fondamentalmente un 'quale direzione prendere' domanda.

La situazione è: Attualmente sto prendendo un corso di algoritmi avanzati, e per il bene di 'crescere come i programmatori', sono tenuto a utilizzare puro C per attuare le esercitazioni pratiche (che funziona bene: praticamente qualsiasi piccolo errore si rendere effettivamente ti costringe a capire completamente quello che stai facendo per risolvere il problema). Nel corso di attuazione, ovviamente incontrato il problema di dover attuare le strutture di dati 'di base' da zero:. Liste in realtà non solo legati, ma anche pile, alberi, eccetera

mi sto concentrando sulle liste in questa discussione, perché è tipicamente una struttura che finire con un sacco nel programma, sia come struttura di 'main' o come una struttura 'aiuto' per altri più grandi (ad esempio, un hash albero che risolve i conflitti utilizzando una lista collegata).

Ciò richiede che l'elenco memorizza elementi di un sacco di diversi tipi. Io parto dal presupposto qui come premessa che io non voglio ricodificare l'elenco per ogni tipo. Quindi, posso venire con queste alternative:

  • Fare un elenco di puntatori void (kinda poco elegante; più difficile da eseguire il debug)
  • Fare una sola lista, ma che hanno un Union come 'tipo di elemento', che contiene tutti i tipi di elementi che è possibile usare nel programma (più facile da eseguire il debug; rifiuti spazio se gli elementi non sono tutti della stessa dimensione )
  • Utilizzo di una macro di preprocessore per rigenerare il codice per ogni tipo, nello stile di SGLIB , 'imitando' C ++ 's STL (soluzione creativa; non sprecare spazio, elementi hanno il tipo esplicito che realmente sono quando sono restituiti; alcun cambiamento nel codice elenco può essere davvero drammatica )
  • La tua idea / soluzione

Per fare la domanda chiara: quale di quanto sopra è migliore

PS: Dato che io sono fondamentalmente in un contesto accademico, sono molto interessato alla vista delle persone che lavorano con puro C là fuori nel settore anche. Capisco che la maggior parte dei programmatori puri C sono nella zona di dispositivi embedded, dove io non credo che questo tipo di problema che sto affrontando è comune. Tuttavia, se qualcuno là fuori sa come si fa 'nel mondo reale', sarei molto interessato al vostro parere.

È stato utile?

Soluzione

Un void * è un po 'di dolore in una lista collegata da quando si deve gestire è l'allocazione separatamente alla lista stessa. Un approccio che ho usato in passato è quello di avere una struttura 'di dimensione variabile' come: 

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char payload[1];  // or use different type for alignment.
} tNode;

Ora mi rendo conto che non significa Cerca di dimensioni variabili ma cerchiamo di allocare una struttura così: 

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

Ora avete un nodo che, per tutti gli effetti, si presenta così: 

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

o, in forma grafica (dove [n] significa n bytes): 

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

Cioè, supponendo che si sa come affrontare correttamente il carico utile. Questo può essere fatto nel seguente modo: 

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");

Quella linea getto getta semplicemente l'indirizzo del personaggio payload (nel tipo tNode) per essere un indirizzo del tipo tPerson carico utile effettivo.

Con questo metodo, è possibile trasportare qualsiasi tipo di carico utile che si desidera in un nodo, anche diversi tipi di payload in ogni nodo , senza lo spazio sprecato di un'unione. Questo spreco può essere visto con il seguente: 

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

dove 96 byte sono sprecati ogni volta che si memorizza un tipo intero nella lista (per un numero intero di 4 byte).

Il tipo di carico utile in tNode consente di rilevare facilmente che tipo di payload questo nodo sta portando, in modo che il codice può decidere come elaborarlo. È possibile utilizzare qualcosa sulla falsariga di: 

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

o (probabilmente migliore): 

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

Altri suggerimenti

Il mio $ .002:

  • Fare un elenco di puntatori void (kinda diselegant; più difficile da eseguire il debug)

Questa non è una cattiva scelta, secondo me, se è necessario scrivere in C. Si potrebbe aggiungere metodi API per consentire l'applicazione di fornire un metodo di stampa () per la facilità di debugging. Metodi simili possono essere richiamati quando (per esempio) articoli vengono aggiunti o rimossi dalla lista. (Per le liste collegate, questo di solito non è necessaria, ma per più strutture dati complesse - tabelle hash, per esempio) -. A volte può essere un salvagente)

  • Fare una sola lista, ma avere un sindacato come 'tipo di elemento', che contiene tutti i tipi di elementi che è possibile usare nel programma (più facile da eseguire il debug; rifiuti spazio se gli elementi non sono tutti della stessa dimensione)

Vorrei evitare come la peste. (Beh, hai chiesto.) Avere un manuale-configurato, al momento della compilazione della dipendenza dalla struttura dati per i suoi tipi contenute è il peggiore di tutti i mondi. Anche in questo caso, IMHO.

  • Utilizzo di una macro di preprocessore per rigenerare il codice per ogni tipo, nello stile di SGLIB (sglib.sourceforge.net), 'imitando' C ++ 's STL (soluzione creativa; non sprecare spazio, elementi hanno il tipo esplicito che in realtà sono quando sono restituiti, qualsiasi cambiamento nel codice elenco può essere davvero drammatica)

un'idea intrigante, ma dal momento che non so SGLIB, non posso dire molto di più.

  • La tua idea / soluzione

mi piacerebbe andare con la prima scelta.

L'ho fatto in passato, nel nostro codice (che da allora è stato convertito in C ++), e, al momento, deciso il * approccio vuoto. Ho appena fatto questo per una maggiore flessibilità -. Eravamo quasi sempre la memorizzazione di un puntatore nella lista in ogni modo, e la semplicità della soluzione, e l'usabilità di esso superato (per me) i lati negativi agli altri approcci

Detto questo, c'è stata una volta in cui ha causato qualche brutto bug che era difficile da eseguire il debug, quindi non è sicuramente una soluzione perfetta. Penso che sia ancora quello mi piacerebbe prendere, però, se stavo facendo di nuovo ora.

Utilizzo di una macro di preprocessore è l'opzione migliore. Il Linux kernel lista collegata è un eccellente un'implementazione eficient di un collegato circolarmente lista in C. è molto portabile e facile da usare. qui una versione autonoma di kernel Linux 2.6.29 intestazione list.h .

Il FreeBSD / OpenBSD sys / coda è un'altra buona opzione per una lista collegata macro generico basato

Non ho codificato C in anni, ma GLib pretende di fornire "un grande set di funzioni di utilità per archi e strutture di dati comuni", tra le quali sono collegate le liste.

Anche se è forte la tentazione di pensare di risolvere questo tipo di problema utilizzando le tecniche di un'altra lingua, per esempio, farmaci generici, in pratica è raramente una vittoria. Probabilmente ci sono alcune soluzioni in scatola che lo fanno bene la maggior parte del tempo (e si raccontano nella loro documentazione quando ottengono sbagliato), usando che potrebbero perdere il punto della cessione, quindi mi piacerebbe pensare due volte su di esso. Per pochissimi numero di casi, potrebbe essere fattibile per rotolare il proprio, ma per un progetto di qualsiasi dimensione ragionevole, non è probabile che sia valsa la pena di debug.

Al contrario, quando la programmazione in linguaggio x, è necessario utilizzare gli idiomi del linguaggio x. Non scrivere Java quando si sta utilizzando Python. Non scrivere C quando si utilizza schema. Non scrivere C ++ quando si utilizza C99.

Io, probabilmente sarei finire con qualcosa come suggerimento di Pax, ma in realtà usano un'unione di char [1] e void * e Int, per rendere i casi comuni conveniente (e un tipo di bandiera enumed)

(Mi piacerebbe anche probabilmente alla fine l'attuazione di un albero di Fibonacci, giusta causa che suona pulito, ed è possibile implementare solo RB alberi così tante volte prima che perda il suo sapore, anche se questo è meglio per i casi comuni che sarebbe essere utilizzati per.)

modifica , sulla base di commenti, sembra che hai un buon caso per l'utilizzo di una soluzione in scatola. Se il vostro istruttore lo permette, e la sintassi che offre sente a suo agio, dargli un vortice.

Questo è un buon problema. Ci sono due soluzioni che mi piace:

    di

  • Dave Hanson C Interfacce e implementazioni utilizza un elenco di void * puntatori, il che è abbastanza buono per me.

  • Per il mio studenti , ho scritto un script awk per generare funzioni elenco specifico di tipo . Rispetto al macro del preprocessore, richiede un passaggio di generazione in più, ma il funzionamento del sistema è molto più trasparente per i programmatori senza un sacco di esperienza. Ed è davvero aiuta a rendere il caso per il polimorfismo parametrico, che vedono più avanti nel loro curriculum.

    Ecco quello che un set di funzioni appare come: 

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

    Lo script awk è un 150-line orrore; esso cerca di codice C per typedefs e genera un insieme di funzioni di lista per ciascuno di essi. E 'molto vecchio; Probabilmente potrei fare meglio ora: -)

Non darei un elenco delle unioni l'ora del giorno (o lo spazio sul mio hard disk). Non è sicuro, e non è estendibile, quindi si può anche semplicemente usare void * e da fare con esso.

Un miglioramento rispetto rendendolo un elenco di void * sarebbe che lo rende una lista di struct che contengono un void * e alcuni meta-dati su ciò che il void * indica, tra cui il tipo, dimensioni, ecc.

Altre idee:. Incorporare un interprete Perl o Lisp

Oppure vai a metà strada: collegamento con la libreria Perl e ne fanno un elenco di Perl SV o qualcosa del genere

.

probabilmente sarei andare con il vuoto * avvicinarsi me stesso, ma mi venne in mente che è possibile memorizzare i dati in formato XML. Poi la lista può solo avere un char * per i dati (che si dovrebbe analizzare su richiesta per qualsiasi elementi sub è necessario) ....

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top