数据结构_图_实验报告08.doc

《数据结构_图_实验报告08.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机科学与工程学院计算机科学与工程学院《算法与数据结构》实验报告(八)专业班级2015级计算机科学与技术1实验地点403机房学生学号1505120488指导教师蔡琼学生姓名杜成昊实验时间2017-05-27实验项目图的应用实验类别基础性（）设计性（√）综合性（）其它（）实验目的及要求（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法；（3）掌握AOV网和拓扑排序算法；（4）掌握AOE网和关键路径。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整

2、、体现收获70分说明：评阅教师：蔡琼日期：2017年6月3日7《算法与数据结构》实验报告计算机科学与工程学院实验内容实验内容：拓扑排序。任意给定一个有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。实验说明：拓扑排序算法伪代码如下：1.栈S初始化；累加器count初始化；2.扫描顶点表，将没有前驱（即入度为0）的顶点压栈；

3、3.当栈S非空时循环3.1vj=退出栈顶元素；输出vj；累加器加1；3.2将顶点vj的各个邻接点的入度减1；3.3将新的入度为0的顶点入栈；4.if(count#include#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMAX20typedefintVertexType;typedefstructArcNode//表结点{intadjvex;//弧所指向的顶点的位置structArc

4、Node*nextarc;}ArcNode;typedefstructVNode//头结点{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该弧的顶点指针}VNode,*AdjList;typedefstruct{AdjListvertices;intvexnum;7《算法与数据结构》实验报告计算机科学与工程学院}ALGraph;typedefstruct//栈的定义{int*base;int*top;intstacksize;}SqStack;voidinitialStack(SqStack*s){s-

5、>base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!s->base)exit(0);s->top=s->base;s->stacksize=STACK_INIT_SIZE;}voidPush(SqStack*s,inte){if(s->top-s->base>=s->stacksize){s->base=(int*)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(int));if(!s->base)exit(0);s->top=s->b

6、ase+s->stacksize;s->stacksize+=STACKINCREMENT;}*(s->top)++=e;}voidPop(SqStack*s,int*e){if(s->top==s->base)exit(0);*e=*--(s->top);}voidGetTop(SqStack*s,int*e){if(s->top==s->base)exit(0);*e=*(s->top-1);}intStackEmpty(SqStack*s){if(s->base==s->top)return(1);elsereturn(0);}voidCrea

7、tAjacentMatrix(int*array,intn)//创建邻接矩矩阵(n行n列){7《算法与数据结构》实验报告计算机科学与工程学院inta;inti,j,flag=0;printf("请输入一个%d行%d列的关于图的邻接矩阵:",n,n);for(i=0;i

8、f("%5d",*(array+i*n+j));printf("");}}voidCreatAdjLis