西安工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗報告(赫夫曼編碼)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計赫夫曼編碼院 系： 計算機科學(xué)與工程學(xué)院 專 業(yè)： 計算機科學(xué)與技術(shù) 姓 名： 林煌東 學(xué) 號： 110601111 指導(dǎo)教師： 潘煜 2013年01月03日12目錄一、實驗?zāi)康?二、題目赫夫曼編碼31.問題描述42.基本要求43.測試要求4三、概要設(shè)計41.分析赫夫曼樹的定義42.所實現(xiàn)的功能函數(shù)43.系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）5四、赫夫曼編碼源代碼5五、調(diào)試分析101.輸入102.建立赫夫曼樹103.編碼10六、實驗心得與體會11一、實驗?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ù)的物理

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

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

4、；4.訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。二、題目赫夫曼編碼1.問題描述利用赫夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，因此需要一個完整的赫夫曼編碼系統(tǒng)。試為發(fā)送端編寫一個赫夫曼碼的編碼系統(tǒng)。2.基本要求一個完整的系統(tǒng)應(yīng)具有以下功能：（1）初始化（Initialization）：從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立赫夫曼樹，輸出結(jié)果。（2）編碼（Encoding）：利用已建好的赫夫曼樹，對赫夫曼樹進行編碼，輸出結(jié)果。3.測試要求已知某系統(tǒng)在

5、通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其頻率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，試設(shè)計赫夫曼編碼。三、概要設(shè)計1.分析赫夫曼樹的定義（1）赫夫曼樹節(jié)點的數(shù)據(jù)類型定義為：typedef structint weight; /節(jié)點權(quán)值int parent,lchild,rchild; /左右孩子的節(jié)點htnode,*huffmantree;typedef char * *huffmancode; 2.所實現(xiàn)的功能函數(shù)（1）void huffmancoding(huffmantree ht,huffmancode hc,int *w,int n)/初始化赫夫

6、曼樹，處理函數(shù)得到的數(shù)據(jù)按照赫夫曼規(guī)則建立2叉樹。此函數(shù)塊調(diào)用了Select()函數(shù)。（2）void select(huffmantree ht,int n,int *s1,int *s2) /Select()函數(shù)，選出赫夫曼樹到n為止，權(quán)值最小且parent為0的2個節(jié)點。（3）int main()主函數(shù)/讓用戶利用已建好的赫夫曼樹對輸入的數(shù)據(jù)進行編碼，輸出結(jié)果。使用數(shù)組存儲，然后分別調(diào)用排序函數(shù)，建立赫夫曼函數(shù)，編碼函數(shù)等來實現(xiàn)功能。3.系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）赫夫曼編碼初始化赫夫曼樹打印編碼編碼打印赫夫曼樹四、赫夫曼編碼源代碼#include<stdlib.h>#includ

7、e<stdio.h>#include<string.h>typedef structint weight; /節(jié)點權(quán)值int parent,lchild,rchild; /雙親、左右孩子的節(jié)點htnode,*huffmantree;typedef char * *huffmancode; void select (huffmantree ht,int n,int *s1,int *s2) /挑選權(quán)值較小的兩個節(jié)點int i,j,temp;for(i=1;i<=n;i+)if(hti.parent=0)*s1=i;break;for(j=i+1;j<=n;j+

8、)if(htj.parent=0)*s2=j;break;for(i=1;i<=n;i+) /挑選權(quán)值較小左節(jié)點if(hti.parent=0) if(ht*s1.weight>hti.weight)if(*s2!=i)*s1=i;for(j=1;j<=n;j+) /挑選權(quán)值較小右節(jié)點if(htj.parent=0)if(ht*s2.weight>htj.weight)if(*s1!=j)*s2=j;if(*s1>*s2)temp=*s1;*s1=*s2;*s2=temp;void huffmancoding(huffmantree ht,huffmancode

9、hc,int *w,int n) /求赫夫曼樹的算法int i,m;int start,c,f;int s1,s2;char *cd;if(n<=1) /n小于2無需構(gòu)造赫夫曼樹return ;m=2*n-1; /一共有m=2n-1個節(jié)點ht=(huffmantree) malloc(m+1)*sizeof(htnode); /0號單元沒用；for(i=1;i<=n;i+) /數(shù)組初始化hti.weight=wi-1; hti.parent=0;hti.lchild=0;hti.rchild=0;for(;i<=m;+i)hti.weight=0;hti.parent=0;h

10、ti.lchild=0;hti.rchild=0;printf("*構(gòu)造過程*n");for(i=n+1;i<=m;i+)select(ht,i-1,&s1,&s2); /自己的編寫代碼hts1.parent=i;hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;for(i=1;i<=m;i+)printf("n");printf(" %d %d %d %d %dn",i,hti.weight,hti.p

11、arent,hti.lchild,hti.rchild);printf("n");/從葉子到根節(jié)點的逆向求每個字符的赫夫曼編碼/分配n個字符編碼的頭指針向量；cd=(char*)malloc(n*sizeof(char); /分配球編碼的工作空間cdn-1='0' /編碼結(jié)束符for(i=1;i<=n;i+) /逐個字符求赫夫曼編碼start=n-1; /編碼結(jié)束符位置for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) /從葉子到根你想編碼分配空間if(htf.lchild=c) cd-start='0

12、9;else cd-start='1'hci=(char*)malloc(n-start)*sizeof(char);/為第i個字符編碼分配空間strcpy(hci,&cdstart); /從cd復(fù)制編碼（字符串）到hc/huffancoding int main()int i,n;int *w;huffmantree ht;huffmancode hc;printf("請輸入構(gòu)建赫夫曼樹的節(jié)點數(shù)與權(quán)值");scanf("%dn",&n);hc=(huffmancode)malloc(n*sizeof(huffmancod

13、e);w=(int *)malloc(n*sizeof(int);for(i=0;i<n;i+)scanf("%dn",&wi);huffmancoding(ht,hc,w,n);printf("輸出編碼為：n");for(i=1;i<=n;i+)printf("n");printf(" 權(quán)重為:%d 編碼為:%sn",wi-1,hci);printf("n");fflush(stdin);getchar();return 0;五、調(diào)試分析1.輸入：2.建立赫夫曼樹：3.編碼：六、實驗心得與體會 在這次課程設(shè)計中，自己在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及困難，在我調(diào)試修改程序中的錯誤時，通過分析，我學(xué)到了：1.在定義頭文件時可多不可少，即我們可多寫些頭文件，肯定不會出錯，但是若沒有定義所引用的相關(guān)頭文件，必定調(diào)試不通過；2.編寫和調(diào)試程序時應(yīng)該有足夠的耐心和細心等。 通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，我學(xué)習(xí)了很多在上課沒懂的知識，并對求赫夫曼樹及赫夫曼編碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于赫夫曼編碼的知識，真正學(xué)會一種算法了。當(dāng)求解一個算法