创建图形使用邻接表

Question

#include<iostream> 

using namespace std; 

class TCSGraph{ 
    public: 
     void addVertex(int vertex); 
     void display(); 
     TCSGraph(){ 

      head = NULL; 
     } 
     ~TCSGraph(); 

    private: 
     struct ListNode 
     { 
      string name; 
      struct ListNode *next; 
     }; 

     ListNode *head; 
} 

void TCSGraph::addVertex(int vertex){ 
    ListNode *newNode; 
    ListNode *nodePtr; 
    string vName; 

    for(int i = 0; i < vertex ; i++){ 
     cout << "what is the name of the vertex"<< endl; 
     cin >> vName; 
     newNode = new ListNode; 
     newNode->name = vName; 

     if (!head) 
     head = newNode; 
     else 
     nodePtr = head; 
     while(nodePtr->next) 
     nodePtr = nodePtr->next; 

     nodePtr->next = newNode; 

    } 
} 

void TCSGraph::display(){ 
    ListNode *nodePtr; 
    nodePtr = head; 

    while(nodePtr){ 
    cout << nodePtr->name<< endl; 
    nodePtr = nodePtr->next; 
    } 
} 

int main(){ 
int vertex; 

cout << " how many vertex u wan to add" << endl; 
cin >> vertex; 

TCSGraph g; 
g.addVertex(vertex); 
g.display(); 

return 0; 
} 

Answer 1

有一个问题，您addvertex方法：

您有：

if (!head) 
    head = newNode; 
else 
nodePtr = head; 
while(nodePtr->next) 
nodePtr = nodePtr->next; 
nodePtr->next = newNode; 

，但它应该是：

if (!head) // check if the list is empty. 
    head = newNode;// if yes..make the new node the first node. 
else { // list exits. 
    nodePtr = head; 
    while(nodePtr->next) // keep moving till the end of the list. 
     nodePtr = nodePtr->next; 
    nodePtr->next = newNode; // add new node to the end. 
} 

而且你是不是使newNodeNULL的next字段为：

newNode = new ListNode; 
newNode->name = vName; 
newNode->next= NULL; // add this. 

另外它是一个很好的实践来释放动态分配的内存。因此，而不是有一个空的析构函数

~TCSGraph(); 

你可以释放列表中的dtor。

编辑：更多的错误

你有一个丢失;类声明后：

class TCSGraph{ 
...... 

}; // <--- add this ; 

此外您的析构函数仅声明。没有def。如果你不想给任何def，你至少必须有一个空的身体。因此，与

~TCSGraph(){} 

Answer 2

你已经采取了看看Boost Graph Library和boost::adjacency_list更换

~TCSGraph(); 

？