1、XXX學院 本科數據結構課程設計總結報告設計題目 ： 實驗一、哈夫曼編 / 譯碼器學生姓名 ： XXX系別： XXX專業： XXX班級： XXX學號： XXX指導教師 ： XXXXXX2012年 6 月 21日xxx 學院課 程設計任務書題目一、赫夫曼編譯碼器專業、班級xxx學號xxx姓名xxx主要內容、基本要求、主要參考資料等：1. 主要內容利用哈夫曼編碼進行信息通信可大大提高信道利用率， 縮短信息傳輸時間， 降低傳輸成本。要求在發送端通過一個編碼系統對待傳數據預先編碼； 在接收端將傳來的數據進行譯碼（復原） 。對于雙工信道（既可以雙向傳輸信息的信道） ，每端都需要一個完整的編 / 譯碼系統

2、。試為這樣的信息收發站寫一個哈夫曼的編 / 譯碼系統。2. 基本要求系統應具有以下功能：（ 1） C：編碼（ Coding）。對文件 tobetrans中的正文進行編碼，然后將結果存入文件 codefile中，將以此建好的哈夫曼樹存入文件HuffmanTree 中（ 2）D：解碼（Decoding ）。利用已建好的哈夫曼樹將文件codefile中的代碼進行譯碼，結果存入textfile中。（ 3） P：打印代碼文件（ Print ）。將文件 codefile以緊湊格式顯示在終端上，每行 50 個代碼。同時將此字符形式的編碼文件寫入文件codeprint中。（ 4） T：打印哈夫曼樹（ Tree

3、 Printing ）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件treeprint中。3. 參考資料：數據結構（ C 語言版） 嚴蔚敏、吳偉民編著；數據結構標準教程胡超、閆寶玉編著完成期限：2012年6月21日指導教師簽名：課程負責人簽名：2012年6月21日2一、設計題目（任選其一）實驗一、哈夫曼編 / 譯碼器二、實驗目的1 鞏固和加深對數據結構的理解，提高綜合運用本課程所學知識的能力；2 深化對算法課程中基本概念、理論和方法的理解；3 鞏固構造赫夫曼樹的算法；4 設計試驗用程序實驗赫夫曼樹的構造。三、運行環境（軟、硬件環境）Win

4、dows xp sp3 ，Visual C+ 6.0英文版四、算法設計的思想（ 1）初始化赫夫曼樹，輸入文件tobetrans.txt 中各字符及其權值，并保存于hfmtree.txt 文件中（ 2）編碼（ Coding）。對文件 tobetrans中的正文進行編碼，然后將結果存入文件codefile 中（ 3） D：解碼（ Decoding）。利用已建好的哈夫曼樹將文件codefile 中的代碼進行譯碼，結果存入textfile 中。（ 4） P：打印代碼文件（ Print）。將文件codefile 以緊湊格式顯示在終端上，每行 50 個代碼。同時將此字符形式的編碼文件寫入文件codepri

5、nt 中。（ 5）T：打印哈夫曼樹（ Tree Printing）。將已在內存中的哈夫曼樹以直觀的方式顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件treeprint 中。五、 流程圖3六、 算法設計分析1. 赫夫曼樹節點的數據類型定義為：typedef struct/赫夫曼樹的結構體char ch;int weight;/權值int parent,lchild,rchild;HTNode,*HuffmanTree;2.void HuffmanCoding(HuffmanTree &,char *,int *,int);建立赫夫曼樹的算法，此函數塊調用了 Select （）函數。void s

6、elect(HuffmanTree HT,int j,int *x,int *y); 從已建好的赫夫曼樹中選擇 parent 為 0，weight 最小的兩個結點。3利用已建好的哈夫曼樹從文件 hfmtree.txt 中讀入，對文件中的正文進行編碼，然后將結果存入文件 codefile.txt 中。4. coding編碼功能：對輸入字符進行編碼5. Decoding譯碼功能： 利用已建好的哈夫曼樹將文件codefile.txt中的代碼進行譯碼， 結果存入文件 textfile.txt中。6. Print()打印功能函數：輸出哈夫曼樹以及對應的編碼。4七、源代碼/#include #includ

7、e #include / 定義赫夫曼樹結點的結構體typedef structchar ch;/增加一個域，存放該節點的字符int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;/指向赫夫曼編碼的指針void tips(); /打印操作選擇界面void HuffmanCoding(HuffmanTree &,char *,int *,int); /建立赫夫曼樹的算法void select(HuffmanTree HT,int j,int *x,int *y); /從已建好的赫夫曼樹中選

8、擇 parent 為 0，weight 最小的兩個結點void Init();void Coding(); /編碼void Decoding();/譯碼void Print_code();/打印譯碼好的代碼void Print_tree();/打印哈夫曼樹int Read_tree(HuffmanTree &); /從文件中讀入赫夫曼樹void find(HuffmanTree &HT,char *code,char *text,int i,int m);/譯碼時根據 01 字符串尋找相應葉子節點的遞歸算法5void Convert_tree(unsignedchar T100100,ints

9、,int*i,intj);/將內存中的赫夫曼樹轉換成凹凸表形式的赫夫曼樹HuffmanTree HT;/全局變量int n=0;/全局變量，存放赫夫曼樹葉子結點的數目int main()char select;while(1)tips();scanf(%c,&select);switch(select)/選擇操作，根據不同的序號選擇不同的操作case 1:Init();break;case 2:Coding();break;case 3:Decoding();break;case 4:Print_code();break;6case 5:Print_tree();break;case 0:ex

10、it(1);default :printf(Input error!n);getchar();return 0;void tips() /操作選擇界面printf( -n);printf( -請選擇操作-n);printf( -n);printf(n);printf( -1初始化赫夫曼樹-n);printf( -2編碼-n);printf( -3譯碼-n);printf( -4打印代碼文件 -n);printf( -5打印赫夫曼樹 -n);printf( -0退出-n);printf( -n);7/ 初始化函數，輸入 n 個字符及其對應的權值，根據權值建立哈夫曼樹，并將其存于文件 hfmtre

11、e 中void Init()FILE *fp;int i,n,w52; /數組存放字符的權值char character52; /存放 n 個字符printf(n輸入字符個數 n:);scanf(%d,&n);/輸入字符集大小printf(輸入 %d個字符及其對應的權值 :n,n);for (i=0;in;i+)char b=getchar();scanf(%c,&characteri);scanf(%d,&wi);/輸入 n 個字符和對應的權值HuffmanCoding(HT,character,w,n);/建立赫夫曼樹if(fp=fopen(hfmtree.txt,w)=NULL)prin

12、tf(Open file hfmtree.txt error!n);for (i=1;i=2*n-1;i+)if(fwrite(&HTi,sizeof(HTNode),1,fp)!=1)/將建立的赫夫曼樹存入文件 hfmtree.txt中printf(File write error!n);printf(n赫夫曼樹建立成功，并已存于文件hfmtree.txt中 n);fclose(fp);8/ 建立赫夫曼樹的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,x,y;HuffmanTree p;if

13、(n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;ich=*character;p-weight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;ich=0;p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;+i)select(HT,i-1,&x,&y);HTx.parent=i;HTy.parent=i;HTi.lchild=x;HTi.rchild=y;HTi.weight=HTx.w

14、eight+HTy.weight;/ 從 HT1 到 HTj 中選擇 parent 為 0， weight 最小的兩個結點，用x 和 y返回其序號void select(HuffmanTree HT,int j,int *x,int *y)9int i;/ 查找 weight 最小的結點for (i=1;i=j;i+)if (HTi.parent=0)*x=i;break;for (;i=j;i+)if (HTi.parent=0)&(HTi.weightHT*x.weight)*x=i;HT*x.parent=1;/ 查找 weight 次小的結點for (i=1;i=j;i+)if (HT

15、i.parent=0)*y=i;break;for (;i=j;i+)if (HTi.parent=0)&(i!=*x)&(HTi.weightHT*y.weight)*y=i;/ 對文件 tobetrans 中的正文進行編碼，然后將結果存入文件 codefile 中void Coding()FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;if(n=0)10n=Read_tree(HT);/從文件 hfmtree.txt中讀入赫夫曼樹 , 返回葉子結點數/ 求赫夫曼樹中各葉子節點的字符對應的的編碼，并存于HC指向的空間中HC=(Huff

16、manCode)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)*sizeof(char);strcpy(HCi,&cdstart);free(cd);if(fp=fopen(tobetrans.txt,rb)=NULL)printf(O

17、pen file tobetrans.txt error!n);if(fw=fopen(codefile.txt,wb+)=NULL)printf(Open file codefile.txt error!n);char temp;fscanf(fp,%c,&temp); / 從文件讀入第一個字符 while(!feof(fp)11for(i=1;i=n;i+)if(HTi.ch=temp) break;/在赫夫曼樹中查找字符所在的位置for(int r=0;HCir!=0;r+) /將字符對應的編碼存入文件fputc(HCir,fw);fscanf(fp,%c,&temp);/從文件讀入下一

18、個字符fclose(fw);fclose(fp);printf(n已將文件hfmtree.txt成功編碼 , 并已存入codefile.txt中！nn);/ 將文件 codefile 中的代碼進行譯碼，結果存入文件 textfile 中void Decoding()FILE *fp,*fw;int m,i;char *code,*text,*p;if(n=0)n=Read_tree(HT);/從文件 hfmtree.txt中讀入赫夫曼樹 , 返回葉子結點數if(fp=fopen(codefile.txt,rb)=NULL)printf(Open file codefile.txt error!

19、n);if(fw=fopen(textfile.txt,wb+)=NULL)12printf(Open file textfile.txt error!n);code=(char *)malloc(sizeof(char);fscanf(fp,%c,code);/從文件讀入一個字符for(i=1;!feof(fp);i+)code=(char *)realloc(code,(i+1)*sizeof(char);/增加空間fscanf(fp,%c,&codei);/從文件讀入下一個字符codei-1=0;/ codefile.txt文件中的字符已全部讀入，存放在code 數組中text=(cha

20、r *)malloc(100*sizeof(char);p=text;m=2*n-1;if(*code=0)find(HT,code,text,HTm.lchild,m);/從根節點的左子樹去找elsefind(HT,code,text,HTm.rchild,m);/從根節點的右子樹去找for(i=0;pi!=0;i+)/把譯碼好的字符存入文件textfile.txt中fputc(pi,fw);fclose(fp);fclose(fw);printf(n已將 codefile.txt文件成功譯碼，兵已存入 textfile.txt文件！nn);13/ 將文件 codefi1e 以緊湊格式顯示在

21、終端上 , 每行 50 個代碼。同時將此字符形式的編碼文件寫入文件 codeprint 中。void Print_code()FILE *fp,*fw;char temp;int i;if(fp=fopen(codefile.txt,rb)=NULL)printf(Open file codefile.txt error!n);if(fw=fopen(codeprint.txt,wb+)=NULL)printf(Open file codeprint.txt error!n);printf(n文件 codefi1e 顯示如下 :n);fscanf(fp,%c,&temp);/從文件讀入一個字符

22、for (i=1;!feof(fp);i+)printf(%c,temp);if(i%50=0) printf(n);fputc(temp,fw);/將該字符存入文件codeprint.txt中fscanf(fp,%c,&temp);/從文件讀入一個字符printf(nn已將此字符形式的編碼寫入文件codeprint.txt中！ nn);fclose(fp);fclose(fw);14/ 將已在內存中的哈夫曼樹顯示在屏幕上，并將此字符形式的哈夫曼樹寫入文件 treeprint 中。void Print_tree()unsigned char T100100;int i,j,m=0;FILE *

23、fp;if(n=0)n=Read_tree(HT); / 從文件 hfmtree.txt 中讀入赫夫曼樹 , 返回葉子結點數Convert_tree(T,0,&m,2*n-1);/將內存中的赫夫曼樹轉換成凹凸表形式的樹，存于數組 T 中if(fp=fopen(treeprint.txt,wb+)=NULL)printf(Open file treeprint.txt error!n);printf(n打印已建好的赫夫曼樹：n);for(i=1;i=2*n-1;i+)for (j=0;Tij!=0;j+)if(Tij= ) printf( );fputc(Tij,fp);elseprintf(%

24、d,Tij);fprintf(fp,%dn,Tij);printf(n);fclose(fp);15printf(n已將該字符形式的哈夫曼樹寫入文件treeprint.txt中！nn);/ 從文件 hfmtree.txt 中讀入赫夫曼樹，返回葉子節點數int Read_tree(HuffmanTree &HT)FILE *fp;int i,n;HT=(HuffmanTree)malloc(sizeof(HTNode);if(fp=fopen(hfmtree.txt,r)=NULL)printf(Open file hfmtree.txt error!n);for (i=1;!feof(fp);

25、i+)HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode);/增加空間fread(&HTi,sizeof(HTNode),1,fp);/讀入一個節點信息fclose(fp);n=(i-1)/2;return n;/ 譯碼時根據 01 字符串尋找相應葉子節點的遞歸算法void find(HuffmanTree &HT,char *code,char *text,int i,int m)if(*code!=0)/若譯碼未結束16code+;if(HTi.lchild=0&HTi.rchild=0)/若找到葉子節點*text=HTi.ch;/將葉子節點的字符

26、存入text中text+;if(*code=0)find(HT,code,text,HTm.lchild,m);/從根節點的左子樹找elsefind(HT,code,text,HTm.rchild,m);/從根節點的右子樹找else/如果不是葉子節點if(*code=0)find(HT,code,text,HTi.lchild,m);/從該節點的左子樹去找elsefind(HT,code,text,HTi.rchild,m);/從該節點的右子樹去找else*text=0; /譯碼結束/ 將文件中的赫夫曼樹轉換成凹凸表形式的赫夫曼樹打印出來void Convert_tree(unsigned c

27、har T100100,int s,int *i,int j)int k,l;17l=+(*i);for(k=0;ks;k+)Tlk= ;Tlk=HTj.weight;if(HTj.lchild)Convert_tree(T,s+1,i,HTj.lchild);if(HTj.rchild)Convert_tree(T,s+1,i,HTj.rchild);Tl+k=0;/八、運行結果分析截圖說明：1、運行后界面如圖（ 1）：圖（ 1）選擇要選擇的操作序號可以運行各個步驟；2、初始化赫夫曼樹：18輸入 tobetrans.txt中各元素及其出現頻率，如圖（2）圖（ 2）3、編碼及譯碼，如圖（ 3）

28、圖（ 3）4、打印編碼文件，如圖（4）19圖（ 4）5、打印赫夫曼樹，如圖（5）圖（ 5）6、各步驟所存的文件內容如圖（6）20圖（ 6）九、收獲及體會課程設計是讓我們充分利用我們專業課程所學知識的機會， 也是我們邁向社會，從事工作前一個必不少的過程。通過這次課程設計， 我深深體會到將知識運用到實踐中的重要作用。 我這兩天的課程設計， 是讓我學會腳踏實地邁開這一步，也是為明天能穩健地在社會大潮中奔跑打下堅實的基礎。我的課程設計題目是赫夫曼編譯碼器。最初做這個程序的時候， 讓我覺得完成這次程序設計真的是太難了，然后我查閱了課本，并去圖書館借了資料， 在寫這個程序的時候也參考了網上的設計流程， 寫

29、完剛運行時出現了很多問題。 尤其是編碼錯誤，導致內存無法 read ，通過同組人員的交流請教，逐漸明白過來，然后經過不知道多少次修改才順利運行。 本次試驗也讓我明白了理論與實際相結合的重要性，并提高了自己組織數據及編寫大型程序的能力，培養了基本的、 良好的程序設計技能以及合作能力。 通過對各個步驟各個流程的控制，逐漸讓我產生了興趣， 在實際編寫過程中， 和同學們相互討論讓我學到的不僅僅是一些解決問題的方法，更是解決問題的思想。課程設計本身也是一種相互學習的過程 ,/21/#include#include/ 為 exit()提供原型#include/ 哈夫曼樹結點的結構typedefstruct

30、char ch;/ 該字符域用于存放節點的關鍵字intweight;intparent, lchild, rchild; HTNode, *HuffmanTree ;/ 動態分配數組存儲哈夫曼樹typedefchar * HuffmanCode;/ 動態分配數組存儲哈夫曼編碼表voidMenu();/ 顯示菜單voidHuffmanCoding( HuffmanTree &HT, char *character,int * w,int n);/ 建立哈夫曼樹voidselect( HuffmanTree HT, int j, int *x, int*y);/從已建好的赫夫曼樹中選擇 paren

31、t為 0， weight 最小的兩個結點voidInit();voidCoding();/ 編碼voidDecoding();/ 譯碼voidPrint_code();/ 打印譯碼好的代碼voidPrint_tree();/ 打印哈夫曼樹intRead_tree(HuffmanTree &); / 從文件中讀入赫夫曼樹voidfind( HuffmanTree &HT,char *code, char*text,inti,intm);/ 譯碼時根據 01 字符串尋找相應葉子節點的遞歸算法voidConvert_tree(unsignedchar T100100,int s,int*i,intj

32、);/ 將內存中的赫夫曼樹轉換成凹凸表形式的赫夫曼樹HuffmanTree HT;/ 全局變量intn = 0;/全局變量，存放赫夫曼樹葉子結點的數目intmain()char select;while (1)Menu();scanf(%c, &select);switch(select)/ 選擇操作，根據不同的序號選擇不同的操作case 1 :Init();break ;22case 2 :Coding();break ;case 3 :Decoding();break ;case 4 :Print_code();break ;case 5 :Print_tree();break ;case

33、 0 :exit(1);default:printf(Input error!n);getchar();return0;void Menu()/ 操作選擇界面printf(-n);printf(-請選擇操作-n);printf(-n);printf(n);printf(-1初始化赫夫曼樹-n);printf(-2編碼-n);printf(-3譯碼-n);printf(-4打印代碼文件 -n);printf(-5打印赫夫曼樹 -n);printf(-0退出-n);printf(-n);/ 初始化函數，輸入n 個字符及其對應的權值，根據權值建立哈夫曼樹，并將其存于文件hfmtree 中void I

34、nit()FILE *fp;inti, n, w52;/ 數組存放字符的權值char character52;/ 存放 n 個字符23printf(n 輸入字符個數n: );scanf( %d, &n);/ 輸入字符集大小printf( 輸入 %d個字符及其對應的權值:n , n);for (i = 0; in; i+)char b = getchar();scanf( %c, &characteri);scanf( %d, &wi);/ 輸入 n 個字符和對應的權值HuffmanCoding(HT, character, w, n);/ 建立赫夫曼樹if(fp = fopen(hfmtree

35、.txt,w ) =NULL)printf(Open file hfmtree.txt error!n);for (i = 1; i 0），構造哈夫曼樹 HT int m, i, x, y;HuffmanTree p;if(n = 1)return ;m = 2 * n - 1;HT = ( HuffmanTree)malloc(m + 1) *sizeof ( HTNode);for (p = HT + 1, i = 1; i ch = *character; p-weight = *w; p-parent = 0; p-lchild = 0; p-rchild = 0;for (;i ch

36、 = 0; p-weight= 0; p-parent= 0; p-lchild= 0; p-rchild=0;for (i = n + 1; i = m; +i)select(HT, i - 1, &x, &y);HTx.parent = i; HTy.parent = i;HTi.lchild = x; HTi.rchild = y;HTi.weight = HTx.weight + HTy.weight;24/ 從 HT1 到 HTj 中選擇 parent 為 0，weight 最小的兩個結點，用 x 和 y 返回其序號 void select( HuffmanTree HT, int j , int * x, int * y)inti;/ 查找 weight 最小的結點for (i = 1; i =j ; i+)if( HTi.parent = 0)* x = i;break ;for (; i =j ; i+)if( HTi.parent = 0) & (HTi.weightHT* x.weight)* x = i;