數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(赫夫曼樹的建立)

1、哈夫曼樹的建立數(shù)據(jù)結(jié)構(gòu)課程設(shè)計文檔班 級： 小組組長: 成 員： 指導(dǎo)老師： 第一章 前 言 數(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)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，通過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進行某種操作。在當(dāng)今信息時代，信息技術(shù)己成為當(dāng)代知識經(jīng)濟的核心技術(shù)。我們時刻都在和數(shù)據(jù)打交道。比如人們在外出工作時找最短路徑，在銀行查詢存

2、款、通過互聯(lián)網(wǎng)查新聞、以及遠(yuǎn)程教育報名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實際上，現(xiàn)實世界中的實體經(jīng)過抽象以后，就可以成為計算機上所處理的數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(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è)計主要

3、達到以下目的：1、 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；2、 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；3、 提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；四、訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。第2章 概要設(shè)計1、 數(shù)據(jù)結(jié)構(gòu)設(shè)計 使用樹TREE的結(jié)構(gòu)，編造最優(yōu)二叉樹（即哈夫曼樹），涉及到主要函數(shù)有Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree等，用于在一定時間復(fù)雜度內(nèi)尋找到最佳

4、（最短）路徑，節(jié)約比較次數(shù)。2、 層次調(diào)用關(guān)系 在main（）函數(shù)中調(diào)用哈夫曼樹的各種操作函數(shù)3、 ADT描述 Huffman tree n 數(shù)據(jù)對象D: D為帶有各自實數(shù)W(D)的數(shù)據(jù)元素的集合 數(shù)據(jù)關(guān)系：D=NULL 則huffmantree不存在DNULL R=H.H為如下二元 關(guān)系： n  D中存在唯一根數(shù)據(jù)元素root,這個元素?zé)o前驅(qū)。 n  D-root NULL.則存在D-root =D1，Dr.且D1Dr=NULL n  

5、;若D1 NULL ，則D1 中存在唯一元素xr,<root, xr>H n    且存在Dr上關(guān)系HrH,H= <root,x1>,<root,xr>,H1,Hr; n  符合  的R的組合中，存在一個組合R使D中所有結(jié)點到root的長度與其權(quán)值W(Di)相乘的和最小，此時的<D/R>集合稱為huffmantree.第3章 詳細(xì)設(shè)計編譯環(huán)境：VC6.0實現(xiàn)該該程序的主要算法是：基本操作1、 Init huffmant

6、ree(&T) 操作結(jié)果：構(gòu)造一個已知節(jié)點和權(quán)值的哈夫曼樹2、 Destory huffmantree(&T) 條件：huffmantree 已存在結(jié)果：銷毀huffmantree3、 huffman coding（&T）條件：huffmantree 已經(jīng)存在結(jié)果：輸出huffman code4、 Visit huffmantree（&T)條件：huffmantree 已經(jīng)存在結(jié)果：顯示huffman tree一、二叉樹的設(shè)計typedef struct unsigned int weight; unsigned int parent,lchild,rchild

7、; HTNode,*HuffmanTree;typedef char *HuffmanCode;typedef struct unsigned int s1; unsigned int s2;MinCode;二、主要過程int main() int code=0; HuffmanTree HT=NULL; HuffmanCode HC=NULL; unsigned int *w=NULL;unsigned int i,n;printf("Input   n:n"); scanf("%d",&n);w=(un

8、signed int*)malloc(n+1)*sizeof(unsigned int*);       w0=0;    printf("Enter   weight:n");      for(i=1;i<=n;i+)      printf("w%d=",i);scanf(&q

9、uot;%d",&wi);          HT=inithuffmantree(w,n);    huffmantreecoding (HT,HC,n)    outputhuffmantree (HT,n);   destroyhuffmantree (HT);三、結(jié)構(gòu)流程圖4、 程序代碼#include<stdio.h>

10、#include<stdlib.h>#include<cstring>#include<conio.h>#include<iostream>#include<algorithm>using namespace std;typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char *HuffmanCode;typedef struct unsigned int s1; unsigned int

11、 s2;MinCode;void outputhuffmantree(HuffmanTree HT,unsigned int n);HuffmanTree inithuffmantree(unsigned int *w,unsigned int n);HuffmanCode huffmantreecoding(HuffmanTree HT,HuffmanCode HC,unsigned int n);void Error(char *message);MinCode Select(HuffmanTree HT,unsigned int n);void destroyhuffmantree(Hu

12、ffmanTree *ht);void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1);void destroyhuffmantree(HuffmanTree ht) cout<<"-"<<endl; free(ht); printf("huffmantree destroiedn"); exit(1);HuffmanCode huffmantreecoding(HuffmanTree HT,HuffmanCode HC,uns

13、igned int n) char *cd; unsigned int i,start,c,f; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd=(char *)malloc(n*sizeof(char *); cdn-1='0' for(i=1;i<=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)ma

14、lloc(n-start)*sizeof(char *); strcpy(HCi,&cdstart); free(cd); cout<<"-"<<endl; printf("NumberttWeightttCoden"); for(i=1;i<=n;i+) printf("%dtt%dtt%sn",i,HTi.weight,HCi); return HC;HuffmanTree inithuffmantree(unsigned int *w,unsigned int n) unsigned int

15、 i,s1=0,s2=0; HuffmanTree p,HT; unsigned int m; MinCode min; if(n<=1) Error("節(jié)點數(shù)量太少，創(chuàng)建失?。"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); if(!HT) Error("無法創(chuàng)建哈夫曼樹，請查看磁盤空間是否足夠！"); for(p=HT,i=0;i<=n;i+,p+,w+) p->weight=*w; p->parent=0; p->lchild=0; p->rchi

16、ld=0; for(;i<=m;i+,p+) p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; for(i=n+1;i<=m;i+) min=Select(HT,i-1); s1=min.s1; s2=min.s2; HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; return HT;MinCode Select(HuffmanTree HT,unsigned i

17、nt n) unsigned int min,secmin; unsigned int temp; unsigned int i,s1,s2,tempi; MinCode code; s1=1; s2=1; for(i=1;i<=n;i+) if(HTi.parent=0) min=HTi.weight; s1=i; break; tempi=i+; for(;i<=n;i+) if(HTi.weight<min&&HTi.parent=0) min=HTi.weight; s1=i; for(i=tempi;i<=n;i+) if(HTi.parent

18、=0&&i!=s1) secmin=HTi.weight; s2=i; break; for(i=1;i<=n;i+) if(HTi.weight<secmin&&i!=s1&&HTi.parent=0) secmin=HTi.weight; s2=i; if(s1>s2) temp=s1; s1=s2; s2=temp; code.s1=s1; code.s2=s2; return code;void outputhuffmantree(HuffmanTree HT,unsigned int n) unsigned int i

19、; printf("HT List:n"); printf("Numberttweightttparentttlchildttrchildn"); cout<<"*"<<endl; for(i=n+1;i<=2*n-1;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);int main() int code=0; HuffmanTree HT=NULL; HuffmanCode

20、 HC=NULL; unsigned int *w=NULL; unsigned int i,n; P: system("color A"); cout<<""<<endl; cout<<" "<<endl; cout<<" 哈夫曼樹計算與編碼程序 "<<endl; cout<<" "<<endl; cout<<""<<endl<<endl; p

21、rintf("請輸入節(jié)點的數(shù)量(大于1個):n"); scanf("%d",&n); if(n=1) system("CLS"); printf("節(jié)點數(shù)太少,請重新輸入.n"); for(int j=1;j<600000000;j+); system("CLS"); goto P; w=(unsigned int *)malloc(n+1)*sizeof(unsigned int *); w0=0; printf("請輸入它們對應(yīng)的權(quán)值:n"); for(i=

22、1;i<=n;i+) printf("w%d=",i); scanf("%d",&wi); sort(w+1,w+n+1); HT=inithuffmantree(w,n);GP: system("CLS"); cout<<"*"<<endl; cout<<" 1.哈夫曼樹編碼 "<<endl; cout<<" 2.哈弗曼樹顯示 "<<endl; cout<<" 3.摧

23、毀哈夫曼樹并退出程序 "<<endl; cout<<" "<<endl; cout<<"*"<<endl; cout<<"請輸入操作編碼："<<endl; cin>>code; system("CLS"); switch(code) case 1: huffmantreecoding(HT,HC,n); system("PAUSE"); cout<<endl<<endl;