《数据结构实验讲义》由会员分享，可在线阅读，更多相关《数据结构实验讲义（20页珍藏版）》请在金锄头文库上搜索。
1、北京邮电大学信息与通信工程学院数据结构实 验 讲义实 验 说 明 实验分为基础实验、应用实验、扩展实验三类。 基础实验：主要验证教材中提到的基础类的实验，该实验评分标准满分为85分； 应用实验：主要目标是应用教材中教授的基础类解决实际的问题，该实验评分标准为满分95分； 扩展实验：该类实验逻辑结构较为复杂，代码实现量较大，可以解决实际的问题并具备扩展到数据结构课程设计的功能。该类实验可以评分标准为满分100分。 每个学生只需要做数据结构实验4次：（1） 线性表 应用实验任选1个（2） 栈和队列 应用和扩展实验任选1个（3） 树 应用实验1个（4） 排序 任选1个实验一 线性表1 实验目的通过选
2、择下面四个题目之一进行实现，掌握如下内容： 熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力2 实验内容2.1题目1 基础实验根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表 线性表的基本功能：1、 构造：使用头插法、尾插法两种方法2、 插入：要求建立的链表按照关键字从小到大有序3、 删除4、 查找5、 获取链表长度6、 销毁7、 其他：可自
3、行定义编写测试main()函数测试线性表的正确性。2.2题目2应用实验利用线性表实现一个通讯录管理，通信录的数据格式如下： struct DataTypeint ID; /编号char name10;/姓名 char ch;/性别char phone13;/电话char addr31;/地址; 要求： 实现通讯录的建立、增加、删除、修改、查询等功能 能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。 能够保存每次更新的数据（选作） 能够进行通讯录分类，比如班级类、好友类、黑名单等等（选作） 编写测试main()函数测试线性表的正确性2.3题目3应用实验利用线性表实现一个一元多项
4、式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + + anxn 提示： Polynomial的结点结构如下： struct term float coef; /系数 int expn; /指数 ; 可以使用链表实现，也可以使用顺序表实现。要求： 能够实现一元多项式的输入和输出 能够进行一元多项式相加 能够进行一元多项式相减 能够计算一元多项式在x处的值 能够计算一元多项式的导数（选作） 能够进行一元多项式相乘（选作） 编写测试main()函数测试线性表的正确性2.4题目4应用实验利用循环链表实现约瑟夫问题的求解。约瑟夫问题如下：已知n个人（n=1）围坐一圆桌
5、周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。3代码要求 1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能实验二 栈和队列1 实验目的通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能
6、力 学习使用队列解决实际问题的能力2 实验内容2.1题目1基础实验根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列的基本功能（四选一）。 要求：1、 实现一个共享栈2、 实现一个链栈3、 实现一个循环队列4、 实现一个链队列编写测试main()函数测试栈或队列的正确性。2.2题目2应用实验 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断
7、任意两个皇后是否在同一行、同一列和同一斜线上2.3题目3应用实验利用栈结构实现迷宫求解问题。迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。提示：1、可以使用递归或非递归两种方法实现 2、老鼠能够记住已经走过的路，不会反复走重复的路径 3、可以自己任意设置迷宫的大小和障碍 4、使用“穷举求解”的方法2.4题目4应用实验设计一个算术四则运算表达式求值的简单计算器。表达式求值是程序设计语言编译中最近本的问题，它要求把一个表达式翻
8、译成能够直接求值的序列。基本要求：1、 输入中缀表达式能够转化成后缀表达式，比如输入中缀表达式“(A+B)*C”，输出“AB+C*”2、操作数使用单字母变量A、B、C等表示，操作符仅为+、-、*、/、（和）；3、能够对变量A、B、C等赋值，得出正确的计算结果2.5题目5应用实验 利用队列结构实现车厢重排问题。车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1n的顺序进入出轨。缓冲轨按照先进先出方式，编写一
9、个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。提示：1、 一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排。2.6 题目6扩展实验设计用于动态内存管理的内存池类。该类提供Allocate、Free、ReAllocate等接口，用于用户程序动态申请、释放、重新申请内存。在分配内存空间时，可通过参数选择分配策略：最佳拟合策略、最差拟合策略或最先拟合策略。编写
10、测试程序对类中各个接口和各种分配策略进行测试，并实时显示内存池中的占用块和空闲块的变化情况。3代码要求 1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出实验三 多维数组1 实验目的通过选择下面两个题目之一进行实现，掌握如下内容： 掌握多维数组基本操作的实现方法 了解bmp图像的结构和算法 学习使用多维数组解决实际问题的能力2 实验内容2.1 题目1基础实验根据三元组的抽象数据类型的定义，使用三元组表实
11、现一个稀疏矩阵。 三元组的基本功能：1、三元组的建立2、三元组转置3、三元组相乘4、其他：自定义操作编写测试main()函数测试三元组的正确性测试数据：2.2题目2扩展实验实现一个识别BMP文件的图像类，能够进行以下图像处理。基本要求：1、能够将24位真彩色Bmp文件读入内存；2、能够将24位真彩色Bmp文件重新写入文件；3、能够将24位真彩色Bmp文件进行24位灰度处理；4、能够将24位灰度Bmp文件进行8位灰度处理；5、能够将8位灰度Bmp文件转化成黑白图像；6、能够将图像进行平滑处理；7、其他：自定义操作，比如翻转、亮度调节、对比度调节、24位真彩色转256色等。 提示： 1、参考教材数
12、据结构与STL第四章4.4小节。 2、灰度处理的转换公式 Grey=0.3*Red+0.59*Blue+0.11*Green 3、平滑处理采用邻域平均法进行，分成4邻域和8邻域平滑，基本原理就是将每一个像素点的值设置为其周围各点像素值得平均值。 4、亮度调节公式，a为亮度调节参数，0a1,越接近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、对比度调节公式（中间值一般为128） R=中间值+(R-中间值)*对比度 G=中间值+(G-中间值)*对比度 B=中间值+(B-中间值)*对
13、比度 注意：调整对比度的时候容易发生越界，需要进行边界处理 6、24位真彩色转256色，需要手动添加颜色表在BMP头结构中，可以使用位截断法、流行色算法、中位切分算法、八叉树算法等方法实现。 3代码要求 1、必须要有异常处理，比如读取文件非法时需要抛出异常；2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 实验四 树1 实验目的通过选择下面三个题目之一进行实现，掌握如下内容： 掌握二叉树基本操作的实现方法 了解哈夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力2 实验内容2.1 题目1基础实验根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 二
