哈弗曼编码实验报告-无损压缩实验报告(共7页)

1、精选优质文档-倾情为你奉上哈弗曼编码实现无损压缩实验报告一、 实验内容通过C+编程实现。要求：1) 字符串的输入是手工输入的；2) 通过程序实现编码，最终在屏幕上显示编码结果，例如，如果选用huffman编码，则要显示字符串的编码以及平均码长；二、 源代码#include<iostream.h>#include<math.h>#include<string.h>#include<stdlib.h>#if !defined _HUFFMANTREE_H_#define _HUFFMANTREE_H_class HuffmanTreepublic:

2、unsigned int Weight; unsigned int Parent; unsigned int lChild; unsigned int rChild;typedef char *HuffmanCode;/*从结点集合中选出权值最小的两个结点将值分别赋给s1和s2*/void Select(HuffmanTree* HT,int Count,int *s1,int *s2) unsigned int temp1=0; unsigned int temp2=0; unsigned int temp3; for(int i=1;i<=Count;i+) if(HTi.Paren

3、t=0) if(temp1=0) temp1=HTi.Weight; (*s1)=i; else if(temp2=0) temp2=HTi.Weight; (*s2)=i; if(temp2<temp1) temp3=temp2; temp2=temp1; temp1=temp3; temp3=(*s2); (*s2)=(*s1); (*s1)=temp3; else if(HTi.Weight<temp1) temp2=temp1; temp1=HTi.Weight; (*s2)=(*s1); (*s1)=i; if(HTi.Weight>temp1&&H

4、Ti.Weight<temp2) temp2=HTi.Weight; (*s2)=i; /*霍夫曼编码函数*/void HuffmanCoding(HuffmanTree * HT, HuffmanCode * HC, int *Weight, int Count) int i; int s1,s2; int TotalLength; char* cd; unsigned int c; unsigned int f; int start; if(Count<=1) return; TotalLength=Count*2-1;HT = new HuffmanTree(TotalLen

5、gth+1)*sizeof(HuffmanTree); for(i=1;i<=Count;i+) HTi.Parent=0; HTi.rChild=0; HTi.lChild=0; HTi.Weight=(*Weight); Weight+; for(i=Count+1;i<=TotalLength;i+) HTi.Weight=0; HTi.Parent=0; HTi.lChild=0; HTi.rChild=0; /建造霍夫曼树 for(i=Count+1;i<=TotalLength;+i) Select(HT, i-1, &s1, &s2); HTs1

6、.Parent = i; HTs2.Parent = i; HTi.lChild = s1; HTi.rChild = s2; HTi.Weight = HTs1.Weight + HTs2.Weight; /输出霍夫曼编码 (*HC)=(HuffmanCode)malloc(Count+1)*sizeof(char*); cd = new charCount*sizeof(char); cdCount-1='0' for(i=1;i<=Count;+i) start=Count-1; for(c = i,f = HTi.Parent; f != 0; c = f, f

7、= HTf.Parent) if(HTf.lChild = c) cd-start='0' else cd-start='1' (*HC)i = new char (Count-start)*sizeof(char); strcpy(*HC)i, &cdstart); delete HT;delete cd;/* 在字符串中查找某个字符* 如果找到，则返回其位置*/int LookFor(char *str, char letter, int count) int i; for(i=0;i<count;i+) if(stri=letter) ret

8、urn i; return -1;void OutputWeight(char *Data,int Length, char *WhatLetter, int *Weight,int *Count) int i; char* Letter = new charLength; int* LetterCount = new intLength; int AllCount=0; int Index; int Sum=0; float Persent=0; for(i=0;i<Length;i+) if(i=0) Letter0=Datai; LetterCount0=1; AllCount+;

9、 else Index=LookFor(Letter,Datai,AllCount); if(Index=-1) LetterAllCount=Datai; LetterCountAllCount=1; AllCount+; else LetterCountIndex+; for(i=0;i<AllCount;i+) Sum=Sum+LetterCounti; (*Weight) = new intAllCount; (*WhatLetter) = new charAllCount; for(i=0;i<AllCount;i+) Persent=(float)LetterCount

10、i/(float)Sum; (*Weight)i=(int)(1000*Persent); (*WhatLetter)i=Letteri; (*Count)=AllCount;delete Letter;delete LetterCount;#endif/*main.cppvoid main() HuffmanTree * HT = NULL; HuffmanCode HC; char Data100; char *WhatLetter; int *Weight; int Count;cout<<"请输入一行文本数据:"<<endl; cin>>Data; cout<<endl; OutputWeight(Data,strlen(Data),&WhatLetter,&Weight,&Count);HuffmanCoding(HT, &HC, Weight, Count);cout<<"字符 出现频率 编码结果"<<endl; int k=0; for(int i = 0; i<Count; i+) cout<<WhatLetteri<<" " cout<<