无损压缩编码实验

1、无损压缩编码实验实验报告一、 实验题目：无损压缩编码实验二、 实验要求：任选一种无损编码方式，通过C+编程实现。（1） 字符串的输入是手工输入的。（2） 通过程序实现编码，最终在屏幕上现实编码结果。三，实验分析 采用霍夫曼编码实现无损压缩编码，从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码，并算出平均码长。四，主要编码原理五，源程序代码#include <iostream>using namespace std;class HuffmanTree/霍夫曼树结构public: un

2、signed 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(temp

3、2=0)temp2=HTi.Weight;(*s2)=i; if(temp2<temp1)temp3=temp2; temp2=temp1; temp1=temp3;temp3=(*s2); (*s2)=(*s1); (*s1)=temp3; elseif(HTi.Weight<temp1)temp2=temp1;temp1=HTi.Weight; (*s2)=(*s1);(*s1)=i;if(HTi.Weight>temp1&&HTi.Weight<temp2)temp2=HTi.Weight; (*s2)=i; void HuffmanCoding(

4、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

5、=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

6、= 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&

7、#39; (*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) return i; return -1;void Quanzhi(char *Data,int Length,char *WhatLetter,int *Weig

8、ht,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+; else Index=LookFor(Letter,Datai,AllCount); if(Index=-1) LetterAllCount=Datai

9、; LetterCountAllCount=1; AllCount+; elseLetterCountIndex+; for(i=0;i<AllCount;i+)/计算平均码长 Sum=Sum+LetterCounti; (*Weight) = new intAllCount; (*WhatLetter) = new charAllCount; for(i=0;i<AllCount;i+) Persent=(float)LetterCounti/(float)Sum; (*Weight)i=(int)(100*Persent); (*WhatLetter)i=Letteri; (*

10、Count)=AllCount;delete Letter;delete LetterCount;int main()/主函数调用HuffmanTree * HT = NULL;HuffmanCode HC; char Data100;/储存输入的字符串char *Letter;int *Weight;int Count;cout<<"*欢迎使用霍夫曼编码器*"<<endl;cout<<"请输入一行字符串:"<<endl;cin>>Data;cout<<endl;Quanzhi(Da

11、ta,strlen(Data),&Letter, &Weight,&Count);HuffmanCoding(HT, &HC, Weight, Count);cout<<"字符出现频率和编码结果"<<endl;double K=0;double L;char P100;for(int i = 0; i<Count; i+)cout<<Letteri<<" "/字符cout<<Weighti<<"%t"/出现频率cout<<HCi+1<<endl;/霍夫曼码strcpy(P,HCi+1);L=strlen(P);K=K+L*Weighti/100;cout<<"平均码长"<<K;cout<<endl;system(&q