实验实验报告基本算法杨涛.doc

实验一数据结构基本算法演示程序实习报告班级:信1301-2姓名:杨涛学号:20133019任务说明小组成员:杨涛刘伟张晓菲朱建颖(组长)杨涛任务包括实验四,八,十二,十六张晓菲任务包括实验一,五,九,十三朱建颖任务包括实验二,六,十,十四刘伟任务包括实验三,七,十一,十五我的任务实验四,实验八,实验十二,实验十六,三天时间完成实验四Prim算法,输入:无向图(顶点序列,边序列),功能要求:输出最小生成树的各组成边及最小生成树的权值。个人收集整理勿做商业用途实验八关键路径算法,输入:有向图(顶点序列,有向边序列),起始顶点,功能要求:能判断是否为AOE网;输出各关键活动或输出关键路径(包括关键路径的长度)个人收集整理勿做商业用途实验十二快速排序,输入:待排序数据序列,功能要求:输出每步的枢轴选择和排序情况;希望能进行排序的选择(从大到小或从小到大)个人收集整理勿做商业用途实验十六四则表达式运算,输入:中缀表达式功能要求:输出后缀表达式和计算结果。:实验四:建立图的数据结构类型如下:typedefstruct{ intvexs[MAX];//顶点信息集合 intarcs[MAX][MAX];//各边的权值 intvexnum;//顶点数 um;//边数}MGraph;//图类型建立辅助数组结构类型如下:structclosed{ intadjvex;//依附于最小权值边在顶点集合U中的顶点intlowcost;//存储最小边的权值};closedclosedge[MAX];主程序流程及各程序模块的层次关系:开始把1赋给j 判断j是否等于输入的顶点数值 j不等于I把I的值赋给j的顶点域里;把邻接矩阵中处于[j][I]位置的值赋给j的权值域中。 j等于I把j+1赋给j判断j是否小于等于图的顶点数 小于等于 :求出最小代价的边的算法流程:把1赋给j把1赋给i把邻接矩阵中处于[1][i]位置的值赋给i的权值域中;把1赋给i的顶点域中把i+1赋给i判断i是否小于图的顶点数 小于 大于等于把0赋给1的顶点域中,把1赋给j此时j的权值域是否小于minj的顶点域是否等于0j的顶点域是否等于0把1赋给j把100赋给min,,把j赋给k 把j+1赋给j判断j是否小于等于图的顶点数是否用两个顶点的集合输出边。 将顶点k加入到U中,表示k顶点已拿走了,把0赋给k的权值域中,这是标志性的赋值。对于上述流程图可简单解释如下,首先通过对其它顶点依次判断,找出相连的顶点,然后得到顶点序号,再通过for循环,进行循环判断,找出边权值最小的,并赋值进入closedge[]中。个人收集整理勿做商业用途重新调整各顶点中的顶点域和权值域的流程:把1赋给m在邻接矩阵中[k][m]存的值是否小于顶点m权值域中的值,m不等于k 有一个不满足答案是肯定的把邻接矩阵[k][m]存的值给顶点m的权值域,把顶点k给m的顶点域 把m+1赋给mm是否小于等于图mg的顶点数 :将各顶点的顶点域、权值域赋值。求出最小代价的边。重新调整各顶点中的顶点域和权值域。输出边的顶点信息结束开始j小于图的顶点数个人收集整理勿做商业用途 是 否 图3-:开始定义g为邻接矩阵数据类型输入顶点数,边数。把顶点数和边数赋给邻接矩阵g把0赋给i输入第i个顶点的信息。循环输入所有顶点的信息循环输入边的起点和终点如果超出编号范围,则重新输入。循环输出各边的权值。调用邻接矩阵的初始化函数、创建函数、PRIM函数。:MGraphCreateMarph(MGraph&G){ intv1,v2,weight,i,j,k; printf("●●请输入无向图的顶点数和边数:"); scanf("%d%d",&,&); for(i=0;i<;i++){//初始化邻接矩阵 for(j=0;j<;j++){ [i][j]=0; }} for(i=0;i<;i++){ printf("第%d个顶点的序号:",i+1); scanf("%d",&[i]); } printf("\n---------------请你确定各条弧的信息--------------\n");个人收集整理勿做商业用途 for(k=0;k<;k++) {printf("●●请输入第%d弧的两个起始顶点和其权值为:",k+1);//输入一条边及依附的顶点及权