數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(赫夫曼編碼)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上中南民族大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告姓 名： 康宇 年 級： 2010 學(xué) 號： 專 業(yè)：計算機科學(xué)與技術(shù) 指導(dǎo)老師： 宋中山 2013年4月15日實習(xí)報告： 赫夫曼編/譯碼器實習(xí)報告題目：為信息收發(fā)站寫一個赫夫曼碼的編/譯碼系統(tǒng)班級：計科一班 姓名：康宇 學(xué)號： 完成日期：2013.4.5 一、 需求分析1、 問題描述：利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端講傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。2、

2、基本要求：（1） I:初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。（2） E：編碼（Encoding）。利用已建好的赫夫曼樹，對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。（3） D:譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。（4） P:印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。（5） T:印赫夫曼樹

3、（Tree Printing）。將已在內(nèi)存中的赫夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的赫夫曼樹寫入文件TreePrint中。3、 實現(xiàn)提示：（1） 編碼結(jié)果以文本方式存儲在文件CodeFile中。（2） 用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。二、 概要設(shè)計1. 元素類型：typedef structint weigt;/權(quán)值int parent,lchild,rchild;/雙親，左孩子，右孩子HTNode,*HuffmanTree

4、;typedef char* HuffmanCode;/存放各個字符的前綴編碼2. 本程序包括六個大板塊：（1）主程序： int main() 輸出菜單；選擇功能選項并調(diào)用對應(yīng)的函數(shù)； （2）初始化函數(shù)： void Initialization(HuffmanTree &ht,FILE *fp) 安全打開文件；輸入字符數(shù)量以及各字符及其權(quán)值；對各節(jié)點進行初始化；創(chuàng)建赫夫曼列表；（需要調(diào)用Select()函數(shù)選擇權(quán)職最小的兩個節(jié)點） void Select(HuffmanTree &ht,int i,int &s_1,int &s_2)找出第一個非零結(jié)點；找出第二

5、個非零結(jié)點；遍歷比較找出權(quán)值最小的兩個節(jié)點；（3）編碼函數(shù)：void Encoding(HuffmanTree &ht,HuffmanCode &hc,FILE *fp1,FILE *fp2)安全打開文件；for:1àn,雙親不為空If(為左孩子)str-start='0'elsestr-start='1'儲存各字符的編碼；從文件中讀取正文；依次遍歷正文各字符，顯示其編碼；（4）譯碼函數(shù)：void Decoding(HuffmanTree &ht,HuffmanCode &hc,FILE *fp1,FILE *fp2)安

6、全打開文件；While（成功讀取字符）遍歷目前的編碼中是否有對應(yīng)的字符；if(有)輸出該字符；else跳到循環(huán)體首；（再次讀入一個字符再判斷）（5）印代碼文件：void Print(FILE *fp1,FILE *fp2)安全打開文件；從文件中讀取字符，50個一行輸出；（6）印赫夫曼樹：void Treeprinting(HuffmanTree ht)安全打開文件；調(diào)用print_tree(ht,root)函數(shù)；void print_tree(HuffmanTree ht, int r)if(存在節(jié)點)深度+1；遞歸調(diào)用print_tree(ht,htr.rchild);/先輸出右子樹用深度控

7、制格式；輸出對應(yīng)的字符；遞歸調(diào)用print_tree(ht,htr.lchild);/再輸出左子樹深度-1三、 詳細(xì)設(shè)計#include <stdio.h>#include <stdlib.h>#include <string.h>typedef structint weigt;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char* HuffmanCode;/存放各個字符的前綴編碼/此全局文件指針用于輸出赫夫曼樹到對應(yīng)文件，便于調(diào)用遞歸FILE *TreePrint=NULL;char *s;/存

8、放各字符int *w;/存放各字符的權(quán)值int n;int m;int dep=0;/存放各字符的深度void Select(HuffmanTree &ht,int i,int &s_1,int &s_2)/挑選出權(quán)值最小的兩個結(jié)點int j;for(j=1;j<=i;j+)/找出第一個非零結(jié)點if(htj.parent=0)s_1=j;break;for(j=s_1+1;j<=i;j+)/找出第二個非零結(jié)點if(htj.parent=0)s_2=j;break;for(j=1;j<=i;j+)/遍歷出權(quán)值最小的兩個結(jié)點if(htj.parent=0)

9、/必須要判斷雙親是否為空if(htj.weigt<hts_1.weigt)s_2=s_1;s_1=j;else if(htj.weigt>hts_1.weigt&&htj.weigt<hts_2.weigt)s_2=j;void Initialization(HuffmanTree &ht,FILE *fp)int i,s1,s2;if(fp=fopen("hfmTree.txt","w")=NULL)/安全打開文件printf("File hfmTree.txt cannot opened.n&quo

10、t;);exit(1);/輸入各字符以及權(quán)值printf("請輸入字符集大小n :");scanf("%d",&n);s=(char *)malloc(n*sizeof(char);w=(int *)malloc(n*sizeof(int);printf("請輸入各字符：n");getchar();/getchar();/處理換行符/scanf("%s",s);gets(s);printf("請輸入各字符對應(yīng)的權(quán)值：n");for(i=0;i<n;i+)scanf("%d

11、",&wi);if(n<=1)return;m=2*n-1;/節(jié)、結(jié)點的個數(shù)ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(i=1;i<=n;i+)/分別對各結(jié)點賦值hti.weigt=wi-1;hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i<=m;i+)hti.weigt=hti.parent=hti.lchild=hti.rchild=0;/構(gòu)建赫夫曼樹for(i=n+1;i<=m;i+)Select(ht,i-1,s1,s2);/選出權(quán)值最小的葉子節(jié)點ht

12、s1.parent=hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weigt=hts1.weigt+hts2.weigt;/構(gòu)建新結(jié)點的權(quán)值/輸出赫夫曼列表printf("赫夫曼列表為：n");for(i=1;i<=n;i+)/葉子節(jié)點fprintf(fp,"t%ct%dt%dt%dt%dn",si,hti.weigt,hti.parent,hti.lchild,hti.rchild);printf("t%ct%dt%dt%dt%dn",si-1,hti.weigt,hti.pare

13、nt,hti.lchild,hti.rchild);for(i=n+1;i<=m;i+)/非葉子節(jié)點fprintf(fp,"t t%dt%dt%dt%dn",hti.weigt,hti.parent,hti.lchild,hti.rchild);printf("t t%dt%dt%dt%dn",hti.weigt,hti.parent,hti.lchild,hti.rchild);fclose(fp);void Encoding(HuffmanTree &ht,HuffmanCode &hc,FILE *fp1,FILE *fp2)

14、/編碼int i,j,c,f,start;char *str;/用于存放編碼char data100;/用于存放文件正文字符if(fp1=fopen("ToBeTran.txt","r")=NULL)printf("File ToBeTran.txt cannot opened.n");exit(1);if(fp2=fopen("CodeFile.txt","w")=NULL)printf("File CodeFile.txt cannot opened.n");exit(1

15、);/根據(jù)赫夫曼樹得到各字符對應(yīng)的編碼hc=(HuffmanCode)malloc(n+1)*sizeof(char *);str=(char *)malloc(n*sizeof(char);/n個字符中的最長的編碼個數(shù)為n-1strn-1='0'/編碼從后開始往前存放for(i=1;i<=n;i+)start=n-1;for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)/由下而上取字符的對應(yīng)編碼if(htf.lchild=c)/為左子樹str-start='0'else/為右子樹str-start='1'

16、hci=(char *)malloc(n-start)*sizeof(char);strcpy(hci,&strstart);/賦值對應(yīng)字符的編碼printf("各字符串的編碼為：n");for(i=1;i<=n;i+)printf("%sn",hci);/對文件正文進行編碼/fscanf(fp1,"%s",data);fgets(data,500,fp1);/讀取正文printf("文件正文為：");printf("%s",data);printf("n文件ToBeTr

17、an中的正文編碼為：n");for(i=0;i<strlen(data);i+)for(j=0;j<n;j+)if(datai=sj)/依次遍歷出正文各字符的編碼，并存儲到文件中printf("%s",hcj+1);fprintf(fp2,"%s",hcj+1);break;printf("n");free(str);fclose(fp1);fclose(fp2);void Decoding(HuffmanTree &ht,HuffmanCode &hc,FILE *fp1,FILE *fp2)i

18、nt i,j;bool flag;char ch;char *data=(char *)malloc(n*sizeof(char);/臨時存放赫夫曼碼if(fp1=fopen("CodeFile.txt","r")=NULL)printf("File CodeFile.txt cannot opened.n");exit(1);if(fp2=fopen("TextFile.txt","w")=NULL)printf("File TextFile.txt cannot opened.n&

19、quot;);exit(1);/進行譯碼printf("文件譯碼為：n");while(fscanf(fp1,"%c",&ch)!=EOF)/有編碼可讀取flag=true;/控制循環(huán)i=0;while(flag)if(i!=0)fscanf(fp1,"%c",&ch);datai+=ch;datai='0'for(j=1;j<=n;j+)if(!strcmp(data,hcj)/如果找到匹配的字符編碼printf("%c",sj-1);fprintf(fp2,"%c

20、",sj-1);flag=false;break;fclose(fp1);fclose(fp2);void Print(FILE *fp1,FILE *fp2)char ch;int sum=0;if(fp1=fopen("CodeFile.txt","r")=NULL)printf("File CodeFile.txt cannot opened.n");exit(1);if(fp2=fopen("CodePrin.txt","w")=NULL)printf("File C

21、odePrin.txt cannot opened.n");exit(1);/從CodeFile中讀取出來輸出到CodePrin中printf("文件字符為：n");while(fscanf(fp1,"%c",&ch)!=EOF)sum+;printf("%c",ch);fprintf(fp2,"%c",ch);if(sum%50=0)/50個字符一行printf("n");fprintf(fp2,"n");fclose(fp1);fclose(fp2);v

22、oid print_tree(HuffmanTree ht, int r)/左倒置90度輸出到文件和終端上if(r)dep+;/控制葉子節(jié)點的深度print_tree(ht,htr.rchild);/先輸出右子樹for(int i=1;i<dep;i+)/控制深度printf("t");fprintf(TreePrint,"t");if(r>n)printf("On");fprintf(TreePrint,"On");elseprintf("%cn",sr-1);fprintf(Tr

23、eePrint,"%cn",sr-1);print_tree(ht,htr.lchild);/再輸出左子樹dep-;void Treeprinting(HuffmanTree ht)int root;/根結(jié)點if(TreePrint=fopen("TreePrint.txt","a")=NULL)/進行數(shù)據(jù)追加printf("File TreePrint.txt cannot opened.n");exit(1); root=m;printf("赫夫曼樹為：n");print_tree(ht,r

24、oot);fclose(TreePrint);/及時關(guān)閉文件int main()int choose;FILE *hfmTree=NULL,*ToBeTran=NULL,*CodeFile=NULL,*TextFile=NULL,*CodePrin=NULL;HuffmanTree huftree=NULL;/指針初始化HuffmanCode hufcode=NULL;while(1)printf("n-赫夫曼編/譯碼器菜單-n");printf("1-Initialization(初始化)n");printf("2-Encoding(編碼)n");printf("3-Decoding(譯碼)n");printf("4-Print(印代碼文件)n");printf("5-Treeprinting(印赫夫曼樹)n");printf("