listas - Implementación de lista enlazada ''multipropósito'' en C pura

listas enlazadas con archivos c++

Question

Esta no es exactamente una pregunta técnica, ya que sé que C es suficiente para hacer las cosas que necesito (quiero decir, en términos de no ''dejar que el idioma se interponga en tu camino''), por lo que esta pregunta es básicamente una ''dirección para tomar ''pregunta.

La situación es: actualmente estoy tomando un curso avanzado de algoritmos y, por el bien de ''crecer como programadores'', debo usar C puro para implementar las tareas prácticas (funciona bien: casi cualquier pequeño error que cometa en realidad es una fuerza que entiendas completamente lo que estás haciendo para arreglarlo). En el curso de la implementación, obviamente me encuentro con el problema de tener que implementar las estructuras de datos "básicas" desde cero: en realidad no solo las listas vinculadas, sino también las pilas, los árboles, etc.

Me estoy enfocando en las listas de este tema porque normalmente es una estructura que termino usando mucho en el programa, ya sea como estructura ''principal'' o como estructura ''auxiliar'' para otras más grandes (por ejemplo, un árbol hash que se resuelve conflictos mediante el uso de una lista vinculada).

Esto requiere que la lista almacene elementos de muchos tipos diferentes. Estoy asumiendo aquí como una premisa que no quiero volver a codificar la lista para cada tipo. Entonces, puedo llegar a estas alternativas:

• Hacer una lista de punteros nulos (algo poco elegante; más difícil de depurar)
• Hacer solo una lista, pero tener una 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 todos del mismo tamaño)
• Usando una macro preprocesadora para regenerar el código para cada tipo, en el estilo de SGLIB , ''imitando'' STL de C ++ (solución creativa; no desperdicia espacio; los elementos tienen el tipo explícito que son cuando se devuelven; cualquier cambio en la lista el código puede ser realmente dramático )
• Tu idea / solución

Para aclarar la pregunta: ¿cuál de las anteriores es mejor?

PD: Ya que estoy básicamente 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 de C pura están en el área de dispositivos integrados, donde no creo que este tipo de problema al que me enfrento sea común. Sin embargo, si alguien sabe cómo se hace ''en el mundo real'', me interesaría mucho su opinión.

Answer 1

Aunque es tentador pensar en resolver este tipo de problema utilizando las técnicas de otro lenguaje, por ejemplo, genéricos, en la práctica rara vez es una victoria. Probablemente hay algunas soluciones enlatadas que lo hacen bien la mayor parte del tiempo (y le dicen en su documentación cuando lo hacen mal), el uso que puede pasar por alto el punto de la asignación, así que lo pensaría dos veces. Para un número muy reducido de casos, podría ser factible rodar el suyo, pero para un proyecto de cualquier tamaño razonable, no es probable que valga la pena el esfuerzo de depuración.

Más bien, cuando programes en el lenguaje x, debes usar los modismos del lenguaje x. No escribas java cuando estés usando python. No escriba C cuando esté utilizando el esquema. No escriba C ++ cuando esté utilizando C99.

Yo mismo, probablemente termine usando algo como la sugerencia de Pax, pero en realidad utilizo una unión de char [1] y void * e int, para hacer los casos comunes convenientes (y una bandera de tipo enumed)

(También es probable que termine implementando un árbol de fibonacci, solo porque suena bien, y usted solo puede implementar los árboles de RB tantas veces antes de que pierda su sabor, incluso si eso es mejor para los casos comunes que se utilizarían para .)

edición: según su comentario, parece que tiene un caso bastante bueno para usar una solución enlatada. Si tu instructor lo permite y la sintaxis que ofrece se siente cómoda, dale un giro.

Answer 2

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

• Las Interfaces e Implementaciones C de Dave Hanson utilizan una lista de punteros void * , que es lo suficientemente bueno para mí.

• Para mis alumnos , escribí un script awk para generar funciones de lista específicas del tipo . En comparación con las macros del 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 caso del polimorfismo paramétrico, que verán más adelante en su plan de estudios.

  Así es como se ve un conjunto de funciones:

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

  El guión awk es un horror de 150 líneas; busca código C para typedef s y genera un conjunto de funciones de lista para cada una. Es muy viejo Probablemente podría hacerlo mejor ahora :-)

No le daría a una lista de uniones 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 terminar con él.

Answer 3

He hecho esto en el pasado, en nuestro código (que desde entonces se ha convertido a C ++), y en ese momento, optó por el enfoque void *. Simplemente hice esto por flexibilidad: de todos modos, casi siempre estábamos almacenando un puntero en la lista, y la simplicidad de la solución y la facilidad de uso de la misma superaban (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 eliminar, por lo que definitivamente no es la solución perfecta. Sin embargo, creo que sigue siendo la que tomaría, si estuviera haciendo esto de nuevo ahora.

Answer 4

Mi $ .002:

• Hacer una lista de punteros nulos (algo deselegante; más difícil de depurar)

Esta no es una mala elección, en mi humilde opinión, si debe escribir en C. Puede agregar métodos API para permitir que la aplicación proporcione un método print () para facilitar la depuración. Se podrían invocar métodos similares cuando (por ejemplo) los elementos se agreguen o eliminen de la lista. (Para listas enlazadas, esto generalmente no es necesario, pero para estructuras de datos más complejas, por ejemplo tablas hash), a veces puede ser un salvavidas.

• Hacer solo una lista, pero tener una 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 todos del mismo tamaño)

Yo evitaría esto como la plaga. (Bueno, lo preguntaste). Tener una dependencia configurada manualmente en tiempo de compilación de la estructura de datos a sus tipos contenidos es el peor de los mundos. Una vez más, en mi humilde opinión.

• Usando una macro preprocesadora para regenerar el código para cada tipo, en el estilo de SGLIB (sglib.sourceforge.net), STL de C ++ "imitando" (solución creativa; no desperdicia espacio; los elementos tienen el tipo explícito que son en realidad cuando son devueltos; cualquier cambio en el código de la lista puede ser realmente dramático)

Idea intrigante, pero como no conozco SGLIB, no puedo decir mucho más que eso.

• Tu idea / solución

Yo iría con la primera opción.

Answer 5

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

Answer 6

Probablemente prefiero el enfoque void *, pero se me ocurrió que podría almacenar sus datos como XML. Entonces, la lista solo puede tener un carácter * para los datos (que se analizarían a petición para cualquier subelemento que necesite) ...

Answer 7

Una mejora con respecto a convertirla en una lista de nulos * sería hacerla en una lista de estructuras que contengan un nulo * y algunos metadatos sobre lo que apunta el nulo *, incluido su tipo, tamaño, etc.

Otras ideas: incrustar un intérprete Perl o Lisp.

O ve a mitad de camino: crea un enlace con la biblioteca de Perl y haz una lista de los SV de Perl o algo así.

Answer 8

Usar una macro de preprocesador es la mejor opción. La lista enlazada del kernel de Linux es una excelente y eficiente implementación de una lista enlazada circularmente en C. Es muy portátil y fácil de usar. Here una versión independiente del encabezado de Linux list.h del núcleo 2.6.29 de Linux.

FreeBSD / OpenBSD sys/queue es otra buena opción para una lista vinculada genérica basada en macros

Answer 9

Un void * es un poco molesto en una lista vinculada, ya que tiene que administrar su asignación por separado a la propia lista. Un enfoque que he usado 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 parece de tamaño variable, pero asignemos una estructura así:

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

Ahora tienes un nodo que, a todos los efectos, tiene este aspecto:

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] significa n bytes):

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

Es decir, suponiendo que sepa cómo abordar la carga útil correctamente. Esto puede hacerse 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");

Esa línea de tNode simplemente convierte la dirección del carácter de payload (en el tipo tNode ) para que sea una dirección del tipo de carga útil tPerson real.

Con este método, puede llevar 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 se puede ver con lo siguiente:

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

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

El tipo de carga útil en tNode permite detectar fácilmente qué tipo de carga útil lleva este nodo, por lo que su código puede decidir cómo procesarlo. Puedes usar algo similar a lo siguiente:

#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;