《数据结构与算法——电文的编码和译码》由会员分享，可在线阅读，更多相关《数据结构与算法——电文的编码和译码（6页珍藏版）》请在金锄头文库上搜索。
1、电文的编码和译码1.问题描述从键盘接受一串电文字符，输出对应的哈夫曼编码；同时能翻译由哈夫曼编码生成的代码串，输出对应的电文字符串。2.设计要求(1)构造一棵哈夫曼树。(2)实现哈夫曼编码，并用哈夫曼编码生成的代码进行译码。(3)程序中字符和权值是可变的，实现程序的灵活性。3.数据结构本课程设计采用结构体数组作为数据结构，来储存哈夫曼树及其编码。4.分析与实现在电报通信中， 电文是以二进制代码传送的。在发送时， 需要将电文中的字符转换成二进制代码串，即编码；在接收时，要将收到的二进制代码串转化成对应的字符序列，即译码。字符被使用的频率是非均匀的。在传送电文时， 要想使电文总长尽可能短，就需要让
2、使用频率高的字符编码长度尽可能短。因此， 若对某字符集进行不定长编码设计，则要求任一一个字符编码都不能使其他字符编码的前缀，这种编码称作前缀编码。由哈弗曼树求得的编码是最优前缀码，也称哈夫曼编码。 给出字符集和各个字符的概率分布，构造哈弗曼树，将哈夫曼树中每个分支结点的左分支标0，右分支标1，从根到每个叶子的路径上的标号连起来就是给叶子所代表字符的编码。(1)构造哈夫曼树根据哈弗曼算法，若已知n 个叶结点，则构造的哈弗曼树有2n-1 个结点。第一步：先输入字符集中的n 个字符（叶结点）和表示其概率分布的权值，储存在ht（HuffNode 型）数组的前n 个数组元素中。 然后将 2n-1 个结点
3、的双亲和孩子结点均置为0。第二步： 在所有的结点中， 选取双亲为零且具有最小权值m1 和次小权值m2 的两个结点，用 p1 和 p2 指示这两个结点在数组中的位置。将根为htp1 和 htp2 的两棵树合并，使其成为新结点hti 的左右孩子，hti 的权值为最小权值m1 和次小权值m2 之和； htp1 和 htp2的双亲指向i。共进行 n-1 次合并，产生n-1 个结点，依次放入ht 数组中数组下标从n+1 到2n-1。这样就构成了一棵哈夫曼树。(2)编码基本思想是：从哈弗曼树的叶结点hti (1 in)出发，通过双亲parent 找到其双亲htf ，通过 htf 的域 left 和 rig
4、ht，可知 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; / 左右孩子 HuffNode; typedef struct /
6、 哈夫曼编码的存储结构 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=n+1;i=2*n-1;i
7、+) m1=m2=32767; / 令 m1、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; / 新结点的权值为最小权值和次小权值的和htp1.parent=i;
8、 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; / 规定右树代码为1 hcdi=d; printf(“
9、 输出哈夫曼编码：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(“ 输出哈弗曼译码：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; /
11、 定义存放编码的数组while(1) printf(“1- 建立哈夫曼树 n“); printf(“2- 编码 n“); printf(“3- 译码 n“); printf(“4- 退出系统 n“); printf(“ 请输入您所要实现的功能：“); scanf(“%d“, switch(select) case 1: printf(“ 请输入字符个数：“); scanf(“%d“, HuffmanCreate(ht,n); break; case 2: Encoding(ht,hcd,n); break; case 3: Decoding(ht,n); break; case 4: exit(0); 6.结果
