软件学院数据结构上机实验题目2013

实验要求：每位同学需要完成四个必作实验，至少一个选作实验；每位同学至少提交五份实验报告（报告格式见附件一）；实验报告不准包括源代码，必须在一页纸内，可以手写可以打印。实验题目：必作实验一实验项目名称单链表类实现与算法实验目的设计、实现并应用单链表SLList类，掌握单链表的定义和性质，能够灵活运用单链表的各种运算实现针对单链表的相关操作。实验内容1、定义并实现单链表类；2、实现单链表类的如下运算，并实验验证算法正确性以及各项性能指标：1）创建单链表；2）插入操作；3）删除操作；4）存取操作；5）查找操作；6）其他相关扩展操作；3、设计输出函数，能在输出设备上以图形等直观的形式展现运行结果；4、实现课后习题2-2，2-8.实验原理链接存储的线性表-单链表必作实验二实验项目名称二叉树类实现与算法实验目的设计并实现二叉树类，掌握二叉树的性质以及各种操作，灵活运用二叉树类解决问题。实验内容1、构造并实现链接存储的二叉树类，实现二叉树的插入、删除、查找和遍历等基本操作；2、应用二叉树类解决相关问题，如哈夫曼压缩、表达式树求值等。实验原理链接存储的二叉树类必作实验三实验项目名称图类实现与算法实验目的设计并实现图类及各种操作，掌握图的性质，能够灵活运用图解决相关问题。实验内容1、用邻接矩阵和邻接表两种存储方式，实现图类及各操作，重点实现深度优先遍历、广度优先遍历、拓扑排序和关键路径等算法；2、利用图类解决相关实际问题；3、设计输出函数，能在输出设备上以图形等直观的形式展现运行结果。实验原理图类定义及邻接矩阵和邻接表存储方式必作实验四实验项目名称各种排序算法实现与性能测试实验目的掌握各种排序算法的原理和性质，实现各种排序算法并实验测试其性能。实验内容1、实现Shell排序、快速排序、堆排序、合并排序等算法；2、设计实验，验证上述排序算法的正确性和时空复杂性；3、通过数据测试分析和比较各种算法性能。实验原理排序算法必作实验五实验项目名称折半查找算法实现及二叉查找树类实现实验目的验证二叉查找树及其相关操作。实验内容1、实现折半查找算法；2、实现二叉查找树类及查找、插入和删除等算法；3、实验验证查找算法的正确性以及时空性能测试。实验原理二叉查找树选作实验一检查一个算术表达式中的括号是否正确匹配。实验内容及要求：设计算法BracketMatch(strings)，其功能是：检查存储在字符串中的算术表达式s所包含的括号“(”与“)”、“[”与“]”、“{”与“编写程序实现函数BracketMatch，并输出检查结果。测试程序时，s遍取各种有代表性的值。为增强程序的可读性，对程序中较难理解的语句要有准确、清晰的注释。选作实验二设计并实现一个算法，求自由树的直径。实验内容及要求：无环连通图G=(V,E)亦称为自由树T，其直径是树中所有顶点之间最短路径的最大值，设计一个算法求T的直径；编制程序实现该算法，制定测试方案，并调试通过。创建自由树T.设计并实现求T的直径的算法。为增强程序的可读性，对程序中较难理解的语句要有准确、清晰的注释。选作实验三判别给定二叉树是否为完全二叉树。[实验目的]在掌握二叉树的链接存储及基本操作的基础上，设计解决问题的算法。[实验内容及要求]设计算法（或曰函数）CompleteTree(BinTreeNode<T>*t)，其功能是判别给定二叉树t是否为完全二叉树；编制程序实现该函数，制定测试方案，并调试通过。实现链接存储的二叉树类。实现函数CompleteTree.为便于观察程序的运行结果，设计输出函数，该函数能在输出设备上以图形、表格或其它直观的形式展现程序的运行结果，并能存储程序的这些运行结果。为程序制定测试方案。为方便程序测试，程序代码中应包括合适的调试语句。测试程序时，所有输入变量应遍取各种有代表性的值。为增强程序的可读性，对程序中较难理解的语句要有准确、清晰的注释。选作实验四哈夫曼编码/译码器[实验目的]综合运用树、线性表、文件等数据结构知识，掌握、提高分析、设计、实现及测试程序的综合能力。[实验内容及要求]设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。从文件中读入任意一篇英文短文（文件为ASCII编码扩展名为txt）；统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；图形化输出哈夫曼树、哈夫曼编码；将文本文件利用哈夫曼树进行编码，生存储成压缩文件（编码文件后缀名.huf）用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；进行译码，将huf文件译码为ASCII编码为txt文件，与原txt文进行比较。[测试数据]文本文件自行选择，至少含3000个字符。

附件