數(shù)據(jù)結(jié)構(gòu)課程方案設(shè)計書哈夫曼編碼2

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計目 錄一、前言1摘要2. 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書二、實驗?zāi)康娜?、題目-赫夫曼編碼/譯碼器1問題描述2. 基本要求3. 測試要求4. 實現(xiàn)提示四、需求分析-具體要求五、概要設(shè)計六、程序說明七、詳細(xì)設(shè)計八、實驗心得與體會.、八、 一前言1.摘要隨著計算機(jī)的普遍應(yīng)用與日益發(fā)展， 其應(yīng)用早已不局限于簡單的數(shù)值運算， 而涉及到問題的分析、 數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計以及設(shè)計最短路線等復(fù)雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)就是為以后利用計算機(jī)資源高效地開發(fā)非數(shù)值處理的計算機(jī)程序打下堅實的理論、方法和技術(shù)基礎(chǔ)。算法與數(shù)據(jù)結(jié)構(gòu)旨在分析研究計算機(jī)加工的數(shù)據(jù)對象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)

2、結(jié)構(gòu)和存儲結(jié) 構(gòu)，從而使建立在其上的解決問題的算法達(dá)到最優(yōu)。數(shù)據(jù)結(jié)構(gòu)是在整個計算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個數(shù)據(jù)的內(nèi)部構(gòu)成，即一個數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成， 以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理 上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計算機(jī)內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。數(shù)據(jù)結(jié)構(gòu) 主要介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計算機(jī)中的存儲表示，以及在其上進(jìn)行各種運算時的實現(xiàn)算法，并對算法的效率進(jìn)行簡單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)軟件和計算機(jī)硬件之間

3、的一門計算機(jī)專業(yè)的核心課程，它是計算機(jī)程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。2.數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書數(shù)據(jù)結(jié)構(gòu)與算法 是計算機(jī)專業(yè)重要的核心課程之一，在計算機(jī)專業(yè)的學(xué)習(xí)過程中占有非常重要的地位。數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計 就是要運用本課程以及到目前為止的有關(guān)課程中的知識和技術(shù)來 解決實際問題。特別是面臨非數(shù)值計算類型的應(yīng)用問題時，需要選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)， 設(shè)計出滿足一定時間和空間

4、限制的有效算法。本課程設(shè)計要求同學(xué)獨立完成一個較為完整的應(yīng)用需求分析。并在設(shè)計和編寫具有一定規(guī)模程序的過程中，深化對數(shù)據(jù)結(jié)構(gòu)與算法課程中基本概念、理論和方法的理解；訓(xùn)練綜合運用所學(xué)知識處理 實際問題的能力，強(qiáng)化面向?qū)ο蟮某绦蛟O(shè)計理念；使自己的程序設(shè)計與調(diào)試水平有一個明顯的提高。、實驗?zāi)康臄?shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此,主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲結(jié)構(gòu)；對數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組

5、算法的集合相對應(yīng)，通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。在當(dāng)今信息時代，信息技術(shù)己成為當(dāng)代知識經(jīng)濟(jì)的核心技術(shù)。 我們時刻都在和數(shù)據(jù)打交道。比如人們在外出工作時找最短路徑，在銀行查詢存款、通過互聯(lián)網(wǎng)查新聞、以及遠(yuǎn)程教育報名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實際上，現(xiàn)實世界中的實體經(jīng)過抽象以后，就可以成為計算機(jī)上所處理的數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機(jī)操作對象以及它們之間的 關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)軟件和計算機(jī)硬件之間的一門計算機(jī)專業(yè)的核心課程， 它是計算機(jī)程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信

6、息學(xué)、 系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達(dá)到以下目的：+了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；律初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；+提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；*訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。三、題目-赫夫曼編碼/譯碼器1. 問題描述利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用

7、率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個赫夫曼碼的編/譯碼系統(tǒng)。2. 基本要求一個完整的系統(tǒng)應(yīng)具有以下功能：I :初始化(Initialization )。從終端讀入字符集大小n,以及n個字符和n個權(quán)值，建立赫夫曼樹，并將它存于文件 hfmTree中。E :編碼(Encoding )。利用已建好的赫夫曼樹(如不在內(nèi)存，則從文件hfmTree中讀入)，對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件

8、CodeFile中。D :譯碼(Decoding )。利用已建好的赫夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile 中。以下為選做：P:印代碼文件(Print )。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。T：印赫夫曼樹(Tree printing )。將已在內(nèi)存中的赫夫曼樹以直觀的方式(比如樹)顯示在終端上， 同時將此字符形式的赫夫曼樹寫入文件TreePrint中。3. 測試要求(1) 已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其頻率分別為0.05,0.29,0.07,0.08,0.14,0

9、.23,0.03,0.11，試設(shè)計赫夫曼編碼。(2) 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立赫夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THISPROGRAME IS MY FAVORITE ”。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381811614. 實現(xiàn)提示(1) 編碼結(jié)果以文本方式存儲在文件Codefile中。(2) 用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行 Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選

10、擇了“Q”為止。(3) 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，赫夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。四、具體要求：課程設(shè)計成果的內(nèi)容必須由以下四個部分組成，缺一不可。（1）上交源程序：學(xué)生按照實驗題目的具體要求所開發(fā)的所有源程序（應(yīng)該放到一個文件夾中）；（2）上交程序的說明文件：（保存在.txt中）在說明文檔中應(yīng)該寫明上交程序所在的目錄，上交程序 的主程序文件名，如果需要安裝，要有程序的安裝使用說明；（3）設(shè)計報告：（保存在word文檔中，文件名要求：按照“姓名_學(xué)號_設(shè)計題目”起名，如文件名為“張三_XXX_赫夫曼編

11、碼” .doc。打印稿用A4紙）。其中包括：+ 題目；+ 實驗?zāi)康模? 需求分析：在該部分中敘述實現(xiàn)的功能要求；+ 概要設(shè)計：在此說明每個部分的算法設(shè)計說明（可以是描述算法的流程圖），每個程序中使用的存儲結(jié)構(gòu)設(shè)計說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義）；+ 詳細(xì)設(shè)計各個算法實現(xiàn)的源程序， 對每個題目要有相應(yīng)的源程序（可以是一組源程序， 每個功能模塊采用不同的函數(shù)實現(xiàn)）。源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量、重點功能部 分要加上清晰的程序注釋；+ 調(diào)試分析測試數(shù)據(jù)，測試輸出的結(jié)果，時間復(fù)雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考（問題是 哪些？問題如何解決？）

12、，算法的改進(jìn)設(shè)想；+ 總結(jié)：總結(jié)可以包括：設(shè)計過程的收獲、遇到問題及解決問題過程的思考、程序調(diào)試能力的思考、對數(shù) 據(jù)結(jié)構(gòu)這門課程的思考、在設(shè)計過程中對數(shù)據(jù)結(jié)構(gòu)課程的認(rèn)識等內(nèi)容。（4）考核成績評定標(biāo)準(zhǔn)：本課程設(shè)計的評價由三部分組成，包括程序演示（50%）,課程設(shè)計報告（30%,回答教師提問（20%。1. 程序演示：優(yōu)功能完善，全部測試正確，并且能夠?qū)植窟M(jìn)行完善。良功能完善，但測試欠缺。中功能基本完善，但程序尚有部分錯誤。及格 完成內(nèi)存中赫夫曼編碼/譯碼，但不涉及文件操作。 不及格功能不完善，且程序錯誤較多，無法運行。2 課程設(shè)計報告:1優(yōu)包括設(shè)計內(nèi)容，設(shè)計思想，已經(jīng)完成的任務(wù)及達(dá)到的目標(biāo)，設(shè)計

13、思路清晰、書寫條理清楚，源程序結(jié)構(gòu)合理、清晰，注釋說明完整，有對本次課程設(shè)計的心得體會。2良包括設(shè)計內(nèi)容，設(shè)計思想，已經(jīng)完成的任務(wù)及達(dá)到的目標(biāo)，設(shè)計思路基本清晰、書寫條理基本清楚，源程序結(jié)構(gòu)合理、清晰，注釋說明基本完整，有對本次課程設(shè)計的心得體會。3中課程設(shè)計報告內(nèi)容基本完整，思路較清晰，書寫基本清楚，源程序結(jié)構(gòu)尚可，有注釋說明但不完整。4及格 課程設(shè)計報告內(nèi)容基本完整，思路較差，書寫尚清楚。5. 不及格 課程設(shè)計報告內(nèi)容不完整，書寫沒有條理。3 .回答教師提問：1. 優(yōu)能回答教師提出的所有問題，并完全正確，思路清晰2. 良基本能回答教師提出的所有問題，有些小錯誤3. 中基本能回答教師提出的問

14、題，少數(shù)問題回答錯誤或不清楚4. 及格 能回答教師提出的問題，但較多問題回答錯誤或不能回答5. 不及格基本不能回答教師提出的問題四、概要設(shè)計1) 問題分析哈夫曼樹的定義1.哈夫曼樹節(jié)點的數(shù)據(jù)類型定義為：typedef struct赫夫曼樹的結(jié)構(gòu)體char ch;int weight;/ 權(quán)值int parent,lchild,rchild;htnode,*hfmtree;2) 所實現(xiàn)的功能函數(shù)如下1、 void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼樹，處理InputHuffman(HuffmanHfm)函數(shù)得到的數(shù)據(jù)，按照

15、哈夫曼規(guī)則建立2叉樹。此函數(shù)塊調(diào)用了Select ()函數(shù)。2、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函數(shù)，選出 HT 樹到 a 為止，權(quán)值最小且pare nt為0的2個節(jié)點2、int mai n()主函數(shù)：利用已建好的哈夫曼樹(如不在內(nèi)存，則從文件hfmtree.txt 中讀入)對文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲到 ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容， 將編碼好的哈夫曼編碼存儲到 CodeFile 中。3、En

16、coding編碼功能：對輸入字符進(jìn)行編碼4、Decoding譯碼功能：利用已建好的哈夫曼樹將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat 中。Print()打印功能函數(shù)：輸出哈夫曼樹，字符，權(quán)值，以及它對應(yīng)的編碼。5. 主函數(shù)的簡要說明，主函數(shù)主要設(shè)計的是一個分支語句，讓用戶挑選所實現(xiàn)的功能。使用鏈樹存儲，然后分別調(diào)用統(tǒng)計頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實現(xiàn) 功能。2)系統(tǒng)結(jié)構(gòu)圖(功能模塊圖)五. 程序說明1).哈夫曼編碼/譯碼器源代碼#in clude<iostream.h>#in clude<stdio.h&g

17、t;#in clude<stdlib.h>#in clude<stri ng.h>#in clude<fstream.h>typedef struct/赫夫曼樹的結(jié)構(gòu)體char ch;int weight;/ 權(quán)值int pare nt,lchild,rchild;ht no de,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2)/Select 函數(shù)，選出 HT 樹到 a 為止，權(quán)值最小且 parent 為 0 的 2 個節(jié)占八、int i,j,

18、x,y;for(j=1;j<=a;+j)if(HTj.pare nt=0)x=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTx.weight&&H Ti.pare nt=0)x=i;選出最小的節(jié)點for(j=1;j<=a;+j) if(HTj.pare nt=0&& x!=j)y=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTy.weight&&H Ti.pare nt=0&& x!=i)y=i;選出次小的節(jié)點if(x&

19、gt;y)*p 仁y;*p2=x;else*p 仁x;*p2=y;HCvoid hfmcoding(hfmtree &Hhfmcode &HC,int n) / 構(gòu)建赫夫曼樹 HT,并求出n個字符的赫夫曼編碼 int i,start,c,f,m,w;in t p1,p2;char *cd,z;if(n<=1)return;m=2* n-1;HT=(hfmtree)malloc(m+1)*sizeof(ht no de);for(i=1;i<=n;+i)/初始化n個葉子結(jié)點printf("請輸入第%d字符信息和權(quán)值：",i);scan f(&quo

20、t;%c%d"，&z,&w);while(getchar()!='n')con ti nue;HTi.ch=z;HTi.weight=w;HTi.pare nt=O;HTi.lchild=O;HTi.rchild=O;for(;i<=m;+i)初始化其余的結(jié)點HTi.ch='O'HTi.weight=O;HTi.pare nt=O;HTi.lchild=O;HTi.rchild=O;for(i=n+1;i<=m;+i)/ 建立赫夫曼樹Select(HT,i-1,&p1,&p2);HTp1.pare nt=i;

21、HTp2.pare nt=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);cd n-1='0：for(i=1;i<=n;+i)給 n 個字符編碼start=n-1;for(c=i,f=HTi.pare nt;f!=O;c=f,f=HTf.pare nt)if(HTf.lchild=c)cd-start='0'elsecd-start=&

22、#39;1'HCi=(char*)malloc( n-start)*sizeof(char); strcpy(HCi,&cdstart);free(cd); int mai n()char code100,h100,hl100;int n,i,j,k,l;ifstream in put_file;/文件輸入輸出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;cout<<"n""<<"Q07620307"<<"

23、;/當(dāng)choice的值不為"<<"XXXn"q且不為Q時循環(huán)cout<<""<<"計算機(jī)(3 )班"<<"while(choice!=Q&&choice!='q')cout<<""<<H*赫夫曼編碼/譯碼器*n"cout<<""<<"1ni t"<<""<<"E.E

24、ncodi ng"<<""<<"D.Decod in g"<<""<<"Q.Exit n"cout<<"請輸入您要操作的步驟:cin> >choice;/初始化赫夫曼樹if(choice=T|choice='i')cout<<"請輸入字符個數(shù): cin»n;hfmcodi ng(HT,HC, n);for(i=1;i<=n ;+i)cout<<HTi.ch&l

25、t;<":"<<HCi<<e ndl; output_file.ope n("hfmTree.txt"); if(!output_file)cout<<"ca n't oen file!"<<e ndl;return 1;for(i=1;i<=n ;i+)output_file<<"("<<HTi.ch<<HCi<<")"output_file.close();cout<&l

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

27、lt;e ndl; return 1;output_file<<str<<e ndl; output_file.close();output_file.ope n( "CodeFile.txt"); if(!output_file)cout<<"ca n't oen file!"<<e ndl;return 1;for(i=0;i<strle n( str);i+)for(j=0;j<=n;+j)if(HTj.ch=stri)output_file<<HCj;break;ou

28、tput_file.close();cout<<"n"cout<<"編碼完畢，并且已經(jīng)存入CodeFile.txt文件！ n"input_file.open("CodeFile.txt");/從 CodeFile.txt 中讀入編碼，輸出在終端if(!i nput_file)cout<<"ca n't oen file!"<<e ndl;return 1;in put_file>>code;cout<<"編碼碼值為："

29、;<<code<<endl;in put_file.close();else if(choice='D'|choice='d') /讀入CodeFile.txt中的編碼進(jìn)行譯碼，將譯出來的字符放入 Textfile.txt 中in put_file.ope n( "CodeFile.txt");if(!i nput_file)cout<<"ca n't oen file!"<<e ndl;return 1;in put_file>>h;in put_fil

30、e.close();output_file.ope n("Textfile.txt");if(!output_file)cout<<"ca n't oen file!"<<e ndl;return 1;k=0;while(hk!='0')/先用編碼中的前幾個和字符的編碼相比較，然后往后移for(i=1;i<=n; i+)l=k;for(j=0;j<strle n(HCi);j+,l+)hlj=hl;hlj='0'if(strcmp(HCi,hl)=O)output_file<

31、;<HTi.ch;k=k+strle n(HCi); break;output_file.close();in put_file.ope n("Textfile.txt");if(!i nput_file)cout<<"ca n't oen file!"<<e ndl;return 1;in put_file>>h;cout<<h<<e ndl;in put_file.close();cout<<"譯碼結(jié)束，字符已經(jīng)存入 Textfile.txt文件中！&qu

32、ot;<<endl;else if(choice=Q|choice='q')/ 退出程序Iexit(0); else/如果選了選項之外的就讓用戶重新選擇cout<<"您沒有輸入正確的步驟，請重新輸入！"<<endl;cout<<e ndl;return 0;六. 調(diào)試分析編碼HXXMEX 耳 XiMH 轉(zhuǎn) MMEJCKXiMHXrXXJCKXM：工阮卜廣-4蘭扁吊馬尋骨 H X Mi JC J< K K XU X M X J< K K It X K 耳 X :H KKKXI « Init：E. ErkcodiiiD. DecodiflgQ.Exit清揄入您葺操作的歩驟：衛(wèi)睛輸入字符1 *并且已經(jīng)存入CodePile.txt文件