tda - ¿Es posible tener una lista vinculada de diferentes tipos de datos?
tda lista (10)
Bueno, en una lista vinculada, NO TIENES que vincular las estructuras iguales. Siempre y cuando tengan los punteros hacia adelante y hacia atrás apropiados, estarás bien. Por ejemplo:
struct BaseLink
{
BaseLink* pNext;
BaseLink* pPrev;
int typeId;
};
struct StringLink
{
BaseLink baseLink;
char* pString;
};
struct IntLink
{
BaseLink baseLink;
int nInt;
};
De esta forma, tendrías una lista vinculada que va desde BaseLink a BaseLink. Los datos adicionales no son un problema. ¿Quieres verlo como un StringLink? Luego, transfiera BaseLink a StringLink.
Solo recuerde que necesita alguna forma de letra para que sepa a qué echarla cuando llegue.
Esta es solo otra pregunta de entrevista.
¿Podemos tener una lista vinculada de diferentes tipos de datos, es decir, cada elemento de una lista vinculada puede tener diferentes estructuras o elementos de unión? Si es posible, ¿puedes explicar con un ejemplo?
En realidad, no tiene que poner el puntero primero en la estructura, puede colocarlo en cualquier lugar y luego encontrar el comienzo para la estructura con una macro containerof (). El kernel de Linux hace esto con sus listas vinculadas.
Puede hacer que cada nodo en una lista vinculada tenga un vacío * que apunte a sus datos. Depende de usted cómo determine a qué tipo de datos apunta el puntero.
Puede usar un tipo de unión:
enum type_tag {INT_TYPE, DOUBLE_TYPE, STRING_TYPE, R1_TYPE, R2_TYPE, ...};
struct node {
union {
int ival;
double dval;
char *sval;
struct recordType1 r1val;
struct recordType2 r2val;
...
} data;
enum type_tag dataType;
struct node *prev;
struct node *next;
};
Otro método que he explorado es usar un vacío * para los datos y adjuntar punteros a las funciones que manejan las cosas sensibles al tipo:
/**
* Define a key type for indexing and searching
*/
typedef ... key_t;
/**
* Define the list node type
*/
struct node {
void *data;
struct node *prev;
struct node *next;
void *(*cpy)(void *); // make a deep copy of the data
void (*del)(void *); // delete the data
char *(*dpy)(void *); // format the data for display as a string
int (*match)(void *, key_t); // match against a key value
};
/**
* Define functions for handling a specific data type
*/
void *copyARecordType(void *data)
{
struct aRecordType v = *(struct aRecordType *) data;
struct aRecordType *new = malloc(sizeof *new);
if (new)
{
// copy elements of v to new
}
return new;
}
void deleteARecordType(void *data) {...}
char *displayARecordType(void *data) {...}
int matchARecordType(void *data, key_t key) {...}
/**
* Define functions for handling a different type
*/
void *copyADifferentRecordType(void *data) {...}
void deleteADifferentRecordType(void *data) {...}
char *displayADifferentRecordType(void *data) {...}
int matchADifferentRecordType(void *data, key_t key) {...}
/**
* Function for creating new list nodes
*/
struct node *createNode(void *data, void *(*cpy)(void *), void (*del)(void *),
char *(*dpy)(void *), int (*match)(void *, key_t))
{
struct node *new = malloc(sizeof *new);
if (new)
{
new->cpy = cpy;
new->del = del;
new->dpy = dpy;
new->match = match;
new->data = new->cpy(data);
new->prev = new->next = NULL;
}
return new;
}
/**
* Function for deleting list nodes
*/
void deleteNode(struct node *p)
{
if (p)
p->del(p->data);
free(p);
}
/**
* Add new node to the list; for this example, we just add to the end
* as in a FIFO queue.
*/
void addNode(struct node *head, void *data, void *(*cpy)(void*),
void (*del)(void *), char *(*dpy)(void *), int (*match)(void*, key_t))
{
struct node *new = createNode(data, cpy, del, dpy, match);
if (!head->next)
head->next = new;
else
{
struct node *cur = head->next;
while (cur->next != NULL)
cur = cur->next;
cur->next = new;
new->prev = cur;
}
}
/**
* Examples of how all of this would be used.
*/
int main(void)
{
struct aRecordType r1 = {...};
struct aDifferentRecordType r2 = {...};
struct node list, *p;
addNode(&list, &r1, copyARecordType, deleteARecordType, displayARecordType,
matchARecordType);
addNode(&list, &r2, copyADifferentRecordType, deleteADifferentRecordType,
displayADifferentRecordType, matchADifferentRecordType);
p = list.next;
while (p)
{
printf("Data at node %p: %s/n", (void*) p, p->dpy(p->data));
p = p->next;
}
return 0;
}
Obviamente, he omitido algún código de comprobación y manejo de errores de este ejemplo, y no dudo de que haya una serie de problemas con él, pero debería ser ilustrativo.
Uso estas macros que escribí para crear listas enlazadas generales. Simplemente crea tu propia estructura y usa la macro list_link algún lugar como miembro de la estructura. Dale a esa macro un argumento nombrando la estructura (sin la palabra clave struct ). Esto implementa una lista doblemente enlazada sin un nodo ficticio (por ejemplo, el último nodo enlaza con el primer nodo). El ancla es un puntero al primer nodo que comienza siendo inicializado por list_init(anchor) dándole el valor l (un puntero desreferenciado es un lvalue). Luego puede usar las otras macros en el encabezado. Lea la fuente para comentarios sobre cada macro funciones disponibles. Esto se implementa al 100% en macros.
Solo un FYI, en C # puede usar Object como su miembro de datos.
class Node
{
Node next;
Object Data;
}
El usuario puede usar algo como esto para descubrir qué Object almacena el Node :
if (obj.GetType() == this.GetType()) //
{
}
Use union para crear el tipo de datos
union u_tag{
char ch;
int d;
double dl;
};
struct node {
char type;
union u_tag u;
struct node *next;
};
Use struct node para crear una lista vinculada. tipo decide cuál es el tipo de datos de los datos.
Harsha T, Bangalore
Si no desea tener que especificar el tipo de cada nodo en la lista a través de la solución de unión, siempre puede almacenar los datos en un char * y tomar punteros de función específicos del tipo como parámetros para operaciones sensibles al tipo, como la impresión o clasificando la lista. De esta forma, no tiene que preocuparse por qué nodo es de qué tipo y puede simplemente transmitir los datos como desee.
/* data types */
typedef struct list_node list_node;
struct list_node {
char *data;
list_node *next;
list_node *prev;
};
typedef struct list list;
struct list {
list_node *head;
list_node *tail;
size_t size;
};
/* type sensitive functions */
int list_sort(list *l, int (*compar)(const void*, const void*));
int list_print(list *l, void (*print)(char *data));
Sí, lo hago definiendo el valor del elemento de la lista como void void* . Para conocer el tipo almacenado en cada elemento de la lista, también tengo un campo .type allí, así que sé cómo desreferenciar lo que señala el puntero para cada elemento.
struct node {
struct node* next;
int type;
void* value;
};
Aquí hay un ejemplo completo de esto:
//
// An exercise to play with a struct that stores anything using a void* field.
//
#include <stdio.h>
#define TRUE 1
int TYPE_INT = 0;
int TYPE_STRING = 1;
int TYPE_BOOLEAN = 2;
int TYPE_PERSON = 3;
struct node {
struct node* next;
int type;
void* value;
};
struct person {
char* name;
int age;
};
int main(int args, char **argv) {
struct person aPerson;
aPerson.name = "Angel";
aPerson.age = 35;
// Define a linked list of objects.
// We use that .type field to know what we''re dealing
// with on every iteration. On .value we store our values.
struct node nodes[] = {
{ .next = &nodes[1], .type = TYPE_INT , .value=1 },
{ .next = &nodes[2], .type = TYPE_STRING , .value="anyfing, anyfing!" },
{ .next = &nodes[3], .type = TYPE_PERSON , .value=&aPerson },
{ .next = NULL , .type = TYPE_BOOLEAN, .value=TRUE }
};
// We iterate through the list
for ( struct node *currentNode = &nodes[0]; currentNode; currentNode = currentNode->next) {
int currentType = (*currentNode).type;
if (currentType == TYPE_INT) {
printf("%s: %d/n", "- INTEGER", (*currentNode).value); // just playing with syntax, same as currentNode->value
} else if (currentType == TYPE_STRING) {
printf("%s: %s/n", "- STRING", currentNode->value);
} else if (currentType == TYPE_BOOLEAN) {
printf("%s: %d/n", "- BOOLEAN (true:1, false:0)", currentNode->value);
} else if (currentType == TYPE_PERSON) {
// since we''re using void*, we end up with a pointer to struct person, which we *dereference
// into a struct in the stack.
struct person currentPerson = *(struct person*) currentNode->value;
printf("%s: %s (%d)/n","- TYPE_PERSON", currentPerson.name, currentPerson.age);
}
}
return 0;
}
Rendimiento esperado:
- INTEGER: 1
- STRING: anyfing, anyfing!
- TYPE_PERSON: Angel (35)
- BOOLEAN (true:1, false:0): 1
Como se dijo, puede tener un nodo con un vacío *. Sugiero usar algo para saber sobre tu tipo:
typedef struct
{
/* linked list stuff here */
char m_type;
void* m_data;
}
Node;
Ver esta pregunta