数据结构与算法――电文的编码和译码

1、电文的编码和译码 1. 问题描述 从键盘接受一串电文字符，输出对应的哈夫曼编码；同时能翻译由哈夫曼 编码生成的代码串，输出对应的电文字符串。 2. 设计要求 (1) 构造一棵 xx 树。 (2) 实现哈夫曼编码，并用哈夫曼编码生成的代码进行译码。 (3) 程序中字符和权值是可变的，实现程序的灵活性。 3. 数据结构 本课程设计采用结构体数组作为数据结构，来储存哈夫曼树及其编码。 4. 分析与实现 在电报通信中，电文是以二进制代码传送的。在发送时，需要将电文中的 字符转换成二进制代码串，即编码；在接收时，要将收到的二进制代码串转化 成对应的字符序列，即译码。 字符被使用的频率是非均匀的。在传送电

2、文时，要想使电文总长尽可能 短，就需要让使用频率高的字符编码长度尽可能短。因此，若对某字符集进行 不定长编码设计，则要求任一一个字符编码都不能使其他字符编码的前缀，这 种编码称作前缀编码。 由哈弗曼树求得的编码是最优前缀码，也称哈夫曼编码。给出字符集和各 个字符的概率分布，构造哈弗曼树，将哈夫曼树中每个分支结点的左分支标0， 右分支标 1，从根到每个叶子的路径上的标号连起来就是给叶子所代表字符的编 码。 (1) 构造 xx 树 根据哈弗曼算法，若已知n个叶结点，则构造的哈弗曼树有 2n-1个结点。 第一步： 先输入字符集中的 n 个字符（叶结点）和表示其概率分布的权值，储存在 ht （Huff

3、Node 型）数组的前 n 个数组元素中。然后将 2n-1 个结点的双亲和孩子 结点均置为 0。 第二步： 在所有的结点中，选取双亲为零且具有最小权值 m1 和次小权值 m2 的两个 结点，用pl和p2指示这两个结点在数组中的位置。将根为 htp1和htp2的两 棵树合并，使其成为新结点hti的左右孩子，hti的权值为最小权值ml和次小 权值m2之和；htp1和htp2的双亲指向i。共进行n-1次合并，产生n-1个结 点，依次放入ht数组中数组下标从n+1到2n-1。这样就构成了一棵哈夫曼树。 （2）编码 基本思想是： 从哈弗曼树的叶结点hti （1 i哇出发，通过双亲pare nt找到其双亲

4、htf, 通过htf的域left和right，可知hti是htf的左分支还是右分支，若是左分 支，生成的代码0;若是右分支，生成代码1。代码存放在数组cd的下标start 中，然后把htf作为出发点，重复上述过程，直到找到根为止。显然这样生成 的代码序列与要求的编码次序相反，为了得到正确的代码，把最先生成的代码 存放在数组的第 n 个（虽然各个字符的编码长度不一，但都不会超过 n 个）位 置处，再次生成的代码存放在数组的第 n-1 个位置处，以此类推。用变量 start 来指示编码在数组cd中的起始位置，start的初始值为n,生成一个代码后， start 的值就减 1。 （3）译码 基本思想

5、是： 首先输入二进制代码串，存放在数组 ch 中，以#为结束标志；接下来，将 代码与编码表比较，如果为 0，转向左子树，如果为 1，转向右子树，直到叶结 点结束，此时输出叶结点的数据域，即所对应的字符；继续译码，直到代码串 结束。 5. 源代码 #include #include #include #define MAXSIZE 50 typedef char DataType; typedef struct / 哈夫曼树结点的结构 DataType data;/ 数据用字符表示 int weight;/ 权值 int parent;/ 双亲 int lchild,rchild;/ 左右孩子

6、HuffNode; typedef struct /哈夫曼编码的存储结构DataType cdMAXSIZE;存放编码位 串 int start;/ 编码的起始位置 HuffCode; void HuffmanCreate(HuffNode *ht,int n)int i,j,p1,p2,m1,m2; for(i=1;i=n;i+)getchar(); 接收回车 printf(第%d个字符及其权重分别为(用空格分隔)： n,i); scanf(%c %d,for(i=1;i=2*n-1;i+)/ 对数组初始化 hti.parent=hti.lchild=hti.rchild=0; for(i=

7、n+1;i=2*n-1;i+)m1=m2=32767;/ 令 m 1、 m2 为整数最大值 p1=p2=1; for(j=1;ji;j+)/ 找出 parent 为 0 且权值最小的两个结点 if(htj.parent=0) if(htj.weightm1) m2=m1; p2=p1; m1=htj.weight; p1=j;else if(htj.weightm2)m2=htj.weight; p2=j;hti.lchild=p1;/p1 为新结点的左孩子 hti.rchild=p2;/p2 为新结点的右孩子 hti.weight=m1+m2;/ 新结点的权值为最小权值和次小权值的和 htp

8、1.parent=i; htp2.parent=i; printf( 哈夫曼树已成功建立！ n);void Encoding(HuffNode *ht,HuffCode *hcd,int n)HuffCode d; int i,j,f; for(i=1;i=n;i+)/ 对所有结点循环 d.start=n+1;/ 起始位置 f=hti.parent;/ 双亲的位置 for(j=i;f!=0;j=f,f=htj.parent)if(htf.lchild=j) d.cd-d.start=0;/ 规定左树代码为 0 else d.cd-d.start=1;/ 规定右树代码为 1hcdi=d;prin

9、tf( 输出哈夫曼编码： n); for(i=1;i=n;i+)printf(%c ,hti.data);/ 先输出结点 for(j=hcdi.start;j=n;j+)/ 在输出其对应编码 printf(%c,hcdi.cdj); printf(n); void Decoding(HuffNode *ht,int n)DataType c,ch200;/c 接收输入电文， ch 储存 int i,temp,f; printf( 请输入电文，以 “ #为”结束标志： n); c=getchar(); i=0; while(c!=#)i+;/ch 数组下标后移 chi=c;/ 将单个字符依次存入

10、 ch 字符串中 c=getchar(); temp=i;/ 标记数组存储末位位置 i=1; printf( 输出 xx 弗曼译码： n); while(i=temp)f=2*n-1;/ 每次都从根节点开始查找 while(htf.lchild!=0)if(chi=0) f=htf.lchild; if(chi=1) f=htf.rchild; i+;printf(%c,htf.data);printf(n);void main()int n,select; HuffNode htMAXSIZE*2;/ 定义存放哈夫曼树的数组 HuffCode hcdMAXSIZE;/定义存放编码的数组 while (1)printf(1- 建立哈夫曼树 n); printf(2-编码n); 6. 结果 printf(3-译码n); printf(4- 退出系统 n); printf( 请输入您所要实现的功能： ); scanf(%d, swit