三题目：哈夫曼编/译码器班级：姓名：学号：完成日期：15.11.14一、题目要求描述：写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。

构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0.输入：输入表示字符集大小为n（n <= 100）的正整数，以及n个字符和n个权值（正整数，值越大表示该字符出现的概率越大）；输入串长小于或等于100的目标报文。

输出：经过编码后的二进制码，占一行；以及对应解码后的报文，占一行；最后输出一个回车符。

输入样例： 5 a b c d e 12 40 15 8 25bbbaddeccbbb输出样例：00011111110111010110110000bbbaddeccbbb提示：利用编码前缀性质。

二、概要设计1.设计需要的数据结构：树型结构2.需要的抽象数据类型：ADT Tree{数据对象D：D是具有相同特性的数据元素的集合。

数据关系R：若D为空集，则称为空树；若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3,…,Dm(m>0)，对于任意j≠k(≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有<root,xi>∈H; (3) 对应于D-{root}的划分，H-{<root,xi>,…,<root,xm>}有唯一的一个划分H1，H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。

基本操作：InitTree(&T);操作结果：构造空树T。

DestroyTree(&T);初始条件：树T存在。

操作结果：销毁树T。

CreateTree(&T,definition);初始条件：definition给出树T的定义。

操作结果：按definition构造树T。

｝三、详细设计算法设计1.设计一个存储数据的数组结构体typedef struct{char cd[200];//最大的数据int start;}HuffmanCode;2.设计一个结构体数组：在表示哈夫曼树时，用如下的结构体保存哈夫曼树中个结构体的信息，根据二叉树的性质可知，具有N个节点的哈夫曼树共有2n-1个节点。

typedef struct{int weight;char data;unsigned int parent, lchild, rchild;}HTNode, *HuffmanTree;3.设置全局变量HTNode ht[2*200];HuffmanCode hcd[200],d;int i, k, f, l, r, n, c, s1, s2;char a;4.创建输入函数void creatsz(){for(i=1;i<=n;i++){cin>>ht[i].data;//输入数据}for(i=1;i<=n;i++){cin>>ht[i].weight;//输入数据的权重}}5.创建构造哈夫曼树的伪代码算法void creattree(){for(i=n+1;i<=2*n-1;i++){s1=s2=100000;l=r=0;for(k=1;k<=i-1;k++)//建立哈夫曼树{if(ht[k].parent==0){if(ht[k].weight<s1){s2=s1;r=l;s1=ht[k].weight;l=k;}else if(ht[k].weight<s2){s2=ht[k].weight;r=k;}}}ht[l].parent=i;ht[r].parent=i;ht[i].weight=ht[l].weight+ht[r].weight;ht[i].lchild=l;ht[i].rchild=r;}6.创建构造哈夫曼编码的伪代码算法void creatlist(){for(i=1;i<=n;i++)//逐个字符求哈夫曼编码{d.start=n+1;//编码结束位置c=i;f=ht[i].parent;while(f!=0)//从叶子到根逆向求编码{if(ht[f].lchild==c){d.cd[--d.start]='0';}else{d.cd[--d.start]='1';}c=f;f=ht[f].parent;}hcd[i]=d;}}7.主函数int main(){ int j=0;char h[100];cin>>n;//输入要求的数据个数creatsz();creattree();creatlist();a=getchar();cin>>h;for(j=0;h[j]!='\0';j++){for(i=1;;i++){if(ht[i].data==h[j])break;}for(k=hcd[i].start;k<=n;k++){cout<<hcd[i].cd[k];//输出编码后的数据}}cout<<'\n';for(i=0;i<j;i++){cout<<h[i];}cout<<'\n';return 0;}实现流程Main()←←←←↓→→→→↓↓↓creatsz() →void creattree() →creatlist()传递参数见算法设计部分。

四、调试分析与心得体会1.开始的时候，有点不知如何下手，就想到了老师经常说的，假设子问题已经解决了，并不需要想太多，细节问题最后再说。

写程序的时候从整体再到细节。

2.初步完成，有一个字符串的输入解决不了，按部检错也没有用，最后经同学指点才发现codeblocks不能直接调用getchar()函数库，于是加了标准头文件函数库。

3. 在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较。

4.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。

把HT[i].weight=HT[i].weight+HT[i].weight;中的r写成了。

5. 格式错误。

这是在提交的过程中令人头痛的问题，经总结后发现，基本是输出结果时的空格或换行问题，毕竟只是机器，不能很好的识别并加以判断。

6. 在调试中，为了方便检查，经常在程序中间编写一些输出程序，打印中间结果，跟踪数据变化，检查何处出错7.编程是需要细心与耐心的工作，只要肯静下心来努力思考，多看书，多操作，并不存在所谓的不会。

其实，每次编程成功的喜悦，足以弥补遇到的不快。

五、用户操作说明程序说明可参考三详细设计部分。

1. 本程序的运行环境为Windows7旗舰版/Windows xp操作系统。

2.需要输入的数据：5 a b c d e 12 40 15 8 25Bbbaddeccbbb六、运行结果如图：七、附录源程序：#include<iostream>#include<stdio.h>using namespace std;typedef struct{int weight;char data;unsigned int parent, lchild, rchild; }HTNode, *HuffmanTree;typedef struct{char cd[200];int start;}HuffmanCode;HTNode ht[2*200];HuffmanCode hcd[200],d;int i, k, f, l, r, n, c, s1, s2;char a;void creatsz(){for(i=1;i<=n;i++){cin>>ht[i].data;}for(i=1;i<=n;i++){cin>>ht[i].weight;}}void creattree(){for(i=n+1;i<=2*n-1;i++){s1=s2=100000;l=r=0;for(k=1;k<=i-1;k++){if(ht[k].parent==0){if(ht[k].weight<s1){s2=s1;r=l;s1=ht[k].weight;l=k;}else if(ht[k].weight<s2){s2=ht[k].weight;r=k;}}}ht[l].parent=i;ht[r].parent=i;ht[i].weight=ht[l].weight+ht[r].weight;ht[i].lchild=l;ht[i].rchild=r;}}void creatlist(){for(i=1;i<=n;i++){d.start=n+1;c=i;f=ht[i].parent;while(f!=0){if(ht[f].lchild==c){d.cd[--d.start]='0';}else{d.cd[--d.start]='1';}c=f;f=ht[f].parent;}hcd[i]=d;}}int main(){ int j=0;char h[100];cin>>n;creatsz();creattree();creatlist();a=getchar();cin>>h;for(j=0;h[j]!='\0';j++){for(i=1;;i++){if(ht[i].data==h[j])break;}for(k=hcd[i].start;k<=n;k++){cout<<hcd[i].cd[k];}}cout<<'\n';for(i=0;i<j;i++){cout<<h[i];}cout<<'\n';return 0;}。