哈夫曼编码-数据结构-C++程序.doc

数据结构课程设计一、目的数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、要求通过这次设计，要求在数据结构析逻辑特性和物理表示，数据结构的选择的应用、算法的设计及其实现等方面中深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。三、内容2.哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；(2)编码：利用建好的哈夫曼树生成哈夫曼编码；(3)输出编码；(4)设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【选做内容】(1)译码功能；(2)显示哈夫曼树；(3)界面设计的优化。哈夫曼编写编译码一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，这要求在发送端通过一个编码系统对待传输预先编码，在接收端将传来的数据进行译码。对于双工通道，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。二、概要设计1 哈夫曼树的定义：在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。2哈夫曼树的构造：假设有N个权值，则构造出的哈夫曼树有N个叶子结点。N个权值分别设为W1,W2,.Wn,则哈夫曼树的构造规则为： （1） 将W1，W2，.Wn看成有N棵树的森林；（2） 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左，右子树，且新树的根结点为其左，右子树结点权值之和；（3） 从森林中删除选取取的两面三刀棵树，并将新树加入森林；（4） 重复（2）（3）步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。在构造哈夫曼树的过程中，每次由两棵权值最小的树生成一棵新树时，新树的左子树和右子树可以任意安排，这样将会得到具有不同结构的多个哈夫曼树，但字们都具有相同的带权路径长度。为了歙得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权要小于等于右女树根结点的权。3构造哈夫曼树的算法实现：假设哈夫曼树采用双亲孩子表示法存储，并增加权值域，构造哈夫曼树的叶子结点（树木的权）有N个，合并次数为N1次，则森林中总共有2N1棵树，（包含合并后删除的）。存储结构描述为： const int n=maxn /maxn表示叶子数目 const int m=2*n-1 /m为森林中树的棵数 class tree public: float weight; /权值 int parent; /双亲 int lch, rch; /左，右孩子 tree hftreem+1; /规定从第一个元素hftree1开始使用数组元素，故定义长度为m+1而不为m4结构类型：typedef structchar data;int weight;int parent;int lchild;int rchild;huffnode;typedef structchar cdMAX;int start;huffcode;5主程序int main() 初始化:输入字符代码以及权值. 编制哈夫曼码:根据权值建立二叉树, 输出相应的根节点到叶结点的路径,便是哈夫曼编码.编码:输入字符,输出哈夫曼码.译码:输入哈夫曼,输出字符代码.退出:结束进程,退出程序.return 0;三、详细设计#include#include#include#define MAX 25typedef structchar data;int weight;int parent;int lchild;int rchild; HTNode;typedef struct char cdMAX;int start; HuffmanCode;int main()HTNode ht2*MAX;HuffmanCode hcdMAX, d;int i, k, f, l, r, n, c, s1, s2; cout* * * * * * * * * * * * * * * * * * * * * n t哈夫曼编码与译码系统n* * * * * * * * * * * * * * * * * * * * * n;coutn;cout请输入各个元素的结点值与权值:n;for(i=1;i=n;i+)cout 第int结点值：;cin&hti.data;couthti.weight;for(i=1;i=2*n-1;i+)hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=2*n-1;i+)s1=s2=32767;l=r=0;for(k=1;k=i-1;k+)if(htk.parent=0)if(htk.weights1)s2=s1;r=l;s1=htk.weight;l=k;else if(htk.weights2)s2=htk.weight;r=k;htl.parent=i;htr.parent=i;hti.weight=htl.weight+htr.weight;hti.lchild=l;hti.rchild=r;for(i=1;i=n;i+)d.start=n+1;c=i;f=hti.parent;while(f!=0)if(htf.lchild=c)d.cd-d.start=0;else d.cd-d.start=1;c=f;f=htf.parent;hcdi=d;cout输出哈夫曼编码：n;for(i=1;i=n;i+)couthti.data: ;for(k=hcdi.start;k=n;k+)couthcdi.cdk;coutn;l: couthfm;if(hfm=e)return 0;elseswitch(hfm)caseb: int q; char bs;coutn* * * 哈夫曼编码 * * *n;cout请输入字符代码: endl;for(q=0;bs!=10;q+)bs=getchar();for(i=1;i=n;i+)if (bs=hti.data)for(k=hcdi.start;k=n;k+)couthcdi.cdk;coutendl; break;casey: char e;int t,u;t=2*n-1;coutn* * * 哈夫曼译码 * * *n;coutn请输入哈夫曼码: endl;for(u=0;e!=10;u+)if(htt.lchild!=0)e=getchar();if(e=0)t=htt.lchild;else t=htt.rchild;else couthtt.data;t=2*n-1;cout结点植：1权 植：10第2个元素结点植：3权 植：13第3个元素结点植：5权 植：12第4个元素结点植：4权 植：15输出哈夫曼编码：1：003：105：014：11请选择编码/译码/退出系统：y* * * 哈夫曼编码 * * *请输入哈夫曼码：00 1请选择编码/译码/退出系统：b* * * 哈夫曼编码 * * *请输入字符代码： 100请选择编码/译码/退出系统：epress any key to continue 七实验心得在通信中，可以采用0,1的不同排列来表示不同的字符，称为二进制编码。而哈夫曼树在数据中的应用，是数据库的最小冗余编码问题，字是数据压缩学的基础。若每个字符出现的频率相同，则可以采用等长的二进制编码，若频率不同，则可以采用不等长的二进制编码，频率较大的字符采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小冗余编码问题。而哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。为了使不等长编码成为无前缀编码，避免译码时的二义性，可用该字符集中的每个字符作为叶子结生成一棵编码二叉树，为了获得传送电文的最短长度，可以将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送电文的最短长度。因此，求传送电文的最短长度问题就转化为求由集中的所有字符作为叶子结点为，由字符的出现频率作为其权值所产生的哈夫曼权的问题。通过这次的实验我对软件设计有了一定的了解，同时感觉到自己还有很多的不足之处，特别是实际动手能力还有待于提高。在以后的学习中，要勤于思考，多动脑，多动手，这样才能不断提高成绩。附录：程序源代码#include#include#include#define MAX 25typedef structchar data;int weight;int parent;int lchild;int rchild; HTNode;typedef struct char cdMAX;int start; HuffmanCode;int main()HTNode ht2*MAX;HuffmanCode hcdMAX, d;int i, k, f, l, r, n, c, s1, s2; cout* * * * * * * * * * * * * * * * * * * * * n t哈夫曼编码与译码系统n* * * * * * * * * * * * * * * * * * * * * n;coutn;cout请输入各个元素的结点值与权值:n;for(i=1;i=n;i+)cout 第int结点值：;cin&hti.data;couthti.weight;for(i=1;i=2*n-1;i+)hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=2*n-1;i+)s1=s2=32767;l=r=0;for(k=1;k=i-1;k+)if(htk.parent=0)if(htk.weights1)s2=s1;r=l;s1=htk.weight;l=k;else if(htk.weights2)s2=htk.weight;r=k;htl.parent=i;htr.parent=i;hti.weight=htl.weight+htr.weight;hti.lchild=l;hti.rchild=r;for(i=1;i=n;i+)d.start=n+1;c=i;f=hti.parent;while(f!=0)if(htf.lchild=c)d.cd-d.start=0;else d.cd-d.start=1;c=f;f=htf.parent;hcdi=d;cout输出哈夫曼编码：n;for(i=1;i=n;i+)couthti.data: ;for(k=hcdi.start;k=n;k+)couthcdi.cdk;coutn;l: couthfm;if(hfm=e)return 0;elseswitch(hfm)caseb: int q; char bs;coutn* * * 哈夫曼编码 * * *n;cout请输入字符代码: endl;for(q=0;bs!=10;q+)bs=getchar();for(i=1;i=n;i+)if (bs=hti.data)for(k=hcdi.sta