2014年算法与大数据结构说明书.doc

《2014年算法与大数据结构说明书.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、*******************实践教学*******************理工大学计算机与通信学院2014年春季学期数据结构与算法课程设计题目1.集合运算问题2.递归替换问题3.哈夫曼码的编/译码系统4.排序重构问题专业班级：姓名：学号：指导教师：成绩：目录1.采用类语言定义相关的数据类型42.算法设计43.函数的调用关系图74.调试分析75.测试结果86.源程序（带注释）9二、递归替换问题123、源程序14三、哈夫曼码的编/译码系统161、数据结构设计162、算法设计173、调试分析184、执行结果19四、排序重构问题202、算法设计214、调试分析215、测试

2、结果216、源程序（带注释）22总结26参考文献27致28摘要第一道题是编写算法实现集合的相关操作包括集合的输入、输出、删除集合中重复的元素、删除、修改，求两个集合的交、并、差。在MicrosoftVisualC++或者C-Free中实现程序的调试这个程序实现集合中元素的录入、删除、修改、并、交、差等操作。采用单链表对集合进行操作、运行等。通过该题目的设计过程，可以进一步理解和熟练掌握课本中所学的各种数据结构的知识，加深对链表的认识。学会如何把学到的知识用于解决实际问题，培养自己的动手能力。第二个程序为递归替换仿编译问题，具体要递归替换问题。编写程序，扩展C/C++源文件中

3、的#include指令（以递归的方式）。以文件名的容替换形预编译命令“include”。具体是用相应文件的容来替换上面的代码“预编译”的命令，即在最后的结果查看文件中没有“#include”字样，其位置为相应文件的容，考虑到有可能在我们要替换的文件中也可能会有预编译命令，所以要用递归的算法。通过这个代码的编写可以帮我们更深层次的理解c语言编译的过程，同时也能够练习递归的运用。第三道题是哈夫曼的编译码问题。本课程设计主要研究如何通过给定权值以及字符集生成哈夫曼前缀码并用前缀码对文件进行编码和译码的方法。通过对问题的分析，采用哈夫曼算法的设计思想。根据给定的权值构成二叉树森林，

4、在森林中任意选取两棵根结点权值最小的树，将这两棵树合并为新的树，为保证新树仍为二叉树，需要增加一个新的结点作为根将这两个孩子的权值之和作为新树根的权值。对新的森林重复上述步骤直到森林中只剩一棵树为止。此树即为哈夫曼树。根据构造的二叉树，将每个叶子节点进行编码。进而实现对报文的编码和译码。第四道为排序重构问题。具体要由题目给出的一个顺序序列按照题目给定的相关计算方法得到新的序列，然后对计算方法进行逆推得到新的顺序序列，由于计算方法我们得到的序列并不唯一。关键词：集合幂集递归替换预编译哈夫曼编码译码排序重构一．集合运算问题设计一个程序，实现两个集合的并集、交集、差集、显示输出等

5、，要求结果集合中的元素不重复；实现一个集合的幂集的求解。1.采用类语言定义相关的数据类型定义一个结构体存储结构，用来生成求幂集的二叉树只在求幂集函数使用typedefstruct//根节点结构体（幂集使用）{intdata[MAX];intlength;}root;定义一个二维数组，用来存储节点选择情况，其第一个下标表示是左孩子还是右孩子，第二个表示节点当前所处的层数intc[2][MAX];//c构造数据池2.算法设计1.并集：用两个循环结构为并集赋值，最后进行重复元素检查（check（））。for(i=0;i

6、=0;i<=m;i++)//B集合赋值{c[n+i]=b[i];}k=n+m;//集合大小k=check(c,k);//集合重复元素检查2.利用双重循环判断元素是否在A、B里面均存在，存在则赋值在C里面for(i=0;i<=n;i++)//在A里面检查for(j=0;j<=m;j++)//在B里面检查{if(a[i]==b[j])//元素在A和B里面均出现{c[k]=a[i];//赋值k++;//C集合容量加1printf("%d",c[k-1]);//屏幕输出}}3.利用双重循环判断只在A里面出现过的元素，并把它们赋值到C里面for(i=0;i<=n;i++)//在A里面

7、检查{for(j=0;j<=m;j++)//在B里面检查{if(a[i]==b[j])//两个集合都有直接退出循环{flag=0;//更改标志break;}elseflag=1;}if(flag)//通过标识检查{c[k]=a[i];printf("%d",c[k]);}}4.利用二叉树的思想求解幂集，我们认为根节点为空集，然后每一层向树里面加入一个元素，直到集合中所有元素添加完毕，在具体每一层中，上一层的叶子节点会有两个孩子，左孩子表示有这一层的元素，右孩子没有，这样的话通过最后一层的叶子节点的扫描就可以得到所有