数据结构实验课件及实验

------------------------------------------- --------------------最新资料推荐------------------------ ------------------------------

数据结构实验课件及实验

北京科技大学 计算机与通信工程学院 数据结构实验报告
专 专 业：
班 班 级：
学生姓名：
学 学 号：
指导教师：
实验地点：
实验时间：
年 月 日~ 月 日 实验成绩：
________________________________ 一、实验目的与实验要求
1 实验目的 （1）加深对常用数据结构和算法设计基本思路、思考方
法及其适用场合的理解 ，并能运用于解决实际问题； （2）能根据特
定问题需求，分析建立计算模型（包括逻辑结构和物理结 构）、设计
算法和程序，并在设计中综合考虑多种因素，对结果的有效性进行分
析； （3）训练分析问题、解决问题的能力以及自主学习与程序设计
实践能力； （4）形成将非数值型问题抽象为计算模型到算法设计、
程序实现、结果有效性分析的能力。
2 实验要求 （1）由于在有限的实验课内学时难以较好完成所有
实验内容，因此要求在实验课前自主 完成部分实验或实验的部分内
容； （2）对于每个实验都要针对问题进行分析，设计出有效的数据



1 9

结构、算法和程序，对实现结果的正确性进行测试验证，给出测试用
例和结 果，分析算法的时间复杂度、空间复杂度、有效性和不足，在
算法设计和实现过程中体现创新意识，并能 综合考虑时空权衡、用户
的友好性、程序的模块化和扩展性等；（如实验中有优化或改进的设
计 ，请将优化过程进行说明，并给出前后对比分析。
） （3）完成的每个实验需要在实验课内经 指导教师现场检查、
查看程序代码，回答指导教师提出的问题，以确认实验实际完成的质
量； （4）在实验报告中体现问题分析、算法思路、算法描述、程序
实现和验证、算法和结果的有效性分析。
（注：
此模板中的红色文字为解释性文字，提交时请将所有红色文字删
除。
） 二、实验设备（环境）及要求 实验室提供 Windows 7 系统下
的 Visual C++环境。
本实验目的是对数据结构知识掌握及应用能力的考察，对编程语
言和开发环境不做严格要求。
建议采用 C 语言，在支持 C 的编译环境下运行。
三、实验内容、步骤与结果分析 1 实验 1：
链表的应用 1.1 实验内容 输入数据（设为整型）建立单链表，
并求相邻 k 个节点 data 值之和为最大的第一节点。
要求：
（1）建立链表、求最大值功能采用独立函数实现； （2）可根< /p>

---------------------------------------- -----------------------最新资料推荐--------------------- ---------------------------------

据用户需求多次建表； （3）数据的输入可从键盘输入，也可从 txt
文件输入； （4）程序结束时要释放链表空间。
1.2 主要步骤 1.2.1 问题分析与算法思路 通过对问题进行分
析，得出求解问题的算法思路。
包括问题分析的过程、适合采用的数据结构、算法思路。
在算法设计中体现创新意识，能综合考虑时空权衡等。
1.2.2 算法描述 用伪代码给出算法描述。
1.2.3 程序实现 给出完整的程序源代码和注释，说明在程序 实
现中对用户的友好性、程序的模块化和扩展性等是如何考虑的。
为了减少篇幅，源代码采用较小的字体打印，也可适当采用分栏
排版。
1.3 结果分析 1.3.1 测试 说明测试的思路，是如何验证在不同
输入下（包括边界情况）程序正确性的；给出测试用例和测试结果。
1.3.2 算法和结果的有效性分析 分析算法的时间复杂度、空间
复杂度、有效性、不足和改进意见。
如果同时采用了多种实现方法，进行对比说明、分析。
2 实验 2：
栈的应用 2.1 实验内容 算术表达式求值：
输入中缀形式的算术表达式，如：
5+(4-2)*3，将其转换成后缀表达式并输出：
542-3*+，然后对后缀表达式求值（本例结果为 11）并将结果输

3 9

出。
要求：
（1）中缀表达式转换后缀表达式和后缀表达式求值采用独立函
数实现； （2）操作数支持多位数和小数； （3）运算符仅考虑+、-、
*、、（、）、#（#可用作结束符）； （4）中缀表达式可从键盘输入也
可以从文件输入。
对输入的中缀表达式要进行合法性检查（表达式头尾以及运算符
左右可以包含若干空格）； （5）可根据用户需求，多次计算不同的
表达式； （6）自行定义栈类型以及需要的栈的基本操作。
2.2 主要步骤 2.2.1 问题分析与算法思路 通过对问题进
行分析，得出求解问题的算法思路。
包括问题分析的过程、需要采用的数据结构、算法思路。
在算法设计中体现创新意识，能综合考虑时空权衡等。
2.2.2 算法描述 用伪代码给出算法描述。
2.2.3 程序实现 给出完整的程序源代码和注释，说明在程序 实
现中对用户的友好性、程序的模块化和扩展性等是如何考虑的。
为了减少篇幅，源代码采用较小的字体打印，也可适当采用分栏
排版。
2.3 结果分析 2.3.1 测试 说明测试的思路，是如何验证在不同
输入下（包括边界情况）程序正确性的；给出测试用例和测试结果。
2.3.2 算法和结果的有效性分析 分析算法的时间复杂度、空间
复杂度、有效性、不足和改进意见。

----- -------------------------------------------------- --------最新资料推荐------------------------------------ ------------------

如果同时采用了多种实现方法，进行对比说明、分析。
3 实验 3：
队列的应用 3.1 实验内容 将从键盘输入的一系列字符存储到链
式队列中，当输入的字符为0时， 执行出队操作并将出队元素打印到
屏幕上；当输入的字符为@时，队列中剩余所有元素依次出队并打印< br>到屏幕上；当输入其他字符时，字符入队。
要求：
可根据用户需求多次重复该过程；自行补充所需的队列基本操作。
3.2 主要步骤 3.2.1 问题分析与算法思路 通过对问题进
行分析，得出求解问题的算法思路。
包括问题分析的过程、需要采用的数据结构、算法思路。
在算法设计中体现创新意识，能综合考虑时空权衡等。
3.2.2 算法描述 用伪代码给出算法描述。
3.2.3 程序实现 给出完整的程序源代码和注释，说明在程序 实
现中对用户的友好性、程序的模块化和扩展性等是如何考虑的。
为了减少篇幅，源代码采用较小的字体打印，也可适当采用分栏
排版。
3.3 结果分析 3.3.1 测试 说明测试的思路，是如何验证在不同
输入下（包括边界情况）程序正确性的；给出测试用例和测试结果。
3.3.2 算法和结果的有效性分析 分析算法的时间复杂度、空间
复杂度、有效性、不足和改进意见。

5 9

如果同时采用了多种实现方法，进行对比说明、分析。
4 实验 4：
二叉树的应用 4.1 实验内容 树表的查找：
输入一个英文句子，按照字典顺序构造一棵二叉排序树；对此二
叉排序树进行中序遍历， 并将遍历序列输出到屏幕上。
要求：
（1）英文句子可从键盘输入，也可从 txt 文件输入； （2）遍
历算法采用非递归遍历算法； （3）程序结束时需释放树空间。
4.2 主要步骤 4.2.1 问题分析与算法思路 通过对问题进
行分析，得出求解问题的算法思路。
包括问题分析的过程、需要采用的数据结构、算法思路。
在算法设计中体现创新意识，能综合考虑时空权衡等。
4.2.2 算法描述 用伪代码给出算法描述。
4.2.3 程序实现 给出完整的程序源代码和注释，说明在程序 实
现中对用户的友好性、程序的模块化和扩展性等是如何考虑的。
为了减少篇幅，源代码采用较小的字体打印，也可适当采用分栏
排版。
4.3 结果分析 4.3.1 测试 说明测试的思路，是如何验证在不同
输入下（包括边界情况）程序正确性的；给出测试用例和测试结果。
4.3.2 算法和结果的有效性分析 分析算法的时间复杂度、空间
复杂度、有效性、不足和改进意见。
如果同时采用了多种实现方法，进行对比说明、分析。

-------------- -------------------------------------------------最 新资料推荐--------------------------------------------- ---------

5 实验 5：
图的应用 5.1 实验内容 建立有向图的十字链表存储结构，利用
拓扑排序方法判断该图是否为有向无环图。
要求：
有向图的顶点信息和弧信息可以从键盘或 txt 文件输入，输入格
式自拟。
5.2 主要步骤 5.2.1 问题分析与算法思路 通过对问题进
行分析，得出求解问题的算法思路。
包括问题分析的过程、需要采用的数据结构、算法思路。
在算法设计中体现创新意识，能综合考虑时空权衡等。
5.2.2 算法描述 用伪代码给出算法描述。
5.2.3 程序实现 给出完整的程序源代码和注释，说明在程序 实
现中对用户的友好性、程序的模块化和扩展性等是如何考虑的。
为了减少篇幅，源代码采用较小的字体打印，也可适当采用分栏
排版。
5.3 结果分析 5.3.1 测试 说明测试的思路，是如何验证在不同
输入下（包括边界情况）程序正确性的；给出测试用例和测试结果。
5.3.2 算法和结果的有效性分析 分析算法的时间复杂度、空间
复杂度、有效性、不足和改进意见。
如果同时采用了多种实现方法，进行对比说明、分析。
6 实验 6：

7 9

综合应用 6.1 实验内容 统计若干个大型英文 txt 文件（如英文
小说）中所有单词出现的次数，并输出出现次数最多的前 10 个单词
及其出现次数。
假设单词字符定义为大小写字母、数字和下划线，其他字符均看
作单词分隔符。
要求：
（1）自行设计合适的数据结构及相关算法； （2）程序运行结
束时将 txt 文件名以及统计结果写入磁盘； （3）每次程序启动时
（除了首次运行）将上次的结果读入内存、显示； （4）能根据用户
选择实现重新初始化、查找某单词出现次数、追加统计、退出等功能。
6.2 主要步骤 6.2.1 问题分析与算法思路 通过对问题进
行分析，得出求解问题的算法思路。
包括问题分析的过程、适合采用的数据结构、算法思路。
在算法设计中体现创新意识，能综合考虑时空权衡等。
6.2.2 算法描述 用伪代码给出算法描述。
6.2.3 程序实现 给出完整的程序源代码和注释，说明在程序 实
现中对用户的友好性、程序的模块化和扩展性等是如何考虑的。
为了减少篇幅，源代码采用较小的字体打印，也可适当采用分栏
排版。
6.3 结果分析 6.3.1 测试 说明测试的思路，是如何验证在不同
输入下（包括边界情况）程序正确性的；给出测试用例和测试结果。
6.3.2 算法和结果的有效性分析 分析算法的时间复杂度、空间

-------------------------------------------------- -------------最新资料推荐------------------------------- -----------------------

复杂度、有效性、不足和改进意见。
如果同时采用了多种实现方法，进行对比说明、分析。
四、结论与讨论 对照实验内容，简要总结完成的主要工作；
对照实验目的，着重说明通过实验所取得的收获和能力的达成 情况；
存在的问题及可能的改进方向；其他需要说明的问题。
五、教师评审 教师评语 实验成绩（25 分）
签名：
日期：





9 9