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

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

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

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

4、CDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161（二）系統(tǒng)模塊結構設計通過對系統(tǒng)功能的分析，哈夫曼編碼/譯碼器系統(tǒng)功能如圖1所示。 編 碼 印 代 碼 文 件 印 哈 夫 曼 樹 哈夫曼編碼/譯碼器系統(tǒng) 初 始 化 譯 碼 圖1 哈夫曼編碼/譯碼器系統(tǒng)功能圖通過上圖的功能分析，把整個系統(tǒng)劃分為5個模塊：1、 初始化（Initialization），該模塊主要實現(xiàn)：初始化要編輯的語句，然后語句里面有個調用輸入編碼的語句 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)的設計與實現(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("打印工作結束n");四、系統(tǒng)測試 （一） 測試main函數(shù) （二）測試編

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

12、程序執(zhí)行時的提示性輸出的重要性，編寫程序的時候，應先寫出算法，再寫程序，一段一段調試；此外，學編程一定要親自動手，實踐是檢驗真理正確性的唯一標準，不能眼高手低，還要學會歸納，發(fā)現(xiàn)編程的捷徑，想著用更高效的方法去完成一個個任務。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("字符對應的編碼為: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、與對應編碼寫入根目錄下文件htmTree.txt中nn");void Encoding() printf("下面對目錄下文件tobetran.txt中的字符進行編碼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中的字符進行譯碼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("打印工作結束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("打印工作結束"); 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);