是否可以拥有不同数据类型的链表？
这只是另一个面试问题。
我们可以有一个不同数据类型的链表，即链表中的每个元素可以有不同的结构或联合元素吗？ 如果有可能请你举个例子解释一下吗？
使用union创建数据类型
union u_tag{ char ch; int d; double dl; }; struct node { char type; union u_tag u; struct node *next; }; 使用struct node创建链表。 type决定数据的数据类型。
Harsha T，class加罗尔
好吧，在一个链表中，你不需要像喜欢结构一样链接。 只要他们有适当的前进和/或后退指针你就可以了。 例如：
struct BaseLink { BaseLink* pNext; BaseLink* pPrev; int typeId; }; struct StringLink { BaseLink baseLink; char* pString; }; struct IntLink { BaseLink baseLink; int nInt; };
这样你就有了一个从BaseLink到BaseLink的链表。 额外的数据不是问题。 你想看到它作为StringLink？ 然后将BaseLink转换为StringLink。
请记住，你需要某种forms的typeid，所以当你到达它时你知道要把它投射到什么。
您可以使用联合类型：
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; };
我探索的另一种方法是对数据使用void *并将指针附加到处理类型感知内容的函数：
/** * 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; }
显然，我从这个例子中遗漏了一些错误检查和处理代码，我不怀疑它有很多问题，但它应该是说明性的。
您可以让链接列表中的每个节点都具有指向您的数据的void *。 由您决定指针指向哪种类型的数据取决于您。
如果您不想通过联合解决方案指定列表中每个节点的类型，您始终只需将数据存储在char *中，并将类型特定的函数指针作为参数进行类型敏感操作（如打印）或排序列表。 这样您就不必担心哪个节点是什么类型，只需按照您喜欢的方式转换数据。
/* 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));
是的，我通过将列表的元素值定义为void指针 void* 。 为了知道存储在列表的每个元素中的类型，我还有一个.type字段，所以我知道如何取消引用指针指向每个元素的内容。
struct node { struct node* next; int type; void* value; };
这是一个完整的例子：
// // An exercise to play with a struct that stores anything using a void* field. // #include #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; }
预期产量：
- INTEGER: 1 - STRING: anyfing, anyfing! - TYPE_PERSON: Angel (35) - BOOLEAN (true:1, false:0): 1
如上所述，你可以让这个问题的节点有一个void *。 我建议使用一些东西来了解你的类型：
typedef struct { /* linked list stuff here */ char m_type; void* m_data; } Node;
看到这个问题 。
实际上，您不必将指针放在结构中，您可以将它放在任何位置，然后使用containerof（）宏找到结构的开头。 Linux内核使用其链表进行此操作。
我使用我写的这些宏来制作一般的链表。 您只需创建自己的结构并在某处使用宏list_link作为结构的成员。 给宏指定一个用于命名结构的参数（不带struct关键字）。 这实现了没有虚节点的双链表（例如，最后节点链接回第一节点）。 锚是一个指向第一个节点的指针，它由list_init(anchor)初始化，通过赋予它左值（一个解除引用它的指针是一个左值）。 然后，您可以使用标头中的其他宏。 阅读有关每个可用宏function的注释的来源。 这在宏中实现100％。
只是一个FYI，在C＃中你可以使用Object作为你的数据成员。
class Node { Node next; Object Data; }
然后，用户可以使用类似的东西来找出Node存储的Object ：
if (obj.GetType() == this.GetType()) // { }