數(shù)據(jù)結(jié)構(gòu)-哈夫曼編碼器課程設(shè)計(jì)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課程設(shè)計(jì)報(bào)告一. 需求分析1、 一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：（1） I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2） E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。（3） D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。（4） P：印代碼文件（Print）。將文件CodeF

2、ile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件中。（5） T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。2、 利用哈夫曼編譯碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。3、 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運(yùn)行Quito。請用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。4、 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，哈夫曼樹已經(jīng)在

3、內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。二、概要設(shè)計(jì)1、部分函數(shù) 1） 樹與編碼類型struct HTNode2） 選兩個(gè)最小的樹組成二叉樹Void Select(HNode *HT,int I,int &s1,int &s2)3) 初始化哈夫曼樹 void Initialization(HTNode *&HT,HuffmanCode *&HC,int *&w,char *&x,int &n)4) 輸出哈夫曼樹 void TreePrint(HTNode *HT,int n)5) 輸出哈夫曼編碼

4、 void CodePrint(HuffmanCode *HC,int n)2、主函數(shù) void main() 初始化; Switch() end;3、模塊之間的調(diào)用關(guān)系 三、詳細(xì)設(shè)計(jì)1、樹的結(jié)構(gòu)體的建立 struct HTNode int weight,parent,lchild,rchild; char zifu;struct HuffmanCode char *code; char zifu; int size;2、部分編碼 void Select(HTNode *HT,int i,int &s1,int &s2) int k; for(k=1;k<=i;k+) i

5、f(HTk.parent=0) s1=k; break; for(k=k+1;k<=i;k+) if(HTk.parent=0) s2=k; break; for(k=k+1;k<=i;k+) if(HTk.parent=0) if(HTk.weight<HTs1.weight) if(HTk.weight<HTs2.weight) if(HTs2.weight<HTs1.weight) s1=s2; s2=k; else s2=k; else s1=s2; s2=k; else if(HTk.weight<HTs2.weight) s2=k; void H

6、uffmanCoding(HTNode *&HT,HuffmanCode *&HC,char *x,int *w,int n) if(n<=1)return; int m=2*n-1,i,s1,s2; HTNode *p; HT=(HTNode *)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;i<=n;i+,p+,w+,x+) p->weight=*w,p->parent=0,p->lchild=0,p->rchild=0,p->zifu=*x; for(;i<=m;i+,p+) p-&g

7、t;weight=0,p->parent=0,p->lchild=0,p->rchild=0,p->zifu='N' for(i=n+1;i<=m;i+) Select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; char *CD; int k,j; CD=(char *)malloc(n*sizeof(char); for(i=1;i<=n;i+) j=i; k=0

8、; while(HTj.parent!=0) if(HTHTj.parent.lchild=j) CDk='0' else CDk='1' k+; j=HTj.parent; HCi-1.code=(char *)malloc(k+1)*sizeof(char); HCi-1.codek='0' k-; int m=k; HCi-1.size=m; for(int l=0;l<=m;l+) HCi-1.codel=CDk; k-; HCi-1.zifu=HTi.zifu; free(CD);int Strsize(char *d) int

9、i=0; while(*d!='0') d+; i+; return i;char* Bianma(HuffmanCode *&HC,char *d)/哈夫曼樹編碼 int n=Strsize(d),i,k,j,sum=0; char *a; a=(char *)malloc(10*n)*sizeof(char); for(i=0;i<n;i+) k=0; while(*d!=HCk.zifu) k+; j=0; while(HCk.codej!='0') asum=HCk.codej; j+; sum+; d+; asum='0'

10、 return a;void Yima(HTNode *HT,char *&a,char *b,int n) int k=2*n-1,i=0; int m=k; while(*b!='0') if(*b='0') if(HTHTm.lchild.lchild=0) ai=HTHTm.lchild.zifu; i+; b+; m=k; else m=HTm.lchild; b+; else if(HTHTm.rchild.lchild=0) ai=HTHTm.rchild.zifu; i+; b+; m=k; else m=HTm.rchild; b+;

11、ai='0'void Initialization(HTNode *&HT,HuffmanCode *&HC,int *&w,char *&x,int &n)/初始化哈夫曼樹 printf("輸入字符集大小nn"); scanf("%d",&n); fflush(stdin); w=(int *)malloc(n*sizeof(int); x=(char *)malloc(n*sizeof(char); for(int i=0;i<n;i+) printf("輸入第%d個(gè)字符

12、和權(quán)值:n",i+1); scanf("%c %d",&xi,&wi); fflush(stdin); HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode); HuffmanCoding(HT,HC,x,w,n);void TreePrint(HTNode *HT,int n)/輸出哈夫曼樹 for(int i=1;i<(2*n);i+) printf("%c %d %d %d %dn",HTi.zifu,HTi.weight,HTi.parent,HTi.lchild,HTi.rc

13、hild);void CodePrint(HuffmanCode *HC,int n)/輸出哈夫曼編碼 for(int i=0;i<n;i+) printf("%c ",HCi.zifu); puts(HCi.code); 3、主程序 void main() HTNode *HT; HuffmanCode *HC; int n,*w; char *x,*y,Z; char *a,*b; a=(char *)malloc(100*sizeof(char); b=(char *)malloc(100*sizeof(char); start: printf("初始

14、化 i，編碼 e，譯碼 d，印哈夫曼碼 p，印哈夫曼樹 t，退出 q。n"); scanf("%c",&Z); fflush(stdin); switch(Z) case 'i': Initialization(HT,HC,w,x,n); goto start; case 'e': gets(a); fflush(stdin); y=Bianma(HC,a); puts(y); goto start; case 'd': gets(b); fflush(stdin); Yima(HT,a,b,n); puts

15、(a); goto start; case 'p': CodePrint(HC,n); goto start; case 't': TreePrint(HT,n); goto start; case 'q': goto end; end: ;4、函數(shù)的調(diào)用關(guān)系圖四、設(shè)計(jì)和調(diào)試分析1、利用哈夫曼編譯碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。2、在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。3、在譯碼時(shí)，由于對程序的不是很

16、了解，把兩個(gè)循環(huán)搞錯(cuò)，最后導(dǎo)致無法正確譯碼。五、用戶手冊1、本程序的運(yùn)行環(huán)境為Windows操作系統(tǒng)，執(zhí)行文件為：Untitled1.exe2、進(jìn)入演示程序后，按要求鍵入。3、之后即顯示文本方式的用戶界面：4、進(jìn)入“初始化命令”后，即提示輸入字符的大小，字符以及權(quán)值。5、進(jìn)入“印代碼文件”命令后，終端顯示哈夫曼編碼6、進(jìn)入“印哈夫曼樹”命令后，終端顯示哈夫曼樹。六、測試結(jié)果七、附錄#include<stdio.h>#include<stdlib.h>struct HTNode int weight,parent,lchild,rchild; char zifu;stru

17、ct HuffmanCode char *code; char zifu; int size;void Select(HTNode *HT,int i,int &s1,int &s2) int k; for(k=1;k<=i;k+) if(HTk.parent=0) s1=k; break; for(k=k+1;k<=i;k+) if(HTk.parent=0) s2=k; break; for(k=k+1;k<=i;k+) if(HTk.parent=0) if(HTk.weight<HTs1.weight) if(HTk.weight<HTs2

18、.weight) if(HTs2.weight<HTs1.weight) s1=s2; s2=k; else s2=k; else s1=s2; s2=k; else if(HTk.weight<HTs2.weight) s2=k; void HuffmanCoding(HTNode *&HT,HuffmanCode *&HC,char *x,int *w,int n) if(n<=1)return; int m=2*n-1,i,s1,s2; HTNode *p; HT=(HTNode *)malloc(m+1)*sizeof(HTNode); for(p=H

19、T+1,i=1;i<=n;i+,p+,w+,x+) p->weight=*w,p->parent=0,p->lchild=0,p->rchild=0,p->zifu=*x; for(;i<=m;i+,p+) p->weight=0,p->parent=0,p->lchild=0,p->rchild=0,p->zifu='N' for(i=n+1;i<=m;i+) Select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi

20、.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; char *CD; int k,j; CD=(char *)malloc(n*sizeof(char); for(i=1;i<=n;i+) j=i; k=0; while(HTj.parent!=0) if(HTHTj.parent.lchild=j) CDk='0' else CDk='1' k+; j=HTj.parent; HCi-1.code=(char *)malloc(k+1)*sizeof(char); HCi-1.codek='0'

21、; k-; int m=k; HCi-1.size=m; for(int l=0;l<=m;l+) HCi-1.codel=CDk; k-; HCi-1.zifu=HTi.zifu; free(CD);int Strsize(char *d) int i=0; while(*d!='0') d+; i+; return i;char* Bianma(HuffmanCode *&HC,char *d) int n=Strsize(d),i,k,j,sum=0; char *a; a=(char *)malloc(10*n)*sizeof(char); for(i=0

22、;i<n;i+) k=0; while(*d!=HCk.zifu) k+; j=0; while(HCk.codej!='0') asum=HCk.codej; j+; sum+; d+; asum='0' return a;void Yima(HTNode *HT,char *&a,char *b,int n) int k=2*n-1,i=0; int m=k; while(*b!='0') if(*b='0') if(HTHTm.lchild.lchild=0) ai=HTHTm.lchild.zifu; i+;

23、 b+; m=k; else m=HTm.lchild; b+; else if(HTHTm.rchild.lchild=0) ai=HTHTm.rchild.zifu; i+; b+; m=k; else m=HTm.rchild; b+; ai='0'void Initialization(HTNode *&HT,HuffmanCode *&HC,int *&w,char *&x,int &n) printf("輸入字符集大小nn"); scanf("%d",&n); fflush(st

24、din); w=(int *)malloc(n*sizeof(int); x=(char *)malloc(n*sizeof(char); for(int i=0;i<n;i+) printf("輸入第%d個(gè)字符和權(quán)值:n",i+1); scanf("%c %d",&xi,&wi); fflush(stdin); HC=(HuffmanCode *)malloc(n*sizeof(HuffmanCode); HuffmanCoding(HT,HC,x,w,n);void TreePrint(HTNode *HT,int n) for(int i=1;i<(2*n);i+) printf("%c %d