数据结构实习题七.docVIP

数 据 结 构 实 习 题 七 班级：计算机科学与技术01班 姓名：王 浩 学号：41009010111 一、分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。 邻接表表示： #includemalloc.h #define max 20 #includestdio.h typedef struct arcnode { int num; struct arcnode *nextarc; }arcnode; typedef struct vexnode { char data; arcnode *firstarc; }vexnode; typedef struct { vexnode vertex[max]; int vexnum; int arcnum; }ALG; typedef struct { int data[max+10]; int front; int rear; }queue; int visited[max]; queue q; int locate(ALG *g,char v) { int i; for(i=0;ig-vexnum;i++) if(g-vertex[i].data==v) break; return(i); } void creatgraph(ALG *g) { int i; char c; arcnode *rear,*temp; printf(输入图的顶点数和边数\n); scanf(%d%d,g-vexnum,g-arcnum); getchar(); printf(输入所有顶点\n); for(i=0;ig-vexnum;i++) { scanf(%c,(g-vertex[i].data)); g-vertex[i].firstarc=NULL; } getchar(); for(i=0;ig-vexnum;i++) { printf(输入所有和%c相连的顶点，以*结束\n,g-vertex[i].data); if((c=getchar())!=*) { rear=(arcnode *)malloc(sizeof(arcnode)); g-vertex[i].firstarc=rear; rear-num=locate(g,c); while((c=getchar())!=*) { temp=(arcnode *)malloc(sizeof(arcnode)); temp-num=locate(g,c); rear-nextarc=temp; rear=temp; } } rear-nextarc=NULL; getchar(); } } void depthfirstsearch(ALG *g,int vi) { arcnode *rear; putchar(g-vertex[vi].data); visited[vi]=1; rear=g-vertex[vi].firstarc; while((rear!=NULL)(!visited[rear-num])) { depthfirstsearch(g,rear-num); rear=rear-nextarc; } } void travel(ALG *g) { int v; for(v=0;vg-vexnum;v++) if(!visited[v]) depthfirstsearch(g,v); } void enterqueue(int v) { q.data[q.rear]=v; q.rear++; } int deletequeue() { int t; t=q.data[q.front]; q.front++; return(t); } int empty