如何在c或c++中创建异构链接列表

Question

一个可以保存浮点数、整数、字符等数据和算法的链接列表应该很好而且不是很复杂

我想到创建一个带有 void 指针的结构，该指针将指向后续节点。但问题是我不能使用具有结构的模板。

归结为c，我必须测试用户输入的每个字符来测试它是否是整数、浮点数或字符。然后我们可以进一步进行，

请建议一个有效的算法/代码

Answer 1

如果您想自己执行此操作，您基本上需要创建一个数组或元素链接列表，对数据和数据类型进行编码。您可以使用包含类型指示符和要处理的各种类型的联合的结构，并创建该结构的数组或链接列表：

typedef struct {
    int type_indicator;
    union {
        float f;
        int i;
        double d;
        void *p;
        char c;
    }
} generic_item;

generic_item generic_array[10];

我将留给您为以下内容提供适当的枚举 ：类型指示器并为您的算法添加函数指针。如果您想要一个链表而不是数组，那么显然您还需要添加一个 generic_item *next 指针。

我还没有研究过其他答案链接到的增强选项，但在尝试推出自己的解决方案之前，我可能会先看看那里。

Answer 2

使用 boost::variant 或 boost::any。取决于您的需求。

Answer 3

注意：这是一个纯粹的 C 答案。

这个数据结构就是我开始的内容：

typedef struct heterogeneous_list
{
    enum { CHAR, STRING, FLOAT, INT } type;
    void *item;
    struct heterogeneous_list *next;
}

当我从用户那里获得该项目时，我会将其存储在列表中（假设当前指向末尾）列表的）：

current->next = malloc(sizeof(heterogeneous_list));
case (/* whether the user entered a char, string, float, or int */
{
    case /* char */:
        current->next.item = malloc(sizeof(char));
        current->next.type = CHAR;
        current->next.next = NULL;
        break;
/* and so forth, for string, int, and float */
}
current = current->next;

当迭代列表时，现在可以很容易地根据类型处理列表中的内容。以下代码假设 current 是在迭代中查看的列表中的当前项（for 循环遍历列表）：

char currentItemChar;
char * currentItemString;
float currentItemFloat;
int currentItemInt;

case (current->type)
{
    case CHAR:
        currentItemChar = *((char*) current->item);
        // process a character
        break;
    case STRING:
        currentItemString = (char*) current->item;
        // process a string
        break;
    case FLOAT: 
        currentItemFloat = *((float*) current->item);
        // process a float
        break;
    .
    .
    .
};

这就是我要做的。

Answer 4

http://www.boost.org/doc/libs/1_48_0 /doc/html/variant.html

（当然，在解释 boost 变体给你带来了什么之前，它当然也提到了 C/C++ 联合）

Answer 5

可以通过使用void *作为指向数据项的指针来创建异构链表：

struct Node
{
    Node * previous;
    Node * next;
    void * p_data;
};

在实现异构容器之前，人们可能会问是否可以更改设计以使用同类容器。

Answer 6

正如您所提到的，您可以使用一些与一些或多或少棘手的宏相关的空指针来执行此类操作。

您可以定义一个包含三个指针的结构（或类）：next、prev（用于下一个和上一个列表元素）和某种 void* 数据。此外，您还可以存储每个列表条目的类型（可以通过enum或等效的东西来实现）。

此外，您可以定义一个宏 - 给定一个列表项 - 检索数据并自动将其转换为给定类型：

#define get_list_item(item, type) *(type*)(((item)->data))