5

我正在尝试设计一个从文件中获取数据的程序，然后对唯一数据进行编号，链表还包含父列表和子列表。

数据结构：

                   ____A
                  /    |     
                 B     C    
                 |  /    \  
                 E-->  F   G
                 |     |   |
                 I     J   K

节点可以有多个下一个节点（例如A和C），并且可以有多个前一个节点。

文本文件包含这样的数据，我将从文件中获取数据并将它们转换为链表：

                    A
                    B
                    E
                    I

                    A
                    C
                    E
                    F
                    J

                    A
                    C
                    G
                    K

我的问题：是否可以创建具有多个下一个或多个先前节点的节点的链表，如果是这样，结构会是什么样子？

我试过的：

我制作了一个结构，其中包含一个由 4 个整数组成的数组，用于父子元素。

struct abcd{
 char data;
 int nodeid;

 int parent[4];
 int child[4];

 struct abcd *next;

}

所以父数组保存了大多数前一个节点的节点ID（可以不止一个，因为例如E（B＆C指向它）->（节点ID - 1）。

子数组保存即时下一个节点的节点 ID（节点 ID +1）。

A 或任何其他节点没有重复节点。

输出：

1 :  A <-- 
2 :  B <-- 1
3    E <-- 2,5
4 :  I <-- 3
5 :  C <-- 1
6 :  F <-- 3
7 :  J <-- 6
8 :  G <-- 5
9 :  K <-- 8

希望它清楚，请让我不知道我应该如何实施它。问候。

4

6 回答 6

8

是的，所以这被称为有向图。并且有大约一千种方法可以实现它。“正确”的方式完全取决于你将如何使用它，你没有描述过。由于您似乎确实将其限制为链接列表或双向链接列表，因此我将只使用双向链接列表。

转发声明您的数据类型

typedef struct ItemInfo_s ItemInfo;
typedef struct DoubleLinkedListNode_s DoubleLinkedListNode;

像往常一样创建一个 ListNode：

struct DoubleLinkedListNode_s {
    DoubleLinkedListNode *next;
    DoubleLinkedListNode *prev;
    ItemInfo *data;
};

然后创建您的 ItemInfo：

struct ItemInfo_s {
    DoubleLinkedListNode *children;
    DoubleLinkedListNode *parents;
    ...  /* other item data */
};

此外，为了理智起见，创建所有已创建节点的列表：

DoubleLinkedListNode *items;

现在，我不打算写所有的链表管理函数，但我相信你能想出来。按照惯例，我将 (B) 写为指向项目 B (node.data = &B) 的节点。我还将用“=”和“-”表示任何两个链接在一起的节点作为未链接的（空值）节点链接。我将编写一个元素链 [ -(1)=(2)=(3)- ]，按照惯例，指向项目链的指针将始终指向链中的第一个节点（本例中的 (1) ）。您给定的图表在内存中如下所示：

items = [ -(A)=(B)=(C)=(E)=(F)=(G)=(I)=(J)=(K)- ]

A.children = [ -(B)=(C)- ]
A.parents = []

B.children = [ -(E)- ]
B.parents = [ -(A)- ]

C.children = [ -(E)=(G)- ]
C.parents = [ -(A)- ]

E.children = [ -(I)=(F)- ]
E.parents = [ -(B)=(C)- ]

F.children = [ -(J)- ]
F.parents = [ -(E)- ]

G.children = [ -(K)- ]
G.parents = [ -(C)- ]

I.children = []
I.parents = [ -(E)- ]

J.children = []
J.parents = [ -(F)- ]

K.children = []
K.parents = [ -(G)- ]

总共有 9 个 ItemInfos 和 27 个 DoubleLinkedListNodes。我几乎想不出我会在实践中实现它的原因，但它只使用双链表实现。它可能使列表管理更容易进行双重链接环（将列表的头部和尾部连接在一起），但这更难以文本形式显示。:)

于 2013-08-16T15:39:24.520 回答
4

链表和双向链表是一种特定的有向图，可以优化为您熟悉的结构head/tail。data/next/prev由于您正在扩展其功能，因此您失去了这种特殊性，并希望回到通用的有向图结构并从那里开始工作。

有向图最容易用邻接表来描述： 具有邻接表的图的图像

您可以将其实现为列表列表、列表数组或锯齿状数组，或者您喜欢的任何方式。现在，在右边，我以有向图的形式绘制了一个双向链表。由于next指针与指针不同prev，因此您的邻接列表需要将它们分开。所以它实际上是一个双重列表的列表：

typedef struct _BPNode { // "Back-Pointing Node"
    void *data;
    struct _BPNode *nexts[];
    struct _BPNode *prevs[];
} Node;

typedef struct _BPGraph { // "Back-Pointing Graph"
    Node **allNodes;
} BPGraph;

或类似的东西。免责声明：我没有在编译器中对此进行测试。为了以防万一，这里有一个关于如何阅读其中一些声明的指南。

或者，您可以创建两个有向图，一个向前运行，一个向后运行。但是，这将比这个“反向”图占用更多的内存。它也会运行得更慢（更多的 cpu 缓存未命中），不太直观，并且释放内存更麻烦。

于 2013-08-18T18:48:09.430 回答
4

你可以有这样的结构：

struct abcd{
 char data;
 struct abcd *next[10];  //array of next nodes
 struct abcd *prev[10];  //array of previous nodes
}

访问下一个节点时，您可以node->next[i]代替node->next, where 0<= i < 10。分配/创建节点时，将所有数组元素重置为，NULL以便您没有未初始化节点的垃圾。

因此，假设您添加了节点 for 'A'，那么您可以添加节点 for'B'和'C'as

int idx;
//find index for free element.
for(idx = 0; nodeA->next[idx] && idx < 10; idx++)
   ;
if(idx == 10)
   //dont have free space
nodeA->next[idx] = nodeB;
nodeB->prev[0] = nodeA;

//similarly add for C, you may have to check for appropriate idx!
nodeA->next[idx++]] = nodeC;
nodeC->prev[0] = nodeA;

有了这个基本上你可以创建最多可以有 10 个下一个或上一个节点的节点。

数组是为了简单起见，您也可以struct abcd **next;在可以拥有动态数量的下一个/上一个节点的地方进行操作。不过，您必须适当地分配内存。

于 2013-08-09T05:42:01.933 回答
2

您所描述的是Graph。

（双）链接列表实际上只是一个一维列表，对于您想要的内容来说是一个不恰当的术语。

实现图有两种主要方式：

  • 邻接列表。每个节点/顶点都有一个传入和传出边的列表。就像你描述的那样。
  • 邻接矩阵。一个n时间n矩阵（其中n是节点/顶点的数量），[a][b]如果节点a有一条边到b.

使用哪一个取决于您的用例。根据经验：如果您有很多顶点（数万个），并且您可以平均限制每个顶点的边数为常数，那么您应该使用列表。在其他用例中，最好使用矩阵（主要是因为易于实现）。

我假设您的用例仅限于 ASCII 字母，所以我实际上会在这里使用矩阵。通过适当的优化（位域等），您可以非常快速地浏览它。

您的实现可能如下所示：

char adj_matrix[0x80][0x80]; // I am assuming that you only have ASCII letters
memset(adj_matrix, 0, sizeof(adj_matrix)); // initialise empty

插入元素会像：

adj_matrix['A']['C'] = 1; // edge from A --> C

要确定“A”的所有传入边，您必须遍历矩阵：

for (i = 'A'; i <= 'Z'; i++)
    if (adj_matrix[i]['A'])
        // A has an incoming edge from i

反方向传出

for (i = 'A'; i <= 'Z'; i++)
    if (adj_matrix['E'][i])
        // E has an outgoing edge to i

如前所述，使用位域和位扫描指令（例如 gcc __builtin_clzll、 icc _bit_scan_reverse）可以显着提高空间和时间性能。

于 2013-08-19T13:25:21.563 回答
1

是否可以创建具有多个下一个或多个先前节点的节点的链表，如果是这样，结构会是什么样子？

是的，这是可能的——你必须问自己的问题是“我如何存储任意大量的数据？” ，简短的回答是“你必须使用 ADT”。回想一下，ADT是数据集合的数学模型。

您可以使用任何 ADT 来实现它，具体 ADT 的选择取决于您计划最常使用的操作。对于我的示例，我将使用动态数组。该结构将声明如下（省略节点的特定字段）：

struct llnode {
  int item;
  struct llnode *children;
  int length;
  int capacity;
};

...其中 item 是 'A'、'B'、'C' 等的 ASCII 代码，而 children 是指向结构 llnodes 数组的指针。但是，您可以为动态数组创建一个单独的结构以减少混乱，但这完全取决于您。同样的想法也适用于父节点。

于 2013-08-09T05:29:49.560 回答
1

您可以尝试通过实现指向数据对象的指针列表来将数据与数据结构分开：

struct data_item {
    unsigned char data;
    unsigned char id;
    unsigned int  count;
    // Whatever other data you want.
};

struct list_node {
    struct data_item *item;
    struct list_node *next;
}

现在，当我们在文件中遇到字符时，我们将它们插入到“存储库”数据结构中。对于这个例子，我将使用一个简单的表格，但是如果你想节省空间，你可以使用一个列表，如果你想在保持快速搜索速度的同时节省空间，你可以使用树等。

data_item data_table[UCHAR_MAX + 1] = {0};
...

unsigned char data = read_character_from_file();
struct data_item *di = data_table[data];

if (di == NULL)
    di = new_data_item(data);
else
    ++di->count;

并将它们附加到当前列表：

struct list_node *list;
if (first_item_in_list())
    list = new_list(di)
else
    list - add_list(list, di);

现在，您可以拥有任意数量的此类列表（如果您事先不知道列表的数量，甚至是列表列表）。

于 2013-08-16T15:49:00.063 回答