哈夫曼編碼譯碼器系統(tǒng).

1、 目錄1、 系統(tǒng)開發(fā)的背景.(1)2、 系統(tǒng)分析與設(shè)計.(1)3、 系統(tǒng)的設(shè)計與實現(xiàn).(2)（一）設(shè)計初始化（Initialization）.(2)（二）設(shè)計編碼（Encoding）.(3)（三）設(shè)計譯碼（Decoding）.(3)（四）設(shè)計印代碼文件（Print）.(4)（五）設(shè)計印哈夫曼樹（TreePrinting）.(4)4、 系統(tǒng)測試.(5)（一）測試main函數(shù).(5)（二）測試編碼（Encoding）及譯碼（Decoding）函數(shù).(5)（三）測試印代碼文件（Print）函數(shù).(6)（四）測試相關(guān)的根目錄.(6)5、 總結(jié).(6)6、 附件（代碼、部分圖表）.(7) 哈夫曼編/譯碼

2、器系統(tǒng)一、系統(tǒng)開發(fā)的背景為了提高信道利用率，縮短信息傳輸時間，降低傳輸成本，且在信息發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在信息接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原），因此設(shè)計哈夫曼編碼/譯碼器系統(tǒng)。二、系統(tǒng)分析與設(shè)計（一）系統(tǒng)功能要求：【任務(wù)要求】I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件To Be Tran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。D：譯碼（Decoding）。利用

3、已建好的哈夫曼樹將文件Code File中的代碼進(jìn)行譯碼，結(jié)果存入文件Text File中。P：印代碼文件（Print）。將文件Code File以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件Code Prin中。T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件Tree Print中?！緶y試數(shù)據(jù)】利用教科書中的數(shù)據(jù)調(diào)試程序。用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符AB

4、CDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161（二）系統(tǒng)模塊結(jié)構(gòu)設(shè)計通過對系統(tǒng)功能的分析，哈夫曼編碼/譯碼器系統(tǒng)功能如圖1所示。 編 碼 印 代 碼 文 件 印 哈 夫 曼 樹 哈夫曼編碼/譯碼器系統(tǒng) 初 始 化 譯 碼 圖1 哈夫曼編碼/譯碼器系統(tǒng)功能圖通過上圖的功能分析，把整個系統(tǒng)劃分為5個模塊：1、 初始化（Initialization），該模塊主要實現(xiàn)：初始化要編輯的語句，然后語句里面有個調(diào)用輸入編碼的語句 len=InputCode();2、 編碼（Encoding），該

5、模塊主要實現(xiàn)：void Encoding(); 3、譯碼（Incoding）,該模塊主要實現(xiàn)： void Decoding(); 4、印代碼文件（Print），該模塊主要實現(xiàn)：由函數(shù)void Code_printing()和函數(shù)void Code_printing1()實現(xiàn)。 5、印哈夫曼樹（TreePrinting），該模塊主要實現(xiàn)： coprint(p,HT);三、系統(tǒng)的設(shè)計與實現(xiàn)（一） 初始化（Initialization），該模塊主要實現(xiàn)void Initialization() int a,k,flag,len; a=0; len=InputCode(); for(i=0;i<

6、len;i+) k=0;flag=1; coui-a.data=stri; coui-a.count=1; while(i>k) if(stri=strk) a+; flag=0; k+; if(flag=0) break; if(flag) for(j=i+1;j<len;j+) if(stri=strj) +coui-a.count; n=len-a; for(i=0;i<n;i+) printf("%d%d ",i,coui.data); printf("%d%dn",i,coui.count); for(i=0;i<=n;

7、i+) *(z+i)=coui.data; *(w+i)=coui.count; （二） 編碼（Encoding），該模塊主要實現(xiàn)void Encoding() char *tran; i=99; tran=(char*)malloc(100*sizeof(char); while(i=99) if(fgets(tran,100,tobetran)=NULL) printf("不能打開文件n"); break; for(i=0;*(tran+i)!='0'i+) for(j=0;j<=n;j+) if(*(z+j-1)=*(tran+i) fputs(

8、HCj,codefile); if(j>n) printf("字符錯誤，無法編碼!n"); break; （三） 譯碼（Decoding），該模塊主要實現(xiàn)void Decoding() char *work,*work2,i2;int i4=0,i,i3;unsigned long length=10000;work=(char*)malloc(length*sizeof(char);fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char);i3=2*n-1;for(i=0;*(work+i-1)

9、!='0'i+) i2=*(work+i);if(HTi3.lchild=0) *(work2+i4)=*(z+i3-1);i4+;i3=2*n-1;i-; else if(i2='0')i3=HTi3.lchild;else if(i2='1') i3=HTi3.rchild;（四） 印代碼文件（Print），該模塊主要實現(xiàn)void Code_printing1() char *work5; work5=(char*)malloc(51*sizeof(char); do if(fgets(work5,51,txtfile)=NULL) prin

10、tf("不能讀取文件n"); break; fputs(work5,CodePrin1); puts(work5); while(strlen(work5)=50); free(work5);（五）印哈夫曼樹（TreePrinting），該模塊主要實現(xiàn)void Tree_printing(HuffmanTree HT,int w) HuffmanTree p; p=HT+w; printf("下面打印哈夫曼樹n"); coprint(p,HT); printf("打印工作結(jié)束n");四、系統(tǒng)測試 （一） 測試main函數(shù) （二）測試編

11、碼（Encoding）及譯碼（Decoding）函數(shù).（二）測試印代碼文件（Print）函數(shù)（四）相關(guān)的根目錄五、總結(jié)系統(tǒng)完成的功能：本程序完成的功能是可以在信息發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在信息接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。系統(tǒng)的不足：本次課程設(shè)計，我認(rèn)為還有很多不足，比如說不能把一個隨機(jī)輸入的字符串中不同字符作為葉子結(jié)點元素，把其在該字符串中出現(xiàn)的次數(shù)作為權(quán)值構(gòu)造一個赫夫曼樹，并得到各個葉子結(jié)點的赫夫曼編碼和整個輸入的字符串的赫夫曼編碼，還有不能夠順利按題目要求寫出相應(yīng)的文件，將編碼存儲在tex文件中。 我的收獲是：通過本次實驗，提高了自已調(diào)試程序的能力，充分體會到了在

12、程序執(zhí)行時的提示性輸出的重要性，編寫程序的時候，應(yīng)先寫出算法，再寫程序，一段一段調(diào)試；此外，學(xué)編程一定要親自動手，實踐是檢驗真理正確性的唯一標(biāo)準(zhǔn)，不能眼高手低，還要學(xué)會歸納，發(fā)現(xiàn)編程的捷徑，想著用更高效的方法去完成一個個任務(wù)。6、 附件（代碼、部分圖表）#include<stdio.h>#include <string.h>#include <malloc.h>#include <stdlib.h>const int UINT_MAX=1000;char str50;typedef struct int weight,K; int parent,

13、lchild,rchild;HTNode,* HuffmanTree;typedef char *HuffmanCode;HuffmanTree HT;HuffmanCode HC;int w50,i,j,n;char z50;int flag=0; int numb=0; struct cou char data; int count;cou50;int min(HuffmanTree t,int i) int j,flag; int k=UINT_MAX; for(j=1;j<=i;j+) if(tj.weight<k&&tj.parent=0) k=tj.we

14、ight,flag=j; tflag.parent=1; return flag;void select(HuffmanTree t,int i,int &s1,int &s2) int j; s1=min(t,i); s2=min(t,i); if(s1>s2) j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd; if(n<=

15、1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;i<=n;+i,+p,+w) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; for(;i<=m;+i,+p) p->parent=0; for(i=n+1;i<=m;+i) select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; H

16、Ti.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1='0' for(i=1;i<=n;i+) start=n-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' HCi=(char*)malloc(n-start)*sizeo

17、f(char); strcpy(HCi,&cdstart); free(cd); int InputCode() FILE *tobetran; if(tobetran=fopen("tobetran.txt","w")=NULL) printf("不能打開文件n"); return 0; printf("請輸入你想要編碼的字符n"); gets(str); fputs(str,tobetran); printf("獲取報文成功n"); fclose(tobetran); return

18、strlen(str);void Initialization() int a,k,flag,len; a=0; len=InputCode(); for(i=0;i<len;i+) k=0;flag=1; coui-a.data=stri; coui-a.count=1; while(i>k) if(stri=strk) a+; flag=0; k+; if(flag=0) break; if(flag) for(j=i+1;j<len;j+) if(stri=strj) +coui-a.count; n=len-a; for(i=0;i<n;i+) printf(&

19、quot;%d%d ",i,coui.data); printf("%d%dn",i,coui.count); for(i=0;i<=n;i+) *(z+i)=coui.data; *(w+i)=coui.count; HuffmanCoding(HT,HC,w,n); printf("字符對應(yīng)的編碼為:n"); for(i=1;i<=n;i+) puts(HCi); printf("下面將哈夫曼編碼寫入文件n.nn"); FILE *htmTree; char r=' ','0'

20、 if(htmTree=fopen("htmTree.txt","w")=NULL) printf("can not open filen"); return; fputs(z,htmTree); for(i=0;i<n+1;i+) fprintf(htmTree,"%6d",*(w+i); fputs(r,htmTree); for(i=1;i<=n;i+) fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree); printf("已將字符

21、與對應(yīng)編碼寫入根目錄下文件htmTree.txt中nn");void Encoding() printf("下面對目錄下文件tobetran.txt中的字符進(jìn)行編碼n"); FILE *tobetran,*codefile; if(tobetran=fopen("tobetran.txt","rb")=NULL) printf("不能打開文件n"); if(codefile=fopen("codefile.txt","wb")=NULL) printf("

22、不能打開文件n"); char *tran; i=99; tran=(char*)malloc(100*sizeof(char); while(i=99) if(fgets(tran,100,tobetran)=NULL) printf("不能打開文件n"); break; for(i=0;*(tran+i)!='0'i+) for(j=0;j<=n;j+) if(*(z+j-1)=*(tran+i) fputs(HCj,codefile); if(j>n) printf("字符錯誤，無法編碼!n"); break;

23、 printf("編碼工作完成nn編碼寫入目錄下的codefile.txt中nn"); fclose(tobetran); fclose(codefile); free(tran);void Decoding() printf("下面對根目錄下文件codefile.txt中的字符進(jìn)行譯碼n"); FILE *codef,*txtfile; if(txtfile=fopen("txtfile.txt","w")=NULL) printf("不能打開文件n"); if (codef=fopen(&q

24、uot;codefile.txt","r")=NULL) printf("不能打開文件n"); char *work,*work2,i2; int i4=0,i,i3; unsigned long length=10000; work=(char*)malloc(length*sizeof(char); fgets(work,length,codef); work2=(char*)malloc(length*sizeof(char); i3=2*n-1; for(i=0;*(work+i-1)!='0'i+) i2=*(work

25、+i); if(HTi3.lchild=0) *(work2+i4)=*(z+i3-1); i4+; i3=2*n-1; i-; else if(i2='0') i3=HTi3.lchild; else if(i2='1') i3=HTi3.rchild; *(work2+i4)='0' fputs(work2,txtfile); printf("譯碼完成n內(nèi)容寫入根目錄下的文件txtfile.txt中nn"); free(work); free(work2); fclose(txtfile); fclose(codef);v

26、oid Code_printing() printf("下面打印根目錄下文件CodePrin.txt中編碼字符n"); FILE * CodePrin,* codefile; if(CodePrin=fopen("CodePrin.txt","w")=NULL) printf("不能打開文件n"); return; if(codefile=fopen("codefile.txt","r")=NULL) printf("不能打開文件n"); return;

27、char *work3; work3=(char*)malloc(51*sizeof(char); do if(fgets(work3,51,codefile)=NULL) printf("不能讀取文件n"); break; fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50); free(work3); printf("打印工作結(jié)束nn"); fclose(CodePrin); fclose(codefile);void Code_printing1() printf("下面打

28、印根目錄下文件txtfile.txt中譯碼字符n"); FILE * CodePrin1,* txtfile; if(CodePrin1=fopen("CodePrin1.txt","w")=NULL) printf("不能打開文件n"); return; if(txtfile=fopen("txtfile.txt","r")=NULL) printf("不能打開文件n"); return; char *work5; work5=(char*)malloc(51*s

29、izeof(char); do if(fgets(work5,51,txtfile)=NULL) printf("不能讀取文件n"); break; fputs(work5,CodePrin1); puts(work5); while(strlen(work5)=50); free(work5); printf("打印工作結(jié)束"); fclose(CodePrin1); fclose(txtfile);void coprint(HuffmanTree start,HuffmanTree HT) if(start!=HT) FILE * TreePrint; if(TreePrint=fopen("TreePrint.txt","a")=NULL) printf("創(chuàng)建文件失敗n"); return; numb+; coprint(HT+start->rchild,HT);