哈夫曼编码实验报告

数据结构作业报告——哈夫曼编码实验报告姓名：班级：学号：摘要本程序能执行让一段字符以哈夫曼编码的形式被转存，或将一段哈夫曼编码翻译成字符，通过字符的频率统计，哈夫曼树的建立，递归求字符的哈夫曼编码完成，这个程序让我熟悉哈夫曼编码的全过程。内容设计哈夫曼树的结构体（htnode），其中包含权重、左右孩子、父母和要编码的字符。用这个结构体（htnode）定义一个哈夫曼数组（hfmt[]）。使用循环过程，每次选择两个权值最小、且没有父母的节点，将其权值相加建立新的节点放置在哈夫曼数组的最末尾。循环直至数组中仅有一个节点没有父母时结束，至此哈夫曼树建立。从哈夫曼编码中存储某一字符的单元开始，不断寻找它的父母节点，并判断上一节点是其父母节点的左孩子还是右孩子。左孩子记录为“0”，右孩子记录为“1”，直至找到哈夫曼树的根节点为止。从根节点开始，读取哈夫曼编码的每一位，“0”则寻找节点的左孩子，“1”则寻找节点的右孩子。直至节点没有孩子为止，此时读取该节点所存储的字符即可。变量说明：voidinithfmt(hfmtt)对结构体进行初始化voidinputweight(hfmtt)输入函数voidselectmin(hfmtt,inti,int*p1,int*p2)选中两个权值最小的函数voidcreathfmt(hfmtt)创建哈夫曼树的函数voidphfmnode(hfmtt)对字符进行初始编码voidhuffpath递归求哈夫曼编码程序执行结果第一次运行结果：第二次运行结果：第三次运行结果：结论本程序思路基本正确，运行结果合法的，可以满足哈夫曼编码的转存和翻译。编程中遇到的问题以及解决方法1.程序在运行中多次出现溢出，后发现是在生成哈夫曼树时没有将数组下标附初值。2.递归过程死循环，后发现是没有设置边界条件。附录//aa.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXLEN1000typedefstruct{intweight;intlchild;intrchild;intparent;charkey;}htnode;typedefhtnodehuff[MAXLEN];intn=0;voidinithuff(hufft)//对结构体进行初始化{inti;printf("\n");for(i=0;i<2*n-1;i++){t[i].lchild=-1;t[i].rchild=-1;t[i].parent=-1;}printf("\n");}voidinputweight(hufft)//输入函数{intw;//w表示权值inti,len,str[1000];chark[1000];//k表示获取的字符 printf("请输入测试文本:\n");gets(k);len=strlen(k); for(i=0;i<1000;i++)str[i]=0; for(i=0;i<len;i++)str[k[i]]++; for(i=0;i<1000;i++) { if(str[i]!=0) { t[n].key=i; t[n].weight=str[i];n++; } } for(i=n;i<MAXLEN;i++)t[i].weight=0; }voidselectmin(hufft,inti,int*p1,int*p2)//选中两个权值最小的函数{longmin1=999999;longmin2=999999;intj;for(j=0;j<=i;j++)//选择最小权值字符的下标返回if(t[j].parent==-1)if(min1>t[j].weight){min1=t[j].weight;*p1=j;}for(j=0;j<=i;j++)//选择次小权值字符的下标还回if(t[j].parent==-1)if(min2>t[j].weight&&j!=(*p1))//注意此处需j!=(*p1))才能保证是次小的{min2=t[j].weight;*p2=j;}}voidcreathuff(hufft)//创建哈夫曼树的函数{inti,p1,p2;inputweight(t); inithuff(t);for(i=n;i<2*n-1;i++){selectmin(t,i-1,&p1,&p2);t[p1].parent=i;t[p2].parent=i;t[i].lchild=p1;t[i].rchild=p2;t[i].weight=t[p1].weight+t[p2].weight;}}voidprinthuff(hufft)//打印哈夫曼树{inti;printf("哈夫曼树结构:\n");printf("\t\t权重\t父母\t左孩子\t右孩子\t字符\t");for(i=0;i<2*n-1;i++){printf("\n");printf("\t\t%d\t%d\t%d\t%d\t%c",t[i].weight,t[i].parent,t[i].lchild,t[i].rchild,t[i].key);}printf("\n");}voidhuffpath(hufft,inti,intj)//编码的重要哈夫曼树路径递归算法{inta,b;a=i;b=j=t[i].parent;if(t[j].parent!=-1){i=j;huffpath(t,i,j);}if(t[b].lchild==a)printf("0");elseprintf("1");}voidphfmnode(hufft)//对字符进行初始编码{inti,j,a;printf("\n");printf("哈夫曼编码");for(i=0;i<n;i++){j=0;printf("\n");printf("\t\t%c\t",t[i].key,t[i].weight);huffpath(t,i,j);}}voidbianma(hufft)//对用户输入的文章进行编码{charr[1000];//用来存储输入的字符串inti,j;printf("请输入需要编码的字符:");gets(r);printf("编码结果为:");for(j=0;r[j]!='\0';j++)for(i=0;i<n;i++)if(r[j]==t[i].key)huffpath(t,i,j);printf("\n");}voidyima(hufft)//对用户输入的密文进行译码{charr[100];inti,j,len;j=2*n-2;//j初始从树的根节点开始printf("请输入需要译码的字符串:");gets(r);len=strlen(r);printf("译码的结果是:");for(i=0;i<len;i++){if(r[i]=='0'){j=t[j].lchild;if(t[j].lchild==-1){printf("%c",t[j].key);j=2*n-2;}}elseif(r[i]=='1'){j=t[j].rchild;if(t[j].rchild==-1){printf("%c",t[j].key);j=2*n-2;}}}printf("\n\n");}intmain(){ printf("我的学号是：07112039\n");inti,j;huffht;charflag;creathuff(ht);printhuff(ht);phfmnode(ht);printf("\n【1】编码\t【2】\t译码\t【0】退出");printf("\n您的选择：");flag=getchar();getchar();while(flag!='0'){if(flag=='1')bianma(ht);