C++ 图的邻接矩阵与邻接表转换函数出错
错误出现在Conversion函数邻接矩阵与邻接表转换中，我不知道是哪里有问题
#include<iostream>
#include<iomanip>
using namespace std;
const int MAXV = 100; //图中最多结点数
const int MAXL = 50; //顶点信息的最大字符个数
const int INF = 32767; //用INF表示无穷
int visited[MAXV]; //全局数组变量visited
struct VertexType //顶点类型
{
int no; //顶点编号
char data[MAXL]; //顶点其他信息
};
template <class T>
struct Mgraph //图邻接矩阵类型
{
T edges[MAXV][MAXV]; //邻接矩阵的边数组，假设权值为T类型
int n, e; //顶点数，边数
VertexType vexs[MAXV]; //存放顶点信息
};
template <class T>
struct ArcNode //边结点类型
{
int adjvex; //该边的终点编号
ArcNode* nextarc; //指向下一条边的指针
T weight; //该边的相关信息,如边的权值
};
template <class T>
struct VNode //表头结点类型
{
char data[MAXL]; //顶点信息
ArcNode<T>* firstarc; //指向第一条边的相邻顶点
};
template <class T>
struct ALgraph //图的邻接表类型
{
VNode<T> adjlist[MAXV]; //邻接表数组
int n, e; //图中顶点数n和边数e
};
template <class T>
class SMygraph
{
Mgraph<T> g; //图的邻接矩阵
ALgraph<T>* G; //图的邻接表
public:
SMygraph(); //构造函数，建立一个邻接表
~SMygraph(); //析构函数
void ALgraph(T a[][MAXV], int n, int e); //构造函数，建立一个邻接表
void CreatMgraph(T a[][MAXV], int n, int e); //建立一个邻接矩阵
void DispMgraph(); //输出邻接矩阵
void DispALgraph(); //输出邻接表
private:
void DeleteGraph(); //销毁图的邻接表
public:
friend void Conversion(SMygraph<T>& gobj); //将带权图的邻接矩阵g转换成邻接表G
friend void DFTraverse(SMygraph<T>& gobj, int v); //图的深度优先遍历
friend void BFTraverse(SMygraph<T>& gobj, int v); //图的广度优先遍历
};
template <class T>
SMygraph<T>::SMygraph()
{
//初始化邻接矩阵
int i,j;
for (i = 0; i < this->g.n; i++)
{
for (j = 0; j < this->g.n; j++)
{
this->g.edges[i][j] = 0;
}
}
G = NULL;
}
template <class T>
SMygraph<T>::~SMygraph() //析构函数,释放图的邻接表空间
{
if (G != NULL)
DeleteGraph();
}
template <class T>
void SMygraph<T>::DeleteGraph() //销毁图的邻接表
{
int i;
ArcNode<T>* pre, * p;
for (i = 0; i < G->n; i++) //遍历所有的头结点
{
pre = G->adjlist[i].firstarc;
if (pre != NULL)
{
p = pre->nextarc;
while (p != NULL) //释放adjlist[i]的所有边结点空间
{
delete pre;
pre = p; p = p->nextarc;
}
delete pre;
}
}
delete G; //释放G所指的头结点数组的内存空间
}
template <class T>
void SMygraph<T>::ALgraph(T a[][MAXV], int n, int e) //通过边数组a、顶点数n和边数e来建立图的邻接表
{
int i, j;
ArcNode<T>* p;
G = new class ALgraph<T>(); //创建图的邻接表
G->n = n; G->e = e; //置顶点数和边数
for (i = 0; i < G->n; i++) //给邻接表中所有头结点的指针域置初值
G->adjlist[i].firstarc = NULL;
for (i = 0; i < G->n; i++) //检查邻接矩阵中每个元素
for (j = G->n - 1; j >= 0; j--)
if (a[i][j] != 0 && a[i][j] != INF) //存在一条边
{
p = new ArcNode<T>(); //创建一个结点*p
p->adjvex = j;
p->weight = a[i][j];
p->nextarc = G->adjlist[i].firstarc; //采用头插法插入*p
G->adjlist[i].firstarc = p;
}
}
template <class T>
void SMygraph<T>::CreatMgraph(T a[][MAXV], int n, int e) //通过边数组a、顶点数n和边数e来建立图的邻接矩阵
{
int i, j;
g.n = n; g.e = e; //置顶点数和边数
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
g.edges[i][j] = a[i][j];
}
template <class T>
void SMygraph<T>::DispMgraph() //输出图的邻接矩阵
{
int i, j;
for (i = 0; i < g.n; i++)
{
for (j = 0; j < g.n; j++)
if (g.edges[i][j] == INF)
cout << setw(4) << "∞";
else
cout << setw(4) << g.edges[i][j];
cout << endl;
}
}
template <class T>
void SMygraph<T>::DispALgraph() //输出图的邻接表
{
int i;
ArcNode<T>* p;
for (i = 0; i < G->n; i++)
{
cout << "[" << i << "]";
p = G->adjlist[i].firstarc; //p指向第一个邻接点
if (p != NULL) cout << "→";
while (p != NULL)
{
cout << " " << p->adjvex << "(" << p->weight << ")";
p = p->nextarc; //p移向下一个邻接点
}
cout << endl;
}
}
template <class T>
void Conversion(SMygraph<T>& gobj) //将带权图的邻接矩阵g转换成邻接表G
{
int i, j;
ArcNode<T>* p;
gobj.G = new ALgraph<T>(); //给邻接表分配空间
for (i = 0; i < gobj.g.n; i++) //给邻接表中所有头结点的指针域置初值
gobj.G->adjlist[i].firstarc = NULL;
for (i = 0; i < gobj.g.n; i++) //检查邻接矩阵中每个元素
for (j = gobj.g.n - 1; j >= 0; j--)
if (gobj.g.edges[i][j] != 0 && gobj.g.edges[i][j] != INF) //存在一条边
{
p = new ArcNode<T>(); //创建一个结点p
p->adjvex = j; p->weight = gobj.g.edges[i][j];
p->nextarc = gobj.G->adjlist[i].firstarc; //采用头插法插入*p
gobj.G->adjlist[i].firstarc = p;
}
gobj.G->n = gobj.g.n; gobj.G->e = gobj.g.e;//置顶点数和边数
}
template <class T>
void DFTraverse(SMygraph<T>& gobj, int v) //图对象gobj的深度优先遍历
{
int i;
for (i = 0; i < gobj.G->n; i++) visited[i] = 0; //visited数组元素均置为0
DFTraverse1(gobj.G, v);
}
template <class T>
void DFTraverse1(ALgraph<T>* G, int v)
{
int w;
ArcNode<T>* p;
visited[v] = 1; //置已访问标记
//cout << v << " "; //输出被访问顶点的编号
p = G->adjlist[v].firstarc; //p指向顶点v的第一个邻接点
while (p != NULL)
{
w = p->adjvex;
if (visited[w] == 0) DFS1(G, w); //若w顶点未访问,递归访问它
p = p->nextarc; //p置为下一个邻接点
}
}
template <class T>
void BFTraverse(SMygraph<T>& gobj, int v) //图对象gobj的广度优先遍历
{
int i;
for (i = 0; i < gobj.G->n; i++) visited[i] = 0; //visited数组元素均置为0
BFTraverse1(gobj.G, v);
}
template <class T>
void BFTraverse1(ALgraph<T>* G, int v) //被BFTraverse调用进行广度优先遍历
{
ArcNode<T>* p; int w;
int qu[MAXV]; //定义一个循环队列
int front = 0, rear = 0; //循环队列队头队尾初始化
//cout << v << " "; visited[v]=1; //输出访问顶点并置已访问标记
rear = (rear + 1) % MAXV; qu[rear] = v; //v进队
while (front != rear) //若队列不空时循环
{
front = (front + 1) % MAXV;
w = qu[front]; //出队并赋给w
p = G->adjlist[w].firstarc; //找与顶点w邻接的第一个顶点
while (p != NULL)
{
if (visited[p->adjvex] == 0) //若当前邻接顶点未被访问
{
cout << p->adjvex << " "; //访问相邻顶点
visited[p->adjvex] = 1; //置该顶点已被访问的标志
rear = (rear + 1) % MAXV; //该顶点进队
qu[rear] = p->adjvex;
}
p = p->nextarc; //找下一个邻接顶点
}
}
}
int main()
{
SMygraph<int> gobj;
int n = 5, e = 6;
int A[MAXV][MAXV] = { {0,1,0,1,1},{1,0,1,1,0},{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0} };
gobj.CreatMgraph(A, n, e);
cout << "图的邻接矩阵:" << endl;
gobj.DispMgraph();
Conversion(gobj);
cout << "图的邻接表:"<<endl;
gobj.DispALgraph();
cout << "销毁图"<<endl;
}
```