哈夫曼编码与译码

哈夫曼编码与译码哈夫曼编码与译码用哈夫曼树对字符串进行编码译码一、设计思想程序要求: 要求每个字符有自己唯一的编码。将得到的一串利用哈夫曼树对字符串进行编码, 字串译成0、1编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解码。实现方法: 输入一串字符，要求字符的区间为大写的26个英文字母，将获得的串字符用计算进行字符统计，统计出现的字符种数以及每种字符出现的次权值的函数(jsquanzhi()) 数，将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC...

哈夫曼编码与译码用哈夫曼树对字符串进行编码译码一、设计思想程序要求: 要求每个字符有自己唯一的编码。将得到的一串利用哈夫曼树对字符串进行编码, 字串译成0、1编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解码。实现方法: 输入一串字符，要求字符的区间为大写的26个英文字母，将获得的串字符用计算进行字符统计，统计出现的字符种数以及每种字符出现的次权值的函数(jsquanzhi()) 数，将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC，利用HT(节点)权值的大小建立哈夫曼树，首先用选择函数select()函数选择两个权值最小的字符作为叶子节点，创建一个新的节点作为这两个叶节点的父节点，被选中的节点给他的HT[i].parent赋值是他下次不再被选中，父节点的权值为，子节点的权值之和。然后将该将父节点放入筛选区中，再进行选择(被选过的不再被使用)，直到所有的节点都被使用，这样一个哈夫曼树就被建立了。根据每个字符在哈夫曼书中的位置来编译每个字符的0、1密文代码，从叶节点判断该叶节点是其父节点的左右字左字为‘0’，右子为‘1’，在判断父节点是上级父节点的左右子直至根节点，将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins[]数组。重新一个一个字符的读取输入的字符串，按照字符出现的顺序将它转为0、1代码并存到一个txt文件夹中去。解码时从文件夹中，一个一个字符的读出那串0、1代码赋给一个临时字符串cd[]，用该字符串与每个字符的HC[i].bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr[]中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。 - 1 - 用哈夫曼树对字符串进行编码译码二、算法流程图开始获得输入的字符串getstr[]，i=0。判断getstr[i]是否i++; 为26个大写字母否是 k=getstr[i]-64;quantemp[k]++( quantemp为int型数组开始值都为0)i++; i=1,j=0 否 i<27? 是结束是 quantemp[i]=i++; 0? 否 j++;str[j]=i+64; quan[j]=quantemp[i] ; 图1计算字符权值及字符种类算法说明:将的的字符串进行字符种类级每种字符出现频率的统计 - 2 - 用哈夫曼树对字符串进行编码译码开始将所有的几点的父节点和子节点权值赋成0 i=1;(num为字符的种类) HT[i].weight=quan[i] i<=num 是否 i=num+1 否 i<=2*num-1? 是结束 ? 选择权值最小的两个节点将下标赋给s1,s2. HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weigh t; i++ 图2 构建哈夫曼树算法说明:利用选择排序，选择节点权值最小的两个节点，构建一个子树，将该树的根节点再放入选择区，重复该操作，直至用完所有节点完成哈夫曼数的搭建。 - 3 - 用哈夫曼树对字符串进行编码译码开始将str[i]的值依次赋给HC[i].ch i=0;cd[num]='\0'; i<=num; 是 start=num; c=i 否 i++ HT[c].parent strcpy(HC[i].bits, >0 否 &cd[start]); 是 HC[i].len=num-start; cd[--start]=(HT[p]. lchild==c)?'0':'1'; c= HT[c].parent; 打开codefile.txt文件,获得字符串str指针，i=0; 否 i<=num; 是结束否否 HC[i].ch=*str? i++ 是将HC[i].bits[j]存进文件图3 利用哈夫曼树加密算法说明:利用每个字符在哈夫曼树中的位子，得到每个字符的0、1密文编码。再将字符串按字符密文进行编译，然后存入文件夹中。 - 4 - 用哈夫曼树对字符串进行编码译码开始 cjs=0, i=0 打开文件夹codefile.txt, !feof(fp) 结束 (i='A'&&*p<='Z') //判断字符是否为26字母 {k=*p-64; //看是26个字符中的哪个字符 quantemp[k]++; //字符权值加1 } } j=0; for(i=1,j=0;i<27;i++) {if(quantemp[i]!=0) {j++; //用于统计字符种类个数 str[j]=i+64; //str按字母表顺序存储出现过的字符 quan[j]=quantemp[i]; } } return j; } - 7 - 用哈夫曼树对字符串进行编码译码 void select(HafumanTree HT,int k,int *s1,int*s2) //选择权值最小的两个 {int i,j; int min1=9999; //声明一个int类型的数值min1，赋个较大的输给它 for(i=1;i<=k;i++) //选择权值最小的一个节点(且该节点无父节点) {if((HT[i].weight 记录字符在哈夫曼树的位置 int start; cd[num]='\0'; //给cd赋个结束符 for(i=1;i<=num;i++) {start=num; c=i; while((p=HT[c].parent)>0) //根据节点是其父节点的左右子来记录它的位置 {cd[--start]=(HT[p].lchild==c)?'0':'1'; c=p; //将父节点转为子节点 } strcpy(HC[i].bits,&cd[start]); //将得到的0、1字串存入结构体HC printf("%c:%s\n",HC[i].ch,HC[i].bits); HC[i].len=num-start; //求每个字符0、1编码长度 } } void coding(HafumanCode HC,char *str) //根据哈夫曼树确定每个字符的0、1代码code {int i,j; FILE *fp; //声明一个文件夹指针 fp=fopen("codefile.txt","w"); //打开文件夹codefile printf("密文为:\n"); while(*str) //字符串未结束时 {for(i=1;i<=num;i++) {if(HC[i].ch==*str) //判断字符是否在Codenode中存在 {for(j=0;j 规范自己对不同类型数据存储和使用，还有就是当一个数据不再被使用时或下次你要用它来存放其他数值时要记得提前赋空，以免数据出错。还有就是在程序中如果你要重复某些步骤时你可以考虑在主程序外建立一个函数来实现这些步骤，这样在主程序中通过调用这个函数来实现这些步骤，这样可以避免编写同样的代码，并简化你的程序代码。除此之外就是大括号{}的一定要对其，不然一旦代码长度变长，会出现一堆的括号，你可能看的眼花缭乱不知道哪个与哪个是一对，最后影响你的代码检查。 - 13 -

                    本文档为【哈夫曼编码与译码】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

哈夫曼编码与译码

你可能还喜欢