数据结构课程设计

《数据结构课程设计》由会员分享，可在线阅读，更多相关《数据结构课程设计（14页珍藏版）》请在金锄头文库上搜索。

1、黑龙江大学数据结构课程设计读书报告学 院计算机科学与技术学院年 级2010专 业计算机科学与技术学 号姓 名刘曈霖日 期2011年12月2日星期五成 绩黑龙江大学计算机科学技术学院黑龙江大学软件学院一、基本理论阐述1.算术表达式求解算法任何一个表达式都是有操作数（operand）运算符（operator）。和界限符组成的，我们称他们为单词。一般地，操作数既可以是常数也可以是被说明为变量或常量的表示符；运算符可以分为算数运算符，关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束等。我们根据算数四则运算的规则：（1） 先乘除，后加减；（2） 从左算到右；（3） 先括号内，后括号外；在每一

2、步运算中，任意的两个相继出现的运算符1和2之间的优先关系至多是下面三种关系之一。大于，小于，等于；这里我们不给出各个运算符的优先级关系。具体情况参考数据结构。我们直接给出算法：为实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用于寄存运算符；另外一个称作OPND，用于寄存操作数或运算结果。算法的基本思想是：(1) 首先置操作数栈为空栈，表达式其实符“#”为运算符栈的栈底元素；(2) 一次读入表达式中的每个字符，若使操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求解完毕2 最小生成树算法I. Prim算法：假设N=V，E是连通网，TE是

3、最小生成树变得集合。算法从U=u0（u0属于V），TE开始，重复执行下述操作：在所有u属于U，v属于V-U的边（u，v）属于E中找到一条代价最小的边（u0，v0）并入集合TE，同时v0并入U直至U=V为止。此时TE中必有n-1条边，则T=(V,TE)为N的最先生成树。图为Prim算法生成最小生成树的过程。 图1. prim算法构造最小生成树的过程我们可以看出Prim的算法核心策略是贪心。II.Kruskal算法：假设 WN=(V,E) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根

4、结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。 图2.Kruskal算法生成最小树的过程。由此可见Kruskal算法的核心策略也是贪心算法。二、当前应用现状 两种算法的应用都非常的广泛，表达式求解算法在制作计算器是经常会使用到。而最小生成树的应用则是更加的广泛。在我们的日常生活中经常可以看见。比如题中的铺设电

5、网问题等等。三、对XXXX部分的体会 学习一个算法，不紧紧是学习他是如何实现的， 更需要学习它的思想，感受算法的魅力。比如生成树中运用了非常多的思想，贪心，枚举，排序等等一系列基础思想。但是用这些思想我们就能解决一个大问题。这难道不是一件非常美妙的事情么。就像变魔术一样。只有你想不到的，没有你做不到的。四、课程设计过程中的应用与实践I表达式求解算法(1)问题描述及分析要求以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值。需要用两个堆栈来实现这个目的。一个称做OPTR，用于寄存运算符另外一个称作OPND，用于寄存操作数或运算结果。（2）功能模块及数据

6、结构描述首先： 用char型变量定义运算符栈optr。用double型变量定义数据栈opnd。分别有两个指针top1，top2；和各自的出栈，入栈函数；其次：分别有change(char a)函数，将运算符装换成数字，方便查找优先级；operate (double a,double b,char c)函数，对出栈的a和b做相应的运算；bool w（）函数，判断读入的字符是否是数字，返回值是bool型的；bool tony() 函数，用于判断表达式是否正确。然后：主要工作函数double work ()，其中主要做了如下操作：1. 如果扫描到了数字，则入数据栈。其中可以分辨出多位的数字和doub

7、le型数据。2. 扫描到运算符。则和栈顶做比较：(1) 如果栈顶优先级高，将数据栈退栈两个数据，字符栈退栈一个数据，然后做相应的运算。并将运算结果入栈。不接受下一个字符。(2) 如果栈定优先级低，就将运算符入栈。并接受下一个字符。(3) 如果优先级一样。就脱括号。并接受下一个字符。最后：返回栈顶既是我们要求的表达式的结果。 (3)主要算法流程描述首先置操作数栈为空栈，表达式其实符“=”为运算符栈的栈底元素；一次读入表达式中的每个字符，若使操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求解完毕 (4)使用说明 进入系统输入需要计算的表达式。以等

8、号结束。（如果表达式错误程序会自动报错。） 如下图，输入了错误的表达式。正确计算的表达式(以等号结束)：如输入4+（3+2）2+51+0=按回车键后，会自动输出正确的结果如图，结果为19 。本程序还可以运算含有小数的表达式。可精确到小数点后6位。如图。另外，我们还可以循环输入要计算的表达式。 (5)实验及总结 需要知道栈里面是怎么运作的。灵活运用栈。没看清表达式求解的算法。按自己想的写了很久一直不对。没能处理含有负数的表达式。不能记录上一次的运算结果，还需改进。II最小生成树(1)问题描述及分析已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间

9、的线路，赋于边上的权值表示相应的代价。对于n个点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，使总的耗费最小。显而易见，我们可以看出如要解决这个问题，即可转换成构造连通网的最小生成树的问题。（2）功能模块及数据结构描述定义了结构体变量edge，用于存下边的信息，其中包括起点，终点，边的权值。为Kruskal算法用。用map二维数组存下图的信息，为prim算法用。Find（）函数为并查集中的查找功能。其中使用了路径压缩等不同程度的优化算法，使得程序运行更加的迅速。InPut() 函数为输入函数。依次输入每个城市间的距离，然后在函数内部将其转换成

10、两种形式来存储图。一种为邻接矩阵形式，一种为记录边集的形式。分别方便Prim算法和Kruskal算法使用。kruskal( ) 函数为Kruskal算法的主要实现功能函数。其中用到了并查集，贪心等算法思想。prim (int s) 函数为Prim 算法的主要函数。其中使用到了枚举，贪心等算法思想。(3)主要算法流程描述Prim 算法：任意时刻的中间结果都是一棵树。从一个点开始，每次都花费最少的代价，用一条边把一个不在树里面的点加进来。Kruskal算法：任意时刻的中间结果是一个森林。初始是n个点的集合，首先按权的大小排序。每次选权最小且不产生圈的边加进来，合并成森林。为了方便检测环河加边，需要

11、用到并查集。每次家变的复杂度是O(a(n,m),所以总得复杂度为O(mlogm+n a (n,m)。-摘自算法艺术在Prim算法中，起初，遍历每一个点，记录目标点到该点的距离到lowcost数组中，目标点为任意点S。然后从中选出权值距离最小的点，将该点标记，且认定为新的目标点。然后按照以下方法，以该点为目标点更新其余点的信息。如果目标点到该点的距离小于原始记录的信息。则更新其信息。最后再选取lowcost数组中的未被标记的最小边。循环点的个数n - 1次后，即生成树边的个数。我们就能得到一颗最小生成树了。最小生成树的边的信息记录在lowcost数组中。点的信息记录在close数组中。在Krus

12、kal算法中。我们用edge类型的结构体记录下来了图中所有边的信息。我们首先按照权值的大小对其进行一次排序，让最小的边在前。然后我们对边进行遍历。每次选取的边，判断其两个端点是否已经在树的集合中，如果不在则将其加入树的集合中。如果在则遍历下一条边。直到选取了n-1条边。这样我们就得到了一颗最小生成树了。当判断两个点是否是在生成树的集合中的时候，我们用到了并查集来对其优化和简化。并查集通常有三个操作。初始化把每个点所在集合初始化为其自身。 通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。 查找查找元素所在的集合，即根节点。 合并将两个元素所在的集

13、合合并为一个集合。 通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。(4)使用说明 进 入 系 统输入城市的数量，我们以4为例。然后我们依次输入两个城市间的距离：选择prim算法。重新计算选择kruskal算法输出的结果有1-2 表示从1号城市到2号城市。(1)表示两个城市的距离为1.选择下一次计算。输入0个城市，程序结束。欢迎使用。(5)实验及总结Prim算法代码简单。但是思想比较难。Kruskal算法代码复杂。但是思想比较简单，容易理解。Prim算法适合边比较多的图。因为用二维数组来存图，对空间比较浪费。Kruskal算法比较适合边比较少的图。因为需要对所有的边按权值的大小排序。两个算法各有各的好处和缺点。要正确的使用和选择需要的算法。五、读书工程心得总结 每一个算法都有它的美妙之处。我们要细细挺会，仔细感悟其中的奥妙。参考文献1.秦明,李波. 计算机操作系统实验与实践:基于Windows与LinuxM. 中力出版社,2004,4:第13-15页,第36-54页2.刘汝佳，黄亮。算法艺术与信息学竞赛清华大学出版社。3. Donald E.KnuthIntroduction to Algorithms算法导论机械工业出版社出版。4.数据结构与算法教程(第二版、第三版)，李春葆著，清华大学出版社，2008年9月。