数据结构课程设计
一、课程设计的目的
1. 课程设计是一种全面的综合训练，是课堂教学的延续。 2. 对学生数据结构知识的全面综合训练，把书上学到的知识用于解决实际问题、
培养今后软件开发工作所需的动手实践能力，包括问题分析、总体结构设计，用户界面的设计、程序设计的基本技能和技巧，以及一整套软件工作规范的训练和团体协作精神的培养。
二、课程设计的要求
1. 认真上机编程，不得从事与课程设计无关的活动。
2. 程序运行正确，请指导老师检查提问，通过后提交课程设计报告。 3. 报告提交要求
课程设计结束应完成课程设计实习报告。课程设计报告规范参见附录。课程设计报告必须以书面形式和电子版两种形式提交（注意：两种方式都要完成）。书面报告装课程设计资料袋保存，电子版课程设计报告提交时打一个zip包，zip包文件名统一以以下格式命名：
[班级][学号].zip
例：计021班学号为03的学生zip文件名为：j02103.zip。zip包中含有：
⑴readme.txt文件，把你的程序运行环境、编译运行步骤、程序功能等等简单说明一下。
⑵附加了诚实代码保证和足够注释的源程序以及相关的项目和资源文件。
三、课程设计具体内容
注意：以下题目供上课老师布置题目时参考。
题目1．哈夫曼编/译码器
【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编/译码系统。试为这样的通信端编写一个哈夫曼编/译码系统。 【基本功能】
一个完整的系统应具有以下功能：
初始化：输入一串字符（正文），计算不同字符 (包括空格)的数目以及每种字符出现的频率
(以该种字符出现的次数作为其出现频率），根据权值建立哈夫曼树，输出每一种字符的哈夫曼编码。
编码：利用求出的哈夫曼编码，对该正文（字符串）进行编码，并输出。
译码：对于得到的一串编码，利用已求得的哈夫曼编码进行译码，将译出的正文输出。 输出哈夫曼树形态：以树的形式输出哈夫曼树。
【运行流程】
【测试数据】 1．初始化：
① 输入正文“there are three students” ② 统计字符出现次数并输出
字符 次数 a 1 d 1 e 6 h 2 n 1 r 3 s 2 t 4 u 1 空格 3 ③ 根据字符出现次数求出哈夫曼编码并输出（根据算法差异得到的编码可能不同，但应具有两个特征，一是编码长度应与表中相同，二是编码应该是前缀编码）
字符 次数 a d e h n r s t u 空格 0000 0001 01 1110 0010 100 1111 110 0011 101 ④ 以树的形式输出哈夫曼树 2．编码：
发送方利用得到的哈夫曼编码对正文进行编码，输出密文应为：
11011100110001101000010001101110111010001011011111110001100010100101101111 3．译码：
接收方利用哈夫曼编码对密文进行译码，输出译后的字符串应为： there are three students
题目2． 以邻接矩阵的方式确定有向网，完成： ⑴建立并显示出它的邻接链表；
⑵以非递归的方式进行深度优先遍历，显示遍历的结果，（并随时显示栈的入、出情况）； ⑶对该图进行拓扑排序，显示拓扑排序的结果，并随时显示入度域的变化情况； ⑷给出某一确定顶点到所有其它顶点的最短路径
题目3． 以邻接链表的方式确定一个无向网，完成： ⑴建立并显示出它的邻接矩阵；
⑵对该图进行广度优先遍历，显示遍历的结果，（并随时显示队列的入、出情况）； ⑶用普里姆算法构造其最小生成树，随时显示其构造的过程； ⑷用克鲁斯卡尔算法构造其最小生成树，随时显示其构造的过程；
题目4． 二叉排序树的建立、插入、删除和查找 给出一组关键值，建立相应的二叉排序树，完成：
⑴结点的删除操作。要求可以实现删除根结点、叶子结点以及其它任意结点的功能； ⑵插入一个新结点的操作；
⑶对给定的值在二叉排序树进行查找； ⑷随时显示操作的结果。
题目5. 几种排序算法的演示，要求给出从初始开始时的每一趟的变化情况，并对各种排序算法的排序性能作分析和比较： ⑴直接插入排序； ⑵折半插入排序； ⑶冒泡排序； ⑷简单选择排序； ⑸快速排序； ⑹堆排序； ⑺归并排序。
参考文献
1. 缪淮扣，顾训穰，沈俊.数据结构――C＋＋实现.科学出版社，2002年
2. Sartaj Sahni.Data Structures,Algorithms,and Applications in C++.北京：机械工业出
版社，2000年
3. 严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，1997年 4. 陈慧南.数据结构使用C＋＋语言描述.南京：东南大学出版社，2000年
附：课程设计实习报告的书写格式
题目：
班级： 姓名： 学号： 完成日期： 一、需求分析
1. 运行环境（软、硬件环境）； 2. 程序所实现的功能；
3. 程序的输入：包含输入的数据格式和说明； 4. 程序的输出：程序输出的形式；
5. 测试数据，如果程序输入的数据量比较大，需要给出测试数据； 6. 合作人及其分工（如果有的话） 二、设计说明
1. 算法设计的思想；
2. 主要的数据结构设计说明； 3. 程序的主要流程图；
4. 程序的主要模块，要求对主要流程图中出现的模块进行说明； 5. 程序的主要函数及其伪代码说明 (不需要完整的代码) ； 6. 合作人设计分工（如果有的话）。 三、上机结果及体会
1. 合作人编码分工（如果有的话）；
2. 实际完成的情况说明（完成的功能，支持的数据类型等）； 3. 程序的性能分析，包括时空分析；
4. 打印程序运行时的初值和运行结果，画出相应的图示； 5. 上机过程中出现的问题及其解决方案； 6. 程序中可以改进的地方说明；
7. 程序中可以扩充的功能及设计实现假想； 8. 收获及体会；
9. 打印一份源程序清单并附上注释。 四、参考文献
关于课程设计实习报告的附加说明：
1. 如果程序比较大，可以将设计说明分为概要设计和详细设计两部分。概要设计主要负责
程序的流程、模块、抽象数据类型设计；详细设计负责程序的数据类型定义和主要函数的说明。 2. 设计说明中，不需要写出代码或者模块的详细代码，只需要写出主要函数的伪代码说明。