入栈程序停止运行
这是源码，太长可以忽略
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 //最多的定点个数
#define INFINTY 0 //表示极大值
#define Error -1
#define False 0
#define True 1
#define OK 1 //出错
int visited[MAX_VERTEX_NUM]; //标志图顶点是否被访问过
/*图的种类：DG表示有向图，DN表示有向网，UDG表示无向图，UDN表示无向网*/
typedef enum{DG,DN,UDG,UDN} GraphKind;//枚举变量
typedef char VertexData;
typedef int AdjType;
typedef struct ArcNode{
AdjType adj; //对于无权图，用1或0表示是否相邻；对带权图，则为权值类型
//OtherInfo info； //其他信息
}ArcNode; //弧
typedef struct {
VertexData vertex[MAX_VERTEX_NUM]; // 顶点向量
ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum,arcnum; //图的顶点数和弧数
GraphKind kind; //图的种类
}AdjMatrix;
//typedef AdjMatrix Graph;
typedef struct stack
{
int S[MAX_VERTEX_NUM];
int top;
}Stack; //图
int LocateVertex(AdjMatrix *G,VertexData v)
{
int j=Error,k;
for(k=0;k<G->vexnum;k++)
if(G->vertex[k]==v){
j=k;break;}
return j;
} //Adjcency Matrix Graph 邻接 矩阵 图
void CreateDN(AdjMatrix *G)
{
int i,j,k,weight;
VertexData v1,v2;
printf("请输入顶点数目和弧数目\n");
scanf("%d %d",&G->vexnum,&G->arcnum); //输入图的顶点数和弧数
getchar();
for(i=0;i<G->vexnum;i++) //初始化
for(j=0;j<G->vexnum;j++)
G->arcs[i][j].adj=INFINTY;
for(i=0;i<G->vexnum;i++){
printf("请输入图顶点信息(a char)\n");
scanf("%c",&G->vertex[i]);getchar();}
for(k=0;k<G->arcnum;k++)
{
printf("输入弧信息，比如顶点 顶点 权值\n");
scanf("%c %c %d",&v1,&v2,&weight);//输入一条弧的两个顶点及权值
fflush(stdin); //清空缓冲区内容，避免下一次输入字符时，读入以前遗留的
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G->arcs[i][j].adj=weight; // 建立弧
}
}
void Output(AdjMatrix *G) //输出矩阵
{
int i,j;
for(i=0;i<G->vexnum;i++)
for(j=0;j<G->vexnum;j++)
{
printf("%d\t",G->arcs[i][j].adj);
if(j!=0&&(j+1)%G->vexnum==0)
printf("\n");
}
}
void DepthFirstSearch(AdjMatrix *G,int v0) //采用邻接矩阵的DepthFirstSearch()
{
visited[v0]=True;
int vj;
for(vj=0;vj<G->vexnum;vj++)
if(!visited[vj]&&G->arcs[v0][vj].adj!=0){
printf("%c\t",G->vertex[vj]);
//visited[vj]=True;
DepthFirstSearch(G,vj);}
/*while(w!=-1) //邻接点存在
{
if(!visited[w])
DepthFirstSearch(G,w); //递归调用DepthFirstSearch()
w=NextAdjVertex(G,v0,w); //找下一个邻接点
}*/
}
void InitStack(Stack *s)
{
s->top=-1;
}
int FirstAdjVertex(AdjMatrix *G,int v0)
{
int i;
for(i=0;i<G->arcnum;i++)
{
if(!visited[i]&&G->arcs[v0][i].adj!=0)
{
return i;break;
}
}
return False;
}
int NextAdjVertex(AdjMatrix *G,int v,int w) //求v相对于w的下一个邻接点
{
int i;
for(i=0;i<G->vexnum;i++)
{
if(!visited[i]&&G->arcs[v][i].adj!=0)
return i;
break;
}
return False;
}
int Empty(Stack *s)
{
if(s->top==-1)
return True;
return False;
}
int Push(Stack *s,int v)
{
if(s->top==MAX_VERTEX_NUM-1)
return False;
s->top++;
s->S[s->top]=v;
return True;
}
void Pop(Stack *s)
{
s->top--;
}
void gettop(Stack *s,int *v)
{
if(s->top==-1)
return False;
*v=s->S[s->top];
}
/*void DepthFirstSearch_stack(AdjMatrix *G,int v0)
{
Stack *s=(Stack *)malloc(sizeof(Stack));
int v,w;
InitStack(s);
Push(s,v0);
while(!Empty(s)) //判断该点还有其他弧
{
if(v0==0) Pop(s,&v);
else if(!NextAdjVertex(G,v,w))
Pop(s,&v); //依次出栈,从下至上依次出栈，输出
if(!visited[v])
{
visited[v]=True;
w=FirstAdjVertex(G,v);
while(w!=0)
{
if(!visited[w]) Push(G,w);
printf("%c",G->vertex[s->S[w]]);
w=NextAdjVertex(G,v,w);
}
}
}
}*/
void DepthFirstSearch_stack(AdjMatrix *G,int v0)
{
Stack *s=(Stack *)malloc(sizeof(Stack));
int v,w;
InitStack(s);
Push(s,v0);
while(!Empty(s)) //判断该点还有其他弧
{
if(v0!=0&&!NextAdjVertex(G,v,w)) //依次出栈,从下至上依次出栈，输出
Pop(s);
gettop(s,&v);
if(!visited[v])
{
visited[v]=True;
w=FirstAdjVertex(G,v);
while(w!=0)
{
if(!visited[w]) Push(G,w);
printf("%c",G->vertex[s->S[w]]);
w=NextAdjVertex(G,v,w);
}
}
}
}
/*1.以第几个节点出发
2.1出栈*/
void TraverseGraph(AdjMatrix *G) //遍历图
{
int vi; //相当于矩阵的行下标
for(vi=0;vi<G->vexnum;vi++)
visited[vi]=False;
for(vi=0;vi<G->vexnum;vi++)
if(!visited[vi]) //如果该节点没被访问过，输出
{ printf("%c\t",G->vertex[vi]);
DepthFirstSearch(G,vi);
} //采用深度遍历
}
void TraverseGraph_Stack(AdjMatrix *G) //遍历图
{
int vi; //相当于矩阵的行下标
for(vi=0;vi<G->vexnum;vi++)
visited[vi]=False;
for(vi=0;vi<G->vexnum;vi++)
if(!visited[vi]) //如果该节点没被访问过，输出
{ printf("%c\t",G->vertex[vi]);
DepthFirstSearch_stack(G,vi);
} //采用深度遍历
}
int main()
{
AdjMatrix *G; //定义邻接矩阵
G=(AdjMatrix *)malloc(sizeof(AdjMatrix));
int menu,flag;
while(flag){
printf("************menu***************\n");
printf("********************************\n");
printf("1.输入图的信息\n");
printf("2.输出邻接矩阵\t3.输出深度遍历的序列(递归)\n");
printf("4.输出深度遍历序列(非递归)\t5.清空前面\n");
printf("请输入操作选项:");
scanf("%d",&menu);
switch(menu)
{
case 1: CreateDN(G);break;
case 2: Output(G);break;
case 3: TraverseGraph(G);printf("\n");break;
case 4:TraverseGraph_Stack(G);printf("\n");break;
case 5:system("cls");break; //清空屏幕
}
}
return 0;
}
