数据结构实验课件及实验

《数据结构实验课件及实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、课内学时难以较好完成所有实验内容，因此要求在实验课前口主完成部分实验或实验的部分内容；（2）对于每个实验都要针对问题进行分析，设计出有效的数据结构、算法和程序，对实现结果的正确性进行测试验证，给出测试用例和结果，分析算法的时间复杂度、空间复杂度、有效性和不足，在算法设计和实现过程中体现创新意识，并能综合考虑时空权衡、用户的友好性、程序的模块化和扩展性等；（如实验中有优化或改进的设讣，请将优化过程进行说明，并给出前后对比分析。）（3）完成的每个实验需要在实验课内经指导教师现场检查、查看程序代码，冋答指导教师提出的问题，以确认实验实际完成的质量；（4）在实验报告中体现问题

3、分析、算法思路、算法描述、程序实现和验证、算法和结果的有效性分析。（注：此模板中的红色文字为解释性文字，提交时请将所有红色文字删除。）二、实验设备（环境〉及要求实验室提供Windows7系统下的VisualC++坏境。本实验li的是对数据结构知识掌握及应用能力的考察，对编程语言和开发环境不做严格要求。建议釆用C语言，在支持C的编译坏境下运行。三、实验内容、步骤与结果分析1实验1:链表的应用1.1实验内容输入数据（设为整型）建立单链表，并求相邻k个节点data值之和为最大的第一节点。要求：（1）建立链表、求最大值功能采用独立函数实现；（2）可根据用户需求多次建表；（3）

4、数据的输入可从键盘输入，也可从txt文件输入；（4）程序结束时耍释放链表空间。1.2主要步骤1.2.1问题分析与算法思路通过对问题进行分析，得出求解问题的算法思路。包插问题分析的过程、适合采用的数据结构、算法思路。在算法设计屮体现创新意识，能综合考虑时空权衡等。1.2.2算法描述用伪代码给出算法描述。1.2.3程序实现给出完整的程序源代码和注释，说明在程序实现中对用八的友好性、程序的模块化和扩展性等是如何考虑的。为了减少篇幅，源代码采用较小的字体打印，也可适当采用分栏排版。1.3结果分析1.3.1测试说明测试的思路，是如何验证在不同输入下（包括边界情况）程序正确性的；

5、给出测试用例和测试结果。1.3.2算法和结果的有效性分析分析算法的时I'可复杂度、空间复杂度、有效性、不足和改进意见。如果同时采用了多种实现方法，进行对比说明、分析。2实验2：栈的应用2.1实验内容算术表达式求值：输入中缀形式的算术表达式，如：5+（4・2严3,将其转换成后缀表达式并输出：542-3*+,然后对后缀表达式求值（本例结果为11）并将结果输出。要求：（1）“中缀表达式转换后缀表达式”和“后缀表达式求值”采用独立函数实现；（2）操作数支持多位数和小数；（3）运算符仅考虑+、・、*、/、（、）、#（#可用作结束符）；（4）中缀表达式可从键盘输入也可以从文件输入

6、。对输入的川缀表达式要进行合法性检查（表达式头尾以及运算符左右可以包含若干空格）；（5）可根据用户需求，多次汁算不同的表达式；（6）自行定义栈类型以及需要的栈的基本操作。2.2主要步骤2.2.1问题分析与算法思路通过对问题进行分析，得出求解问题的算法思路。包括问题分析的过程、需耍采用的数据结构、算法思路。在算法设计中体现创新意识，能综合考虑时空权衡等。2.2.2算法描述用伪代码给出算法描述。2.2.3程序实现给出完整的程序源代码和注释，说明在程序实现中对用八的友好性、程序的模块化和扩展性等是如何考虑的。为了减少篇幅，源代码采用较小的字体打印，也可适当采用分栏排版。2.

7、3结果分析2.3.1测试说明测试的思路，是如何验证在不同输入下（包括边界情况）程序正确性的；给出测试用例和测试结果。2.3.2算法和结果的有效性分析分析算法的时间复杂度、空间复杂度、有效性、不足和改进意见。如果同时采用了多种实现方法，进行对比说明、分析。3实验3：队列的应用3.1实验内容将从键盘输入的一系列字符存储到链式队列中，当输入的字符为，（r时，执行出队操作并将出队元素打印到屏幕上；当输入的字符为'@'时，队列中剩余所有元素依次出队并打印到屏幕上；当输入其他字符时，字符入队。要求：可根据用户需求多次重复该过程；自行补充所需的队列基本操作。3.2