邻接表的 C++ 实现错误
Error in C++ implementation of Adjacency List
为什么我在这个邻接表的 C++ 实现中出现分段错误?我的 printList()
函数或 getter 和 setter 函数之一有问题吗?相同的实现在 Java 中有效,但在 C++ 中无效。
#include<iostream>
#include<list>
using namespace std;
class Graph
{
int V;
list<int> *adj;
public:
Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void addEdge(int u, int v)
{
this->adj[u].push_back(v);
}
int getVertexCount()
{
return this->V;
}
list<int>* getList()
{
return this->adj;
}
};
void printList(Graph g)
{
list<int> *adj = g.getList();
list<int>::iterator it;
for(int i=0; i< g.getVertexCount(); i++)
{
cout << "Adjacency list of vertex " << i << "is:" <<endl;
for(it=adj[i].begin(); it != adj[i].end(); it++)
{
cout << *it << "->";
}
}
}
int main()
{
Graph g(7);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(0,3);
g.addEdge(1,5);
g.addEdge(1,6);
g.addEdge(2,0);
g.addEdge(2,4);
g.addEdge(2,6);
g.addEdge(3,0);
g.addEdge(3,5);
g.addEdge(3,7);
g.addEdge(4,2);
g.addEdge(4,7);
g.addEdge(5,3);
g.addEdge(5,7);
g.addEdge(6,1);
g.addEdge(6,2);
g.addEdge(7,5);
g.addEdge(7,3);
g.addEdge(7,4);
printList(g);
return 0;
}
问题是分配 7 个条目:
Graph g(7);
之后访问第 8 个
g.addEdge(7,4);
更好更灵活
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Graph {
vector< list<int> > adj;
public:
Graph( void ) {}
void addEdge( int u, int v ) {
if ( u > ( ( int )( adj.size() ) - 1 ) ) {
adj.resize( u + 1 );
}
adj[u].push_back( v );
}
int getVertexCount() const {
return adj.size();
}
const vector< list<int> >& getList() const {
return adj;
}
};
void printList( const Graph& g ) {
const vector< list<int> >& adj( g.getList() );
list<int>::const_iterator it;
for ( int i = 0; i < g.getVertexCount(); i++ ) {
cout << "Adjacency list of vertex " << i << " is:";
for ( it = adj[i].begin(); it != adj[i].end(); it++ ) {
cout << *it << "->";
}
cout << endl;
}
}
int main() {
Graph g;
g.addEdge( 0, 1 );
g.addEdge( 0, 2 );
g.addEdge( 0, 3 );
g.addEdge( 1, 5 );
g.addEdge( 1, 6 );
g.addEdge( 2, 0 );
g.addEdge( 2, 4 );
g.addEdge( 2, 6 );
g.addEdge( 3, 0 );
g.addEdge( 3, 5 );
g.addEdge( 3, 7 );
g.addEdge( 4, 2 );
g.addEdge( 4, 7 );
g.addEdge( 5, 3 );
g.addEdge( 5, 7 );
g.addEdge( 6, 1 );
g.addEdge( 6, 2 );
g.addEdge( 7, 5 );
g.addEdge( 7, 3 );
g.addEdge( 7, 4 );
printList( g );
return 0;
}
玩得开心。
为什么我在这个邻接表的 C++ 实现中出现分段错误?我的 printList()
函数或 getter 和 setter 函数之一有问题吗?相同的实现在 Java 中有效,但在 C++ 中无效。
#include<iostream>
#include<list>
using namespace std;
class Graph
{
int V;
list<int> *adj;
public:
Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void addEdge(int u, int v)
{
this->adj[u].push_back(v);
}
int getVertexCount()
{
return this->V;
}
list<int>* getList()
{
return this->adj;
}
};
void printList(Graph g)
{
list<int> *adj = g.getList();
list<int>::iterator it;
for(int i=0; i< g.getVertexCount(); i++)
{
cout << "Adjacency list of vertex " << i << "is:" <<endl;
for(it=adj[i].begin(); it != adj[i].end(); it++)
{
cout << *it << "->";
}
}
}
int main()
{
Graph g(7);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(0,3);
g.addEdge(1,5);
g.addEdge(1,6);
g.addEdge(2,0);
g.addEdge(2,4);
g.addEdge(2,6);
g.addEdge(3,0);
g.addEdge(3,5);
g.addEdge(3,7);
g.addEdge(4,2);
g.addEdge(4,7);
g.addEdge(5,3);
g.addEdge(5,7);
g.addEdge(6,1);
g.addEdge(6,2);
g.addEdge(7,5);
g.addEdge(7,3);
g.addEdge(7,4);
printList(g);
return 0;
}
问题是分配 7 个条目:
Graph g(7);
之后访问第 8 个
g.addEdge(7,4);
更好更灵活
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Graph {
vector< list<int> > adj;
public:
Graph( void ) {}
void addEdge( int u, int v ) {
if ( u > ( ( int )( adj.size() ) - 1 ) ) {
adj.resize( u + 1 );
}
adj[u].push_back( v );
}
int getVertexCount() const {
return adj.size();
}
const vector< list<int> >& getList() const {
return adj;
}
};
void printList( const Graph& g ) {
const vector< list<int> >& adj( g.getList() );
list<int>::const_iterator it;
for ( int i = 0; i < g.getVertexCount(); i++ ) {
cout << "Adjacency list of vertex " << i << " is:";
for ( it = adj[i].begin(); it != adj[i].end(); it++ ) {
cout << *it << "->";
}
cout << endl;
}
}
int main() {
Graph g;
g.addEdge( 0, 1 );
g.addEdge( 0, 2 );
g.addEdge( 0, 3 );
g.addEdge( 1, 5 );
g.addEdge( 1, 6 );
g.addEdge( 2, 0 );
g.addEdge( 2, 4 );
g.addEdge( 2, 6 );
g.addEdge( 3, 0 );
g.addEdge( 3, 5 );
g.addEdge( 3, 7 );
g.addEdge( 4, 2 );
g.addEdge( 4, 7 );
g.addEdge( 5, 3 );
g.addEdge( 5, 7 );
g.addEdge( 6, 1 );
g.addEdge( 6, 2 );
g.addEdge( 7, 5 );
g.addEdge( 7, 3 );
g.addEdge( 7, 4 );
printList( g );
return 0;
}
玩得开心。