数据结构实习

学院： 信息工程学院 专业： 信息工程 班级： 116102-22 学号： 20101003525 姓名： 冉传鄂 指导老师： 吴亮 陈占龙

问题一：大数阶乘

1.需求规格说明 【问题描述】

大数运算——计算 n 的阶乘（n>=20 ）。 【基本要求】

（1）数据的表示和存储；

（1.1） 累积运算的中间结果和最终的计算结果的数据类型要求是整型——这是问题本身的要求；

（1.2） 试设计合适的存储结构，要求每个元素或结点最多存储数据的 3 位数值。 （2 ）数据的操作及其实现：

基于设计的存储结构实现乘法操作，要求从键盘上输入 n 值；在屏幕上显示最终计算结果。

2 ．总体分析与设计 （1）设计思想：

一般来说，任何大于0的正整数n的阶乘等于n与（n-1）的阶乘的积，即n!=n（n-1）!。用（n-1）!的值来表示n!的值其表达式就是一种递归调用，因为一个阶乘的值是以另一个阶乘的值为基础的。 此程序是采用递归调用求正数n的阶乘的程序。然而需要解决的问题是，当n很大的时候得出的结果有很多位，以至于超出数据类型的范围，所以可以采用一个数组元素或者一个链表的节点类来存储结果的一位，这样虽然会浪费一些内存空间，但至少不会有错误出现。

（1.1）存储结构：

对于本实验中描述的问题，我采用的是线性表中的链式存储结构，用链表类中的每一个节点来存储大数阶乘中算出的结果的每一位元素。 （1.2)主要的算法思想： 1. 乘法与进位处理要分开;

2. 位数不够时要通过Insert增加链表节点，并将多出来的一位放到新的节点中; 3. 链表中的头节点存的是最低位的数,因此输出打印时要通过递归来恢复正常顺序.

（2 ）设计表示：

GetNum（） 将获取键盘输入的n值 传n 计算大数阶乘，主要的递归函数 Chain：：BigNumber（） 进位则插入新的节 （3 ）详细设计表示： （<五号宋体> ，具体内容：主要算法的框架。） Chain::Insert()

3 ．编码

①问题：当数据很大时，不能用于定义的数据结构来存储结果； 解决方法 ：用一个链表结构来存储数据，每一个节点就存储一位。 ②问题：在对进位进行处理的时候出现错误；

解决方法:一步步调试，发现每添加一个进位之后，要将进位清零。

4 ．程序及算法分析

5 ．小结 改进：

在输出1000的结成的时候输出的数；排列不均匀，要将算法改进使得输出美观。

体会：

在这一题的问题中，我注意到了原来很少注意到的数据类型超范围问题，原来写程序的时候，不会去专门考虑如果定义的数据超出了范围该怎么办，但是在这个问题中，我充分认识到了

这种情况的危害性，在以后的编程过程中会去注意这些看起来不起眼的东西。

问题二：表达式求值 1．需求规格说明 【问题描述】

对一个合法的中缀表达式求值。 假设表达式只包含+ 、-、×、÷ 四个双目运算符，且运算符本身不具有二义性。 【基本要求】

（1）正确解释表达式； (2)符合四则运算

2 ．总体分析与设计 设计思想：

（1）从左到右一次扫描中缀表达式的每一个字符，如果是数字字符则直接将它们写入后缀表达式中。

（2）如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：

1、当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表式,并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级； 2、当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。

（3）重复上述步骤直到遇到中缀表达式的结束符标记“#”，弹出栈中的所有元素并放入后缀表达式中，转换结束。

3 ．编码

①问题一：输入控制

控制输入的表达式是正确的形式，①表达式中不含字母；②表达式不含括号；③表达式中的运算符不可以连续两次出现； 解决方法：

用多个for循环来历次检查输入的字符的ASCall码来判断； ②问题二：运算符的优先级的比较； 解决方法：

用一个比较函数bijiao(char）来重定义他们的优先级（switch语句的实现）； ③问题三：

将字符型的数据转换成浮点型的数据； 解决方法：

刚开始的时候是想调用库函数来实现这一功能的，但是没有找到这样的库函数，于是自己写了一个转换函数getnuber(char)将各个字符型的数据转换成浮点型的数据。

4 ．程序及算法分析

5 ．小结

5.1本程序需要改进之处：

①改程序只能计算整型的不带括号的表达式，应该在这些地方做些改进。

②在本体中出了有关于栈的一些操作是放在类中，其他的一些很重要的操作都是直接在main函数里面直接写出来的，这样写出来的代码，调理不够清晰，而且不易改错，也不易读，以后应该改进。

5.2体会：

在本例中，主要体会到了栈的构建，栈的数据存储，出栈，入栈，等一系列的操作。在见栈的时候，我出了很多的过错，原来在编写程序的时候，我很少会考虑建立多个类来解决问题。但是，在本体中我充分体会到了类的好处，首先，类可以帮助我们建立一个很好的数据操作规则，也就是所谓的数据结构，比如说，栈，说白了，还是一个数组，但是，这个数组的相关操作是本封装起来和这个数组紧密的联系在一起的，用户看不到这个类的具体信息，但是，却可以很安全的使用这一个数据类型，这就是类的魅力所在。

6 ．附录 略

问题三：二叉树的建立和遍历 1．需求规格说明 【问题描述】

以二叉链表作为二叉树的存储结构建立二叉树，并对其进行操作，基本功能要求：

（1）建立一棵二叉树；

（2 ）对该二叉树进行前序、中序、后序、层序遍历； （3 ）统计该二叉树叶子结点的个数。 （4 ）求二叉树的深度。

（5 ）用非递归方法实现二叉树的中序遍历。 【基本要求】

从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并 采用递归算法对其进行遍历（先序、中序、后序）、统计叶节点个数、求二叉树的深度并用 非递归方法实现二叉树的中序遍历和层序遍历，将结果打印输出，。

2 ．总体分析与设计 （1）设计思想：

本题中的二叉树的存储结构，采用的是；链式的存储结构，在这个链表类的结构中节点类是如下形式：

LeftChild data RightChild

LeftChild指向左孩子的指针，RightChild指向右孩子的指针 （2）设计表示：

（<五号宋体> ，具体内容：子程序（过程或函数）的规格说明，通过调用关系

void ct(BinaryTreeNode *t); int Height(BinaryTreeNode*t)const; static void output(BinaryTreeNode*u);

Ct函数没被调用一次，就会有一个全局变量加一，又因为在遍历的时候只会遍历一次所有的节点，将这个函数传给前序，中序，后序，层序遍历函数中的任意一个，就可以得到链表中节点的个数。同理可以将Height和output函数的指针传给这些个遍历函数，来进行高度计算和节点的输出。

3 ．编码 ①问题一：

在类成员的各成员的访问权限控制上经常出错； 解决方法：

采用友元类的方法在一定程度上破坏类的封转性，从而达到访问原类的私有成员的目的。 ②问题二：

在写层序遍历函数的时候，会用到队列，在队列的出入方面总是会有内存操作出错； 解决方法：调试，在调试的过程中发现Delete函数错误，调试之后，将其解决。 4 ．程序及算法分析

5 ．小结 体会：

毫无疑问在数据结构这儿门课中，树这一章绝对是重点之中的重点，树这种数据结构也的的确确将各种基础的数据结构发挥到了一个高度；在本题中，我最有体会的就是在建树的过程中链表以及双指针域节点的使用，各种遍历手段，前序，中序，后序，层序，四种遍历方法的代码虽然简单，但是他们完成的工作却是重要的，这就是递归算法的优点，思路简单，代码易读，然而，工作量却是庞大的。 6 ．附录 略

问题四：图及图的遍历 1．需求规格说明 1、图的遍历 【问题描述】

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示无向图的 遍历操作。 【基本要求】

以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点 为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。

2 ．总体分析与设计 （1）设计思想：

以链表为存储结构，来建立一个图的数据结构类型，每一个节点都是存的一个图的顶点，用一个链表类型的数组来存所有的顶点，然后依次将各个顶点的所有邻接的顶点依次存入到相应的链表中。这样就把图建好了。

接下来就是图的遍历了，图的遍历有两种方式，分别为深度遍历和广度遍历。在详细设计版块将仔细的描述。 （2 ）设计表示：

（<五号宋体> ，具体内容：子程序（过程或函数）的规格说明，通过调用关系

LinkedBase LinkedDigraph LinkedGraph

（3 ）详细设计表示： 宽度遍历：

广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，类似于树的层次遍历。

为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。

为避免重复访问，需要一个辅助数组 reach [ ]，给被访问过的顶点加标记。

深度遍历：

（1）首先访问指定的起始顶点v0，再访问与v0邻接的任一未访问过的顶点w1；

（2）从w1出发，访问与w1邻接的任一未访问过的顶点w2；

（3）从w2出发，重复与（2）类似的访问，直到遇到一个所有邻接点都被访问过的顶点为止；

（4）依次回退到尚有邻接点未被访问过的顶点，重复与（3）类似的访问，直到图中所有和v0有路径相通的顶点都被访问过；

（5）如果图中存在未被访问过的顶点，从其中一个未被访问过的顶点出发，重复（1）-（5），直至图中所有顶点都被访问完。

3 ．编码 ①问题一：

图中的每一个顶点从原来的只有顶点序号的节点变成了不仅有顶点序号还有权重的节点，那么原来使用的链表中的简单节点是不能再用的。 解决办法：

定义了一个新节点类GraphNode类来解决这一问题。Vertice是代表了节点编号，weight代表了权重，link是指针域，指向下一个邻接顶点；

Vertice weight link

②问题二：

在进行搜索的时候，要对其进行标记跟踪，这种跟踪如何进行。 解决办法：

用一个数组来跟踪，定义一个const 的值，当到达节点i的是后，则reach[i]=Lebal；

4 ．程序及算法分析

5 ．小结

（<五号宋体> ，具体内容：经验与体会，或需要改进的地方）

体会：

①在这个题目中，我充分认识了累的继承的巨大能量，在继承的过程中，可以将相似的但却不完全相同的问题用一层一层的继承关系来实现。在这个体中，用三层的继承关系，将各种各样的图建立起来。

②在平常的编程中我很少涉及跟踪问题，但在这个题中，我了解到了跟踪的好处； ③队列这种数据结构的运用更为熟悉。

6 ．附录 略

问题五：校园导游图 1．需求规格说明 【问题描述】

设计一个校园导游程序，为来访的客人提供各种信息查询服务。 【基本要求】

（1）设计学校的校园平面图，所含景点不少于 10 个。图中顶点表示校内各景点，存放景

点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2 ）为来访客人提供图中任意景点相关信息查询；

（3 ）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的

简单路径。

2 ．总体分析与设计

（1）设计思想：

首先，这一题用到的思想是贪心算法；贪心算法，在对问题求解时，总是做出在当前看来是最好的选择。不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解 。 （2 ）详细设计表示： 单源点最短路径的寻找：

（1）初始化d[i]=a[s][i]（1≤i≤n)

对于邻接于s的所有顶点i，置p[i]=s，对于其余的顶点p[i]=0; 对于p[i] ≠0的所有顶点建立L表； （2）若L为空，终止，否则转至（3）

（3）从L中删除d值最小的顶点，标识为i；

（4）对于与i邻接的所有还未到达的顶点j，更新d[j]值为min{d[j],d[i]+a[i][j]}；若d[j]发生了变化且j还未在L中，则置p[j]=i，并将j加入L，转至（2）。

3 ．编码 ①问题一：

链表遍历器的使用时，总是会报出内存出错 解决方法：

将树上的begin函数和next函数的返回值变成location-data; ②问题二：原来的求的是单源点最短路径 解决办法：

要将原来的单源点最短路经函数改为求两个点之间的最短路径。

4 ．程序及算法分析

（<五号宋体> ，具体内容：使用说明、程序运行结果、讨论与分析、改进设想、经验

与体会、时空复杂度等。）

5 ．小结 体会：

贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的。贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。就比如说本题中的度量标准是选取与每一个顶点相连的所有定点中所有点中权最短的那个点。 6 ．附录 略