哈弗曼樹課程設(shè)計

1、<p><b>　　09計算機課程設(shè)計</b></p><p>　　哈夫曼編碼/譯碼器（樹的應(yīng)用）</p><p><b>　　題目</b></p><p>　　哈弗曼樹編碼/譯碼（樹的應(yīng)用）</p><p><b>　　二 ．目的</b></p>&l

2、t;p>　　鞏固數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識，了解并初步掌握設(shè)計、實現(xiàn)較大系統(tǒng)的完整過程，包括系統(tǒng)分析、編碼設(shè)計、系統(tǒng)集成、以及調(diào)試分析，從而提高分析問題、解決問題的能力，提高編程技能，培養(yǎng)理論結(jié)合實踐的能力。</p><p>　　熟練掌握數(shù)據(jù)結(jié)構(gòu)的線性表、樹、圖等結(jié)構(gòu)的應(yīng)用的設(shè)計實現(xiàn)以及操作方法，為進一步的應(yīng)用開發(fā)打好基礎(chǔ)。</p><p>　　3. 培養(yǎng)查閱文獻和撰寫文檔的能力。</p

3、><p><b>　　三． 要求</b></p><p>　　1. 課程設(shè)計題目可從指導(dǎo)老師提供的題目列表中選擇或自行提出。從實際情況出發(fā)選擇工作量適當(dāng)、難度適中的題目。自選題目必須要得到指導(dǎo)老師的同意才能開題，否則不予承認，要求課題能夠體現(xiàn)學(xué)生綜合運用所學(xué)知識的能力。</p><p>　　2. 課程設(shè)計可參考已有的成果，但必須在功能、數(shù)據(jù)結(jié)構(gòu)

4、及算法上體現(xiàn)自己的獨到之處。</p><p>　　3. 程序源代碼和課程設(shè)計說明書必須按照相關(guān)要求和格式完成。</p><p>　　四．題目設(shè)計分析：簡述算法實現(xiàn)的過程。</p><p><b>　　1.定義哈弗曼樹。</b></p><p>　　2.設(shè)計算法CrtHuffmanTree存放哈弗曼樹的各個權(quán)值，建立哈弗

5、曼樹。</p><p>　　3.設(shè)計算法CrtHuffmanCode從葉子結(jié)點到根，逆向求每個葉子結(jié)點對應(yīng)的哈夫曼編碼，即“密文”。</p><p>　　4.設(shè)計算法TrsHuffmanTree求哈弗曼編碼對應(yīng)的“明文”。</p><p>　　5．設(shè)計main函數(shù)，利用以上函數(shù)實現(xiàn)建立哈弗曼函數(shù)、求編碼和譯文的目的。</p><p><

6、b>　　五．設(shè)計源代碼</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <string.h></p><p>　　typedef char* HuffmanCode;/*動態(tài)

7、分配數(shù)組，存儲哈夫曼編碼*/</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　unsigned int weight ; /* 用來存放各個結(jié)點的權(quán)值*/</p><p>　　unsigned int parent, LChild,RChild ; /*指向

8、雙親、孩子結(jié)點的指針*/</p><p>　　}HTNode, * HuffmanTree; /*動態(tài)分配數(shù)組，存儲哈夫曼樹*/</p><p>　　void select(HuffmanTree *ht,int n, int *s1, int *s2)</p><p><b>　　{</b></p><p><

9、;b>　　int i;</b></p><p><b>　　int min;</b></p><p>　　for(i=1; i<=n; i++)</p><p><b>　　{</b></p><p>　　if((*ht)[i].parent == 0)</p>

10、<p><b>　　{</b></p><p><b>　　min = i;</b></p><p><b>　　i = n+1;</b></p><p><b>　　}</b></p><p><b>　　}</b>&l

11、t;/p><p>　　for(i=1; i<=n; i++)</p><p><b>　　{</b></p><p>　　if((*ht)[i].parent == 0)</p><p><b>　　{</b></p><p>　　if((*ht)[i].weight &l

12、t; (*ht)[min].weight)</p><p><b>　　min = i;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　*s1 = min;</p><p>　　for(i=1

13、; i<=n; i++)</p><p><b>　　{</b></p><p>　　if((*ht)[i].parent == 0 && i!=(*s1))</p><p><b>　　{</b></p><p><b>　　min = i;</b>&l

14、t;/p><p><b>　　i = n+1;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=1; i<=n; i++)</p><p><b>　　{</b&g

15、t;</p><p>　　if((*ht)[i].parent == 0 && i!=(*s1))</p><p><b>　　{</b></p><p>　　if((*ht)[i].weight < (*ht)[min].weight)</p><p><b>　　min = i;<

16、;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　*s2 = min;</p><p><b>　　}</b></p><p>　　void CrtHuffmanTree(HuffmanT

17、ree *ht , int *w, int n)</p><p>　　{ /* w存放已知的n個權(quán)值，構(gòu)造哈夫曼樹ht */</p><p><b>　　int m,i;</b></p><p>　　int s1,s2;</p><p><b>　　m=2*n-1;</b></p>&

18、lt;p>　　*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0號單元未使用*/</p><p>　　for(i=1;i<=n;i++) </p><p>　　{/*1-n號放葉子結(jié)點，初始化*/</p><p>　　(*ht)[i].weight = w[i];</p><p>

19、;　　(*ht)[i].LChild = 0;</p><p>　　(*ht)[i].parent = 0;</p><p>　　(*ht)[i].RChild = 0;</p><p><b>　　} </b></p><p>　　for(i=n+1;i<=m;i++)</p><p>

20、<b>　　{</b></p><p>　　(*ht)[i].weight = 0;</p><p>　　(*ht)[i].LChild = 0;</p><p>　　(*ht)[i].parent = 0;</p><p>　　(*ht)[i].RChild = 0;</p><p>　　}

21、 /*非葉子結(jié)點初始化*/</p><p>　　/* ------------初始化完畢！對應(yīng)算法步驟1---------*/</p><p>　　for(i=n+1;i<=m;i++) /*創(chuàng)建非葉子結(jié)點,建哈夫曼樹*/</p><p>　　{ /*在(*ht)[1]~(*ht)[i-1]的范圍內(nèi)選擇兩個parent為0且weight最小的結(jié)點，其

22、序號分別賦值給s1、s2返回*/</p><p>　　select(ht,i-1,&s1,&s2);</p><p>　　(*ht)[s1].parent=i;</p><p>　　(*ht)[s2].parent=i;</p><p>　　(*ht)[i].LChild=s1;</p><p>　　(

23、*ht)[i].RChild=s2;</p><p>　　(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;</p><p><b>　　} </b></p><p>　　}/*哈夫曼樹建立完畢*/</p><p>　　void outputHuffman(Huffman

24、Tree HT, int m)</p><p><b>　　{</b></p><p><b>　　if(m!=0)</b></p><p><b>　　{</b></p><p>　　printf("%d ", HT[m].weight);</p&

25、gt;<p>　　outputHuffman(HT,HT[m].LChild);</p><p>　　outputHuffman(HT,HT[m].RChild);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void CrtHu

26、ffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)</p><p>　　/*從葉子結(jié)點到根，逆向求每個葉子結(jié)點對應(yīng)的哈夫曼編碼*/</p><p><b>　　{</b></p><p><b>　　char *cd;</b></p><p><

27、;b>　　int i;</b></p><p>　　unsigned int c;</p><p>　　int start;</p><p><b>　　int p;</b></p><p>　　hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n

28、個編碼的頭指針*/</p><p>　　cd=(char * )malloc(n * sizeof(char )); /*分配求當(dāng)前編碼的工作空間*/</p><p>　　cd[n-1]='\0'; /*從右向左逐位存放編碼，首先存放編碼結(jié)束符*/</p><p>　　for(i=1;i<=n;i++) /*求n個葉子結(jié)點對應(yīng)的哈夫曼編

29、碼*/</p><p><b>　　{</b></p><p>　　start=n-1; /*初始化編碼起始指針*/</p><p>　　for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) /*從葉子到根結(jié)點求編碼*/</p><p>　　if( (*ht

30、)[p].LChild == c) </p><p>　　cd[--start]='0'; /*左分支標0*/</p><p><b>　　else </b></p><p>　　cd[--start]='1'; /*右分支標1*/</p><p>　　hc[i]=(char *)ma

31、lloc((n-start)*sizeof(char)); /*為第i個編碼分配空間*/</p><p>　　strcpy(hc[i],&cd[start]);</p><p><b>　　}</b></p><p><b>　　free(cd);</b></p><p>　　for(i=

32、1;i<=n;i++)</p><p>　　printf("%d編碼為%s\n",(*ht)[i].weight,hc[i]);</p><p><b>　　}</b></p><p>　　void main() </p><p><b>　　{ </b></p>

33、;<p>　　HuffmanTree HT; </p><p>　　HuffmanCode HC; </p><p><b>　　int *w; </b></p><p>　　int i,j,n; // the number of elements; </p><p>　　int wei;

34、// the weight of a element; </p><p><b>　　int m;</b></p><p>　　char a[15];</p><p>　　printf("input the total number of the Huffman Tree:" ); </p><p>

35、　　scanf("%d",&n);</p><p>　　printf("input %d character of the Huffman Tree:", n);</p><p>　　for(i=1;i<=n+1;i++)</p><p>　　scanf("%c",&a[i]);<

36、;/p><p>　　w=(int *)malloc((n+1)*sizeof(int)); </p><p>　　for(j=1;j<=n;j++)</p><p><b>　　{ </b></p><p>　　printf("input the %c 's weight:",a[j+1])

37、; </p><p>　　fflush(stdin);</p><p>　　scanf("%d",&wei); </p><p>　　w[j]=wei; </p><p><b>　　} </b></p><p>　　CrtHuffmanTree(&HT,w,n

38、); </p><p>　　m = 2*n-1;</p><p>　　printf("the Huffman Tree is: ");</p><p>　　outputHuffman(HT,m); </p><p>　　printf("\n");</p><p>　　CrtHuf