数据结构与算法——电文的编码和译码.doc

电文的编码和译码1. 问题描述 从键盘接受一串电文字符，输出对应的哈夫曼编码；同时能翻译由哈夫曼编码生成的代码串，输出对应的电文字符串。2. 设计要求(1) 构造一棵哈夫曼树。(2) 实现哈夫曼编码，并用哈夫曼编码生成的代码进行译码。(3) 程序中字符和权值是可变的，实现程序的灵活性。3. 数据结构 本课程设计采用结构体数组作为数据结构，来储存哈夫曼树及其编码。4. 分析与实现 在电报通信中，电文是以二进制代码传送的。在发送时，需要将电文中的字符转换成二进制代码串，即编码；在接收时，要将收到的二进制代码串转化成对应的字符序列，即译码。字符被使用的频率是非均匀的。在传送电文时，要想使电文总长尽可能短，就需要让使用频率高的字符编码长度尽可能短。因此，若对某字符集进行不定长编码设计，则要求任一一个字符编码都不能使其他字符编码的前缀，这种编码称作前缀编码。 由哈弗曼树求得的编码是最优前缀码，也称哈夫曼编码。给出字符集和各个字符的概率分布，构造哈弗曼树，将哈夫曼树中每个分支结点的左分支标0，右分支标1，从根到每个叶子的路径上的标号连起来就是给叶子所代表字符的编码。(1) 构造哈夫曼树 根据哈弗曼算法，若已知n个叶结点，则构造的哈弗曼树有2n-1个结点。 第一步：先输入字符集中的n个字符（叶结点）和表示其概率分布的权值，储存在ht（HuffNode型）数组的前n个数组元素中。然后将2n-1个结点的双亲和孩子结点均置为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 (1in)出发，通过双亲parent找到其双亲htf，通过htf的域left和right，可知hti是htf的左分支还是右分支，若是左分支，生成的代码0；若是右分支，生成代码1。代码存放在数组cd的下标start中，然后把htf作为出发点，重复上述过程，直到找到根为止。显然这样生成的代码序列与要求的编码次序相反，为了得到正确的代码，把最先生成的代码存放在数组的第n个（虽然各个字符的编码长度不一，但都不会超过n个）位置处，再次生成的代码存放在数组的第n-1个位置处，以此类推。用变量start来指示编码在数组cd中的起始位置，start的初始值为n，生成一个代码后，start的值就减1。(3) 译码 基本思想是：首先输入二进制代码串，存放在数组ch中，以#为结束标志；接下来，将代码与编码表比较，如果为0，转向左子树，如果为1，转向右子树，直到叶结点结束，此时输出叶结点的数据域，即所对应的字符；继续译码，直到代码串结束。5. 源代码#include#include#include#define MAXSIZE 50typedef char DataType;typedef struct /哈夫曼树结点的结构DataType data; /数据用字符表示int weight; /权值int parent; /双亲int lchild,rchild; /左右孩子 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,&hti.data,&hti.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+)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;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; /规定左树代码为0elsed.cd-d.start=1; /规定右树代码为1hcdi=d;printf(输出哈夫曼编码：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; /将单个字符依次存入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; /定义存放编码的数组while(1)printf(1-建立哈夫曼树n);printf(2-编码n);printf(3-译码n);printf(4-退出系统n);printf(请输入您所要实现的功能：);scanf(%d,&select);