《数据结构与算法》课程设计汇总

《数据结构与算法》课程设计(2013/2014学年第一学期17周)班级：12计算机科学与技术3班2.基本要求3.测试要求3字符ABCDEFGHIJKLM频度15字符N0PQRSTUVWXYZ频度1811某文件中的一个符号)进行编码。这张编码表的特殊现的估算概率而建立起来的(出现概率高的字符使用较短的编码，反之出现概率低的则使目的)。赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信表示"0”码，指向右子树的分支表示“1"码，取每条路径上的"0”或“1"的序列作为哈夫曼编\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼曼编码后进行译码。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0,右分支代表1,则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编(1)其主要流程图如图1-1所示。开始否结点数是否大于1是输出根结点和权值否是调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点否是否为根结点?是是左子是否为空?是否是此时编码为0右子是否为空此时编码为0否编码为1结束6(2)设计包含的几个方面：①赫夫曼树的建立赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n-1次合并，所以共产生n-1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的赫夫曼个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n--1的一维数组来存储赫夫曼树中的结点。要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下：charch;//存放编码的字符charbits[N+1];//存放编码位串intlen;//编码的长度}CodeNode;//编码结构体类型③代码文件的译码译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。源程序如下：//义用N表示50叶节点数//用M表示节点总数当叶节点数位n时总节点数为2n-1typedefstructtypedefstructif(ht[k].weight<minl)elseif(ht[kweightminmin2=ht[kweightrnode8if(ht[f].Ichild==c)9化while(flag)//菜单函数，当flag为0时跳出循环{调试分析五、详细设计(1)①赫夫曼树的存储结构描述为：if(ht[k].weight<minl)(2)哈弗曼编码printf("%c",hcd[i].cd[k])字符的编码break(3)哈弗曼译码/为记录所存储这个字符的编码个数}printf("%c",ht[i].data)(4)主函数charstr[]={A',B',C',D',E',F,G,H,T,J,K,L,M,N',O,P',Q,R'化{}//菜单函数，当flag为0时跳出循环//菜单函数，当flag为0时跳出循环printf("***********************本课程设计的评价由三部分组成，包括程序演示(50%),课程设计报告(30%),回答教师提问(20%)。