Elenco double link C con tipo di dati astratto

Question

ho bisogno in doppio elenco collegato in C, ma deve essere per diversi tipi. In C++ usiamo i modelli per questo. Dove posso trovare un esempio in C per la doppia lista collegata con elementi di tipi astratti.

si

Answer 1

Ci sono alcuni approcci che è possibile eseguire, uno dei quali riguarda la memorizzazione di un void* nell'ADT.

Ho sempre trovato che questo è un po 'un dolore in una lista collegata dal momento che devi gestire la sua allocazione separatamente alla lista stessa. In altre parole, per allocare un nodo, è necessario posizionare separatamente sia il nodo che il suo payload (e ricordarsi di eliminarli entrambi alla cancellazione).

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; 
    char payload[1]; 
} tNode; 

Ora questo non guardare variabile dimensioni ma cerchiamo di allocare una struttura così:

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

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

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

vale a dire, a patto di saper come affrontare correttamente il carico utile. Questo può essere fatto come segue:

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

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

Utilizzando questo metodo, è possibile trasportare qualsiasi tipo di carico utile che si desidera in un nodo, anche diversi tipi di payload in ogni nodo, se si effettua la struttura più simile:

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

e utilizzare payloadType per memorizzare un indicatore di ciò che il carico utile è in realtà.

Questo ha il vantaggio rispetto un'unione nel senso che non spreca spazio, come si può vedere con il seguente:

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

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

Il tipo di payload nel tNode consente di rilevare facilmente il tipo di payload che trasporta questo nodo, in modo che il codice possa 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; 

L'unica cosa che dovete guardare fuori per è quello di garantire che l'allineamento del carico utile è corretta. Poiché sia ​​il mio segnaposto payload che il payload sono tutti i tipi char, non è un problema. Tuttavia, se il carico utile è costituito da tipi con requisiti di allineamento più stringenti (ad esempio qualcosa di più severo dei puntatori, potrebbe essere necessario regolarlo).

Anche se non ho mai visto un ambiente con allineamenti più rigidi dei puntatori, è possibile secondo lo standard ISO C.

Di solito è possibile ottenere l'allineamento richiesto semplicemente utilizzando un tipo di dati per il segnaposto payload, che ha l'obbligo di allineamento più rigoroso come ad esempio:

long payload; 

---

Col senno di poi, mi viene in mente che probabilmente non necessario un array come segnaposto del payload. È abbastanza semplice avere solo qualcosa a cui puoi prendere l'indirizzo. Sospetto che quel particolare idioma dei miei ricordi risalga ai giorni in cui ho appena archiviato una serie di caratteri (piuttosto che una struttura) e li ho citati direttamente. In tal caso, è possibile utilizzare payload[] da solo senza eseguire il casting in un altro tipo.

Answer 2

Grazie Gestione dati arbitrari in C di solito è fatto utilizzando puntatori - specificamente void * nella maggior parte dei casi.

Answer 3

Il più vicino pensa in C a una classe di base "oggetto" o tipi di modelli è un puntatore void. Un void * rappresenta un puntatore a qualcosa, ma non specifica quale tipo di dati viene puntato. Se si desidera accedere ai dati, è necessario utilizzare un cast.

Un nodo lista doppiamente collegata potrebbe essere la seguente:

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

Per assegnare un nodo di una stringa, per esempio, si potrebbe fare:

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

per ottenere la stringa di ritorno da un nodo , si utilizza un cast:

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

per memorizzare un non-puntatore, è necessario effettuare un puntatore dai dati. Per le strutture, potresti essere in grado di dereferenziare l'istanza se la sua durata è abbastanza lunga (simile all'esempio precedente). In caso contrario, o se si ha a che fare con un tipo primitivo (ad esempio uno int o float), è necessario uno spazio pari a malloc. Assicurati di liberare la memoria quando hai finito.

Answer 4

È possibile utilizzare macro come dimostrato here (questo esempio particolare implementa tabelle hash generiche).

Answer 5

Ovviamente, il kernel linux utilizza elenchi collegati in molte, molte posizioni sia nel kernel stesso che nei numerosi moduli del driver del dispositivo. Quasi tutti questi sono implementati utilizzando lo stesso una serie di macro definite in linux/list.h

Vedi http://isis.poly.edu/kulesh/stuff/src/klist/ o http://kernelnewbies.org/FAQ/LinkedLists per una buona spiegazione.

Le macro sembrano un po 'strane in un primo momento, ma sono facili da usare e diventano presto una seconda natura. Possono essere adattati banalmente per l'utilizzo nello spazio utente (vedere list.h).