哈夫曼編譯碼

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

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

3、進行編碼，然后將結果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼寫入文件CodePrint中。（5）T：印哈夫曼樹（Tree Printing）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。2.函數劃分：該程序有一個主函數和多個子函數，主函數完成對子函數的調用，各子函數實現相應的功能?？梢?/p>

4、定義相應的抽象數據類型。三、詳細設計1.算法void CrtHuffmanTree(HuffmanTree *ht , int *w,ElemTypes *d, int n) /* w存放已知的n個權值，構造哈夫曼樹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號放葉子結點，初始化*/(*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; /*非葉子結點初始化*/*-初始化完畢！對應算法步驟1-*/for(i=n+1;i<=m;i+) /*創(chuàng)建非葉子結點,建哈夫曼樹*/ /*在(*ht)1(*ht)i-1的范圍內選擇兩個parent為0且weight最小的結點，其序號分別賦值給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)/譯碼，遞歸調用char c;if(!feof(fp)/當文件CodeFile未結束if(ch='1')if(*HT)(*HT)m.RChild.RChild=0)/當到達葉子節(jié)點時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/未到達葉子結點時，繼續(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)/當到達葉子節(jié)點時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.主要函數的實現CrtHuffmanTree(&HT,w,d,n); /構建哈夫曼樹。CrtHuffmanCode(&HT,&HC,n,flag);/對哈夫曼樹編碼CrtHuffmanCode(&HT,&HC,n,flag);/對文件編碼Print_d(&HT,m,ch,n,fp,fps);/譯碼PrintTre

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

11、ypedef struct ElemTypes data;unsigned int weight ; /* 用來存放各個結點的權值*/unsigned int parent, LChild,RChild ; /*指向雙親、孩子結點的指針*/HTNode, * HuffmanTree; /*動態(tài)分配數組，存儲哈夫曼樹*/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個權值，構造哈夫曼樹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號放葉子結點，初始化*/(*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; /*非葉子結點初始化*/*-初始化完畢！對應算法步驟1-*/for(i=n+1;i<=m;i+) /*創(chuàng)建非葉子結點,建哈夫曼樹*/ /*在(*ht)1(*ht)i-1的范圍內選擇兩個parent為0且weight最小的結點，其序號分別賦值給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)/*從葉子結點到根，逆向求每個葉子結點對應的哈夫曼編碼*/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、分配求當前編碼的工作空間*/cdn-1='0' /*從右向左逐位存放編碼，首先存放編碼結束符*/for(i=1;i<=n;i+) /*求n個葉子結點對應的哈夫曼編碼*/start=n-1; /*初始化編碼起始指針*/for(c=i,p=(*ht)i.parent; p!=0; c=p,p=(*ht)p.parent) /*從葉子到根結點求編碼*/if( (*ht)p.LChild = c) cd-start='0' /*左分支標0*/else cd-start='1' /*右分支標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權值t編碼n");printf(&

18、quot;字符t權值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)/關閉文件printf("Can not close the file!n");exit(0);if( flag=1)/當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的文章進行編碼: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)/關閉文件printf("Can not close the file!n&qu

21、ot;);exit(0);if(fclose(fps)/關閉文件printf("Can not close the file!n");exit(0);void Print_d(HuffmanTree *HT,int m,char ch,int n,FILE *fp,FILE *fps)/譯碼，遞歸調用char c;if(!feof(fp)/當文件CodeFile未結束if(ch='1')if(*HT)(*HT)m.RChild.RChild=0)/當到達葉子節(jié)點時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/未到達葉子結點時，繼續(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)/當到達葉子節(jié)點時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權值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)/關閉文件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)/關閉文件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; / 結點個數; int wei; / 權值; 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.對譯文進行解碼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字符的權值:",di); fflush(stdin);scanf("%d",&wei); wi=wei; flag=2;CrtHuffmanTree(&HT,w,d,n); /構建哈夫曼樹。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("成功