关于C语言图的操作问题
老师让编一个代码，要求可以创建编写程序分别实现DG, DN, UDG, UDN的邻接矩阵和邻接表存储结构的构建并遍历；以界面的形式给出选择；构建时候程序是没问题的；但当我加上遍历后(才编了邻接矩阵的DFS)，虽然编译没问题，但运行到一半就会停止，这是为什么？该怎么修改？求帮忙
[code#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INT_MAX 32687
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
#define ERROR false
#define OK true
typedef int VRType;
typedef char InfoType;
typedef char VertexType[INT_MAX];
typedef bool Status;
typedef enum {DG, DN, UDG, UDN} GraphKind;
typedef struct ArcCell {
VRType adj;
InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
struct MGraph
{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum, arcnum;
GraphKind kind;
};
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
int *info;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
Status CreateDG(MGraph &G);
Status CreateDN(MGraph &G);
Status CreateUDG(MGraph &G);
Status CreateUDN(MGraph &G);
Status CreateDG1(ALGraph &M);
Status CreateDN1(ALGraph &M);
Status CreateUDG1(ALGraph &M);
Status CreateUDN1(ALGraph &M);
int LocateVex(MGraph G, VertexType u)
{
int i;
for (i=0; i<G.vexnum; ++i)
if (strcmp(u, G.vexs[i]) == 0)
return i;
return -1;
}
Status CreateGraph(MGraph &G) {
printf("请输入你要创建的图的类型：\n1、有向图邻接矩阵；2、有向网邻接矩阵；3、无向图邻接矩阵；4、无向网邻接矩阵\n");
scanf("%d",&G.kind);
switch(G.kind-1) {
case DG: CreateDG(G);break; //构造有向图
case DN: CreateDN(G); break; //构造有向网
case UDG: CreateUDG(G); break; //构造无向图
case UDN: CreateUDN(G);break; //构造无向网
default:return ERROR;
}
}
Status CreateGraph1(ALGraph &M) {
printf("请输入你要创建的图的类型：\n1、有向图邻接表；2、有向网邻接表；3、无向图邻接表；4、无向网邻接表\n");
scanf("%d",&M.kind);
switch(M.kind-1) {
case DG: CreateDG1(M);break; //构造有向图
case DN: CreateDN1(M);break; //构造有向网
case UDG: CreateUDG1(M);break; //构造无向图
case UDN: CreateUDN1(M);break; //构造无向网
default:return ERROR;
}
}
Status CreateDG(MGraph &G) {
int IncInfo;
int i,j,k;
VertexType v1,v2;
printf("构建有向图邻接矩阵，请输入顶点的数目和边的数目：\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请依次输入对应的顶点的名称：\n");
for( i = 0; i < G.vexnum; ++i ) {
scanf("%s",&G.vexs[i]);
}
for( i = 0; i < G.vexnum; ++i ) {
for( j = 0; j <G.vexnum; ++j ) {
G.arcs[i][j].adj = 0;
G.arcs[i][j].info = NULL;
}
}
for( k = 0; k < G.arcnum; ++k ) {
printf("请输入第%d条边的两个顶点的名称：\n",k+1);
scanf("%s%s",&v1,&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=1;
printf("此边是否含有其他信息：（0、不是；1、是）\n");
scanf("%d",&IncInfo);
if(IncInfo)
scanf("%s",&G.arcs[i][j].info);
}
return OK;
}
Status CreateDN(MGraph &G) {
int IncInfo;
int i,j,k,w;
VertexType v1,v2;
printf("构建有向网邻接矩阵，请输入顶点的数目和边的数目：\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请依次输入对应的顶点的名称：\n");
for( i = 0; i < G.vexnum; ++i ) {
scanf("%s",&G.vexs[i]);
}
for( i = 0; i < G.vexnum; ++i ) {
for( j = 0; j <G.vexnum; ++j ) {
G.arcs[i][j].adj = INFINITY;
G.arcs[i][j].info = NULL;
}
}
for( k = 0; k < G.arcnum; ++k ) {
printf("请输入第%d条边的两个顶点的名称和相应的权重：\n",k+1);
scanf("%s%s%d",&v1,&v2,&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
printf("此边是否含有其他信息：（0、不是；1、是）\n");
scanf("%d",&IncInfo);
if(IncInfo)
scanf("%s",&G.arcs[i][j].info);
}
return OK;
}
Status CreateUDG(MGraph &G) {
int IncInfo;
int i,j,k;
VertexType v1,v2;
printf("构建无向图邻接矩阵，请输入顶点的数目和边的数目：\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请依次输入对应的顶点的名称：\n");
for( i = 0; i < G.vexnum; ++i ) {
scanf("%s",&G.vexs[i]);
}
for( i = 0; i < G.vexnum; ++i ) {
for( j = 0; j <G.vexnum; ++j ) {
G.arcs[i][j].adj = 0;
G.arcs[i][j].info = NULL;
}
}
for( k = 0; k < G.arcnum; ++k ) {
printf("请输入第%d条边的两个顶点的名称：\n",k+1);
scanf("%s%s",&v1,&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=1;
printf("此边是否含有其他信息：（0、不是；1、是）\n");
scanf("%d",&IncInfo);
if(IncInfo)
scanf("%s",&G.arcs[i][j].info);
G.arcs[j][i]=G.arcs[i][j];
}
return OK;
}
Status CreateUDN(MGraph &G) {
int IncInfo;
int i,j,k,w;
VertexType v1,v2;
printf("构建无向网邻接矩阵，请输入顶点的数目和边的数目：\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请依次输入对应的顶点的名称：\n");
for( i = 0; i < G.vexnum; ++i ) {
scanf("%s",&G.vexs[i]);
}
for( i = 0; i < G.vexnum; ++i ) {
for( j = 0; j <G.vexnum; ++j ) {
G.arcs[i][j].adj = INFINITY;
G.arcs[i][j].info = NULL;
}
}
for( k = 0; k < G.arcnum; ++k ) {
printf("请输入第%d条边的两个顶点的名称和相应的权重：\n",k+1);
scanf("%s%s%d",&v1,&v2,&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
printf("此边是否含有其他信息：（0、不是；1、是）\n");
scanf("%d",&IncInfo);
if(IncInfo)
scanf("%s",&G.arcs[i][j].info);
G.arcs[j][i]=G.arcs[i][j];
}
return OK;
}
Status CreateDG1(ALGraph &M){
int i,s,d,k;
printf("构建有向图邻接表，请输入顶点的数目和边的数目：\n");
scanf("%d%d",&M.vexnum,&M.arcnum);
printf("请依次输入对应的顶点的值：\n");
for( i=0;i<M.vexnum;i++ ) {
getchar();
scanf("%c",&M.vertices[i].data);
M.vertices[i].firstarc=NULL;
}
for( k = 0; k < M.arcnum; k++ ) {
printf("请输入第%d条边的两个顶点的序号：\n",k+1);
scanf("%d%d",&s,&d);
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=d;
p->nextarc=M.vertices[s].firstarc;M.vertices[s].firstarc=p;
}
}
Status CreateDN1(ALGraph &M){
int i,s,d,k,*w;
printf("构建有向网邻接表，请输入顶点的数目和边的数目：\n");
scanf("%d%d",&M.vexnum,&M.arcnum);
printf("请依次输入对应的顶点的值：\n");
for( i = 0; i < M.vexnum; i++ ) {
getchar();
scanf("%c",&M.vertices[i].data);
M.vertices[i].firstarc=NULL;
}
for( k = 0; k < M.arcnum; k++ ) {
printf("请输入第%d条边的两个顶点的序号：\n",k+1);
scanf("%d%d",&s,&d);
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=d;
printf("请输入该边权值\n");
scanf("%d",&w);
p->info=w;p->nextarc=M.vertices[s].firstarc;M.vertices[s].firstarc=p;
}
}
Status CreateUDG1(ALGraph &M){
int i,s,d,k;
printf("构建无向图邻接表，请输入顶点的数目和边的数目：\n");
scanf("%d%d",&M.vexnum,&M.arcnum);
printf("请依次输入对应的顶点的值：\n");
for( i = 0; i < M.vexnum; i++ ) {
getchar();
scanf("%c",&M.vertices[i].data);
M.vertices[i].firstarc=NULL;
}
for( k = 0; k < M.arcnum; k++ ) {
printf("请输入第%d条边的两个顶点的序号：\n",k+1);
scanf("%d%d",&s,&d);
ArcNode *p,*q;
p=(ArcNode*)malloc(sizeof(ArcNode));
q=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=d;q->adjvex=s;
p->nextarc=M.vertices[s].firstarc;M.vertices[s].firstarc=p;
q->nextarc=M.vertices[d].firstarc;M.vertices[d].firstarc=q;
}
}
Status CreateUDN1(ALGraph &M){
int i,s,d,k,*w;
printf("构建无向网邻接表，请输入顶点的数目和边的数目：\n");
scanf("%d%d",&M.vexnum,&M.arcnum);
printf("请依次输入对应的顶点的值：\n");
for( i = 0; i < M.vexnum; i++ ) {
getchar();
scanf("%c",&M.vertices[i].data);
M.vertices[i].firstarc=NULL;
}
for( k = 0; k < M.arcnum; k++ ) {
printf("请输入第%d条边的两个顶点的序号：\n",k+1);
scanf("%d%d",&s,&d);
ArcNode *p,*q;
p=(ArcNode*)malloc(sizeof(ArcNode));
q=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=d;q->adjvex=s;
printf("请输入该边权值\n");
scanf("%d",&w);
p->info=w;p->nextarc=M.vertices[s].firstarc;M.vertices[s].firstarc=p;
q->info=w;q->nextarc=M.vertices[d].firstarc;M.vertices[d].firstarc=q;
}
}
bool *visited;
int FirstVex(MGraph G,int k)
{
if(k>=0 && k<G.vexnum){
for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i].adj!=INFINITY||G.arcs[k][i].adj!=0) return i;
}
return -1;
}
int NextVex(MGraph G,int i,int j){
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k].adj!=INFINITY||G.arcs[k][i].adj!=0) return k;
}
return -1;
}
void DFS(MGraph G,int v){
int w;
visited[v]=true;
printf("%c",G.vexs[v]);
for(w=FirstVex(G,v);w>0;w=NextVex(G,v,w))
if(!visited[w])
DFS(G,w);
}
void DFSTrave(MGraph G){
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=false;
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v);
}
int main()
{
MGraph G;
ALGraph M;
int a;
printf("创建邻接矩阵输入0，邻接表输入1\n");
scanf("%d",&a);
switch(a){
case 0:CreateGraph(G);DFSTrave(G);break;
case 1:CreateGraph1(M);
}
return 0;
}][/code]
