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

Question

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

这是我的图表:

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

Create a Linked-List class that just adds the nodes and prints them out for the methods. Then for each edge access the index of an array and go to that Linked list. So then my array would have [s,a,d,g,b,e,h,c,f,i,t] where each letter would represent the >Linked list of that vertex. So if i would like to call the S vertex i would have to call the >0 element of the array and that would point to s Linked-List. Is there a easy implementation >of this in 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

有一个名为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