無(wú)損壓縮編碼實(shí)驗(yàn)

1、無(wú)損壓縮編碼實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告一、 實(shí)驗(yàn)題目：無(wú)損壓縮編碼實(shí)驗(yàn)二、 實(shí)驗(yàn)要求：任選一種無(wú)損編碼方式，通過(guò)C+編程實(shí)現(xiàn)。（1） 字符串的輸入是手工輸入的。（2） 通過(guò)程序?qū)崿F(xiàn)編碼，最終在屏幕上現(xiàn)實(shí)編碼結(jié)果。三，實(shí)驗(yàn)分析 采用霍夫曼編碼實(shí)現(xiàn)無(wú)損壓縮編碼，從鍵盤(pán)輸入若干字符及每個(gè)字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結(jié)點(diǎn)的權(quán)值，建立哈夫曼樹(shù)，然后對(duì)各個(gè)字符進(jìn)行哈夫曼編碼，最后打印輸出字符及對(duì)應(yīng)的哈夫曼編碼，并算出平均碼長(zhǎng)。四，主要編碼原理五，源程序代碼#include <iostream>using namespace std;class HuffmanTree/霍夫曼樹(shù)結(jié)構(gòu)public: un

2、signed int Weight, Parent, lChild, rChild;typedef char *HuffmanCode;void Select(HuffmanTree* HT,int Count,int *s2,int *s1)/從結(jié)點(diǎn)集合中選出權(quán)值最小的兩個(gè)結(jié)點(diǎn) 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)/霍夫曼編碼函數(shù)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;/父節(jié)點(diǎn)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; /建造霍夫曼樹(shù) 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)/在字符串中查找某個(gè)字符,如果找到，則返回其位置 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)/計(jì)算權(quán)值并輸出 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+)/計(jì)算平均碼長(zhǎng) 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()/主函數(shù)調(diào)用HuffmanTree * HT = NULL;HuffmanCode HC; char Data100;/儲(chǔ)存輸入的字符串char *Letter;int *Weight;int Count;cout<<"*歡迎使用霍夫曼編碼器*"<<endl;cout<<"請(qǐng)輸入一行字符串:"<<endl;cin>>Data;cout<<endl;Quanzhi(Da

11、ta,strlen(Data),&Letter, &Weight,&Count);HuffmanCoding(HT, &HC, Weight, Count);cout<<"字符出現(xiàn)頻率和編碼結(jié)果"<<endl;double K=0;double L;char P100;for(int i = 0; i<Count; i+)cout<<Letteri<<" "/字符cout<<Weighti<<"%t"/出現(xiàn)頻率cout<<HCi+1<<endl;/霍夫曼碼strcpy(P,HCi+1);L=strlen(P);K=K+L*Weighti/100;cout<<"平均碼長(zhǎng)"<<K;cout<<endl;system(&q