补充上一个问题代码
来源：8-5 优化后的Prim算法的实现
易萧
2017-07-13
那个return 0是main.cpp就是最后结束程序的时候。我先贴个图：
main.cpp：
#include <iostream>
#include <vector>
#include "ReadGraphW.h"
#include "DenseGraphW.h"
#include "Edge.h"
#include "Prim.h"
using namespace std;
int main()
{
vector<Edge<double> >vec;
DenseGraphW<double> g1( 8, false );
ReadGraphW<DenseGraphW<double>, double>( g1, "testG1.txt" );
g1.show();
cout<<endl;
Prim<DenseGraphW<double>, double> p1( g1, g1.V() );
/*如果不适用这个Prim算法，则不会崩溃*/
p1.min_path( vec );
for( int i=0 ; i<vec.size() ; i++ )
cout<<vec[i]<<endl;
cout<<"最小权值为："<<p1.min_weight()<<endl;
return 0;//就是在这里崩溃的
}DensgraphW.h：
#ifndef DENSEGRAGH_H_INCLUDED
#define DENSEGRAGH_H_INCLUDED
#include <vector>
#include "Edge.h"
#include <iostream>
using namespace std;
template <class Value>
class DenseGraphW
{
int v, e;
bool direction;
vector<vector<Edge<Value>* > > graph;
public:
DenseGraphW( int n, bool dir )
{
int i;
v = n;
direction = dir;
e = 0;
for( i=0 ; i<n ; i++ )
graph.push_back( vector<Edge<Value>* >(n, NULL) );
}
~DenseGraphW()
{
for( int i=0 ; i<v ; i++)
for( int j=0 ; j<v ; j++)
if( graph[i][j] )
delete graph[i][j];
}
int V(){return v;}
int E(){return e;}
bool hasEdge( int a, int b ){return graph[a][b]!=NULL;}
void addEdge( int a, int b, Value value )
{
if( hasEdge(a,b) )
{
graph[a][b]->change( value );
if( !direction )
graph[b][a]->change( value );
return;
}
graph[a][b] = new Edge<Value>( a, b, value );
if( !direction ) graph[b][a] = new Edge<Value>( b, a, value );
e++;
}
void show()
{
int i,j;
for( i=0 ; i<v ; i++ )
{
cout<<i<<": ";
for( j=0 ; j<v ; j++ )
if( hasEdge( i,j ) )
cout<<j<<'('<<graph[i][j]->val()<<')'<<" ";
cout<<endl;
}
}
class Iterator
{
DenseGraphW& G;
int v, index;
public:
Iterator( DenseGraphW& g, int v ):G(g){ this->v = v; index = 0; }
Edge<Value>* begin()
{
index = -1;
return next();
}
Edge<Value>* next()
{
for( ++index ; index<G.V() ; ++index )
if( G.graph[v][index] ) return G.graph[v][index];
return NULL;
}
bool end(){return index>=G.V();}
};
};
#endif // DENSEGRAGH_H_INCLUDEDReadGraphW.h
#ifndef READGRAPH_H_INCLUDED
#define READGRAPH_H_INCLUDED
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <cassert>
using namespace std;
template<class Graph, class Value>
class ReadGraphW
{
public:
ReadGraphW( Graph& graph, const string& filename )
{
int V,E,i,a,b;Value c;
string line;
ifstream file(filename);
getline(file, line);
stringstream ss(line);
ss>>V>>E;
assert( file.is_open() );
assert( graph.V()==V );
for( i=0 ; i<E ; i++ )
{
getline(file, line);
stringstream ss(line);
ss>>a>>b>>c;
graph.addEdge( a, b, c );
}
}
};
#endif // READGRAPH_H_INCLUDEDEdge.h
#ifndef EDGE_H_INCLUDED
#define EDGE_H_INCLUDED
#include <iostream>
using std::ostream;
template<class Value>
class Edge
{
int v, w;
Value value;
public:
Edge( int v, int w, const Value& value )
{
this->v=v;
this->w=w;
this->value=value;
}
Edge(){}
int other( int p ){ return p==v?w:v; }
Value val()const { return value; }
int V(){ return v;}
int W(){ return w;}
void change( const Value& value ){ this->value = value; }
bool operator<( const Edge& e ){ return value<e.val(); }
bool operator>( const Edge& e ){ return value>e.val(); }
bool operator==( const Edge& e ){ return value==e.val(); }
bool operator<=( const Edge& e ){ return value<=e.val(); }
bool operator>=( const Edge& e ){ return value>=e.val(); }
friend ostream& operator<<( ostream& out, const Edge& e ){
return out<<e.v<<"-"<<e.w<<": "<<e.value;
}
};
#endif // EDGE_H_INCLUDEDPrim.h
#ifndef PRIM_H_INCLUDED
#define PRIM_H_INCLUDED
#include "Edge.h"
#include "MinIndexHeap2.h"
#include <vector>
using namespace std;
template <class Graph, class Value>
class Prim
{
Graph G;
bool *visited;
MIHeap2<Value> heap;
vector<Edge<Value>* > edgeto;
vector<Edge<Value> > vec;
Value minw;
void prim( int i )
{
class Graph::Iterator ite( G, i );
Edge<Value> *p; int j;
visited[i] = true;
for( p=ite.begin() ; !ite.end(); p=ite.next() )
{
j=p->other(i);
if( !visited[j] )
{
if( !edgeto[j] )
{
heap.insert( j, p->val() );
edgeto[j] = p;
}
else if( p->val() < heap[j] )
{
heap.change( j, p->val() );
edgeto[j] = p;
}
}
}
}
public:
Prim( Graph& g, int v ):
G(g), heap(v), vec(v-1)
{
int i,tmp;
visited = new bool[v];
for( i=0 ; i<v ; i++ )
{
visited[i] = false;
edgeto.push_back(NULL);
}
vec.clear();
prim(0);
while( !heap.isEmpty() )
{
tmp = heap.popindex();
vec.push_back( *edgeto[tmp] );
prim(tmp);
}
minw=vec[0].val();
for( i=1 ; i<vec.size() ; i++)
minw+=vec[i].val();
}
~Prim(){ delete []visited; }
void min_path( vector<Edge<Value> >& vec_s ){ vec_s = vec; }
Value min_weight() { return minw; }
};
#endif // PRIM_H_INCLUDED以下是使用VS调试的时候弹出提示触发了一个断点：
这是VS触发断点时弹出的一个名为debug_heap.cpp的文件里的，其中905和908都有问题，还有第1407行没有截图下来。这些我都看不懂。。。。下面是读到这一行时的监测窗口
由于长度限制，没有把MinIndexHeap2.h弄上来
写回答
1回答
-
believe or not，你贴的编译器提示的错误，我也不懂。
但是我们可以推测啊！因为return 0前的cout被成功打印出来了。那么最后执行的就只有析构函数了。问题肯定出在析构函数上。请在你的所有类的析构函数中打上断点，或者在析构逻辑的开始和结尾加上输出。以Prim类为例：
~Prim(){ cout << "Prim destructor begin." << endl; delete []visited; cout << "Prim destructor end." << endl; }再看看崩溃在哪里发生，进而寻找为什么会崩溃。
一定不要忘了测试你没有贴上来的索引堆。另外，对于索引堆，包括这里的ReadGraph类，等等等等，都可以使用模块测试的方式。用索引堆完成一个排序看是不是有问题，简单验证一下我们的索引堆的正确性；同理，用ReadGraph读取一个图，输出相应信息试一下，验证ReadGraph的正确性，等等等等。如果能够确保每个模块儿的正确性，就可以进一步缩小错误发生的位置了。
虽然在有些时候，编译器提供的信息是有用的；但是当你犯的错误越“高级”，你就会发现编译器提供的错误越没用，有的时候甚至有迷惑作用。debug首先要学会的，是一点一点寻找错误产生的位置。
加油！
012017-07-14
相似问题