数据结构的实验《图》.doc

#includestdio.h #includestdlib.h #define MAX 26 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define ER -2 typedef int status; int visit[MAX]; typedef struct QNode{ int data; struct QNode *next;//指向第一条依附该顶点的弧的指针 }QNode,*QueuePtr;//链表 typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue;//队列 typedef struct { char vers[MAX]; int arcs[MAX][MAX]; int vexnum,arcnum; }UDGraph;//邻接矩阵 status InitQueue(LinkQueue Q)// 构造一个空链表 { Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(Q.front==NULL) return FALSE; Q.front-next=NULL; return OK; } status EnQueue(LinkQueue Q,int e)//插入元素e为Q的新的队尾元素 { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) return FALSE; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; } status QueueEmpty(LinkQueue Q)//是否为空 { if(Q.front==Q.rear) return TRUE; else return FALSE; } status DeQueue(LinkQueue Q,int e)// 删除对头元素 { QueuePtr p; if(Q.front==Q.rear) return FALSE; p=Q.front-next; e=Q.front-next-data; Q.front-next=p-next; if(p==Q.rear) Q.rear=Q.front; free(p); return OK; }//队列 status Create_UDGraph(UDGraph G)//创建邻接矩阵 { int i,j,f1,f2; char v1,v2; printf(请输入顶点及边的数目:\n); scanf(%d %d,G.vexnum,G.arcnum); for(i=0;iG.vexnum;i++)//二维数组 for(j=0;jG.vexnum;j++) G.arcs[i][j]=0; printf(请依次输入顶点:\n); for(i=0;iG.vexnum;i++) scanf( %c,G.vers[i]); printf(请依次输入边:\n); i=G.arcnum; while(i--) { scanf( %c %c,v1,v2); for(j=0;jG.vexnum;j++) { if(G.vers[j]==v1) f1=j; if(G.vers[j]==v2) f2=j; } G.arcs[f1][f2]=1; G.arcs[f2][f1]=1; }//边放进矩阵里面 return OK; } //返回v的第一个邻接点 int FirstAdjVex(UDGraph G,int v) { int i; for(i=0;iG.vexnum;i++) if(G.arcs[v][i]) return i; return ER; }//返回v的第一个邻接点 //返回v的（相对于w）下一个邻接点 int NextAdjVex(UDGraph G,int v,int w) { int i; for(i=w+1;iG.vexnum;i++) if(G.arcs[v][i]) return i; return ER; }//返回v的（相对于w）下一个邻接点 //深度优先遍历 void DFS(UDGraph G, int v) { int w; visit[v]=TRUE; printf(%c , G.vers[v]);//访问第v个顶点 for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)) { if(w=0) { if(!visit[w]) DFS(G,w);//对v的尚未访问的邻接顶点w递归调用df