c++ - 将链表存储为数组 C++ 中的索引

Question

概述：我目前正在尝试编写一个代码，该代码将采用 AOV 网络图并将其放入链接列表中。我是如何遇到麻烦最好的方法来解决这个问题。我在纸上理解如何以链表形式表示图形。

这是我的图表：

我的思考过程/Pusdo 代码如下：

创建一个 Linked-List 类，它只添加节点并将它们打印出来用于方法。然后对于每个边访问数组的索引并转到该链接列表。那么我的数组将具有 [s,a,d,g,b,e,h,c,f,i,t] ，其中每个字母代表该顶点的 >Linked 列表。因此，如果我想调用 S 顶点，我将不得不调用数组的 >0 元素，这将指向 s Linked-List。在 C++ 中有一个简单的实现吗？

这是我现在的链表类：

class List{
private:
    typedef struct node{
        char vertex;
        node* next;
    }* nodePtr;
    nodePtr head;
    nodePtr curr;
    nodePtr temp;
public:
    List();
    void AddNode(char AddData);
    void printList();
};

List::List(){
    head = NULL;
    curr = NULL;
    temp = NULL;
}

void List::AddNode(char AddData){
    nodePtr n = new node;
    n->next = NULL;
    n->vertex = AddData;

    if(head != NULL){
        curr = head;
        while(curr->next != NULL){
            curr = curr->next;
        }
        curr->next = n;
    }
    else{
        head = n;
    }
}

void List::printList(){
    curr = head;
    while(curr != NULL){
        cout << curr->vertex << endl;
        curr = curr->next;
    }
}

任何帮助将非常感激。

编辑：可以使用像这样的双链表吗？

Answer 1

你有一个图表问题，而不是一个列表问题。使用“节点”和“边”的图形隐喻而不是“列表”。

Answer 2

有一个名为 Adjacent Table 的数据结构将图形存储在链表结构中

AT中的元素就像

struct ATEle {
    char name;
    ATEle * neighborPointer;
    ATEle * nodelistPointer;
}

图中的节点被组织在一个链表中，每个节点也是它所有邻居的链表的头部

例如，我们有一个由 4 个节点组成的图，A、B、C、D 和 A 连接 B、C、D 连接 A、B 连接 C、D，在相邻表中它看起来像：

A -> B -> C

|

B -> C -> D

|

C

|

D -> A