哈弗曼編碼實驗報告-無損壓縮實驗報告

1、精品哈弗曼編碼實現(xiàn)無損壓縮實驗報告一、實驗內(nèi)容通過 C+ 編程實現(xiàn)。要求： 1) 字符串的輸入是手工輸入的；2) 通過程序?qū)崿F(xiàn)編碼， 最終在屏幕上顯示編碼結(jié)果， 例如，如果選用 huffman 編碼，則要顯示字符串的編碼以及平均碼長；二、源代碼#include<iostream.h>#include<math.h>#include<string.h>#include<stdlib.h>#if !defined _HUFFMANTREE_H_#define _HUFFMANTREE_H_class HuffmanTreepublic:unsigne

2、d int Weight;unsigned int Parent;-可編輯 -精品unsigned int lChild;unsigned int rChild;typedef char *HuffmanCode;/* 從結(jié)點集合中選出權(quán)值最小的兩個結(jié)點將值分別賦給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)

3、if(temp1=0)temp1=HTi.Weight;(*s1)=i;elseif(temp2=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

4、<temp2)temp2=HTi.Weight;(*s2)=i;/* 霍夫曼編碼函數(shù)*/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(H

5、uffmanTree);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.Pare

6、nt = 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)

7、cd-start='0'elsecd-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) return i;return -1;void OutputWeight

8、(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+;elseIndex=LookFor(Letter,Datai,AllCount)

9、;if(Index=-1)-可編輯 -精品LetterAllCount=Datai;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)(1000*Persent);-可

10、編輯 -精品(*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<<"請輸入一行文本數(shù)據(jù):"<<endl;cin>>Data;-可編輯 -精品cout<<endl;OutputWeight(Data,strlen(Data),&WhatLetter,&Weight,&Count);HuffmanCoding(HT, &HC, Weight, Count);cout<<"字符出現(xiàn)頻率編碼結(jié)果 "<<endl;int k=0;for(int i = 0; i<Count; i+)cout<<WhatLetteri<<""cout<<Weight