哈夫曼編碼資料

1、哈夫曼編碼譯碼系統(tǒng)需求分析程序的基本功能：構(gòu)造哈夫曼樹(shù)及哈夫曼編碼：從終端讀入字符集大小n、 n 個(gè)字符以及n 個(gè)對(duì)應(yīng)的權(quán)值， 建立哈夫曼樹(shù)；利用已將建好的哈弗曼樹(shù)求每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼，并保存。編碼：利用已構(gòu)造的哈弗曼編碼對(duì)“明文”文件中的正文進(jìn)行編碼，然后將結(jié)果存入“密文”文件中。譯碼：將“密文”文件中的 0、 1 代碼序列進(jìn)行譯碼。打印“密文”文件：將文件以緊湊格式顯示在終端上，同時(shí)，將此字符形式的編碼保存。打印哈夫曼樹(shù): 將已在內(nèi)存中的哈夫曼以凹入表形式顯示在終端上。輸入輸出要求：從鍵盤(pán)接收字符集大小n 、以及 n 個(gè)字符和n 個(gè)權(quán)值；構(gòu)造哈夫曼樹(shù)：將 HFMTree 數(shù)組中的各個(gè)位

2、置的各個(gè)域都添上相關(guān)的值，并將結(jié)構(gòu)體數(shù)組存入文件HTree.txt 中。打印哈夫曼樹(shù)：從 HFMTree 數(shù)組讀取相關(guān)的結(jié)點(diǎn)信息，以凹入表方式將各個(gè)結(jié)點(diǎn)畫(huà)出來(lái)；構(gòu)造哈夫曼編碼：先從文件HTree.txt 中讀入相關(guān)的字符信息進(jìn)行哈夫曼編碼，將字符與其對(duì)應(yīng)的編碼存入文件HNode.txt 中；編碼：利用已構(gòu)造的哈夫曼樹(shù)對(duì)文件進(jìn)行編碼，打印結(jié)果，并將結(jié)果存入新建文件中；譯碼：將密文文件中的內(nèi)容利用HNode.txt 中建立的編碼規(guī)則進(jìn)行翻譯，打印結(jié)果，并將結(jié)果存入新建文件中。測(cè)試數(shù)據(jù)：輸入葉子結(jié)點(diǎn)個(gè)數(shù)為4，權(quán)值集合為1,3,5,7 ，字符集合為A,B,C,D ，且字符集與權(quán)值集合一一對(duì)應(yīng)。概要設(shè)計(jì)

3、抽象數(shù)據(jù)類型的定義： 采用靜態(tài)鏈表作為哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)；求哈夫曼編碼時(shí)使用一維數(shù)組HCode作為哈夫曼編碼信息的存儲(chǔ)。主模塊的流程及各子模塊的主要功能：int main()主菜單；swich 語(yǔ)句結(jié)構(gòu)選擇；return 0;in_park()輸入車牌號(hào)；若停車場(chǎng)已滿，停入便道中，否則停入停車場(chǎng)；output()輸入所要離開(kāi)車輛的車牌號(hào)，以及離開(kāi)時(shí)間； 停在便道內(nèi)的第一輛車進(jìn)入停車場(chǎng)；show_car()依次顯示停車場(chǎng)內(nèi)的車輛信息；show_queue()依次顯示便道內(nèi)的車輛信息；3、模塊之間的層次關(guān)系：主函數(shù)Creatoutputshow_carshow_queuejudge詳細(xì)設(shè)計(jì)1、定義

4、的相關(guān)數(shù)據(jù)類型：哈夫曼樹(shù)結(jié)點(diǎn)：typedef structint weight;int park;int lchild;int rchild;char ch;哈弗曼編碼結(jié)點(diǎn)：typedef structCar ParkMAX_PARK;int top;ParkStack;2、函數(shù)的調(diào)用關(guān)系：mainin_parkoutputshow_carshow_queuejudge調(diào)試分析調(diào)試中遇到的問(wèn)題及對(duì)問(wèn)題的解決方法：遇到的問(wèn)題：編碼時(shí)最后一位總是多出一位數(shù)字；編碼時(shí)出現(xiàn)無(wú)限循環(huán)；解決方法：改變構(gòu)造哈夫曼樹(shù)時(shí)的循環(huán)條件；改變構(gòu)造哈夫曼編碼的循環(huán)條件；使用說(shuō)明及測(cè)試結(jié)果1、使用說(shuō)明：進(jìn)入主菜單，選擇所

5、要進(jìn)行的操作；構(gòu)造哈夫曼樹(shù)：輸入葉結(jié)點(diǎn)個(gè)數(shù)，及其字符與權(quán)值；選擇顯示哈夫曼樹(shù)，哈夫曼樹(shù)以凹入表形式顯示；選擇構(gòu)造哈夫曼編碼，即構(gòu)造哈夫曼編碼，若成功，則顯示成功；選擇編碼：選擇進(jìn)行鍵盤(pán)輸入或者從文件中獲取。2、測(cè)試結(jié)果：停車場(chǎng)容量為5,連續(xù)有7輛車到來(lái)，牌照號(hào)分別為 f001、f002、f003、f004、f005、 f006、f007 ,前5輛車進(jìn)入停車場(chǎng) 1-5號(hào)車位，第6、7輛車停入便道的1、2號(hào)位置上。牌 照號(hào)為f003的車輛從停車場(chǎng)開(kāi)走后，f006從便道進(jìn)入停車場(chǎng)，便道上只剩 f007。偽碼算法#include #include #include#include#include#in

6、clude #include stdlib.h#define N #define MAXVSLUE 1000typedef structchar letter;int weight;int parent;int lchild;int rchild;HNodeType;HNodeType HNode2*N-1;#define MAXBIT 10typedef structchar bitMAXBIT;int start;HCodeType;HCodeType HCodeN;void Creat_HuffMtree(HNodeType HFMTree,int n) ;/* 構(gòu)造哈夫曼樹(shù) */voi

7、d HaffmanConde(HNodeType HFMTree, HCodeType HuffCode);void Display();void makecode1(char sMAXVSLUE);void makecode2(char sMAXVSLUE);void yicode1();void yicode2();void Dis1();void Dis2();void printing(int root,int length);void main()coutI*歡迎進(jìn)入編譯器系統(tǒng)endl;*”Display();for(;)char ch;char c=getch();if(c=4)b

8、reak;switch(c)case 1:Dis2();ch=getch();switch(ch)case 1:Creat_HuffMtree(HNode,N) ;HaffmanConde(HNode,HCode);break;case 2:cout 此哈夫曼樹(shù)的凹入法表示為endl;printing(2*N-2,0);break;Display();break;case 2:Dis1();ch=getch();char sMAXVSLUE;switch(ch)case 1:makecode1(s);break;case 2:makecode2(s);break;Display();break

9、;case 3:Dis1();ch=getch();switch(ch)case 1:break;yicode1();case 2:yicode2();break;Display();break;void Creat_HuffMtree(HNodeType HFMTree,int n)/* 構(gòu)造哈夫曼樹(shù) */* 構(gòu)造的哈夫曼樹(shù)存儲(chǔ)于HFMTree，n 為葉子結(jié)點(diǎn)的個(gè)數(shù)*/int m1,x1,m2,x2;/* x1和x2存儲(chǔ)最小和次小權(quán)值，ml和m2存儲(chǔ)其位置 */int i,j;for(i=0;i2*n-1;i+)/* HFMTre創(chuàng)始化 */HFMTreei.weight=0;HFMTree

10、i.parent=-1;HFMTreei.lchild=-1;HFMTreei.rchild=-1;for(i=0;iN;i+)HFMTreei.letter=NULL;cout依次輸入vvnvv”個(gè)葉子結(jié)點(diǎn)的符號(hào)和權(quán)侑endl;for(i=0;in;i+)(cout Ai+1個(gè)葉子符號(hào)cinHFMT reei. letter;cout輸入vvi+lvv個(gè)葉子權(quán)值cinHFMT reei.weight;/*出入n個(gè)葉子結(jié)點(diǎn)的權(quán)值，設(shè)為整型*/for(i=0;in-1;i+)/* 構(gòu)造哈夫曼樹(shù) */(x1=x2=MAXVSLUE;m1=m2=0;for(j=0;jn+i;j+)(if(HFMTr

11、eej.parent=-1 & HFMTreej.weightx1)(/*找出根結(jié)點(diǎn)具有最小和此最小權(quán)值的兩棵樹(shù)*/x2=x1;m2=m1;x1=HFMTreej.weight;m1=j;else if(HFMTreej.parent=-1 & HFMTreej.weightx2)x2=HFMTreej.weight;m2=j;/* 將找出的兩棵子樹(shù)合并成一棵樹(shù)*/HFMTreem1.parent=n+i;HFMTreem2.parent=n+i;HFMTreen+i.weight=HFMTreem1.weight+HFMTreem2.weight;HFMTreen+i.letter=z-i;

12、HFMTreen+i.lchild=m1;HFMTreen+i.rchild=m2;HFMTreen+i.parent=-1;FILE *fptr;if(fptr=fopen(HTree.txt,w)!=NULL)fprintf(fptr,letterweigth lchild rchildparentn);for(i=0;i2*N-1;i+ )fprintf(fptr,%d%c%d%d%d%dn ,i,HFMTreei.letter,HFMTreei.weight, HFMTreei.lchild,HFMTreei.rchild,HFMTreei.parent );elseprintf( 文

13、件打開(kāi)失敗);fclose(fptr);printf(letter weigth lchild rchild parentn);for(i=0;i2*N-1;i+ )printf(%d%c%d%d %d%dn ,i,HFMTreei.letter,HFMTreei.weight, HFMTreei.lchild,HFMTreei.rchild,HFMTreei.parent );void HaffmanConde(HNodeType HFMTree, HCodeType HUffCode) FILE *fptr1,*fptr2;fptr1=fopen(HTree.txt,a);if(fptr1

14、=NULL)printf( 文件打開(kāi)失敗);HCodeType cd;int i,j,c,p;for(i=0;iN;i+)cd.start=MAXBIT-1;c=i;fscanf(fptr1 , %d%d%d%d,&HFMTreei.weight,&HFMTreei.lchild,&HFMTreei.rchild,&HFMTreei.parent );p=HFMTreec.parent;while(p!=-1)if(HFMTreep.lchild=c)cd.bitcd.start=0;else cd.bitcd.start=1;cd.start-;c=p;p=HFMTreec.parent;f

15、or(j=cd.start+1;jMAXBIT;j+)HUffCodei.bitj=cd.bitj;HUffCodei.start=cd.start+1;fclose(fptr1);printf( 字符權(quán)值代碼 n);if(fptr2=fopen(HNode.txt,w)!=NULL)for(i=0;iN;i+)fprintf(fptr2,%c,HFMTreei.letter);printf(%c,HFMTreei.letter);printf(%d,HFMTreei.weight);for(j=HUffCodei.start;jMAXBIT;j+)fprintf(fptr2,%d,HUffC

16、odei.bitj);for(j=HUffCodei.start;jfile;ptr=fopen(file,r);if(ptr=NULL)printf( 文件打開(kāi)失敗);for(i=0;ifile;ptr=fopen(file,w);n=strlen(s);for(i=0;in;i+)for(j=0;jN;j+)if(si=HNodej.letter)break;for(m=HCodej.start;mMAXBIT;m+)fprintf(ptr,%d,HCodej.bitm);printf(%d,HCodej.bitm);fclose(ptr);printf(n);void makecode2

17、(char sMAXVSLUE)char file100;FILE *ptr;int n,i,j,m;printf( 輸入要編碼的字符串：);scanf(%s,s);n=strlen(s);for(i=0;in;i+)for(j=0;jN;j+)if(si=HNodej.letter)break;for(m=HCodej.start;mfile;ptr=fopen(file,w);n=strlen(s);for(i=0;in;i+)for(j=0;jN;j+)if(si=HNodej.letter)break;for(m=HCodej.start;mMAXBIT;m+) fprintf(ptr

18、,%d,HCodej.bitm);fclose(ptr);printf(n);printf(n);void yicode1()int i,c=2*N-2;char sMAXVSLUE;char file100;for(i=0;ifile;ptr=fopen(file,r);if(ptr=NULL)printf（ 文件打開(kāi)失?。?ch0=fgetc(ptr);while(ch0!=EOF)strcat(s,ch);ch0=fgetc(ptr);fclose(ptr);printf( 輸入保存譯文的文件名);cinfile;ptr=fopen(file,w);if(ptr=NULL)printf(

19、 文件打開(kāi)失敗);i=0;while(si!=NULL)if(si=0)c=HNodec.lchild;if(HNodec.lchild=-1 & HNodec.rchild=-1)printf(%c,HNodec.letter);fprintf(ptr,%c,HNodec.letter);c=2*N-2;else if(si=1)c=HNodec.rchild;if(HNodec.lchild=-1 & HNodec.rchild=-1)printf(%c,HNodec.letter);fprintf(ptr,%c,HNodec.letter);c=2*N-2;i+;printf(譯碼成功,密文在s文件中n”,file);fclose(ptr);void yicode2()char file100;FILE *ptr;int i,c=2*N-2;char sMAXVSLUE;for(i=0;ifile;ptr=fopen(file,w);if(ptr=NULL)prin