实验要求：

1、每位同学需要完成四个必作实验，至少一个选作实验；

2、每位同学至少提交五份实验报告（报告格式见附件一）；

3、实验报告不准包括源代码，必须在一页纸内，可以手写可以打印。

实验题目：

必作实验一

必作实验二 

必作实验三 

必作实验四  

必作实验五  

选作实验一

检查一个算术表达式中的括号是否正确匹配。

实验内容及要求：设计算法BracketMatch(string s)，其功能是：检查存储在字符串中的算术表达式s所包含的括号“(” 与 “)”、“[”与 “]”、“{”与 “}”是否正确匹配。

1、编写程序实现函数BracketMatch，并输出检查结果。

2、测试程序时，s遍取各种有代表性的值。

3、为增强程序的可读性，对程序中较难理解的语句要有准确、清晰的注释。

选作实验二

设计并实现一个算法，求自由树的直径。

实验内容及要求：无环连通图G=(V, E)亦称为自由树T，其直径是树中所有顶点之间最短路径的最大值，设计一个算法求T的直径；编制程序实现该算法，制定测试方案，并调试通过。

1、创建自由树T .

2、设计并实现求T的直径的算法。

3、为增强程序的可读性，对程序中较难理解的语句要有准确、清晰的注释。

选作实验三

判别给定二叉树是否为完全二叉树。

[实验目的]

在掌握二叉树的链接存储及基本操作的基础上，设计解决问题的算法。

[实验内容及要求]

设计算法（或曰函数）CompleteTree(BinTreeNode<T> * t)，其功能是判别给定二叉树t是否为完全二叉树；编制程序实现该函数，制定测试方案，并调试通过。

1、实现链接存储的二叉树类。

2、实现函数CompleteTree .

3、为便于观察程序的运行结果，设计输出函数，该函数能在输出设备上以图形、表格或其它直观的形式展现程序的运行结果，并能存储程序的这些运行结果。

4、为程序制定测试方案。

5、为方便程序测试，程序代码中应包括合适的调试语句。

6、测试程序时，所有输入变量应遍取各种有代表性的值。

7、为增强程序的可读性，对程序中较难理解的语句要有准确、清晰的注释。

选作实验四

哈夫曼编码/译码器

[实验目的]

综合运用树、线性表、文件等数据结构知识，掌握、提高分析、设计、实现及测试程序的综合能力。

[实验内容及要求]

设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。

（1）    从文件中读入任意一篇英文短文（文件为ASCII编码扩展名为txt）；

（2）    统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；

（3）    根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；

（4）    图形化输出哈夫曼树、哈夫曼编码；

（5）    将文本文件利用哈夫曼树进行编码，生存储成压缩文件（编码文件后缀名.huf）

（6）    用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；

（7）    进行译码，将huf文件译码为ASCII编码为txt文件，与原txt文进行比较。

[测试数据]

文本文件自行选择，至少含3000个字符。

附件一

 

第二篇：《数据结构》实验大纲(软件学院)

《数据结构》实验课程教学大纲

一、       课程名称：《数据结构》实验

二、       课程性质：学科与专业必修课

三、       实验学时：12学时

四、       课程类型：非独立设课

五、       课程适用专业：计算机科学技术专业、软件工程专业

六、       教学目的：《数据结构》是计算机科学与技术专业及软件工程专业的一门重要的专业基础课，课程旨在使学生学会计算机加工的数据对象的特性，学会数据的组织方法，以便选择合适的数据的逻辑结构及存储结构，并进行相应的运算。实验是该课程实践教学的重要环节，目的是培养学生根据求解问题的性质选择合理的数据结构，提高分析、设计、编程以及控制求解算法的时间、空间复杂性的能力。

七、       实验教学项目表

八、实验报告要求：

实验报告内容应该主要包括如下内容：

（1）实验题目    （2）实验内容    （3）实验目的    （4）实验环境

（5）主要算法与数据结构    （6）实验结果    （7）实验总结

九、实验成绩评定：

（1）本实验总计10分，每个实验2分，每个实验需在规定时间内完成。

（2）缺勤1次扣1分。

（3）在学院组织的抽查中若被发现实验不是自己完成的，将取消本课程的考试资格。

十、教材及参考书：

教材：

 严蔚敏、李冬梅、吴伟民.《数据结构（C语言版）》[M]，北京：人民邮电出版社，2011

参考书：

1、 严蔚敏、吴伟民.《数据结构(C语言版)》[M]，北京：清华大学出版社，2007

2、  严蔚敏，《数据结构习题集与上机指导》[M]，北京：清华大学出版社，2007