北邮数据结构实验题目

2.3题目3

设计一个算术四则运算表达式求值的简单计算器。表达式求值是程序设计语言编译中最近本的问题，它要求把一个表达式翻译成能够直接求值的序列。

基本要求：

1、输入中缀表达式能够转化成后缀表达式，比如输入中缀表达式 “(A+B)*C”，输出“AB+C*”

2、操作数使用单字母变量A、B、C等表示，操作符仅为+、-、*、/、（和）； 3、能够对变量A、B、C等赋值，得出正确的计算结果

2.4题目4

利用队列结构实现车厢重排问题。车厢重排问题如下：

一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。

提示：

1、一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排。

2.5题目5

实现一个识别BMP文件的图像类，能够进行以下图像处理。 基本要求：

1、能够将24位真彩色Bmp文件读入内存； 2、能够将24位真彩色Bmp文件重新写入文件； 3、能够将24位真彩色Bmp文件进行24位灰度处理； 4、能够将24位灰度Bmp文件进行8位灰度处理； 5、能够将8位灰度Bmp文件转化成黑白图像； 6、能够将图像进行平滑处理；

7、其他：自定义操作，比如翻转、亮度调节、对比度调节、24位真彩色转256色

等。

提示：

1、参考教材《数据结构与STL》第四章4.4小节。 2、灰度处理的转换公式

Grey=0.3*Red+0.59*Blue+0.11*Green

3、平滑处理采用邻域平均法进行，分成4邻域和8邻域平滑，基本原理就是将每一个像素点的值设置为其周围各点像素值得平均值。

4、亮度调节公式，a为亮度调节参数，0 < a < 1, 越接近 0，变化越大 R = pow (R, a) * pow (255, 1 - a) G = pow (G, a) * pow (255, 1 - a) B = pow (B, a) * pow (255, 1 - a)

5、对比度调节公式，a为对比度调节参数，-1< a < 1，（中间值一般为128） R=中间值+(R-中间值)*(1+a) G=中间值+(G-中间值)*(1+a) B=中间值+(B-中间值)*(1+a)

注意：调整对比度的时候容易发生越界，需要进行边界处理

6、24位真彩色转256色，需要手动添加颜色表在BMP头结构中，可以使用位截断法、流行色算法、中位切分算法、八叉树算法等方法实现。

3代码要求

1、必须要有异常处理，比如删除空链表时需要抛出异常；

2、保持良好的编程的风格：

? 代码段与段之间要有空行和缩近 ? 标识符名称应该与其代表的意义一致 ? 函数名之前应该添加注释说明该函数的功能 ? 关键代码应说明其功能

3、递归程序注意调用的过程，防止栈溢出

实验三 树

1 实验目的

通过选择下面两个题目之一进行实现，掌握如下内容： ? 掌握二叉树基本操作的实现方法 ? 了解赫夫曼树的思想和相关概念 ? 学习使用二叉树解决实际问题的能力

2 实验内容

2.1 题目1——基础实验

根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 完成二叉树的基本功能： 1、二叉树的建立 2、二叉树的复制 3、前序遍历二叉树 4、中序遍历二叉树 5、后序遍历二叉树 6、按层序遍历二叉树 7、求二叉树的结点数 8、二叉树的销毁

编写测试main()函数测试线性表的正确性。

思考问题（选作）：

1、若数据量非常大，如何使得构造二叉树时栈不溢出？使用非递归方式编写新的二叉树的构造函数，建立二叉树。提示：可以使用STL中的stack来辅助实现。

2、若二叉树的每一个结点具有数值，如何搜索二叉树，找到指定值的叶子结点？

3、若已知叶子结点的指针，如何输出从根到该叶子的路径？