數(shù)據(jù)結構課程設計哈夫曼編碼

1、數(shù)據(jù)結構與算法 課程設計（ 2009/2010 學年第二學期第20 周）指導教師： 王老師班級：計算機科學與技術（ 3）班學號：姓名：數(shù)據(jù)結構與算法課程設計目錄一、 前言1 摘要2數(shù)據(jù)結構與算法課程設計任務書二、實驗目的三、題目 - 赫夫曼編碼/譯碼器1問題描述2基本要求3測試要求4實現(xiàn)提示4、 需求分析 - 具體要求5、 概要設計6、 程序說明7、 詳細設計8、 實驗心得與體會1 摘要隨著計算機的普遍應用與日益發(fā)展， 其應用早已不局限于簡單的數(shù)值運算， 而涉及到問題的分析、數(shù)據(jù)結構框架的設計以及設計最短路線等復雜的非數(shù)值處理和操作。 算法與數(shù)據(jù)結構的學習就是為以后利用計算機資源高效地開發(fā)非數(shù)

2、值處理的計算機程序打下堅實的理論、方法和技術基礎。算法與數(shù)據(jù)結構旨在分析研究計算機加工的數(shù)據(jù)對象的特性，以便選擇適當?shù)臄?shù)據(jù)結構和存儲結構，從而使建立在其上的解決問題的算法達到最優(yōu)。數(shù)據(jù)結構是在整個計算機科學與技術領域上廣泛被使用的術語。它用來反映一個數(shù)據(jù)的內(nèi)部構成，即一個數(shù)據(jù)由那些成分數(shù)據(jù)構成， 以什么方式構成， 呈什么結構。 數(shù)據(jù)結構有邏輯上的數(shù)據(jù)結構和物理上的數(shù)據(jù)結構之分。 邏輯上的數(shù)據(jù)結構反映成分數(shù)據(jù)之間的邏輯關系， 而物理上的數(shù)據(jù)結構反映成分數(shù)據(jù)在計算機內(nèi)部的存儲安排。數(shù)據(jù)結構是數(shù)據(jù)存在的形式。數(shù)據(jù)結構 主要介紹一些最常用的數(shù)據(jù)結構， 闡明各種數(shù)據(jù)結構內(nèi)在的邏輯關系， 討論其在計算機中

3、的存儲表示， 以及在其上進行各種運算時的實現(xiàn)算法， 并對算法的效率進行簡單的分析和討論。 數(shù)據(jù)結構是介于數(shù)學、 計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程， 它是計算機程序設計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、系統(tǒng)工程等各種領域。學習數(shù)據(jù)結構是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。 通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業(yè)素質(zhì)的提高。2數(shù)據(jù)結構與算法課程設計任務書數(shù)據(jù)結構與算法 是計算機專業(yè)重要的核心課程之一， 在計算機專業(yè)的學習過程中占有非常重要的地位。 數(shù)據(jù)結構與算法課程設計 就是要運用本課程

4、以及到目前為止的有關課程中的知識和技術來解決實際問題。 特別是面臨非數(shù)值計算類型的應用問題時， 需要選擇適當?shù)臄?shù)據(jù)結構， 設計出滿足一定時間和空間限制的有效算法。本課程設計要求同學獨立完成一個較為完整的應用需求分析。 并在設計和編寫具有一定規(guī)模程序的過程中，深化對數(shù)據(jù)結構與算法課程中基本概念、理論和方法的理解；訓練綜合運用所學知識處理實際問題的能力，強化面向對象的程序設計理念；使自己的程序設計與調(diào)試水平有一個明顯的提高。、實驗目的數(shù)據(jù)結構作為一門學科主要研究數(shù)據(jù)的各種邏輯結構和存儲結構， 以及對數(shù)據(jù)的各種操作。 因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結構；數(shù)據(jù)的物理存儲結構；對數(shù)據(jù)的操作（或算

5、法） 。通常，算法的設計取決于數(shù)據(jù)的邏輯結構， 算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結構。 數(shù)據(jù)結構是信息的一種組織方式， 其目的是為了提高算法的效率， 它通常與一組算法的集合相對應， 通過這組算法集合可以對數(shù)據(jù)結構中的數(shù)據(jù)進行某種操作。在當今信息時代， 信息技術己成為當代知識經(jīng)濟的核心技術。 我們時刻都在和數(shù)據(jù)打交道。 比如人們在外出工作時找最短路徑，在銀行查詢存款、通過互聯(lián)網(wǎng)查新聞、以及遠程教育報名等， 所有這些都在與數(shù)據(jù)發(fā)生關系。實際上，現(xiàn)實世界中的實體經(jīng)過抽象以后，就可以成為計算機上所處理的數(shù)據(jù)。數(shù)據(jù)結構課程主要是研究非數(shù)值計算的程序設計問題中所出現(xiàn)的計算機操作對象以及它們之間的關系和操作的

6、學科。 數(shù)據(jù)結構是介于數(shù)學、 計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎，廣泛的應用于信息學、系統(tǒng)工程等各種領域。學習數(shù)據(jù)結構是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。 通過課程設計可以提高學生的思維能力， 促進學生的綜合應用能力和專業(yè)素質(zhì)的提高。 通過此次課程設計主要達到以下目的：了解并掌握數(shù)據(jù)結構與算法的設計方法，具備初步的獨立分析和設計能力；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；訓練用系統(tǒng)的觀

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

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

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

10、。(2)用戶界面可以設計為“菜單”方式：顯示上述功能符號，再加上“ Q”，表示退出運行 Quito請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了 “Q”為止。(3)在程序的一次執(zhí)行過程中，第一次執(zhí)行I, D或C命令之后，赫夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行 I命令，因為文件hfmTree可能早已建好。四、具體要求：課程設計成果的內(nèi)容必須由以下四個部分組成，缺一不可。（1） 上交源程序：學生按照實驗題目的具體要求所開發(fā)的所有源程序（應該放到一個文件夾中） ；（2） 上交程序的說明文件： （保存在 .txt 中）在說明文檔中應該寫明上交程序所在的目錄，

11、上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說明；（3） 設計報告： （保存在 word 文檔中，文件名要求： 按照“姓名_學號_設計題目”起名，如文件名為“ 張三 _XXX_ 赫夫曼編碼” .doc 。打印稿用A4 紙） 。其中包括 :題目；實驗目的；需求分析：在該部分中敘述實現(xiàn)的功能要求；概要設計：在此說明每個部分的算法設計說明 （可以是描述算法的流程圖） ， 每個程序中使用的存儲結構設計說明（如果指定存儲結構請寫出該存儲結構的定義）；詳細設計各個算法實現(xiàn)的源程序， 對每個題目要有相應的源程序 （可以是一組源程序， 每個功能模塊采用不同的函數(shù)實現(xiàn)）。源程序要按照寫程序的規(guī)則來編

12、寫。要結構清晰，重點函數(shù)的重點變量、重點功能部分要加上清晰的程序注釋；調(diào)試分析測試數(shù)據(jù)， 測試輸出的結果，時間復雜度分析，和每個模塊設計和調(diào)試時存在問題的思考（問題是哪些？問題如何解決？），算法的改進設想；總結：總結可以包括: 設計過程的收獲、遇到問題及解決問題過程的思考、程序調(diào)試能力的思考、對數(shù)據(jù)結構這門課程的思考、在設計過程中對數(shù)據(jù)結構課程的認識等內(nèi)容。（ 4 ）考核成績評定標準：本課程設計的評價由三部分組成， 包括程序演示（ 50%） ， 課程設計報告（ 30%） ， 回答教師提問（ 20%） 。1 程序演示：?優(yōu)功能完善，全部測試正確，并且能夠對局部進行完善。?良功能完善，但測試欠缺。

13、?中功能基本完善，但程序尚有部分錯誤。? 及格 完成內(nèi)存中赫夫曼編碼/ 譯碼，但不涉及文件操作。?不及格功能不完善，且程序錯誤較多，無法運行。2 課程設計報告：1優(yōu)包括設計內(nèi)容，設計思想，已經(jīng)完成的任務及達到的目標，設計思路清晰、書寫條理清楚，源程序結構合理、清晰，注釋說明完整，有對本次課程設計的心得體會。2良包括設計內(nèi)容，設計思想，已經(jīng)完成的任務及達到的目標，設計思路基本清晰、書寫條理基本清楚，源程序結構合理、清晰，注釋說明基本完整，有對本次課程設計的心得體會。3中課程設計報告內(nèi)容基本完整，思路較清晰，書寫基本清楚，源程序結構尚可，有注釋說明但不完整。4及格課程設計報告內(nèi)容基本完整，思路較差

14、，書寫尚清楚。5 不及格課程設計報告內(nèi)容不完整，書寫沒有條理。3回答教師提問：1. 優(yōu)能回答教師提出的所有問題，并完全正確，思路清晰2. 良基本能回答教師提出的所有問題，有些小錯誤3. 中基本能回答教師提出的問題，少數(shù)問題回答錯誤或不清楚4. 及格能回答教師提出的問題，但較多問題回答錯誤或不能回答5. 不及格基本不能回答教師提出的問題四、概要設計1)問題分析哈夫曼樹的定義1 .哈夫曼樹節(jié)點的數(shù)據(jù)類型定義為：typedef struct赫夫曼樹的結構體char ch;int weight;權值int parent,lchild,rchild;htnode,*hfmtree;2)所實現(xiàn)的功能函數(shù)如

15、下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 樹到 a 為止，權值最小且 parent為0的2個節(jié)點2、 int main()主函數(shù)：利用已建好的哈夫曼樹(如不在內(nèi)存，則從文件 hfmtree.txt 中讀入)對文件中的正文進行編碼，然后將結

16、果存入文件code中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲到CodeFile中。3、Encoding編碼功能：對輸入字符進行編碼4、Decoding譯碼功能：利用已建好的哈夫曼樹將文件code中的代碼進行譯碼，結果存入文件text中。Print()打印功能函數(shù)：輸出哈夫曼樹，字符，權值，以及它對應的編碼。5.主函數(shù)的簡要說明，主函數(shù)主要設計的是一個分支語句，讓用戶挑選所實現(xiàn)的功能。使用鏈樹存儲，然后分別調(diào)用統(tǒng)計頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實現(xiàn)功能。2)系統(tǒng)結構圖(功能模塊

17、圖)五.程序說明1 ) . 哈夫曼編碼/譯碼器源代碼#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedef struct/ 赫夫曼樹的結構體char ch;int weight;/權值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,i

18、nt *p2) /Select 函數(shù)，選出 HT 樹到 a 為止，權值最小且 parent 為。的 2 個節(jié) 點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é)點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.w

19、eight&&HTi.parent=0&&x!=i)y=i;/選出次小的節(jié)點if(x>y)*p1=y;*p2=x; else*p1=x; *p2=y; HCvoid hfmcoding(hfmtree &HT,hfmcode &HC,int n) / 構建赫夫曼樹HT ， 并求出 n 個字符的赫夫曼編碼int 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

20、<=n;+i)/初始化 n 個葉子結點 printf(" 請輸入第 %d 字符信息和權值： ",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)/初始化其余的結點 HTi.ch='0' HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi

21、.rchild=0; for(i=n+1;i<=m;+i)/建立赫夫曼樹 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

22、=HTi.parent;f!=0;c=f,f=HTf.parent) 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;hf

23、mcode HC;cout<<"n"cout<<""<<" 計算機( 3 )班 "<<""<<"Q07620307"<<""<<"XXXn"while(choice!='Q'&&choice!='q')/ 當 choice 的值不為 q 且不為 Q 時循環(huán) cout<<" "<<&q

24、uot;*赫夫曼編碼/譯碼器*、c” .cout«""«"l.lnit"«""«"E.Encoding"«""«"D.Decoding"«""«"Q.Exitn"cout<<"請輸入您要操作的步驟：cin»choice;if(choice=T|choice='i')初始化赫夫曼樹(cout<< ”請

25、輸入字符個數(shù)：cin»n;hfmcoding(HT,HC,n);for(i=1 ;i<=n;+i)(cout«HTi.ch«":"«HCi«endl;)output_("hfmT ree.txt");if(!output_file)cout«"can't oen file!"«endl;return 1;)for(i=1 ;i<=n;i+)(output_file«"("«HTi.ch«HCi&l

26、t;<")")output_();cout<<"赫夫曼樹已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!"«endl;)else if(choice='E'|choice='e')進行編碼，并將字符放入ToBeTran.txt,碼值放入Code 中(printf("請輸入字符：");gets(str);output_("T oBeTran.txt");if(!output_file)(cout«"can't oen fi

27、le!"«endl;return 1;)output_file«str«endl;output_();output_("Code");if(!output_file)cout«"can't oen file!"«endl;return 1;)for(i=0;i<strlen(str);i+)for(j=0;j<=n;+j)if(HTj.ch=stri) output_file<<HCj; break; output_(); cout<<"n&

28、quot;cout<<" 編碼完畢，并且已經(jīng)存入 Code 文件！ n" input_("Code");/從 Code 中讀入編碼，輸出在終端if(!input_file) cout<<"can't oen file!"<<endl; return 1; input_file>>code;Textcout<<" 編碼碼值為： "<<code<<endl; input_(); else if(choice='D'

29、;|choice='d') /讀入 Code 中的編碼進行譯碼， 將譯出來的字符放入 中 input_("Code"); if(!input_file) cout<<"can't oen file!"<<endl; return 1; input_file>>h; input_();output_("Text"); if(!output_file) cout<<"can't oen file!"<<endl; return

30、1;k=0;while(hk!='0')/先用編碼中的前幾個和字符的編碼相比較，然后往后移 for(i=1;i<=n;i+) l=k; for(j=0;j<strlen(HCi);j+,l+) hlj=hl; hlj='0'if(strcmp(HCi,hl)=0) output_file<<HTi.ch;k=k+strlen(HCi);break;output_();input_("Text");if(!input_file)cout<<"can't oen file!"<

31、<endl;return 1;input_file>>h;cout<<h<<endl;input_();cout<<" 譯碼結束，字符已經(jīng)存入 Text 文件中！ "<<endl;else if(choice='Q'|choice='q')/退出程序exit(0);else/如果選了選項之外的就讓用戶重新選擇cout<<" 您沒有輸入正確的步驟，請重新輸入！ "<<endl;cout<<endl;return 0;六調(diào)試分析dbE一清清酒清*MM 1 flrtlGIMi Lit AMASAlflWlisa iiitf 118111Bill imi AW Aimi M1L10 Aisaimis監(jiān)血lllDM 11U 決耍樹己迂創(chuàng)盤完畢.并且三好放入月球編碼*京京表 號端碼器 / M Mi M X M W M* M - Hi *MiX K M M Mi1 »I n itE. EncodingD.DecodinsrQ . Ex it中建小繆黑操作的步驟：E請輸入字佞fl編碼完畢，并且己經(jīng)存入c口的Fil八七海文件|編碼用值為1。KMFM耳M苒一碑MMMXMMM苒KXM