哈夫曼編譯碼器

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 指導(dǎo)教師： 班 級：121004學(xué) 號：121004116姓 名： 目 錄一、 前言1 摘要二、實(shí)驗(yàn)?zāi)康娜?、題目-赫夫曼編碼/譯碼器1 問題描述2 基本要求3 測試要求4 實(shí)現(xiàn)提示四、 需求分析-具體要求五、 概要設(shè)計(jì)六、 詳細(xì)設(shè)計(jì)七、 調(diào)試分析八、 實(shí)驗(yàn)心得與體會九、 附錄前言1 摘要 隨著計(jì)算機(jī)的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值運(yùn)算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及設(shè)計(jì)最短路線等復(fù)雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)就是為以后利用計(jì)算機(jī)資源高效地開發(fā)非數(shù)值處理的計(jì)算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及

2、的對象在計(jì)算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。 二、實(shí)驗(yàn)?zāi)康?學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對象在計(jì)算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計(jì)主要達(dá)到以下目的：¨ 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；¨ 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；¨ 提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；¨ 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開

3、發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。三、題目-赫夫曼編碼/譯碼器1. 問題描述利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個赫夫曼碼的編/譯碼系統(tǒng)。2.基本要求一個完整的系統(tǒng)應(yīng)具有以下功能：(1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立赫夫曼樹，并將它存于文件hfmTree中。(2

4、) E：編碼（Encoding）。利用已建好的赫夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。(3) D：譯碼（Decoding）。利用已建好的赫夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile中。(4) P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。(5) T：印赫夫曼樹（Tree printing）。將已在內(nèi)存中的赫夫曼樹以直觀的方式（比如樹）顯示在終端上，同時將此字符形式的赫夫曼樹

5、寫入文件TreePrint 中。2. 測試要求(1) 已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其頻率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，試設(shè)計(jì)赫夫曼編碼。(2) 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立赫夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAME IS MY FAVORITE”。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381811613. 實(shí)現(xiàn)提示(1) 編碼結(jié)果以文本方式存儲在文件Codefile中。(2)

6、 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運(yùn)行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。(3) 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，赫夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。四、需求分析：¨ 題目；¨ 實(shí)驗(yàn)?zāi)康模?#168; 需求分析：在該部分中敘述實(shí)現(xiàn)的功能要求；¨ 概要設(shè)計(jì)：在此說明每個部分的算法設(shè)計(jì)說明（可以是描述算法的流程圖），每個程序中使用的存儲結(jié)構(gòu)設(shè)計(jì)說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義

7、）；¨ 詳細(xì)設(shè)計(jì)：各個算法實(shí)現(xiàn)的源程序，對每個題目要有相應(yīng)的源程序（可以是一組源程序，每個功能模塊采用不同的函數(shù)實(shí)現(xiàn)）。源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量、重點(diǎn)功能部分要加上清晰的程序注釋；¨ 調(diào)試分析：測試數(shù)據(jù)，測試輸出的結(jié)果，時間復(fù)雜度分析，和每個模塊設(shè)計(jì)和調(diào)試時存在問題的思考（問題是哪些？問題如何解決？），算法的改進(jìn)設(shè)想；¨ 總結(jié)： 設(shè)計(jì)過程的收獲、遇到問題及解決問題過程的思考、程序調(diào)試能力的思考、對數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在設(shè)計(jì)過程中對數(shù)據(jù)結(jié)構(gòu)課程的認(rèn)識等內(nèi)容。五、 概要設(shè)計(jì)1）問題分析哈夫曼樹的定義1.哈夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定

8、義為：typedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;2）所實(shí)現(xiàn)的功能函數(shù)如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹，處理InputHuffman(Huffman Hfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹。此函數(shù)塊調(diào)用了Select（）函數(shù)。2、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出HT樹

9、到a為止，權(quán)值最小且parent為0的2個節(jié)點(diǎn)3、 int main()主函數(shù)： 利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.txt中讀入）對文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲到CodeFile中。4、Encoding 編碼功能：對輸入字符進(jìn)行編碼5、Decoding譯碼功能： 利用已建好的哈夫曼樹將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。 Print() 打印功能函數(shù)

10、：輸出哈夫曼樹，字符，權(quán)值，以及它對應(yīng)的編碼。3）主函數(shù)的簡要說明，主函數(shù)主要設(shè)計(jì)的是一個分支語句，讓用戶挑選所實(shí)現(xiàn)的功能。使用鏈樹存儲，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實(shí)現(xiàn)功能。2) 系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）六、 詳細(xì)設(shè)計(jì) 1.相關(guān)數(shù)據(jù)類型（采用C語言定義） Int cdn; /存儲哈夫曼編碼 Char strn; /存儲需要編碼的字符串 Double weight; /存儲字符出現(xiàn)頻度 Int child,rchild,lchild,parent; /存儲哈夫曼樹中各節(jié)點(diǎn)位置 2.各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖1.各函數(shù)調(diào)用關(guān)系圖 Main()

11、哈夫曼樹的建立哈夫曼編碼。建立編碼文件哈夫曼譯碼 2.main() 函數(shù) 開始調(diào)用createHT函數(shù)生成haffman樹調(diào)用createHCcode函數(shù)，生成haffman編碼輸入str存在相應(yīng)代碼串 譯碼Flag=0結(jié)束1）編碼模塊： 首先通過鍵盤輸入需要鍵盤的字符串，調(diào)用countstr()函數(shù)統(tǒng)計(jì)并儲存字符頻度，再調(diào)用函數(shù)： void CreateHT(HTNode ht,int n) /構(gòu)造哈弗曼樹 int i,j,k,lnode,rnode; double min1,min2; /分別存放lnode和rnode的兩個結(jié)點(diǎn)位置 使所有結(jié)點(diǎn)的相關(guān)域置-1 for(i=n;i<2*

12、n-1;i+) 先尋找權(quán)值最小結(jié)點(diǎn)，使其成為左右孩子結(jié)點(diǎn)； 再求出權(quán)值為左右孩子結(jié)點(diǎn)權(quán)值之和的hi結(jié)點(diǎn)； 使hti作為雙親結(jié)點(diǎn)； 再調(diào)用： void CreateHCode(HTNode ht,HCode hcd,int n) for(i=0;i<n;i+) hc.start=n; c=i; f=hti.parent; 若hti為htf的左孩子結(jié)點(diǎn)，則 hc.cdhc.start-='0' 若hti為htf的右孩子結(jié)點(diǎn)，則 hc.cdhc.start-='1' 再對htf進(jìn)行同樣的判斷，直至f=-1 hc.start+; hcdi=hc; 2）譯碼模塊：

13、先通過鍵盤輸入哈夫曼編碼代碼串，再調(diào)用： int ReadCode(char str1,HCode hcd,HTNode ht,int MAX,int n) /譯碼函數(shù) int i,j,m=0,k; int flag=1; /flag為1則哈弗曼編碼 輸入合法 char temp30="" for(i=0;str1i!='0'i+,m+) /進(jìn)行譯碼 tempm=str1i; for(j=0;j<n;j+) 若找到對應(yīng)編碼 printf("%c",htj.data); for(k=0;k<30;k+) tempk='0

14、' m=-1; 終止循環(huán)； 七、 調(diào)試分析輸入題目所給的數(shù)據(jù)：編碼：譯碼：退出：八、 實(shí)驗(yàn)心得與體會通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當(dāng)求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細(xì)地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。 這次課程設(shè)計(jì)，我在編輯中犯了不應(yīng)有的錯誤，設(shè)計(jì)統(tǒng)計(jì)字符和合并時忘記應(yīng)該怎樣保存數(shù)據(jù)，對文件的操作也很生疏。在不斷分析后明確并改正

15、了錯誤和疏漏，我的程序有了更高的質(zhì)量。九、 附錄哈夫曼編碼/譯碼器源代碼：#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedef struct /赫夫曼樹的結(jié)構(gòu)體char ch;int weight; /權(quán)值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int

16、 a,int *p1,int *p2) /Select函數(shù)，選出HT樹到a為止，權(quán)值最小且parent為0的2個節(jié)點(diǎn)int i,j,x,y;for(j=1;j<=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTx.weight&&HTi.parent=0)x=i; /選出最小的節(jié)點(diǎn)for(j=1;j<=a;+j)if(HTj.parent=0&&x!=j)y=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTy.

17、weight&&HTi.parent=0&&x!=i)y=i; /選出次小的節(jié)點(diǎn)if(x>y)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /構(gòu)建赫夫曼樹HT，并求出n個字符的赫夫曼編碼HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n<=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i<=n;+i) /

18、初始化n個葉子結(jié)點(diǎn)printf("請輸入第%d字符信息和權(quán)值：",i);scanf("%c%d",&z,&w);while(getchar()!='n')continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i<=m;+i) /初始化其余的結(jié)點(diǎn)HTi.ch='0'HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i<=m;+i)

19、 /建立赫夫曼樹Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1='0'for(i=1;i<=n;+i) /給n個字符編碼start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)

20、if(HTf.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件輸入輸出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;cout<<"n"co

21、ut<<" "<<"計(jì)算機(jī)（3）班"<<" "<<"Q07620307"<<" "<<"XXXn"while(choice!='Q'&&choice!='q') /當(dāng)choice的值不為q且不為Q時循環(huán)cout<<" "<<"*赫夫曼編碼/譯碼器*n" cout<<" &q

22、uot;<<"I.Init"<<" "<<"E.Encoding"<<" "<<"D.Decoding"<<" "<<"Q.Exitn" cout<<"請輸入您要操作的步驟："cin>>choice; if(choice='I'|choice='i') /初始化赫夫曼樹cout<<&qu

23、ot;請輸入字符個數(shù)："cin>>n;hfmcoding(HT,HC,n);for(i=1;i<=n;+i)cout<<HTi.ch<<":"<<HCi<<endl;output_file.open("hfmTree.txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;for(i=1;i<=n;i+)output_file<<"(&

24、quot;<<HTi.ch<<HCi<<")"output_file.close();cout<<"赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!"<<endl; else if(choice='E'|choice='e') /進(jìn)行編碼，并將字符放入ToBeTran.txt，碼值放入CodeFile.txt中printf("請輸入字符：");gets(str);output_file.open("ToBeTran.t

25、xt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;output_file<<str<<endl;output_file.close();output_file.open("CodeFile.txt");if(!output_file)cout<<"can't oen file!"<<endl;return 1;for(i=0;i<strlen(str);i+)fo

26、r(j=0;j<=n;+j)if(HTj.ch=stri)output_file<<HCj;break;output_file.close();cout<<"n"cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！n"input_file.open("CodeFile.txt"); /從CodeFile.txt中讀入編碼，輸出在終端if(!input_file)cout<<"can't oen file!"<<endl;return 1;input_file>>code;cout<<"編碼碼值為："<<code<<endl;input_file.close(); else if(choice='D'|choice='d') /讀入CodeFile.txt中的編碼進(jìn)行譯碼，將譯出來的字符放入Textfile.txt中input_file.open("CodeFile