「无损压缩编码实验」.doc

无损压缩编码实验实验报告一、 实验题目：无损压缩编码实验二、 实验要求：任选一种无损编码方式，通过C+编程实现。（1） 字符串的输入是手工输入的。（2） 通过程序实现编码，最终在屏幕上现实编码结果。三，实验分析 采用霍夫曼编码实现无损压缩编码，从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码，并算出平均码长。四，主要编码原理五，源程序代码#include using namespace std;class HuffmanTree/霍夫曼树结构public: unsigned int Weight, Parent, lChild, rChild;typedef char *HuffmanCode;void Select(HuffmanTree* HT,int Count,int *s2,int *s1)/从结点集合中选出权值最小的两个结点 unsigned int temp1=0; unsigned int temp2=0; unsigned int temp3; for(int i=1;i=Count;i+) if(HTi.Parent=0)if(temp1=0) temp1=HTi.Weight; (*s1)=i; else if(temp2=0)temp2=HTi.Weight;(*s2)=i; if(temp2temp1)temp3=temp2; temp2=temp1; temp1=temp3;temp3=(*s2); (*s2)=(*s1); (*s1)=temp3; elseif(HTi.Weighttemp1&HTi.Weighttemp2)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(TotalLength+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.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 = 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;icount;i+) if(stri=letter) return i; return -1;void Quanzhi(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;iLength;i+) if(i=0) Letter0=Datai; LetterCount0=1; AllCount+; else Index=LookFor(Letter,Datai,AllCount); if(Index=-1) LetterAllCount=Datai; LetterCountAllCount=1; AllCount+; elseLetterCountIndex+; for(i=0;iAllCount;i+)/计算平均码长 Sum=Sum+LetterCounti; (*Weight) = new intAllCount; (*WhatLetter) = new charAllCount; for(i=0;iAllCount;i+) Persent=(float)LetterCounti/(float)Sum; (*Weight)i=(int)(100*Persent); (*WhatLetter)i=Letteri; (*Count)=AllCount;delete Letter;delete LetterCount;int main()/主函数调用HuffmanTree * HT = NULL;HuffmanCode HC; char Data100;/储存输入的字符串char *Letter;int *Weight;int Count;cout*欢迎使用霍夫曼编码器*endl;cout请输入一行字符串:Data;coutendl;Quanzhi(Data,strlen(Data),&Letter, &Weight,&Count);HuffmanCoding(HT, &HC, Weight, Count);cout字符出现频率和编码结果endl;double K=0;double L;char P100;for(int i = 0; iCount; i+)coutLetteri ;/字符coutWeighti%t;/出现频率coutHCi+1endl;/霍夫曼码strcpy(P,HCi+1);L=strlen(P);K=K+L*Weighti/100;cout平均码长K;coutendl;system(pause);return 0;六