Implementación de listas enlazadas 'multipropósito' en C

Question

Esto no es exactamente una pregunta técnica, ya que conozco C lo suficiente como para hacer las cosas que necesito (es decir, en términos de no 'dejar que el lenguaje se interponga en tu camino '), entonces esta pregunta es básicamente una pregunta' qué dirección tomar '.

La situación es la siguiente: actualmente estoy tomando un curso avanzado de algoritmos, y para "crecer como programadores", debo usar C pura para implementar las tareas prácticas (funciona bien: casi cualquier pequeño error) lo que haces realmente te obliga a entender completamente lo que estás haciendo para arreglarlo). En el curso de la implementación, evidentemente me topo con el problema de tener que implementar las estructuras de datos 'básicas' desde cero: en realidad no solo listas enlazadas, sino también montones, árboles, etcétera.

Me estoy enfocando en listas en este tema porque normalmente es una estructura que termino usando mucho en el programa, ya sea como una estructura 'principal' o como una estructura 'ayudante' para otras más grandes (por ejemplo, hash tree que resuelve conflictos usando una lista enlazada).

Esto requiere que la lista almacene elementos de muchos tipos diferentes. Supongo que es una premisa que no quiero volver a codificar la lista para cada tipo. Por lo tanto, puedo llegar a estas alternativas:

• Hacer una lista de punteros void (algo poco elegante; más difícil de depurar)
• Hacer sólo una lista, pero tener un unión como 'tipo de elemento', que contiene todos los tipos de elementos que usaré en el programa (más fácil de depurar, desperdicia espacio si los elementos no son del mismo tamaño)
• Usando una macro preprocesador para regenerar el código para cada tipo, en el estilo de SGLIB, 'imitando' El STL de C++ (solución creativa; no desperdicia espacio; los elementos tienen el tipo explícito que son en realidad cuando se devuelven; cualquier cambio i Lista de códigos n puede ser muy dramática)
• Tu idea/solución

Para hacer clara la pregunta: ¿cuál de los anteriores es el mejor?

PD: Como básicamente estoy en un contexto académico, también estoy muy interesado en la opinión de las personas que trabajan con C pura en la industria. Entiendo que la mayoría de los programadores C puros están en el área de dispositivos integrados, donde no creo que este tipo de problema que estoy enfrentando sea común. Sin embargo, si alguien sabe cómo se hace 'en el mundo real', estaría muy interesado en tu opinión.

Answer 1

A void * es un poco molesto en una lista vinculada ya que tiene que administrar su asignación por separado a la lista misma. 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; 
    int payloadType; 
    char payload[1]; // or use different type for alignment. 
} tNode; 

Ahora me doy cuenta de que no se ven tamaño variable, pero vamos a asignar una estructura así:

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

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

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

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

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.

Utilizando este método, puede transportar cualquier tipo de carga útil que desee en un nodo, incluso diferentes tipos de carga útil en cada nodo, sin el espacio desperdiciado de una unión. Este desperdicio puede ser visto con la siguiente:

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

96 bytes, donde se pierden cada vez que se almacena un tipo entero en la lista (para un número 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; 

Answer 2

Mi $ .002:

• Hacer una lista de punteros void (un poco diselegant; más difícil de depurar)

Ésta no es una mala elección, en mi humilde opinión, si tiene que escribir en C. Puede agregar métodos API para permitir que la aplicación suministre un método print() para facilitar la depuración. Se pueden invocar métodos similares cuando (por ejemplo) elementos se agregan o eliminan de la lista. (Para las listas vinculadas, esto generalmente no es necesario, pero para estructuras de datos más complejas, tablas hash, por ejemplo), a veces puede ser un salvavidas.)

• Hacer sólo una lista, pero que tienen una unión como 'tipo de elemento', que contiene todos los tipos de elementos voy a utilizar en el programa (más fácil de depurar; desechos espaciales, si los elementos no son todos del mismo tamaño)

Yo evitaría esto como la peste. (Bueno, lo preguntaste). Tener una dependencia de tiempo de compilación configurada manualmente desde la estructura de datos a sus tipos contenidos es el peor de todos los mundos. De nuevo, en mi humilde opinión.

• El uso de un macro preprocesador para regenerar el código para cada tipo, en el estilo de SGLIB (sglib.sourceforge.net), 'imitar' STL (solución creativa C++ 's; no desperdicia espacio; elementos tienen la explícita tipo que realmente son cuando se devuelven, cualquier cambio en el código de la lista puede ser realmente dramático)

idea intrigante, pero como no sé SGLIB, no puedo decir mucho más que eso.

• Tu idea/solución

me gustaría ir con la primera opción.

Answer 3

He hecho esto en el pasado, en nuestro código (que desde entonces se ha convertido a C++), y en ese momento, decidí el enfoque nulo *. Acabo de hacer esto por flexibilidad: casi siempre almacenamos un puntero en la lista de todos modos, y la simplicidad de la solución y la usabilidad superan (para mí) las desventajas de los otros enfoques.

Dicho esto, hubo una ocasión en la que causó un error desagradable que fue difícil de depurar, por lo que definitivamente no es una solución perfecta. Creo que todavía es el que tomaría, si estuviera haciendo esto de nuevo ahora.

Answer 4

no he codificado C en años, pero GLib reclamaciones para proporcionar "un gran conjunto de funciones de utilidad para cadenas y estructuras de datos comunes ", entre las que se encuentran las listas enlazadas.

Answer 5

Este es un buen problema. Hay dos soluciones que me gustan: de

• de Dave Hanson C Interfaces and Implementations utiliza una lista de punteros void *, que es lo suficientemente bueno para mí.

• Para mis estudiantes , escribí un guión awk para generar funciones de lista de tipos específicos. En comparación con las macros de preprocesador, requiere un paso de compilación adicional, pero el funcionamiento del sistema es mucho más transparente para los programadores sin mucha experiencia. Y realmente ayuda a defender el polimorfismo paramétrico, que ven más adelante en su plan de estudios.

  Esto es lo que un conjunto de funciones se parece a:

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

  El script awk es un horror línea 150; busca el código C para typedef sy genera un conjunto de funciones de lista para cada uno. Es muy viejo; Probablemente podría hacerlo mejor ahora :-)

No daría una lista de sindicatos a la hora del día (o espacio en mi disco duro). No es seguro y no es extensible, por lo que también puede usar void * y terminarlo.

Answer 6

Aunque es tentador pensar en resolver este tipo de problema utilizando las técnicas de otro idioma, por ejemplo, genéricos, en la práctica rara vez es una ganancia. Probablemente haya algunas soluciones enlatadas que lo hacen correctamente la mayor parte del tiempo (y le dicen en su documentación cuando lo hacen mal), el uso de eso podría perder el punto de la tarea, así que lo pensaría dos veces al respecto. En muy pocos casos, podría ser posible ejecutar el suyo propio, pero para un proyecto de cualquier tamaño razonable, no es probable que valga la pena el esfuerzo de depuración.

Por el contrario, al programar en lenguaje x, debe utilizar los modismos del lenguaje x. No escriba java cuando esté usando Python. No escriba C cuando esté usando el esquema. No escriba C++ cuando esté usando C99.

mí mismo, probablemente terminar con algo así como la sugerencia de Pax, pero en realidad utilizo una unión de char [1] y vacía * y int, para que los casos comunes conveniente (y una bandera de tipo enumed)

(Probablemente también termine implementando un árbol de fibonacci, solo porque suena bien, y solo puedes implementar árboles RB tantas veces antes de que pierda su sabor, incluso si eso es mejor para los casos comunes en que sería usado para.)

editar: Según su comentario, parece que tiene un muy buen caso para usar una solución enlatada. Si su instructor lo permite y la sintaxis que ofrece se siente cómoda, déle un giro.

Answer 7

Una mejora con respecto a lo que es una lista de void * se lo que es una lista de las estructuras que contienen un void * y algunos meta-datos acerca de lo que el vacío * puntos a, incluyendo su tipo, tamaño, etc.

Otras ideas: incorporar un intérprete de Perl o Lisp.

O vaya a la mitad: enlace con la biblioteca de Perl y haga una lista de SV de Perl o algo así.

Answer 8

Probablemente me vaya con el enfoque nulo *, pero se me ocurrió que podía almacenar sus datos como XML. Entonces la lista solo puede tener un char * para los datos (que analizaría bajo demanda para cualquier subelemento que necesite) ....

Answer 9

Usar una macro de preprocesador es la mejor opción. El Linux kernel linked list es una implementación excelente y eficiente de una lista de enlaces circulares en C. Es muy portátil y fácil de usar. Here una versión independiente de linux kernel 2.6.29 list.h header.

El FreeBSD/OpenBSD sys/queue es otra buena opción para una macro genérico basado lista enlazada