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

1、哈夫曼樹的建立數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)文檔班 級(jí)： 小組組長(zhǎng): 成 員： 指導(dǎo)老師： 第一章 前 言 數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的各種操作。因此，主要有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)；對(duì)數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。在當(dāng)今信息時(shí)代，信息技術(shù)己成為當(dāng)代知識(shí)經(jīng)濟(jì)的核心技術(shù)。我們時(shí)刻都在和數(shù)據(jù)打交道。比如人們?cè)谕獬龉ぷ鲿r(shí)找最短路徑，在銀行查詢存

2、款、通過互聯(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ī)操作對(duì)象以及它們之間的關(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í)際問題中所涉及的對(duì)象在計(jì)算機(jī)中表示出來并對(duì)它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計(jì)主要

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

4、（最短）路徑，節(jié)約比較次數(shù)。2、 層次調(diào)用關(guān)系 在main（）函數(shù)中調(diào)用哈夫曼樹的各種操作函數(shù)3、 ADT描述 Huffman tree n 數(shù)據(jù)對(duì)象D: D為帶有各自實(shí)數(shù)W(D)的數(shù)據(jù)元素的集合 數(shù)據(jù)關(guān)系：D=NULL 則huffmantree不存在DNULL R=H.H為如下二元 關(guān)系： n  D中存在唯一根數(shù)據(jù)元素root,這個(gè)元素?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的組合中，存在一個(gè)組合R使D中所有結(jié)點(diǎn)到root的長(zhǎng)度與其權(quán)值W(Di)相乘的和最小，此時(shí)的<D/R>集合稱為huffmantree.第3章 詳細(xì)設(shè)計(jì)編譯環(huán)境：VC6.0實(shí)現(xiàn)該該程序的主要算法是：基本操作1、 Init huffmant

6、ree(&T) 操作結(jié)果：構(gòu)造一個(gè)已知節(jié)點(diǎn)和權(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è)計(jì)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é)點(diǎn)數(shù)量太少，創(chuàng)建失??！n"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); if(!HT) Error("無法創(chuàng)建哈夫曼樹，請(qǐ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<<" 哈夫曼樹計(jì)算與編碼程序 "<<endl; cout<<" "<<endl; cout<<""<<endl<<endl; p

21、rintf("請(qǐng)輸入節(jié)點(diǎn)的數(shù)量(大于1個(gè)):n"); scanf("%d",&n); if(n=1) system("CLS"); printf("節(jié)點(diǎn)數(shù)太少,請(qǐng)重新輸入.n"); for(int j=1;j<600000000;j+); system("CLS"); goto P; w=(unsigned int *)malloc(n+1)*sizeof(unsigned int *); w0=0; printf("請(qǐng)輸入它們對(duì)應(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<<"請(qǐng)輸入操作編碼："<<endl; cin>>code; system("CLS"); switch(code) case 1: huffmantreecoding(HT,HC,n); system("PAUSE"); cout<<endl<<endl;