C双键链表抽象数据类型 [英] C double linked list with abstract data type

问题描述

我需要在C双键链表，但它必须是不同的类型。在C ++中，我们使用的模板吧。我在哪里可以找到例子℃，抽象类型的项目双向链表。

i need in double linked list in C, but it must be for different types. In C++ we use templates for it. Where can i find example in C for double linked list with abstract types items.

感谢您

推荐答案

有您可以采取一些办法，其中之一涉及到存储无效* 在ADT

There are a few approaches you can take, one of which involves storing a void* in your ADT.

我总觉得这是一个痛苦位的链表，因为你必须要管理它分别分配给列表本身。换句话说，分配一个节点，需要alocate节点和它的有效载荷分别都（记住清除它们都起来上删除以及）。

I've always found this to be a bit of a pain in a linked list since you have to manage it's allocation separately to the list itself. In other words, to allocate a node, you need to alocate both the node and its payload separately (and remember to clean them both up on deletion as well).

我已经在过去使用的一种方法是有一个像可变大小的'结构：

One approach I've used in the past is to have a 'variable sized' structure like:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    char payload[1];
} tNode;

现在没有的看的大小可变的，但让这样的分配结构：

Now that doesn't look variable sized but let's allocate a structure thus:

typedef struct {
    char Name[30];
    char Addr[50];
    char Phone[20];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

现在你有一个节点，对于所有意图和目的，看起来是这样的：

Now you have a node that, for all intents and purposes, looks like this:

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

，或在图形的形式（其中 [N] 办法 N 字节）：

+------------+
| prev[4]    |
+------------+
| next[4]    |
+------------+ +-----------+
| payload[1] | | Name[30]  | <- overlap
+------------+ +-----------+
               | Addr[50]  |
               +-----------+
               | Phone[20] |
               +-----------+

也就是说，假设你知道如何正确解决的有效载荷。这是可以做到如下：

That is, assuming you know how to address the payload correctly. This can be done as follows:

node->prev = NULL;
node->next = NULL;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Richard Cranium");
strcpy (person->Addr, "10 Smith St");
strcpy (person->Phone, "555-5555");

这是投行只铸载荷字符的地址（在 TNODE 键入）是一个地址实际 tPerson 载荷类型。

That cast line simply casts the address of the payload character (in the tNode type) to be an address of the actual tPerson payload type.

使用这个方法，你可以随身携带任何你想要的负载类型中的一个节点，甚至的不同类型的有效载荷中的每个节点的，如果你把结构更像是：

Using this method, you can carry any payload type you want in a node, even different payload types in each node, if you make the structure more like:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;       // Allows different payload type at each node.
    char payload[1];
} tNode;

和使用 payloadType 来存储一个指标，以什么有效载荷实际上是。

and use payloadType to store an indicator as to what the payload actually is.

这具有以下优点：通过在其不浪费空间的联合，作为可与以下中可以看出：

This has the advantage over a union in that it doesn't waste space, as can be seen with the following:

union {
    int fourBytes;
    char oneHundredBytes[100];
} u;

在这里96个字节被浪费每一次你存储在列表（4个字节的整数）整型时间。

where 96 bytes are wasted every time you store an integer type in the list (for a 4-byte integer).

在有效载荷类型的 TNODE 让您轻松检测到这种节点执行什么类型的有效载荷，所以你的code可以决定如何处理它。您可以使用的线沿线的东西：

The payload type in the tNode allows you to easily detect what type of payload this node is carrying, so your code can decide how to process it. You can use something along the lines of:

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

或（可能更好）：

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

您需要注意的唯一的事情是确保有效载荷的定位是正确的。由于我的两个占位符的有效载荷和有效载荷都是字符类型，这不是一个问题。但是，如果你的有效载荷由类型更严格对齐要求（如东西比指针更为严格，你可能需要调整它）。

The only thing you need to watch out for is to ensure that the alignment of the payload is correct. Since both my payload placeholder and the payload are all char types, that's not an issue. However, if your payload consists of types with more stringent alignment requirements (such as something more strict than the pointers, you may need to adjust for it).

虽然我从来没有见过比路线的指针更为严格的环境中，它的是的可以根据ISO C标准。

While I've never seen an environment with alignments more strict than pointers, it is possible according to the ISO C standard.

您通常可以简单地通过使用数据类型有最严格的对齐的要求，如有效载荷占位获取所需的对齐方式：

You can usually get the required alignment simply by using a data type for the payload placeholder which has the strictest alignment requirement such as:

long payload;

---

在回想起来，它发生，我认为你可能没有的需求的数组作为有效载荷占位符。这是很简单，只是有一些你可以采取的地址。我怀疑我的特别成语让人回想起，我只是存储字符数组（而不是结构）和直接引用他们天。在这种情况下，你可以使用的有效载荷[] 自身没有转换为另一种类型。

---

In retrospect, it occurs to me that you probably don't need an array as the payload placeholder. It's simple enough to just have something you can take the address of. I suspect that particular idiom of mine hearkens back to the days where I just stored an array of characters (rather than a structure) and referenced them directly. In that case, you could use payload[] on its own without casting to another type.

这篇关于C双键链表抽象数据类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！