哈弗曼编码实验报告-无损压缩实验报告.doc

精品文档哈弗曼编码实现无损压缩实验报告一、 实验内容通过C+编程实现。要求：1) 字符串的输入是手工输入的；2) 通过程序实现编码，最终在屏幕上显示编码结果，例如，如果选用huffman编码，则要显示字符串的编码以及平均码长；二、 源代码#include#include#include#include#if !defined _HUFFMANTREE_H_#define _HUFFMANTREE_H_class HuffmanTreepublic: 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.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; else if(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 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;iLength;i+) if(i=0) Letter0=Datai; LetterCount0=1; AllCount+; else Index=LookFor(Letter,Datai,AllCount); if(Index=-1) LetterAllCount=Datai; LetterCountAllCount=1; AllCount+; else LetterCountIndex+; 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)(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请输入一行文本数据:Data; coutendl; OutputWeight(Data,strlen(Data),&WhatLetter,&Weight,&Count);HuffmanCoding(HT, &HC, Weight, Count);cout字符 出现频率 编码结果endl; int k=0; for(int i = 0; iCount; i+) coutWhatLetteri ; cou