数据结构课程设计题目及要求(2021.doc

数据结构课程设计题目及要求(2021
一 课程设计题目
每位同学在本次课程设计期间须选择两道题目（1,2任选一题，3,4任选一题）并按照要求完成。
1 考试报名管理系统
1.1 题目简介
考试报名工作给各高校报名工作带来了新的挑战，给教务管理部门增加了很大的工作量，报名数据手工录入既费时又会不可避免地出现错误，同时也给不少学生以可乘之机。本项目是对考试报名管理的简单模拟，用菜单选择方式完成下列功能：输入考生信息；输出考生信息；查询考生信息；添加考生信息；修改考生信息；删除考生信息。
1.2 设计思路
本项目的实质是完成对考生信息的建立、查找、插入、修改、删除等功能，可以首先定义项目的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。
1.3 数据结构
本项目的数据是一组考生信息，每条考生信息由准考证号、姓名、性别、年龄、报考类别等信息组成，这组考生信息具有相同特性，属于同一数据对象，相邻数据元素之间存在序偶关系。由此可以看出，这些数据也具有线性表中数据元素的性质，所以该系统的数据可以采用线性表来存储。
我们知道，线性表的顺序存储结构的特点是逻辑关系相邻的两个元素在物理位置上也相邻，因此可以随机存储表中任一元素，它的存储位置可用一个简单、直观的公式来表示。然而，从另一个方面来看，这个特点也铸成了这种存储结构的弱点：在做插入或删除操作时，需要移动大量元素。为克服这一缺点，我们引入另一种存储形式――链式存储。链式存储是线性表的另一种表示方法，由于它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构的弱点，但同时也失去了顺序表可随机存取的特点。
链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。事实上，链表插入、删除运算的快捷是以空间代价来换取时间。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要
操作是插入、删除操作，则采用链表。
本项目对考生数据主要进行插入、删除、修改等操作，所以采用链式存储结构比较适合。用结构体类型定义每个考生信息，故该单链表中的每个结点的结构可描述为：
typedef struct examinee {
char examno[10]; char name[10]; char sex; float age;

//成绩
//准考证号 //姓名
char examtype[5]; } ElemType;
2 家谱管理系统
2.1 题目简介
家谱（或称族谱）是一种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。家谱是中国特有的文化遗产，是中华民族的三大文献（国史，地志，族谱）之一，属珍贵的人文资料，对于历史学、民俗学、人口学、社会学和经济学的深入研究，均有其不可替代的独特功能。本项目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。
2.2 设计思路
本项目的实质是完成对家谱成员信息的建立、查找、插入、修改、删除等功能，可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。
2.3 数据结构
因为家族中的成员之间存在一个对多个的层次结构关系，所以不能用上面讲的线性表来表示。家谱从形状上看像一颗倒长的树，所以用树结构来表示家谱比较适合。树型结构是一类非常重要的非线性数据结构，直观看来，树是以分支关系定义的层次结构。
可以二叉链表作为树的存储结构，链表中的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，固该表示法又称二叉树表示法，或孩子兄弟表示法。孩子兄弟表示法是一种链式存储结构，它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其具
体的结点结构为：
firstChild data
其中，firstchild为指向该结点第一个孩子的指针，nextsibling为指向该结点下一个兄弟，elem是数据元素内容，举例如下：

其存储形式定义如下： typedef struct CSLinklist{ Elemtype data;
struct CSLinklist *firstchild,*nextsibling; } CSLinklist,*CSTree;
nextSibling 3 哈夫曼优化编码
3.1 题目简介
信息时代，人们对使用计算机获取信息、处理信息的依赖性越来越高。计算机系统面临的是数值、文字、语言、音乐、图形、动画、静图像、电视视频图像等多种媒体。数字化的视频和音频信号的数量之大是惊人的，对于电视画面的分辨率640×480的彩色图像，30帧/s，则一秒钟的数据量为：640×480×24×30＝22112M，所以播放时，需要221Mbps的通信回路。存储时，1张CD可存640M，则仅可以存放289s的数据。多媒体信息中，视频信息是一种比较特殊的媒体，数据量极大，信息丰富，并以与时间密切相关的流的形式存在。因此，视频数据的表达、组织、存储和传输都有很大难度。解决的基础在于对视频数据进行压缩。自1948年Oliver提出了PCM编码理论，编码技术日趋成熟，已经设计和应用了许多压缩算法和技术，如在H.261、JPEG和MPEG编码标准中的应用等。数据压缩目前的主要目标是较大的压缩比、较快的压缩解压速度以及尽可能好的图象还原质量，而对于压缩数据的处理如数据组织、检索、重构等还并没有较好的考虑，也没有一个比较完整的解决方案，因此在这方面仍有许多工作要做。哈夫曼编码就是一种优化编码方法。本项目要求从键盘接收任意一个字符串，以‘#’结尾。以字符串中某字符出现的次数，作为该字符的权值。利用得到的权值构建huffman树、并输出每个字符对应的huffman编码。另外，要求利用图形库函数，画出这颗哈夫曼树或动态演示该哈夫曼树的生成过程。
3.2 设计思路
假设一个文件中出现了8种符号S0，SQ，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3bit。假设编码成000，001，010，011，100，101，110，111。那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1
编码后变成
00000111100000111001001001110010100
0000001，共用了42bit。我们发现S0，S1，S2这3个符号出现的频率比较大，其它符号出现的频率比较小，我们采用这样的编码方案：S0到S7的码辽分别01，11，101，0000，0001，0010，0011，100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39bit。尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。对于上述的编码可能导致解码出现非单值性：比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码字。因此，编码必须保证较短的编码决不能是较长编码的前缀。符合这种要求的编码称之为前缀编码。
3.3 数据结构
要构造符合这样的二进制编码体系，可以通过二叉树来实现。
1)首先统计出每个符合出现的频率，上例SO到S7的出现频率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。
2)从左到右把上述频率按从小到大的顺序排列。
3)每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。
4)重复(3)，直到最后得到和为1的根节点。
将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点路径中遇到的0，1序列串起来，得到各个符号的编码。
可以看到，符号只能出现在树叶上，任何一个字符的路径都不会是另一字符路径的前缀路径，这样，前缀编码也就构造成功了。这样一棵二叉树称之为Huffman树，常用于最佳判定，它是最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层，叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为：WPL＝(W1*L1＋W2*L2＋W3*L3＋…＋Wn*Ln)，N个权值Wi(i＝1，2，…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i＝1，2，…n)。Huffman树得出的WPL值最小。
4 综合排序
4.1 题目简介
（1）至少采用四种排序方法实现随机生成100个数值的排序（可采用的排序方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。
（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
4.2 设计思路

4.3 数据结构
略
5 / 5