数据结构课程设计中缀表达式算法最小生成树分析.doc

课程设计报告 课程名称： 数据结构课程设计 课程设计题目： 中缀表达式算法、最小生成树 姓 名： 系： 专 业： 年 级： 学 号： 指导教师： 职 称： 年 月 日 课程设计报告结果评定 评语： 评分项目 分值 得分 课程设计报告符合规范 10分 类图、用例图、系统框图合理 30分 主要技术线路正确 30分 设计报告条理清晰、重点突出 20分 有一定创新性、难易程度 10分 成绩： 指导教师签字： 任务下达日期： 评定日期： 目 录 1.设计目的 4 2.主要仪器设备 4 3.设计要求 4 4.设计方案 5 4.1设计一流程图 5 4.2设计二——prim算法流程图 6 4.3设计二——kruskal算法流程图 7 5.设计内容 8 5.1 设计主要算法思想 8 5.2程序主要算法函数说明 8 5.2.1 设计一 8 5.2.2 设计二 10 5.3程序运行结果 15 5.3.1 设计一 15 5.3.2 设计二 18 6.总结 23 参考文献 23 附录：程序源代码 24 设计目的 通过这次课程设计，加深对这一学期所学的算法与数据结构的掌握，使自己所学的知识得到运用。 设计一： 1、理解堆栈的特点和堆栈的存储结构； 2、掌握堆栈的基本操作的实现方法； 3、掌握后缀表达式在计算机中的应用； 4、掌握后缀表达式的生成算法和计算过程； 5、掌握用堆栈实现后缀表达式的生成算法； 设计二： 掌握网络的邻接表存贮结构。 掌握优先队列的基本运算实现。 掌握网络的邻接表的算法实现。 掌握网络的最小生成树Prim或Kruskal算法。 学习并掌握上述的算法的实现及运算过程。 2.主要仪器设备 硬件环境：PC机 软件环境：Visual C++ 6.0 3.设计要求 设计一：设计内容和要求 设计并实现堆栈，利用堆栈实现对后缀表达式的求值 设计二：对任意给定的网络（顶点数和边数自定），建立它的邻接矩阵并输出，然后利用Prim算法或Kruskal算法生成它的最小生成树，并输出结果。 4.设计方案 3.2算法的设计： 后缀表达式运算的思想为依次读入表达式中的每一个字符，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行，并将运算结果入对象栈，继续处理当前字符，直到遇到结束符。 根据运算规则，每个运算符栈内、栈外的级别如下： 算符 栈内级别 栈外级别 ^ 3 4 *、/、% 2 2 +、- 1 1 （ 0 4 ） -1 -1 后缀表达式的结果计算主要涉及的数据结构为栈结构，包括下面一些操作，如进栈、出栈、判断栈是否为空 、及栈是否为满、读栈顶元素等操作 4.2设计二——prim算法 、 是 是 否 4.3设计二——kruskal算法流程图 5.1 设计主要算法思想 设计一： 中缀表达式是最普通的一种书写表达式的方式，而后缀表达式不需要用括号来表示，计算机可简化对后缀表达式的计算过程，而该过程又是栈的一个典型应用。应用栈的知识，求出输入后缀表达式的值 设计二： 设计二：首先考虑网的邻接矩阵的建立，以及邻接表的建立。然后设计一个函数，将网的所有边的权值，以及边的结点信息，按照权值大小，使用插入排序将数据都放入队列中。最后，使用prim算法，和kruskal算法，分别用来生成最小生成树。 Prim算法的方法： 从网中任一顶点开始，先把该顶点包含在生成树中，此时生成树中只有一个顶点。 找出一个端点在生成树中另一端点在生成树外的所有边，并把权值最小的边连同它所关联的另一顶点添加到生成树中；当有两条及以上具有相同最小权值的边可供选择时，选择其中任意一条都可以。 反复执行②，直到所有定点都包含在生成树中时止。 Kruskal算法： 算法按权的大小顺序考察各边。算法每一步所考察到的边，初始化集合A为空集并建立|V|棵树，每棵树包含图的一个结点。根据其权值非递减次序对E的边进行排序。在for循环中首先检查对每条边(u,v)其端点u和v是否属于同一棵树。如果是，则把(u,v)加入森林就会形成回路，所以这时放弃边(u,v)。如果不是，则两结点分属不同的树，把边加入集合A中，同时对两棵树中的结点进行归并。 5.2程序主要算法函数说明 A)结构体 { struct Stack { int *stack; int top; int MaxSize; }; B)初始化栈 void InitStack(Stack S) { //初始化栈为空 S.MaxSize = 10