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

实验一 数据结构基本算法演示程序实习报告 班级：信1301-2 姓名：杨涛 学号一．任务说明 小组成员：杨涛 刘伟 张晓菲 朱建颖（组长） 杨涛任务包括实验四，八，十二，十六 张晓菲任务包括实验一，五，九，十三 朱建颖任务包括实验二，六，十，十四 刘伟任务包括实验三，七，十一，十五 1.我的任务实验四，实验八，实验十二，实验十六，三天时间完成 2.实验四 Prim算法，输入：无向图（顶点序列，边序列），功能要求：输出最小生成树的各组成边及最小生成树的权值。 实验八 关键路径算法，输入：有向图（顶点序列，有向边序列），起始顶点，功能要求：能判断是否为AOE网；输出各关键活动或输出关键路径（包括关键路径的长度） 实验十二 快速排序，输入：待排序数据序列，功能要求：输出每步的枢轴选择和排序情况；希望能进行排序的选择（从大到小或从小到大） 实验十六 四则表达式运算，输入：中缀表达式 功能要求：输出后缀表达式和计算结果。 二．概要设计 1.抽象数据类型: 实验四：建立图的数据结构类型如下： typedef struct{ int vexs[MAX]; //顶点信息集合 int arcs[MAX][MAX]; //各边的权值 int vexnum; //顶点数 int arcnum; //边数 }MGraph; //图类型 建立辅助数组结构类型如下： struct closed{ int adjvex; //依附于最小权值边在顶点集合U中的顶点 int lowcost; //存储最小边的权值 }; closed closedge[MAX]; 2.主程序流程及各程序模块的层次关系： j不等于I j等于I 小于等于 大于 .求出最小代价的边的算法流程:求出最小代价的边的算法流程: 小于 大于等于  有一个条件不满足 都是肯定的回答 是 否 对于上述流程图可简单解释如下，首先通过对其它顶点依次判断，找出相连的顶点，然后得到顶点序号，再通过for循环，进行循环判断，找出边权值最小的，并赋值进入closedge[]中。 重新调整各顶点中的顶点域和权值域的流程: 有一个不满足 答案是肯定的 是的 否 ? ? 普利姆算法的总流程: 是 否 图3-7. 普利姆算法的总流程图 ? 主函数的流程： 五．详细设计和编码 图的建立： MGraph CreateMarph(MGraph G){ int v1,v2,weight,i,j,k; printf(●●请输入无向图的顶点数和边数：); scanf(%d%d,G.vexnum,G.arcnum); for(i=0;iG.vexnum;i++){ //初始化邻接矩阵 for(j=0;jG.vexnum;j++){ G.arcs[i][j]=0; }} for(i=0;iG.vexnum;i++){ printf(第%d个顶点的序号：,i+1); scanf(%d,G.vexs[i]); } printf(\n---------------请你确定各条弧的信息--------------\n); for(k=0;kG.arcnum;k++) {printf(●●请输入第%d弧的两个起始顶点和其权值为：,k+1);//输入一条边及依附的顶点及权值 for(; ;){ scanf(%d%d%d,v1,v2,weight); if((v10v1=G.vexnum)(v20v2=G.vexnum)) break; else printf(输入有误，不存在该顶点，请重新输入^_^\n); } i=LocateVex(G.vexs,v1); //找到两个结点在邻接矩阵中的位置 j=LocateVex(G.vexs,v2); G.arcs[i][j]=weight; //边的权值 G.arcs[j][i]=G.arcs[i][j]; //置(v1,v2)成(v2,v1) } printf(-----------------------------------------------\n); return G; } 本子函数是