哈夫曼編譯碼

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計（2013-2014學(xué)年第一學(xué)期） 題目：哈夫曼編碼-譯碼院 系 ： 專 業(yè)： 學(xué)生姓名： 學(xué) 號： 指導(dǎo)教師： 年 月 日目 錄1課程設(shè)計任務(wù)和要求 12概要設(shè)計 13詳細(xì)設(shè)計 24調(diào)試結(jié)果325課程設(shè)計總結(jié)336附源程序清單34一、課程設(shè)計的任務(wù)和要求問題描述打開一篇英文文章，統(tǒng)計該文章中每個字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，對每一個字符進(jìn)行編碼，編碼完成后再對其編碼進(jìn)行譯碼?；疽罄霉蚵幋a進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道

2、（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼編/譯碼系統(tǒng)。測試數(shù)據(jù)新建一個.txt文件，用來存放待處理的數(shù)據(jù)，這些數(shù)據(jù)為ASCII碼值的集合，而且每種字符的數(shù)量并不能相同。本實(shí)驗擬設(shè)其中的數(shù)據(jù)為abbcccdddd.二、概要設(shè)計1.總體設(shè)計 一個完整的系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件htmTree中讀入），對文件ToBeTran中的正文

3、進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼寫入文件CodePrint中。（5）T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。2.函數(shù)劃分：該程序有一個主函數(shù)和多個子函數(shù)，主函數(shù)完成對子函數(shù)的調(diào)用，各子函數(shù)實(shí)現(xiàn)相應(yīng)的功能。可以

4、定義相應(yīng)的抽象數(shù)據(jù)類型。三、詳細(xì)設(shè)計1.算法void CrtHuffmanTree(HuffmanTree *ht , int *w,ElemTypes *d, int n) /* w存放已知的n個權(quán)值，構(gòu)造哈夫曼樹ht */int m,i;int s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /*0號單元未使用*/for(i=1;i<=n;i+) /*1-n號放葉子結(jié)點(diǎn)，初始化*/(*ht)i.weight = wi;(*ht)i.data=di;(*ht)i.LChild = 0;(*ht)i.parent =

5、0;(*ht)i.RChild = 0;for(i=n+1;i<=m;i+)(*ht)i.weight = 0;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0; /*非葉子結(jié)點(diǎn)初始化*/*-初始化完畢！對應(yīng)算法步驟1-*/for(i=n+1;i<=m;i+) /*創(chuàng)建非葉子結(jié)點(diǎn),建哈夫曼樹*/ /*在(*ht)1(*ht)i-1的范圍內(nèi)選擇兩個parent為0且weight最小的結(jié)點(diǎn)，其序號分別賦值給s1、s2返回*/select(ht,i-1,&s1,&s2);(*ht)i.data=NULL;(*ht)

6、s1.parent=i;(*ht)s2.parent=i;(*ht)i.LChild=s1;(*ht)i.RChild=s2;(*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight; void Print_d(HuffmanTree *HT,int m,char ch,int n,FILE *fp,FILE *fps)/譯碼，遞歸調(diào)用char c;if(!feof(fp)/當(dāng)文件CodeFile未結(jié)束if(ch='1')if(*HT)(*HT)m.RChild.RChild=0)/當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)時printf("%c",(*H

7、T)(*HT)m.RChild.data);/輸出翻譯后的字符fprintf(fps,"%c",(*HT)(*HT)m.RChild.data);int m=2*n-1;c=fgetc(fp);Print_d(HT,m,c,n,fp,fps);else/未到達(dá)葉子結(jié)點(diǎn)時，繼續(xù)從文件CodeFile讀入0 1代碼c=fgetc(fp);Print_d(HT,(*HT)m.RChild,c,n,fp,fps);if(ch='0')if(*HT)(*HT)m.LChild.LChild=0)/當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)時printf("%c",(*HT)(

8、*HT)m.LChild.data);fprintf(fps,"%c",(*HT)(*HT)m.LChild.data);int m=2*n-1;c=fgetc(fp);Print_d(HT,m,c,n,fp,fps);elsec=fgetc(fp);Print_d(HT,(*HT)m.LChild,c,n,fp,fps);void PrintTree(HuffmanTree HT,int m,int nLayer) /* 按豎向樹狀打印的二叉樹 */if(m!=0)if(HT = NULL)return;PrintTree(HT,HTm.RChild,nLayer+1);

9、for(int i=0;i<nLayer;i+)printf("-");printf("%dn",HTm.weight);PrintTree(HT,HTm.LChild,nLayer+1);2.主要函數(shù)的實(shí)現(xiàn)CrtHuffmanTree(&HT,w,d,n); /構(gòu)建哈夫曼樹。CrtHuffmanCode(&HT,&HC,n,flag);/對哈夫曼樹編碼CrtHuffmanCode(&HT,&HC,n,flag);/對文件編碼Print_d(&HT,m,ch,n,fp,fps);/譯碼PrintTre

10、e(HT,m,nLayer);/打印四、調(diào)試結(jié)果 五、課程設(shè)計總結(jié)1、遇難到哪些問題，解決的方法。一些算法的構(gòu)成不理解，并且不會自己編寫，對哈夫曼譯碼的算法不會等2、通過本次課程設(shè)計，自己得到了哪些方面的訓(xùn)練和提高（經(jīng)驗和教訓(xùn)）。多看書，多上網(wǎng)查資料，多向老師同學(xué)請教等，重視基本知識的運(yùn)用，結(jié)合實(shí)際等六、附源程序清單#include <stdio.h>#include <stdlib.h>#include <string.h>#define ElemTypes chartypedef char* HuffmanCode;/*動態(tài)分配數(shù)組，存儲哈夫曼編碼*/t

11、ypedef struct ElemTypes data;unsigned int weight ; /* 用來存放各個結(jié)點(diǎn)的權(quán)值*/unsigned int parent, LChild,RChild ; /*指向雙親、孩子結(jié)點(diǎn)的指針*/HTNode, * HuffmanTree; /*動態(tài)分配數(shù)組，存儲哈夫曼樹*/void select(HuffmanTree *ht,int n, int *s1, int *s2)int i;int min;for(i=1; i<=n; i+)if(*ht)i.parent = 0)min = i;i = n+1;for(i=1; i<=n;

12、 i+)if(*ht)i.parent = 0)if(*ht)i.weight < (*ht)min.weight)min = i;*s1 = min;for(i=1; i<=n; i+)if(*ht)i.parent = 0 && i!=(*s1)min = i;i = n+1;for(i=1; i<=n; i+)if(*ht)i.parent = 0 && i!=(*s1)if(*ht)i.weight < (*ht)min.weight)min = i;*s2 = min;void CrtHuffmanTree(HuffmanTre

13、e *ht , int *w,ElemTypes *d, int n) /* w存放已知的n個權(quán)值，構(gòu)造哈夫曼樹ht */int m,i;int s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /*0號單元未使用*/for(i=1;i<=n;i+) /*1-n號放葉子結(jié)點(diǎn)，初始化*/(*ht)i.weight = wi;(*ht)i.data=di;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0;for(i=n+1;i<=m;i+)(*ht)i.weig

14、ht = 0;(*ht)i.LChild = 0;(*ht)i.parent = 0;(*ht)i.RChild = 0; /*非葉子結(jié)點(diǎn)初始化*/*-初始化完畢！對應(yīng)算法步驟1-*/for(i=n+1;i<=m;i+) /*創(chuàng)建非葉子結(jié)點(diǎn),建哈夫曼樹*/ /*在(*ht)1(*ht)i-1的范圍內(nèi)選擇兩個parent為0且weight最小的結(jié)點(diǎn)，其序號分別賦值給s1、s2返回*/select(ht,i-1,&s1,&s2);(*ht)i.data=NULL;(*ht)s1.parent=i;(*ht)s2.parent=i;(*ht)i.LChild=s1;(*ht)i

15、.RChild=s2;(*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight; void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n,int flag)/*從葉子結(jié)點(diǎn)到根，逆向求每個葉子結(jié)點(diǎn)對應(yīng)的哈夫曼編碼*/char *cd;int i;unsigned int c;int start;int p;hc=(HuffmanCode *)malloc(n+1)*sizeof(char *); /*分配n個編碼的頭指針*/cd=(char * )malloc(n * sizeof(char ); /*

16、分配求當(dāng)前編碼的工作空間*/cdn-1='0' /*從右向左逐位存放編碼，首先存放編碼結(jié)束符*/for(i=1;i<=n;i+) /*求n個葉子結(jié)點(diǎn)對應(yīng)的哈夫曼編碼*/start=n-1; /*初始化編碼起始指針*/for(c=i,p=(*ht)i.parent; p!=0; c=p,p=(*ht)p.parent) /*從葉子到根結(jié)點(diǎn)求編碼*/if( (*ht)p.LChild = c) cd-start='0' /*左分支標(biāo)0*/else cd-start='1' /*右分支標(biāo)1*/hci=(char *)malloc(n-start)

17、*sizeof(char); /*為第i個編碼分配空間*/strcpy(hci,&cdstart);free(cd);if(flag=2)FILE *fp1;if(fp1=fopen("e:hfmTree.txt","w")=NULL)/創(chuàng)建文件hfmTree存儲字符形式的編碼printf("File open error!n");exit(0);printf("n將下面的哈夫曼樹寫入文件hfmTree.txt中.n");fprintf(fp1,"字符t權(quán)值t編碼n");printf(&

18、quot;字符t權(quán)值t編碼n");for(i=1;i<=n;i+)printf("%ct%dt%sn",(*ht)i.data,(*ht)i.weight,hci);fprintf(fp1,"%ct%dt%sn",(*ht)i.data,(*ht)i.weight,hci);/寫入文件hfmTree中printf("n成功寫入!n");if(fclose(fp1)/關(guān)閉文件printf("Can not close the file!n");exit(0);if( flag=1)/當(dāng)flag=1時對

19、文件ToBeTran編碼FILE *fp;FILE *fps;char ch;int i;if(fp=fopen("e:ToBeTran.txt","r")=NULL)/從文件ToBeTran中讀取要編碼的文章。printf("File open error!n");exit(0);if(fps=fopen("e:CodeFile.txt","w")=NULL)/創(chuàng)建文件CodeFile存儲文件ToBeTran的編碼printf("File open error!n");ex

20、it(0);printf("n對文件ToBeTran.txt的文章進(jìn)行編碼:n");while(!feof(fp)ch=fgetc(fp);for(i=1;i<=n;i+)if(ch!='0')if(ch=(*ht)i.data)fprintf(fps,"%s",hci);printf("%s",hci);printf("n代碼成功保存到文件CodeFile.txx中.nn");if(fclose(fp)/關(guān)閉文件printf("Can not close the file!n&qu

21、ot;);exit(0);if(fclose(fps)/關(guān)閉文件printf("Can not close the file!n");exit(0);void Print_d(HuffmanTree *HT,int m,char ch,int n,FILE *fp,FILE *fps)/譯碼，遞歸調(diào)用char c;if(!feof(fp)/當(dāng)文件CodeFile未結(jié)束if(ch='1')if(*HT)(*HT)m.RChild.RChild=0)/當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)時printf("%c",(*HT)(*HT)m.RChild.data);/

22、輸出翻譯后的字符fprintf(fps,"%c",(*HT)(*HT)m.RChild.data);int m=2*n-1;c=fgetc(fp);Print_d(HT,m,c,n,fp,fps);else/未到達(dá)葉子結(jié)點(diǎn)時，繼續(xù)從文件CodeFile讀入0 1代碼c=fgetc(fp);Print_d(HT,(*HT)m.RChild,c,n,fp,fps);if(ch='0')if(*HT)(*HT)m.LChild.LChild=0)/當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)時printf("%c",(*HT)(*HT)m.LChild.data);fpri

23、ntf(fps,"%c",(*HT)(*HT)m.LChild.data);int m=2*n-1;c=fgetc(fp);Print_d(HT,m,c,n,fp,fps);elsec=fgetc(fp);Print_d(HT,(*HT)m.LChild,c,n,fp,fps);void PrintTree(HuffmanTree HT,int m,int nLayer) /* 按豎向樹狀打印的二叉樹 */if(m!=0)if(HT = NULL)return;PrintTree(HT,HTm.RChild,nLayer+1);for(int i=0;i<nLayer

24、;i+)printf("-");printf("%dn",HTm.weight);PrintTree(HT,HTm.LChild,nLayer+1);void TreePrint(HuffmanTree *ht,int m)FILE *fp;int i;if(fp=fopen("e:TreePrint.txt","w")=NULL)/同時將此字符形式的哈夫曼樹寫入文件TreePrint中printf("File open error!n");exit(0);printf("將字符形式的

25、哈夫曼樹存儲到文件TreePrint中.n");fprintf(fp,"編號t字符t權(quán)值tparenttLChildtRChildn");for(i=1;i<=m;i+)fprintf(fp,"%dt%ct%dt%dt%dt%dn",i,(*ht)i.data,(*ht)i.weight,(*ht)i.parent,(*ht)i.LChild,(*ht)i.RChild);printf("存儲成功!n");if(fclose(fp)/關(guān)閉文件printf("Can not close the file!n&q

26、uot;);exit(0);void PutCode()FILE *fp;char ch;int i=0;if(fp=fopen("e:CodeFile.txt","r")=NULL)/讀取0 1 代碼 輸出文件CodeFile.txt中的代碼printf("File open error!n");exit(0);while(!feof(fp)ch=fgetc(fp);if(ch!='0')printf("%c",ch);i=i+1;if(i%50=0)printf("n");i

27、f(fclose(fp)/關(guān)閉文件printf("Can not close the file!n");exit(0);void main() HuffmanTree HT; HuffmanCode HC; FILE *fp,*fps,*fpss;int *w; char *d,str1000,s2;char data,ch;int i,n,choice; / 結(jié)點(diǎn)個數(shù); int wei; / 權(quán)值; int m,flag;int nLayer=0; printf("*n");printf("*ttt哈夫曼編譯碼ttt*n");pri

28、ntf("*n");doprintf("*n");printf("*tt輸入你要選擇的選項(請先選擇 1)tt *n");printf("*ttt1.初始化哈夫曼樹tt *n");printf("*ttt2.對文件編碼ttt *n");printf("*ttt3.對譯文進(jìn)行解碼tt *n");printf("*ttt4.打印代碼文件ttt *n");printf("*ttt5.打印哈夫曼樹ttt *n");printf("*t

29、tt0.退出程序ttt *n");printf("*n");scanf("%d",&choice);switch(choice)case 1:printf("請輸入字符集大小n:" ); scanf("%d",&n); w=(int *)malloc(n+1)*sizeof(int); d=(ElemTypes *)malloc(n+1)*sizeof(ElemTypes);for(i=1;i<=n;i+)printf("輸入第個%d字符:",i);if(data

30、=getchar()='n')data=getchar();di=data;for(i=1;i<=n;i+) printf("請輸入%c字符的權(quán)值:",di); fflush(stdin);scanf("%d",&wei); wi=wei; flag=2;CrtHuffmanTree(&HT,w,d,n); /構(gòu)建哈夫曼樹。CrtHuffmanCode(&HT,&HC,n,flag);/對哈夫曼樹編碼break;case 2: flag=1;if(fpss=fopen("e:ToBeTran.txt","w")=NULL)/創(chuàng)建文件ToBeTran中存儲要編碼的文章。printf("File open error!n");exit(0);gets(s);printf("輸入你要編碼的英文:n");gets(str);fputs(str,fpss);/將要編碼的英文寫入文件ToBeTran.txt中printf("成功