Implementación de lista enlazada 'multipropósito' en C puro

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

Pregunta

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

La situación es:Actualmente estoy tomando un curso de algoritmos avanzados y, para "crecer como programadores", debo usar C puro para implementar las tareas prácticas (funciona bien:prácticamente cualquier pequeño error que cometas te obliga a comprender completamente lo que estás haciendo para poder solucionarlo).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 listas vinculadas, sino también pilas, árboles, etc.

Me estoy centrando en las listas en 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 resuelve conflictos mediante el uso de una lista enlazada).

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

  • Hacer una lista de sugerencias nulas (un poco poco elegantes;más difícil de depurar)
  • Hacer una sola 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)
  • Usar una macro de preprocesador para regenerar el código para cada tipo, al estilo de SGLIB, 'imitando' el STL de C++ (solución creativa;no desperdicia espacio;los elementos tienen el tipo explícito que realmente son cuando se devuelven; cualquier cambio en el código de la lista puede ser realmente dramático)
  • Tu idea/solución

Para aclarar la pregunta:¿Cuál de los anteriores es mejor?

PD:Como estoy básicamente en un contexto académico, también estoy muy interesado en la visión de las personas que trabajan con C puro en la industria.Entiendo que la mayoría de los programadores de C puro 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 conocer su opinión.

¿Fue útil?

Solución

A void * es un poco de dolor en una lista enlazada, ya que tiene que manejar su asignación por separado a la propia lista. 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 que no significa Look de 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, es el siguiente: 

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

o, en forma gráfica (donde significa [n] 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");

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

El uso de este método, se puede realizar 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;

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 útil de este nodo está llevando, 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;

Otros consejos

Mi $ .002:

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

Esto no es una mala elección, en mi humilde opinión, si tiene que escribir en C. Es posible añadir métodos de la API para permitir la aplicación para el suministro de un método de impresión () para facilitar la depuración. Métodos similares pueden ser invocados cuando (por ejemplo) elementos se añaden o eliminan de la lista. (Para listas enlazadas, esto no suele ser necesaria, 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 espacio si los elementos no son todos del mismo tamaño)

Me evitar esto como la peste. (Bueno, se lo preguntó.) Tener un configurado manualmente, la dependencia en tiempo de compilación de la estructura de datos para sus tipos de contenidos es el peor de todos los mundos. Una vez más, en mi humilde opinión.

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

idea interesante, pero ya no sé SGLIB, no puedo decir mucho más que eso.

  • Tu idea / solución

Me quedo con la primera opción.

Hice esto en el pasado, en nuestro código (que desde entonces se convirtió a C++) y, en ese momento, decidí usar el enfoque void*.Simplemente hice esto por flexibilidad: casi siempre almacenábamos un puntero en la lista de todos modos, y la simplicidad de la solución y su usabilidad superaron (para mí) las desventajas de los otros enfoques.

Dicho esto, hubo un momento en el que causó un error desagradable que fue difícil de depurar, por lo que definitivamente no es una solución perfecta.Sin embargo, creo que sigue siendo el que tomaría si volviera a hacer esto ahora.

El uso de una macro preprocesador es la mejor opción. El Linux kernel lista enlazada es una excelente una implementación de un eficient ligada circularmente lista en C. Es muy portátil y fácil de usar. aquí una versión independiente del kernel de Linux 2.6.29 cabecera list.h .

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

No he codificado C en años, pero GLib pretende ofrecer "una gran un conjunto de funciones de utilidad para cadenas y estructuras de datos comunes", entre las que están listas enlazadas.

Aunque es tentador pensar en resolver este tipo de problemas utilizando las técnicas de otro idioma, por ejemplo, los genéricos, en la práctica es muy raro que una victoria. Probablemente hay algunas soluciones enlatadas que lo hacen bien la mayor parte del tiempo (y le dicen en su documentación cuando se equivocan), el uso que podrían perder el punto de la misión, por lo que pensarían dos veces. Para un número muy limitado de casos, podría ser factible para rodar su propio, pero para un proyecto de cualquier tamaño razonable, no es probable que sea la pena el esfuerzo de depuración.

Por el contrario, la hora de programar en un lenguaje x, debe utilizar las expresiones del lenguaje x. No escriba java cuando se está utilizando Python. No escriba C cuando se está utilizando esquema. No escriba C ++ cuando se está utilizando C99.

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

(yo también probablemente terminará la aplicación de un árbol de Fibonacci, simplemente porque eso suena linda, y sólo se puede implementar RB árboles tantas veces antes de que pierda su sabor, incluso si eso es mejor para los casos comunes que sería ser utilizado para.)

editar basado en su comentario, parece que usted tiene un buen caso para el uso de una solución enlatada. Si su instructor lo permite, y la sintaxis que ofrece se siente cómodo, darle una turbina.

Este es un buen problema. Hay dos soluciones me gusta:

  • Dave Hanson C interfaces e implementaciones utiliza una lista de void * los punteros, que es lo suficientemente bueno para mí.

  • Para mi estudiantes , que escribió un script de awk para generar funciones de lista de tipos específicos . En comparación con las macros del preprocesador, se requiere un paso de generación adicional, pero el funcionamiento del sistema es mucho más transparente para los programadores y sin mucha experiencia. Y lo que realmente ayuda a hacer el caso para 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 150 línea; que busca en código C para typedefs y genera un conjunto de funciones de la lista para cada uno. Es muy antiguo; Probablemente podría hacerlo mejor ahora: -)

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

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:. Incrustar un Perl o Lisp intérprete

O ir a mitad de camino: enlace con la biblioteca Perl y que sea una lista de Perl SV o algo

.

probablemente me vaya con el vacío * acercarse a mí mismo, pero se me ocurrió que se podía almacenar sus datos como XML. A continuación, la lista solo puede tener un char * para los datos (que puedas procesar en la demanda de cualquier elemento secundario que necesita) ....

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top