7 邻接表的建立与遍历.doc

#include stdio.h#include stdlib.h#define MAX_SIZE 20int visitedMAX_SIZE;typedef struct ArcNode /弧的结点结构 int adjvex; ArcNode *nextarc;ArcNode;typedef struct VNode /顶点结构 char data; ArcNode *firstarc;AdjListMAX_SIZE;typedef struct /图的存储结构 AdjList vexs; int arcnum,vexnum; Graph;/* 图的基本操作 */void creatGraph(Graph *h);int Loc(Graph G,char ch);void DFS(Graph G,char ch);void DispGraphStruct(Graph G);void BFS(Graph G); /* 图的基本操作 */ * 队列结构及操作 */typedef int QElemType; typedef struct QNode QElemType data;struct QNode *next; QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q);int EnQueue(LinkQueue &Q,QElemType e);int DeQueue(LinkQueue &Q,QElemType &e);int QueueEmpty(LinkQueue Q);/ * 队列结构及操作 */void main() Graph H; creatGraph(&H);printf(n图的邻接表结构输出：); DispGraphStruct(H); printf(nn深度优先搜索遍历，顶点输出顺序：); DFS(H,H.vexs0.data); /深度优先搜索遍历 printf(nn广度优先搜索遍历，顶点输出顺序：); BFS(H) ; printf(n);void creatGraph(Graph *h) ArcNode *p; int i,j,n; char ch20; printf(输入图的顶点数，边数: ); scanf(%d,%d,&h-vexnum,&h-arcnum); printf(n输入%d个顶点（a-z）: ,h-vexnum); scanf(%s,&ch); for(i=0;ivexnum;i+) h-vexsi.data=chi; h-vexsi.firstarc=NULL; printf(共有%d条边，下面逐条输入：n,h-arcnum); for(i=0;iarcnum;i+) printf(输入第 %d 条边：,i+1);scanf(%s,&ch);j=Loc(*h,ch0); n=Loc(*h,ch1);p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=n;p-nextarc=h-vexsj.firstarc;h-vexsj.firstarc=p; p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=j;p-nextarc=h-vexsn.firstarc;h-vexsn.firstarc=p; /无向图*/void DFS(Graph G,char ch) ArcNode *p;int i;i=Loc(G,ch);printf(%c ,ch);visitedi=1;p=G.vexsi.firstarc;while(p!=NULL) if(!visitedp-adjvex)DFS(G,p-adjvex+a);p=p-nextarc; void BFS(Graph G) int i,j;LinkQueue Q;ArcNode *p;for(i=0;iG.vexnum;i+) visitedi=0;InitQueue(Q);for(i=0;iadjvex) visitedp-adjvex=1;printf(%c ,G.vexsp-adjvex.data);EnQueue(Q,p-adjvex);p=p-nextarc; void DispGraphStruct(Graph G) int i,j;char ch;ArcNode *p,*h;for(i=0;i,ch,ch); if (h) p=h;while (p) j=p-adjvex;printf( %c -,G.vexsj.data);p=p-nextarc; printf( NULL);int Loc(Graph G,char ch) int i; for(i=1;inext=NULL;return 1; /InitQueueint EnQueue(LinkQueue &Q,QElemType e) QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if (!p) return (-1);p-data=e; p-next=NULL;Q.rear-next=p; Q.rear=p;return 1; int DeQueue(LinkQueue &Q,QElemType &e) QueuePtr p;if (QueueEmpty(Q) return -1;p=Q.front-next; e=p-data;Q.front-nex