数据结构-图的遍历演示

院系：数学与统计学学院专业：统计学年级：2008级课程名称：数据结构学号：姓名：指导教师：2010年12月8日年级2008级班号学号专业统计学姓名实验名称图的遍历演示实验类型设计型综合型创新型√实验目的或要求要求：1图采用领接表的存储结构2深度优先搜索图3广度优先搜索图实验原理（算法流程）#includestdio.h#includestdlib.h#defineMAX_VERTEX_NUM20#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineTRUE1#defineOK1#defineFALSE0#defineERROR0#defineOVERFLOW-2typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}boolvisited[MAX_VERTEX_NUM];typedefstructArcNode{intadjvex;//该弧所指向的顶点在数组中的下标structArcNode*nextarc;int*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{intdata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;typedefstruct{int*base;int*top;intstacksize;}SqStack;typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;intLocateVex(ALGraphG,intv){//返回数组下标值inti;for(i=0;iMAX_VERTEX_NUM;++i)if(G.vertices[i].data==v)returni;return-1;}voidCreateDN(ALGraph&G){//采用邻接表存储表示,构造有向图G(G.kind=DN)inti,j,k;ArcNode*p;intv1,v2;G.kind=DN;printf(输入顶点数:);scanf(%d,&G.vexnum);printf(输入弧数:);scanf(%d,&G.arcnum);printf(输入顶点:\n);for(i=0;iG.vexnum;++i){//构造表头向量scanf(%d,&G.vertices[i].data);G.vertices[i].firstarc=NULL;//初始化指针}for(k=0;kG.arcnum;++k){printf(第%d条弧:,k+1);scanf(%d,&v1);scanf(%d,&v2);//输入一条弧的始点和终点i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中位置p=(ArcNode*)malloc(sizeof(ArcNode));//假定有足够空间p-adjvex=j;p-nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;scanf(%d,&p-info);}//for}intPush(SqStack&S,inte){//插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize){//栈满，追加存储空间S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}intInitStack(SqStack&S)//栈的初始化{S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}intPop(SqStack&S,int&e)//删除栈顶元素{//若栈不空，则删除S的栈顶元素，用e返回其值if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}intGetTop(SqStackS,int&e)//取栈顶元素{//若栈不空，则用e返回S的栈顶元素if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}intStackEmpty(SqStackS)//栈空{if(S.top==S.base)returnTRUE;elsereturnFALSE;}intInitQueue(LinkQueue&Q)//队列初始化{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;}intEnQueue(LinkQueue&Q,inte)//插入{//插入元素e为Q的新的队尾元素QueuePtrp=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;}intDeQueue(LinkQueue&Q,int&e){若队列不空，则删除Q的队头元素，用e返回其值if(Q.front==Q.rear)returnERROR;QueuePtrp=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}intQueueEmpty(LinkQueueQ)//队列空{if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}intFirstAdjVex(ALGraphG,intu){if(!G.vertices[u].firstarc)return-1;returnLocateVex(G,G.vertices[u].firstarc-adjvex);}intNextAdjVex(ALGraphG,intu,intw){ArcNode*p=G.vertices[u].firstarc;while(p&&LocateVex(G,p-adjvex)!=w)p=p-nextarc;if(!p)returnFirstAdjVex(G,u);p=p-nextarc;if(!p)return-1;returnLocateVex(G,p-adjvex);}voidVisit(ALGraphG,intv){printf(%2d,G.vertices[v].data);}voidDFSTraverse(ALGraphG){//按深度优先非递归遍历图G,使用辅助栈S和访问标志数组visitedintv,w;SqStackS;for(v=0;vG.vexnum;v++)visited[v]=FALSE;InitStack(S);for(v=0;vG.vexnum;++v)if(!visited[v]){//v尚未被访问visited[v]=TRUE;Visit(G,v);Push(S,v);//v进栈while(!StackEmpty(S)){for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)){if(!visited[w]){Visit(G,w);visited[w]=TRUE;Push(S,w);GetTop(S,v);}//if}//forPop(S,v);GetTop(S,v);}//while}//ifprintf(\n);}voidBFSTraverse(ALGraphG){//按广度优先非递归遍历图G,使用辅助队列Q和访问标志数组visitedintv,u,w;LinkQueueQ;for(v=0;vG.vexnum;++v)visited[v]=FALSE;InitQueue(Q);for(v=0;vG.vexnum;++v)if(!visited[v]){//v尚未被访问visited[v]=TRUE;Visit(G,v);EnQueue(Q,v);//v入队列while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w))if(!visited[w]){//w为u的尚未访问的邻接顶点visited[w]=TRUE;Visit(G,w);EnQueue(Q,w);}//if}//while}//ifprintf(\n);}voidPrintDN(ALGraphG)//图的显示{inti;ArcNode*p;printf(顶点:\n);for(i=0;iG.vexnum;++i)printf(%2d,G.vertices[i].data);printf(\n弧:\n);for(i=0;iG.vexnum;++i){p=G.vertices[i].firstarc;if(p){while(p){printf(%d→%d(%d)\t,i,p-adjvex,p-info);p=p-nextarc;}printf(\n);}//if}//for}voidmain(){ALGraphG;printf(************题目：图的遍历***************\n\n);CreateDN(G);PrintDN(G);printf(深度优先遍历:);DFSTraverse(G);printf(\n广度优先遍历:);BFSTraverse(G);}组内分工（可选）08221673164543957（所要遍历的图）主程序实验结果分析及心得体会实验结果成绩评定教师签名：2010年月日