para - manual de programacion android pdf

Función de manipulación de lista genérica en C?

Question

¿Qué es una función genérica de manipulación de listas en C? (Lo vi cuando revisé algunos materiales).

¿Cuál es la diferencia entre esta función y una función que puede aceptar elementos de cualquier tipo?

¿Son ellos mismos ...? ¿Cómo podemos implementarlos individualmente si no son lo mismo?

Answer 1

C no tiene concepto de punteros u objetos "genéricos": lo más cercano que puede obtener es usar un puntero void* . Si quieres que una parte del código pueda manejar cualquier tipo de datos, tienes que usar void* pointers. Para tipos de datos con tamaños no mayores que un puntero, puede convertir el tipo y el void* ; para tipos de datos más grandes, tendrá que usar memoria dinámica y hacer que el miembro void* apunte a la memoria dinámica. ¡Solo ten cuidado con las pérdidas de memoria!

typedef struct list_node {
  struct list_node *next;
  void *data;
} list_node;

void list_insert(list_node *node, void *data) {
  // ...
}

Por otro lado, si desea generar código para cada tipo de datos posible, tendrá que hacerlo con macros y luego instanciar las macros para cada tipo de datos que pueda usar. Por ejemplo:

#define DEFINE_LIST(type) /
  typedef struct list_node_##type { /
    struct list_node_##type *next; /
    type data; /
  }

#define IMPLEMENT_LIST_INSERT(type) /
  void list_##type##_insert(list_node_##type *node, type data) { /
    ... /
  }

DEFINE_LIST(int);     // defines struct list_node_int
DEFINE_LIST(double);  // defines struct list_node_double
IMPLEMENT_LIST_INSERT(int);    // defines list_int_insert
IMPLEMENT_LIST_INSERT(double); // defines list_double_insert

Answer 2

El kernel de Linux tiene una implementación interesante de una lista vinculada genérica en C en su encabezado linux / list.h. Es una lista doblemente enlazada con un nodo principal, usado así:

struct mystruct {
    ...
    /* Contains the next and prev pointers */
    struct list_head mylist;
    ...
    /* A single struct can be in several lists */
    struct list_head another_list;
    ...
};

struct list_head mylist_head;
struct list_head another_list_head;

Algunas cosas interesantes en este pequeño ejemplo:

• El nodo de lista está incrustado dentro de la estructura de destino, no necesita ningún puntero de datos.
• El nodo de lista no tiene que venir al principio de la estructura de destino.
• Una única estructura puede estar en varias listas vinculadas al mismo tiempo.
• Los punteros siguiente y anterior dentro de la lista apuntan a struct list_head , no a la estructura objetivo (en el ejemplo anterior, apuntan a &(foo->mylist) para la primera lista y &(foo->another_list) para el segundo lista).

Todas las funciones de manipulación de lista toman punteros a struct list_head (y a la mayoría no le importa en absoluto si es el nodo principal separado o uno de los nodos incrustados). Para ir desde el struct list_head a la struct de destino, utiliza la macro list_entry (que es la misma que la containter_of macro del encabezado linux / kernel.h ), que se expande en una simple resta del puntero.

Como es una lista doblemente enlazada con un nodo principal, puede hacerlo en O(1) :

• Compruebe si la lista está vacía o si un nodo no está en ninguna lista.
• Obtenga el nodo antes o después de cualquier otro nodo (si el nodo es la cabeza, obtiene el primer o el último elemento de la lista).
• Inserte un nodo después o antes de cualquier otro nodo (si el nodo es el encabezado, inserte al principio o al final de la lista).
• Elimine un nodo de la lista (solo necesita el puntero al nodo para hacer esto).
• Varias otras operaciones.

Answer 3

C y su biblioteca estándar no ofrecen ninguna función específica de lista.

Pero hay bibliotecas con muchas funciones útiles para C que admiten tipos de datos conocidos de otros lenguajes de programación: http://library.gnome.org/devel/glib/2.18/glib-data-types.html

Answer 4

Es probable que una lista genérica esté vinculada por separado, y probablemente asuma que los elementos de la lista tienen una estructura como esta:

typedef struct list_item list_item;

struct list_item
{
    list_item *next;
    ...data for node...
};

Usando este diseño, puede escribir funciones para manipular listas utilizando solo los siguientes punteros.

A veces, el '' ...data for node... '' será un simple '' void * ''; es decir, los elementos de la lista contendrán punteros al siguiente nodo en la lista (o NULL si no hay próximo nodo) y apunta a los datos.

typedef struct list list;

struct list
{
    list *next;
    void *data;
};

Como puede convertir cualquier puntero a '' void * '', puede tener cualquier combinación de tipos de datos en la lista, pero su código debe saber cómo manejarlos.

Usted pregunta acerca de la función de lista ''a'' genérica, pero probablemente no haya un solo diseño de función-uno-todo, y ciertamente no es simple. Hay una serie de posibles conjuntos de funciones que podrían hacer funciones genéricas de lista. Un conjunto, inspirado en Lisp, consistiría en:

void *car(list *lp);    // Return the data for the first item on the list
list *cdr(list *lp);    // Return the tail of the list
list *cons(list *lp1, list *lp2);   // Construct a list from lists lp1 and lp2

list *cond(list *lp, void *data);  // Append data item to list

Probablemente desee proporcionar la capacidad de probar si la lista está vacía y algunos otros elementos.

Una buena exposición, ciertamente en C ++, se encuentra en " Ruminations on C ++ " de Koenig. Las ideas se pueden adaptar a C con bastante facilidad: no es terriblemente difícil (aunque la gestión del almacenamiento en C es más difícil que en C ++).

Answer 5

Como mencioné anteriormente, intenté usar el enfoque MACROS para crear las funciones de manipulación de listas. Es fácil crear la rutina de operación INSERT pero es difícil crear operaciones de borrado y desplazamiento. Siguiendo con la estructura de la lista y la firma de rutina INSERT:

#define LIST_DEFINE(type) /
    struct list_node_##type /
    { /
        type *data; /`
        struct list_node_##type *next; /
   };

LIST_INSERT(&ListHead,&Data, DataType);

Dónde:
ListHead - Jefe de la lista vinculada
Data : los datos para los cuales se creará un nuevo nodo y los datos se insertarán en el nodo DataType . ¿Se pasa el tipo de datos?

FYI, estoy asignando memoria en la función y copiando todos los datos pasados ​​en el nodo recién creado y ellos anexan el nodo en la lista vinculada.

Ahora, cuando se LIST_DELETE una rutina LIST_DELETE , el nodo necesita ser eliminado se identificará usando un identificador único dentro de los datos. Ese identificador también se pasa en la rutina MACRO como clave que se reemplazará en la expansión MACRO . La firma de rutina podría ser:

LIST_DELETE(&ListHead, DataType, myvar->data->str, char*);

Dónde:
ListHead - Jefe de la lista vinculada
DataType - Es el tipo de datos de los datos
myvar->data->str - Clave única
char* - Tipo de clave

Ahora, cuando la clave se expande, esa misma clave no se puede usar para comparar, como si escribiéramos

if((keytype)ListHead->data->key == (keytype)key)

Se expande a

ListHead->data->myvar->data->str == myvar->data->str

Y aquí no hay ninguna variable como: ListHead->data->myvar->data->str

Por lo tanto, este enfoque no puede funcionar para escribir rutinas de eliminación y, dado que las rutinas transversal y de búsqueda también usan una clave única, el mismo problema se encontrará en ellas también.

Y, en una nota no relacionada, cómo determinar la lógica de coincidencia para una clave única, ya que la clave única podría ser cualquier cosa.

Answer 6

Para mis enseñanzas, vine a desarrollar este módulo de lista "genérico", probablemente una versión simplificada del kernel de Linux, con errores adicionales aunque desconocidos incluidos, y que usa extensiones de gcc ... ¡Todos los comentarios son bienvenidos!

#ifndef _LISTE
#define _LISTE
#include <stdlib.h>
typedef struct liste_s {
  struct liste_s * suivant ;
} * liste ;


#define newl(t) ( (liste) malloc ( sizeof ( struct liste_s ) + sizeof ( t ) ) )
#define elt(l,t) ( * ( ( t * ) ( l + 1 ) ) )

#define liste_vide NULL
#define videp(l) ( l == liste_vide )
#define lvide() liste_vide
#define cons(e,l) /
  ({ liste res = newl(typeof(e)) ;      /
     res->suivant = l ; /
     elt(res,typeof(e)) = e ;           /
    res ; }) 

#define hd(l,t) ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; elt(res,t) ; })
#define tl(l)   ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; res->suivant ;})


#endif

Answer 7

He estado intentando algo diferente. Esta es otra perspectiva de cómo abordar el problema

Si tenemos la siguiente estructura:

typedef struct token {
    int id;
    char *name;
    struct token *next;
} Token;

y necesitamos crear una función que devuelva la cola de una lista vinculada, pero la función debe ser genérica para cualquier lista vinculada, por lo tanto:

void* tail(void* list, void* (*f)(void *)) {
    void *head = list;

    while(f(head) != NULL) {
        head = f(head);
    }

    return head;
}

Ahora será necesario crear una función responsable de hacer el puente entre nuestra estructura personalizada y una usabilidad genérica en la función de cola. De esa manera, tenemos:

void* nextToken(void *a) {
    Token *t = (Token *) t;
    return (void *) (a->next);
}

Finalmente, podemos simplemente usar:

Token *listTokens;
(...)
Token *lastToken = tail(listTokens, nextToken);