《实验一实验报告》由会员分享，可在线阅读，更多相关《实验一实验报告（32页珍藏版）》请在金锄头文库上搜索。
1、实验一数据结构基本算法演示程序实习报告班级：信1301-2姓名：杨涛学号：20133019一任务说明小组成员：杨涛 刘伟 张晓菲 朱建颖（组长）杨涛任务包括实验四，八，十二，十六张晓菲任务包括实验一，五，九，十三朱建颖任务包括实验二，六，十，十四刘伟任务包括实验三，七，十一，十五1. 我的任务实验四，实验八，实验十二，实验十六，三天时间完 成2. 实验四Prim算法，输入：无向图（顶点序列，边序列），功 能要求：输出最小生成树的各组成边及最小生成树的权值。实验八 关键路径算法，输入：有向图（顶点序列，有向边序列）， 起始顶点，功能要求：能判断是否为AOE网；输出各关键活动 或输出关键路径（包括
2、关键路径的长度）实验十二 快速排序，输入：待排序数据序列，功能要求：输出 每步的枢轴选择和排序情况；希望能进行排序的选择（从大到小 或从小到大）实验十六四则表达式运算，输入：中缀表达式 功能要求：输 出后缀表达式和计算结果。二概要设计1.抽象数据类型：实验四：建立图的数据结构类型如下：typedef structint vexsMAX;int arcsMAXMAX;int vexnum;int arcnum;MGraph;顶点信息集合各边的权值顶点数/边数图类型建立辅助数组结构类型如下:struct closedint adjvex;依附于最小权值边在顶点集合U中的顶点int lowcost;
3、存储最小边的权值;closed closedgeMAX;2.主程序流程及各程序模块的层次关系：把1赋给j对于上述流程图可简单解释如下，首先通过对其它顶点依次判断，找出相连的顶 点，然后得到顶点序号，再通过for循环，进行循环判断，找出边权值最小的， 并赋值进入closedge中。重新调整各顶点中的顶点域和权值域的流程：A普利姆算法的总流程:开始图3-7.普利姆算法的总流程图开始五详细设计和编码图的建立：MGraph CreateMarph(MGraph & G)int vl,v2,weight,i,j,k;printf请输入无向图的顶点数和边数：);scanf(%d%d,&Gvexnu m,&
4、Garcnum);for(i=0;ivG.vexnum;i+)初始化邻接矩阵for(j=0;jvGvexnum;j+)G.arcsij=0;for(i=0;ivG.vexnum;i+)printf(”第小个顶点的序号：”,i+1);scanf(%d,&Gvexsi);printf(n请你确定各条弧的信息n);for(k=0;kvG.arcnum;k+)printf请输入第小弧的两个起始顶点和其权值为：”,k+1);输入一条边及依附的 顶点及权值for(; ;)scanf(%d%d%d,&v1,&v2,&weight);if(v1 0&v1v=Gvexnu m)&(v20&v2v=Gvexnum
5、)break;elseprintf(输入有误，不存在该顶点，请重新输入A_An);i=LocateVex(Gvexs,v1);找到两个结点在邻接矩阵中的位置j=LocateVex(Gvexs,v2);G.arcsij=weight;边的权值G.arcsji=G.arcsij;置(v1,v2 )成(v2,v1)printf(”n);return G;本子函数是用来建立图，其中用到了邻接矩阵用以存储各边的权值以及判断是否连通， 其中所调用的LocateVex()是用来指出该顶点在邻接矩阵中所在的位置，其子函数定义如下: int LocateVex(int vexs,int v) 确定结点是否存在i
6、nt t;for(int i=O;ivMAX;i+)if(vexsi=v)t=i;return t;使用Prim算法实现找出图中的最小生成树void MiniTree_PRIM(MGraph G,int u)int k=u;int i,j； for(i=0;ivG.vexnum;i+)初始化 closedge 数组，v=uif(i!=k)两个顶点不重合closedgei.adjvex=u+l; /首先将u视为第一条边的第一个依附顶点 if(!G.arcski)两点之间不连通closedgei.lowcost=-1;elseclosedgei.lowcost=Garcski; 调整 closed
7、ge 数组的最小代价 lowcost 为边上 的权值closedgek.lowcost=0;for(i=0;ivG.vexnum-1;i+) 取其余 G.vexnum-1 个顶点，循环从此处开始，i无任何意义for(j=O;jvGvexnum;j+) if(closedgej.lowcost0)求出 T 的下一个结点，第 K 结占八、k=j;break;for(j=O;jvGvexnum;j+)if(closedgej.lowcost0) if(closedgej.lowcost%d(%d )n,closedgek.adjvex,Gvexsk,closedgek.lowcost);closed
8、gek.lowcost=0;将此第k个顶点并入U集中for(j=O;jvGvexnum;j+)/在顶点 k 并入 U 之后，更新 closedgei，新顶点并入U后重新选择最小边if(G.arcskj0)if(closedgej.lowcost=-1) 如果先前时此两个顶点之间是不连通的 closedgej.lowcost=Garcskj; 新的权值域改成新加入顶点与该顶点 的权值closedgej.adjvex=Gvexsk;else如果此前两顶点本已连通if(G.arcskjvclosedgej.lowcost) 调整 closedge 数组中各边的最小权值closedgej.adjvex
9、=Gvexsk;依附于最小权值边在U中的顶点closedgej.lowcost=Garcskj; 边的权值赋给 closedge 数组的最小权 值域其中要说明的是其中使用了一个辅助数组，其定义如下：struct closedint adjvex;依附于最小权值边在顶点集合U中的顶点int lowcost;存储最小边的权值；此数组对PRIM中产生的顶点和边的权值进行临时存储的数组，因此结构体中设计两个变量， 顶点名adjvex，边的权值lowcost。定义次数组名为closed closedgeMAX在用PRIM算法计算图的最小生成树过程中，这里是整个算法的核心之所在。先要指定点 u最为最小生成
10、树的起点，并以次来构成最小生成树，子函数中用k来作为u的载体，同时它 也是u在图中的位置，后对辅助数组closedge进行初始化，首先将u视为第一条边的第一个 依附顶点，从零开始，所以u+1。如果两点间不连通则给边的权值lowcost赋值T；否则将选 择的边的权值adj赋给loecost,即将起存储在辅助数组中。而后开始寻找下一个结点，进行 边的权值的比较，选择出最小权值的边。将该边的顶点和权值存储入辅助数组中，然后重新 选择最小边，如此重复直至结束。将在次过程中选择的边的顶点和权值全部存储进辅助数组 中。而后开始调整辅助数组中各个边的最小权值，在辅助数组中生成最小生成树。最后将存 储在辅助数
11、组中的最小生成树输出。其中，使用多个FOR的套嵌来实现最小权值边的选择。 数组在这过程中始终作为临时存储空间，将筛选出的边的信息存储着，最后将其输出来。可建立由五点构建的图如下：0615gg605g3g1505645g50g2g36g06gg4260邻接矩阵最后以顶点1开始所生成的最小生成树如下: 对于上图测试结果如下所示:树=12 3 4 5 6萨稱轉强成6 1071牛力 角i亠求娴=点=顶 1S号号号号号号V 3J- Qu Mtf Mtf .3J- 斂点占苦苦小点占小 tr顶顶顶顶顶顶 (12 3 4 5 612 613 114 52 3 52 5 33 4 5-斗.-斗/斗/斗/斗/斗w
12、z斗.-直 息叹叹叹叹叹叹叹叹爵 hH- nnnnnnnnn *TT ，日-!*一!-!*一!-!*一!-!*一!-!*一JT.-!*一!-!*一!-!*一!-!*T 弧占小点占冒苦苦小点占苦缺 条顶顶顶顶顶顶顶顶顶師 TjA口A口A口厶口A口A口A口4 口4 口+:! 4.-LLP:.-p:.-p:.-p:.-p:!I= -rLrrLrn-rru-ru-rLTTrLrrLrru-? 0 1234567891 一第第第第第第第第第第 一A-A-A-A-A-A-A-A-A-A _-.- 刖 d 刖d 刖 d 刖 d 刖 d 刖 d 刖二 刖 d 刖 d 刖 -4-.牛4-.牛一 青青青主月青青青主月青青 - .1 -Lr .1 1K .1 1K .1 -Lr .1 -Lr .1 lr .1 IK .1 IK .1 -Lr .1 -Lr 一 一是否输甥图的邻接矩曙1建立的邻接矩阵如下0 615006 050301505645 050020 360060 04260習薩成所有的最性成柚可如下顶点
