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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)赫夫曼編碼院 系： 計(jì)算機(jī)科學(xué)與工程學(xué)院 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 姓 名： 林煌東 學(xué) 號： 110601111 指導(dǎo)教師： 潘煜 2013年01月03日12目錄一、實(shí)驗(yàn)?zāi)康?二、題目赫夫曼編碼31.問題描述42.基本要求43.測試要求4三、概要設(shè)計(jì)41.分析赫夫曼樹的定義42.所實(shí)現(xiàn)的功能函數(shù)43.系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）5四、赫夫曼編碼源代碼5五、調(diào)試分析101.輸入102.建立赫夫曼樹103.編碼10六、實(shí)驗(yàn)心得與體會(huì)11一、實(shí)驗(yàn)?zāi)康?數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此，主要有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理

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

3、關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。 學(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á)到以下目的：1.了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；3.提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力

4、；4.訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。二、題目赫夫曼編碼1.問題描述利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，因此需要一個(gè)完整的赫夫曼編碼系統(tǒng)。試為發(fā)送端編寫一個(gè)赫夫曼碼的編碼系統(tǒng)。2.基本要求一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：（1）初始化（Initialization）：從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹，輸出結(jié)果。（2）編碼（Encoding）：利用已建好的赫夫曼樹，對赫夫曼樹進(jìn)行編碼，輸出結(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è)計(jì)赫夫曼編碼。三、概要設(shè)計(jì)1.分析赫夫曼樹的定義（1）赫夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定義為：typedef structint weight; /節(jié)點(diǎn)權(quán)值int parent,lchild,rchild; /左右孩子的節(jié)點(diǎn)htnode,*huffmantree;typedef char * *huffmancode; 2.所實(shí)現(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個(gè)節(jié)點(diǎn)。（3）int main()主函數(shù)/讓用戶利用已建好的赫夫曼樹對輸入的數(shù)據(jù)進(jìn)行編碼，輸出結(jié)果。使用數(shù)組存儲，然后分別調(diào)用排序函數(shù)，建立赫夫曼函數(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é)點(diǎn)權(quán)值int parent,lchild,rchild; /雙親、左右孩子的節(jié)點(diǎn)htnode,*huffmantree;typedef char * *huffmancode; void select (huffmantree ht,int n,int *s1,int *s2) /挑選權(quán)值較小的兩個(gè)節(jié)點(diǎn)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é)點(diǎn)if(hti.parent=0) if(ht*s1.weight>hti.weight)if(*s2!=i)*s1=i;for(j=1;j<=n;j+) /挑選權(quán)值較小右節(jié)點(diǎn)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個(gè)節(jié)點(diǎn)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é)點(diǎn)的逆向求每個(gè)字符的赫夫曼編碼/分配n個(gè)字符編碼的頭指針向量；cd=(char*)malloc(n*sizeof(char); /分配球編碼的工作空間cdn-1='0' /編碼結(jié)束符for(i=1;i<=n;i+) /逐個(gè)字符求赫夫曼編碼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個(gè)字符編碼分配空間strcpy(hci,&cdstart); /從cd復(fù)制編碼（字符串）到hc/huffancoding int main()int i,n;int *w;huffmantree ht;huffmancode hc;printf("請輸入構(gòu)建赫夫曼樹的節(jié)點(diǎn)數(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í)驗(yàn)心得與體會(huì) 在這次課程設(shè)計(jì)中，自己在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤，遇到了很多麻煩及困難，在我調(diào)試修改程序中的錯(cuò)誤時(shí)，通過分析，我學(xué)到了：1.在定義頭文件時(shí)可多不可少，即我們可多寫些頭文件，肯定不會(huì)出錯(cuò)，但是若沒有定義所引用的相關(guān)頭文件，必定調(diào)試不通過；2.編寫和調(diào)試程序時(shí)應(yīng)該有足夠的耐心和細(xì)心等。 通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒懂的知識，并對求赫夫曼樹及赫夫曼編碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于赫夫曼編碼的知識，真正學(xué)會(huì)一種算法了。當(dāng)求解一個(gè)算法