数据结构-图的遍历演示.doc

《数据结构-图的遍历演示.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、院系：数学与统计学学院专业：统计学年级：2008级课程名称：数据结构学号：姓名：指导教师：2010年12月8日年级2008级班号 学号专业统计学 姓名 实验名称图的遍历演示实验类型设计型综合型创新型√实验目的或要求要求：l1图采用领接表的存储结构l2深度优先搜索图l3广度优先搜索图实验原理（算法流程）#include#include#defineMAX_VERTEX_NUM20#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineTRUE1#defineOK1#defineF

2、ALSE0#defineERROR0#defineOVERFLOW-2typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}boolvisited[MAX_VERTEX_NUM];typedefstructArcNode{intadjvex;//该弧所指向的顶点在数组中的下标structArcNode*nextarc;int*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{intdata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VN

3、ode,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;intLocate

4、Vex(ALGraphG,intv){//返回数组下标值inti;for(i=0;i

5、n");for(i=0;i

6、空间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.t

7、op=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)//删除栈顶元素{//若栈不空，则删