北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编.docx
- 文档编号:12732403
- 上传时间:2023-06-07
- 格式:DOCX
- 页数:21
- 大小:90.32KB
北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编.docx
《北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编.docx》由会员分享,可在线阅读,更多相关《北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编.docx(21页珍藏版)》请在冰点文库上搜索。
北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编
数据结构实验报告
欧阳光明(2021.03.07)
实验名称:
实验三树——哈夫曼编/解码器
学生姓名:
班级:
班内序号:
学号:
日期:
2014年12月11日
1.实验要求
利用二叉树结构实现赫夫曼编/解码器。
基本要求:
1、初始化(Init):
能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立赫夫曼树
2、建立编码表(CreateTable):
利用已经建好的赫夫曼树进行编码,并将每个字符的编码输出。
3、编码(Encoding):
根据编码表对输入的字符串进行编码,并将编码后的字符串输出。
4、译码(Decoding):
利用已经建好的赫夫曼树对编码后的字符串进行译码,并输出译码结果。
5、打印(Print):
以直观的方式打印赫夫曼树(选作)
6、计算输入的字符串编码前和编码后的长度,并进行分析,讨论赫夫曼编码的压缩效果。
测试数据:
IlovedataStructure,IloveComputer。
IwilltrymybesttostudydataStructure.
提示:
1、用户界面可以设计为“菜单”方式:
能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度,对没有出现的
字符一律不用编码。
2.程序分析
2.1存储结构
Huffman树
给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,其中带权路径长度最小的二叉树称为Huffman树,也叫做最优二叉树。
weightlchildrchildparent
2
-1
-1
-1
5
-1
-1
-1
6
-1
-1
-1
7
-1
-1
-1
9
-1
-1
-1
weightlchildrchildparent
2
-1
-1
5
5
-1
-1
5
6
-1
-1
6
7
-1
-1
6
9
-1
-1
7
7
0
1
7
13
2
3
8
16
5
4
8
29
6
7
-1
2.2关键算法分析
(1)计算出现字符的权值
利用ASCII码统计出现字符的次数,再将未出现的字符进行筛选,将出现的字符及頻数存储在数组a[]中。
voidHuffman:
:
Init()
{
intnNum[256]={0};//记录每一个字符出现的次数
intch=cin.get();
inti=0;
while((ch!
='\r')&&(ch!
='\n'))
{
nNum[ch]++;//统计字符出现的次数
str[i++]=ch;//记录原始字符串
ch=cin.get();//读取下一个字符
}
str[i]='\0';
n=0;
for(i=0;i<256;i++)
{
if(nNum[i]>0)//若nNum[i]==0,字符未出现
{
l[n]=(char)i;
a[n]=nNum[i];
n++;
}
}
}
时间复杂度为O
(1);
(2)创建哈夫曼树:
算法过程:
Huffman树采用顺序存储---数组;
数组的前n个结点存储叶子结点,然后是分支结点,最后是根结点;
首先初始化叶子结点元素—循环实现;
以循环结构,实现分支结点的合成,合成规则按照huffman树构成规则进行。
关键点:
选择最小和次小结点合成。
voidHuffman:
:
CreateHTree()
{
HTree=newHNode[2*n-1];//根据权重数组a[0..n-1]初始化Huffman树
for(intj=0;j { HTree[j].weight=a[j]; HTree[j].LChild=HTree[j].RChild=HTree[j].parent=-1; } intx,y; for(inti=n;i<2*n-1;i++)//开始建Huffman树 { SelectMin(HTree,i,x,y);//从1~i中选出两个权值最小的结点 HTree[x].parent=HTree[y].parent=i; HTree[i].weight=HTree[x].weight+HTree[y].weight; HTree[i].LChild=x; HTree[i].RChild=y; HTree[i].parent=-1; } } 时间复杂度为O(n2) voidHuffman: : SelectMin(HNode*hTree,intn,int&i1,int&i2) { inti; //找一个比较值的起始值 for(i=0;i {if(hTree[i].parent==-1) {i1=i;break;} } i++; for(;i {if(hTree[i].parent==-1) {i2=i;break;} } if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的 {intj=i2;i2=i1;i1=j;} //开始找最小的两个 i++; for(;i {if(hTree[i].parent==-1 &&hTree[i].weight {i2=i1;i1=i;} elseif(hTree[i].parent==-1 &&hTree[i].weight {i2=i;} } } 时间复杂度为O(n) (3)创建编码表 算法过程: 从叶子到根---自底向上 首先定义码表存储空间; 循环对n个叶子结点自底向上回溯到根,记下途径的左右关系,形成编码的逆序串; 将各个叶子结点对应的逆序串反序即可。 voidHuffman: : CreateCodeTable() { HCodeTable=newHCode[n];//生成编码表 for(inti=0;i { HCodeTable[i].data=l[i]; intchild=i;//孩子结点编号 intparent=HTree[i].parent;//当前结点的父结点编号 intk=0; while(parent! =-1) { if(child==HTree[parent].LChild)//左孩子标‘0’ HCodeTable[i].code[k]='0'; else HCodeTable[i].code[k]='1';//右孩子标‘1’ k++; child=parent;//迭代 parent=HTree[child].parent; } HCodeTable[i].code[k]='\0'; Reverse(HCodeTable[i].code);//将编码字符逆置 } } 时间复杂度为O(n) (4)生成编码串 将输入的字符串的每一个字符与编码表比较 voidHuffman: : Encode(char*d)//编码,d为编码后的字符串 { char*s=str; while(*s! ='\0') { for(inti=0;i if(*s==HCodeTable[i].data) { strcat(d,HCodeTable[i].code); break; } s++; } } 时间复杂度为O(n) (5)解码: 算法过程: 从根到叶子---自顶向下 基于huffman树存储数组,从根结点开始,依据输入待解码串s中码字0或1,分别向左或右跟踪至叶子结点,叶子结点对应的字符(见码表),即为解码得到的字符; 只要s串为结束,重复上述过程 voidHuffman: : Decode(char*s,char*d)//解码,s为编码串,d为解码后的字符串 { while(*s! ='\0') { intparent=2*n-2;//根结点在HTree中的下标 while(HTree[parent].LChild! =-1)//如果不是叶子结点 { if(*s=='0') parent=HTree[parent].LChild; else parent=HTree[parent].RChild; s++; } *d=HCodeTable[parent].data; d++; } } 时间复杂度为O(n) 2.3其他 (1)哈夫曼树的输出是以凹入表示法来实现的,具体算法如下: voidHuffman: : Print(inti,intm) { if(HTree[i].LChild==-1) cout< else { cout< Print(HTree[i].LChild,m+1); Print(HTree[i].RChild,m+1); } } (2)统计字符頻数时,利用字符的ASCII码进行计数统计,调用了cin.get()函数 3.程序运行 程序框图: 程序源代码: #include #include usingnamespacestd; structHNode { intweight;//结点权值 intparent;//双亲指针 intLChild;//左孩子指针 intRChild;//右孩子指针 }; structHCode { chardata; charcode[100]; }; classHuffman { private: HNode*HTree;//Huffman树 HCode*HCodeTable;//Huffman编码表 charstr[1024];//输入的原始字符串 charl[256];//叶子节点对应的字符 inta[256];//记录每个出现的字符的个数 public: intn;//叶子节点数 voidInit();//初始化 voidCreateHTree();//创建huffman树 voidCreateCodeTable();//创建编码表 voidPrintTable(); voidEncode(char*d);//编码 voidDecode(char*s,char*d);//解码 voidPrint(inti,intm);//打印Huffman树 voidSelectMin(HNode*hTree,intn,int&i1,int&i2);//找出最小的两个权值 voidReverse(char*s);//逆序 voidCompare(char*d);//比较压缩大小 ~Huffman();//析构 }; voidHuffman: : Init() { intnNum[256]={0};//记录每一个字符出现的次数 intch=cin.get(); inti=0; while((ch! ='\r')&&(ch! ='\n')) { nNum[ch]++;//统计字符出现的次数 str[i++]=ch;//记录原始字符串 ch=cin.get();//读取下一个字符 } str[i]='\0'; n=0; for(i=0;i<256;i++) { if(nNum[i]>0)//若nNum[i]==0,字符未出现 { l[n]=(char)i; a[n]=nNum[i]; n++; } } } voidHuffman: : CreateHTree() { HTree=newHNode[2*n-1];//根据权重数组a[0..n-1]初始化Huffman树 for(intj=0;j { HTree[j].weight=a[j]; HTree[j].LChild=HTree[j].RChild=HTree[j].parent=-1; } intx,y; for(inti=n;i<2*n-1;i++)//开始建Huffman树 { SelectMin(HTree,i,x,y);//从1~i中选出两个权值最小的结点 HTree[x].parent=HTree[y].parent=i; HTree[i].weight=HTree[x].weight+HTree[y].weight; HTree[i].LChild=x; HTree[i].RChild=y; HTree[i].parent=-1; } } voidHuffman: : SelectMin(HNode*hTree,intn,int&i1,int&i2) { inti; //找一个比较值的起始值 for(i=0;i {if(hTree[i].parent==-1) {i1=i;break;} } i++; for(;i {if(hTree[i].parent==-1) {i2=i;break;} } if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的 {intj=i2;i2=i1;i1=j;} //开始找最小的两个 i++; for(;i {if(hTree[i].parent==-1 &&hTree[i].weight {i2=i1;i1=i;} elseif(hTree[i].parent==-1 &&hTree[i].weight {i2=i;} } } voidHuffman: : Print(inti,intm) { if(HTree[i].LChild==-1) cout< else { cout< Print(HTree[i].LChild,m+1); Print(HTree[i].RChild,m+1); } } voidHuffman: : CreateCodeTable() { HCodeTable=newHCode[n];//生成编码表 for(inti=0;i { HCodeTable[i].data=l[i]; intchild=i;//孩子结点编号 intparent=HTree[i].parent;//当前结点的父结点编号 intk=0; while(parent! =-1) { if(child==HTree[parent].LChild)//左孩子标‘0’ HCodeTable[i].code[k]='0'; else HCodeTable[i].code[k]='1';//右孩子标‘1’ k++; child=parent;//迭代 parent=HTree[child].parent; } HCodeTable[i].code[k]='\0'; Reverse(HCodeTable[i].code);//将编码字符逆置 } } voidHuffman: : PrintTable() { for(inti=0;i cout< } voidHuffman: : Encode(char*d)//编码,d为编码后的字符串 { char*s=str; while(*s! ='\0') { for(inti=0;i if(*s==HCodeTable[i].data) { strcat(d,HCodeTable[i].code); break; } s++; } } voidHuffman: : Decode(char*s,char*d)//解码,s为编码串,d为解码后的字符串 { while(*s! ='\0') { intparent=2*n-2;//根结点在HTree中的下标 while(HTree[parent].LChild! =-1)//如果不是叶子结点 { if(*s=='0') parent=HTree[parent].LChild; else parent=HTree[parent].RChild; s++; } *d=HCodeTable[parent].data; d++; } } voidHuffman: : Reverse(char*s)//换序 { charch; intlen=strlen(s); for(inti=0;i { ch=s[i]; s[i]=s[len-i-1]; s[len-i-1]=ch; } } voidHuffman: : Compare(char*d)//比较压缩大小 { cout<<"编码前: "< cout<<"编码后: "< } Huffman: : ~Huffman()//析构函数 { delete[]HTree; delete[]HCodeTable; } voidmain() { HuffmanHFCode; chard[1024]={0}; chars[1024]={0}; cout<<"请输入要编码的字符串: "; HFCode.Init(); HFCode.CreateHTree(); HFCode.CreateCodeTable(); HFCode.Encode(d); HFCode.Decode(d,s); intm; cout<<"欢迎使用\n"<<"1.打印哈夫曼树\n"<<"2.打印哈夫曼编码表\n"<<"3.打印编码\n"<<"4.打印解码\n"<<"5.压缩比"< while (1) {cin>>m; switch(m) { case1: { HFCode.Print(2*HFCode.n-2,1); break; } case2: { HFCode.PrintTable(); break; } case3: { cout<<"编码结果: "< break; } case4: { cout<<"解码结果: "< break; } case5: { HFCode.Compare(d); } } } } 运行结果: 4.总结 在编程时,最开始在字符统计时出现了空格无法统计的问题,后来用cin.get()函数进行统计。 最后由于有一些字符没有出现过,所以还需要进行筛选。 在输出哈夫曼树时,采用了凹入函数法进行输出,更加直观。 创建编码表时,开始是自下到上的进行遍历,所以最后还需要进行逆序,形成最终的编码表。 创建编码树的时候,没有正确运用指针的传递,结果出现了很多问题,各种内存访问错误,最后经过细细地从头到尾检查,发现了是在形式参数的地方出现了错误,在获取两个最小权值的结点的时候应该用引用,改过来之后错误没有了。 打印赫夫曼树是最难的部分,一开始没有找到合适的办法,出现了很多问题,最后采用凹入表示打印的方法,从最右边的结点开始一行一行的打印,最后问题也能解决了。 调试时,出现的问题是在进行编码时循环出现了错误,导致运行后编码变少,通过修改问题得以解决。 通过哈夫曼编码的程序设计,更加深入的学习了哈夫曼树编码的思想,了解了不等长编码的思想,同时也通过实践明白了编码器的原理,在编码过程中,面对出现的问题,也学习了字符串的相关函数的运用,更加了解树的存储结构,受益匪浅。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北邮信通院 数据结构 实验 报告 三哈夫曼 编码器 欧阳 光明 创编