2

概述:我目前正在尝试编写一个代码,该代码将采用 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;
    }
}

任何帮助将非常感激。

编辑:可以使用像这样的双链表吗? 在此处输入图像描述

4

2 回答 2

0

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

于 2013-07-31T12:06:55.233 回答
0

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

于 2013-07-31T12:27:07.097 回答