lista de doble enlace C con tipo de datos abstracto

Question

necesito en la lista de doble enlace en C, pero debe ser para diferentes tipos. En C++ usamos plantillas para eso. ¿Dónde puedo encontrar ejemplos en C para la lista de doble enlace con elementos de tipos abstractos?

Gracias

Answer 1

Hay algunos enfoques que puede tomar, uno de los cuales implica el almacenamiento de un void* en su ADT.

Siempre he encontrado esto un poco molesto en una lista vinculada ya que tiene que administrar su asignación por separado a la lista misma. En otras palabras, para asignar un nodo, debe ubicar tanto el nodo como su carga por separado (y recuerde limpiarlos al eliminarlos también).

Un método que he utilizado en el pasado es tener una estructura 'de tamaño variable' como:

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

Ahora eso no quiere mirar tamaño variable, pero vamos a asignar una estructura así:

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

Ahora usted tiene un nodo que, para todos los efectos, se ve así:

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

o, en forma gráfica (donde [n] significa n bytes):

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

Es decir, suponiendo que conoce la forma de abordar la carga correctamente. Esto se puede hacer de la siguiente manera:

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

que ponen en línea, simplemente pone en la dirección de la payload carácter (en el tipo tNode) a ser una dirección del tipo de carga útil tPerson real.

Usando este método, se puede llevar a cualquier tipo de carga útil que desee en un nodo, incluso tipos de carga diferentes en cada nodo, si usted hace la estructura más como:

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

y utilizar payloadType para almacenar un indicador de lo que es en realidad la carga útil.

Esto tiene la ventaja sobre una unión en la que no pierde el espacio, como se puede ver con lo siguiente:

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

96 bytes, donde se pierden cada vez que se almacena un tipo entero en la lista (para un entero de 4 bytes).

El tipo de carga útil en el tNode le permite detectar fácilmente qué tipo de carga lleva este nodo, por lo que su código puede decidir cómo procesarlo. Se puede usar algo a lo largo de las líneas de:

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

o (probablemente mejor):

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

La única cosa que hay que tener en cuenta es asegurarse de que la alineación de la carga útil es correcta. Dado que tanto mi marcador de posición de carga útil como la carga útil son todos tipos char, eso no es un problema. Sin embargo, si su carga útil se compone de tipos con requisitos de alineación más estrictos (como algo más estricto que los punteros, es posible que deba ajustarlo).

Si bien nunca he visto un entorno con alineaciones más estrictas que los punteros, es posible de acuerdo con el estándar ISO C.

Generalmente, usted puede conseguir la alineación requerida simplemente utilizando un tipo de datos para el marcador de posición de carga útil que tiene el requisito de alineación más estricta, tales como:

long payload; 

---

En retrospectiva, se me ocurre que es probable no necesita una matriz como marcador de posición de carga. Es lo suficientemente simple como para tener algo de lo que puedas tomar la dirección. Sospecho que esa particular expresión mía se remonta a los días en que almacenaba una serie de caracteres (en lugar de una estructura) y los hacía referencia directamente. En ese caso, puede usar payload[] por sí mismo sin convertirlo a otro tipo.

Answer 2

Manejo de datos arbitrarios en C se suele hacer mediante el uso de punteros - específicamente void * en la mayoría de los casos.

Answer 3

La idea más cercana en C a una clase base "objeto" o tipos de plantilla es un puntero void. Un void * representa un puntero a algo, pero no especifica a qué tipo de datos se apunta. Si desea acceder a los datos, necesita usar un elenco.

Un nodo de la lista doblemente enlazada podría tener este aspecto:

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

Para asignar un nodo de una cadena, por ejemplo, se podría hacer:

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

Para obtener la cadena de vuelta de un nodo , se utiliza un reparto:

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

para almacenar un puntero no, es necesario hacer un puntero de los datos. Para las estructuras, puede simplemente desreferenciar la instancia si su duración es lo suficientemente larga (similar al ejemplo anterior). De lo contrario, o si está tratando con un tipo primitivo (por ejemplo, un int o float), necesita un espacio para malloc. Solo asegúrese de liberar la memoria cuando haya terminado.

Answer 4

Puede usar macros como se demostró here (este ejemplo particular implementa hash-tables genéricas).

Answer 5

Obviamente, el kernel de Linux utiliza listas enlazadas en muchos, muchos lugares, tanto en el kernel como en los muchos módulos de controladores de dispositivos. Casi todos estos se implementan utilizando el mismo conjunto de macros definido en linux/list.h

Ver http://isis.poly.edu/kulesh/stuff/src/klist/ o http://kernelnewbies.org/FAQ/LinkedLists para una buena explicación.

Las macros se ven un poco extrañas al principio, pero son fáciles de usar y pronto se convierten en algo natural. Se pueden adaptar trivialmente para usar en el espacio de usuario (ver list.h).