第一篇：數(shù)據(jù)結(jié)構(gòu)huffman編碼作業(yè)報(bào)告

哈夫曼編碼與解碼

一、設(shè)計(jì)思想

在設(shè)計(jì)本程序時(shí)，主要用到的算法有如下三個(gè)：

一、創(chuàng)建哈夫曼樹(shù)算法；

二、求哈夫曼編碼算法；

三、求哈夫曼解碼算法。? 創(chuàng)建哈夫曼樹(shù)算法如下：

1)存儲(chǔ)結(jié)構(gòu)：構(gòu)造由信息元素與對(duì)應(yīng)的權(quán)值組成的信息元素結(jié)構(gòu)體來(lái)存儲(chǔ)已給定的字母與其權(quán)重信息；構(gòu)造由信息元素、權(quán)值、當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)組成的哈夫曼樹(shù)結(jié)點(diǎn)結(jié)構(gòu)體來(lái)存儲(chǔ)樹(shù)結(jié)點(diǎn)的信息，還會(huì)很方便地幫助創(chuàng)建哈夫曼樹(shù)；構(gòu)造由信息元素與對(duì)應(yīng)的哈夫曼編碼結(jié)構(gòu)體來(lái)存儲(chǔ)哈夫曼編碼信息；方便進(jìn)行對(duì)數(shù)據(jù)的編碼。2)結(jié)構(gòu)體數(shù)組處理：哈夫曼樹(shù)沒(méi)有度為 1 的結(jié)點(diǎn)，若一個(gè)哈夫曼樹(shù)由 n 個(gè)葉子結(jié)點(diǎn)，則該哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)。應(yīng)用以上的原理，根據(jù)用戶輸入的信息元素的個(gè)數(shù)n開(kāi)辟大小為2n-1的哈夫曼樹(shù)數(shù)組來(lái)滿足創(chuàng)建哈夫曼樹(shù)的需要，并對(duì)此數(shù)組進(jìn)行初始化，葉子結(jié)點(diǎn)的信息元素與權(quán)值即給定的的信息元素與權(quán)值；非葉子結(jié)點(diǎn)的信息元素與權(quán)值設(shè)置為空值；所有哈夫曼樹(shù)結(jié)點(diǎn)的父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)設(shè)置為 0。

3)選擇權(quán)值最小與次?。涸谶M(jìn)行比較的過(guò)程中循環(huán)取出權(quán)值進(jìn)行比較，設(shè)置兩個(gè)s1，s2分別記錄本次循環(huán)最小與次小的權(quán)值，進(jìn)行下一次的比較選擇。返回權(quán)值最小與次小的哈夫曼樹(shù)結(jié)點(diǎn)信息。

4)生成小樹(shù)：應(yīng)用3)中想法，在用戶輸入的信息元素中選擇權(quán)值中最小與次小的元素分別賦值給右葉子結(jié)點(diǎn)與左葉子結(jié)點(diǎn)，并把這兩個(gè)權(quán)值之和賦值給這兩個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，記錄父結(jié)點(diǎn)位置。

5)生成哈夫曼樹(shù)：再應(yīng)用3)4)把這些小樹(shù)的父結(jié)點(diǎn)的權(quán)值進(jìn)行比較選擇，選擇權(quán)值比較大的設(shè)置為新的右結(jié)點(diǎn)的權(quán)值，權(quán)值比較小的設(shè)置為左結(jié)點(diǎn)，把這兩個(gè)權(quán)值的和賦值給新的父結(jié)點(diǎn)；以此重復(fù)進(jìn)行，最終生成哈夫曼樹(shù)。? 求哈夫曼編碼算法如下

1)采用無(wú)棧非遞歸遍歷哈夫曼樹(shù)：每次站在根結(jié)點(diǎn)遍歷哈夫曼樹(shù)，直至到達(dá)某一個(gè)葉子結(jié)點(diǎn)為止，并臨時(shí)用一個(gè)數(shù)組記錄遍歷過(guò)程中每個(gè)結(jié)點(diǎn)的狀態(tài)。編碼完成后再?gòu)?fù)制給哈夫曼編碼結(jié)構(gòu)體中的編碼數(shù)組。

2)遍歷與編碼：在邏輯上，遍歷時(shí)向左子時(shí)，編碼為0，向右子為1，將每次的結(jié)點(diǎn)狀態(tài)記錄連接即哈夫曼編碼；站在根結(jié)點(diǎn)上，若到左子上記錄此時(shí)的結(jié)點(diǎn)狀態(tài)為0，并把指針指向左子，進(jìn)行下一次的遍歷，若到右結(jié)點(diǎn)上記錄此時(shí)的結(jié)點(diǎn)狀態(tài)1，并把指針指向右子，進(jìn)行下一次的判斷遍歷；重復(fù)進(jìn)行，到達(dá)某一個(gè)葉子結(jié)點(diǎn)為止，完畢后，將每次

哈夫曼編碼與解碼

下面是哈夫曼編碼過(guò)程的大致過(guò)程（如圖2）：

圖2 為huffman樹(shù)的各節(jié)點(diǎn)進(jìn)行編碼

下面是對(duì)指定文件內(nèi)信息編碼的大致過(guò)程（如圖3）：

圖3 信息的編碼

哈夫曼編碼與解碼

{

int j,k;/*找出第一個(gè)單節(jié)點(diǎn)樹(shù)*/

for(k=1;k<=i;k++)

{

if(ht[k].parent!=0)

{ } continue;

s1=k;

break;

} /*找出其中權(quán)重最小的樹(shù)*/

for(j=1;j<=i;j++)

{

if(ht[j].parent!=0)

{ } { }

continue;

if(ht[j].weight

s1=j;

} /*找出第二個(gè)單節(jié)點(diǎn)樹(shù)*/

for(k=1;k<=i;k++)

{

if(ht[k].parent!=0||k==s1){ }

continue;

s2=k;

break;

} /*找出其中權(quán)重次小的樹(shù)*/

for(j=1;j<=i;j++)

{

if(ht[j].parent!=0)

{ } {

continue;

if(ht[j].weight

s2=j;

哈夫曼編碼與解碼

cd[--Istart]='0';

} { }

else/*右1*/

cd[--Istart]='1';

hc[i]=(char *)malloc((n-Istart)*sizeof(char));

strcpy(hc[i], &cd[Istart]);/*將臨時(shí)儲(chǔ)存的code拷貝至hc中*/ }

}

free(cd);/*釋放cd*/ }

void main(){

char text[300];/*聲明儲(chǔ)存源碼或Huffman碼的臨時(shí)數(shù)組*/

int i,j,count,choice;/*儲(chǔ)存字母數(shù)組*/ /*儲(chǔ)存字母對(duì)應(yīng)權(quán)重的數(shù)組*/

char zi[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

int w[26]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};

huffmantree ht;

huffmancode hc;

HuffmanTree(ht,w,zi,26);/*生成huffman樹(shù)*/

huffmancoding(ht,hc,26);/*根據(jù)huffman樹(shù)生成huffman碼*/

FILE *fp;

printf(“[1]Encoding...n”);printf(“[2]Decoding...n”);scanf(“%d”,&choice);if(choice==1)/*1為編碼*/ {

char file[20];printf(“Please choice the file:”);/*輸入需要編碼的文件名*/ scanf(“%s”,file);printf(“******************從%s文件讀取字符串******************n”,file);if((fp=fopen(file,“r”))==NULL){ } fgets(text,300,fp);/*從文件中讀取字符串*/ fclose(fp);printf(“Source code is:”);/*輸出讀取的字符串*/ puts(text);printf(“cannot open this filen”);

printf(“Please choice function:”);/*選擇編碼還是譯碼*/

哈夫曼編碼與解碼

}

}

} printf(“n”);} /*顯示由部分電碼譯碼得到的字符，并準(zhǔn)備對(duì)后面的電碼進(jìn)行譯碼*/ printf(“%c”,ht[count].letter);count=51;

四、運(yùn)行結(jié)果

下圖是對(duì)SourceCode.txt文件信息進(jìn)行編碼，所得到的效果圖（如圖5所示）：

圖5 對(duì)SourceCode.txt文件進(jìn)行編碼

下圖是對(duì)CodeFile.txt文件中Huffman碼進(jìn)行譯碼，所得到的效果圖（如圖6所示）：

圖6 對(duì)CodeFile.txt文件中Huffman碼進(jìn)行譯碼

第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告(HuffMan編碼器)

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告

題目：HuffMan編碼器

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

目 錄

一．問(wèn)題描述

二．基本要求(需求分析)

三．?概要設(shè)計(jì)(設(shè)計(jì)思想、實(shí)現(xiàn)方法、模塊設(shè)計(jì))

四．?詳細(xì)設(shè)計(jì)(數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、算法分析)

五．測(cè)試數(shù)據(jù)及測(cè)試結(jié)果

六．課程設(shè)計(jì)小結(jié)(心得體會(huì)、存在問(wèn)題、改進(jìn)措施)

一． 問(wèn)題描述

利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。

第 1 頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。二． 基本要求(需求分析)

一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：

（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmTree中。

（2）E：編碼（Encoding）。利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。

（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。

（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件CodePrin中。

（5）T：印哈夫曼樹(shù)（Tree printing）。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中。[測(cè)試數(shù)據(jù)] 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。

字符 空格 A

B

C

D

E

F

G

H

I

J

K

L

M 頻度 186

13 22 32 103 21 15 47 57 1

20 字符 N

O

P

Q

R

S

T

U

V

W

X

Y

Z 頻度 57

15 1

51 80 23 8 1 1[實(shí)現(xiàn)提示]

（1）編碼結(jié)果以文本方式存儲(chǔ)在文件CodeFile中。

（2）用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。

（3）在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行I，D或C命令之后，哈夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。

三． 概要設(shè)計(jì)(設(shè)計(jì)思想、實(shí)現(xiàn)方法、模塊設(shè)計(jì))哈夫曼編碼是一種效率比較高的變長(zhǎng)無(wú)失真信源編碼方法，它的平均碼長(zhǎng)

第 2 頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

最短，因此是最佳編碼。我采用二進(jìn)制哈夫曼編碼。

1． 設(shè)計(jì)思想

a、原理：構(gòu)造一個(gè)碼樹(shù)。

b、編碼步驟：

(1)將信源符號(hào)按概率從大到小的順序排列，為方便起見(jiàn)，令p(x1)≥p(x2)≥?≥p(xn)。

(2)對(duì)概率最小的兩個(gè)信源符號(hào)求其概率之和，同時(shí)給兩個(gè)符號(hào)分別賦予碼元“0 ”和“1”。將“概率之和”當(dāng)作一個(gè)新符號(hào)的概率，與剩下符號(hào)的概率一起，形成一個(gè)縮減信源，結(jié)果得到一個(gè)只包含（n－1）個(gè)信源符號(hào)的新信源，稱為信源的第一次縮減信源,用S1表示。

(3)將縮減信源S1的符號(hào)仍按概率從大到小的順序排列，重復(fù)步驟2，得到只含（n－2）個(gè)符號(hào)的縮減信源S2。

(4)重復(fù)上述步驟，直至縮減信源只剩下兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1。

(5)按上述步驟實(shí)際上構(gòu)造了一個(gè)碼樹(shù)，從樹(shù)根到端點(diǎn)經(jīng)過(guò)的樹(shù)枝即為碼字。

2． 實(shí)現(xiàn)方法

第一，哈夫曼編碼實(shí)際上構(gòu)造了一個(gè)碼樹(shù)，碼樹(shù)從最上層的端點(diǎn)開(kāi)始構(gòu)造，直到樹(shù)根束，最后得到一個(gè)橫放的碼樹(shù)，因此，編出的碼是即時(shí)碼。

第二，哈夫曼編碼采用概率匹配方法來(lái)決定各碼字的碼長(zhǎng)，概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，從而使平均碼長(zhǎng)最小。

第三，每次對(duì)概率最小的兩個(gè)符號(hào)求概率之和形成縮減信源時(shí)，就構(gòu)造出兩個(gè)樹(shù)枝，由于給兩個(gè)樹(shù)枝賦碼元時(shí)是任意的，因此編出的碼字并不惟一。

3． 模塊設(shè)計(jì)

第 3 頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

1．進(jìn)入的操作界面：

（圖一）

2．輸入字符串，及編碼結(jié)果

（圖二）

3．統(tǒng)計(jì)不同字符數(shù)及帶權(quán)路徑長(zhǎng)度

（圖三）

4．各字符編碼明細(xì)

第 4 頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

（圖四）

四．詳細(xì)設(shè)計(jì)(數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、算法分析)

（一）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

1)結(jié)點(diǎn)類型：

//huffcode.cpp

typedef struct HaffmanTreeNode {

char ch, code[15];

int weight;

int parent, lchild, rchild;} HTNode, *HaTree;

typedef struct { HTNode arr[MAX_NODE];

int total;} HTree;

2)基本操作：

第 5 頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

int statistic_char(char *text, HTree *t);int create_htree(HTree *t);void coding(HTree *t, int head_i, char *code);void print_htree_ldr(HTree *t, int head_i, int deep, int* path);void code_string(char *text, HTree *t,char *codes);

（二）算法設(shè)計(jì)

在哈夫曼編碼過(guò)程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。

（三）算法分析

(1)有效的信源編碼可取得較好的冗余壓縮效果。(2)有效的信源編碼可使輸出碼元概率均勻化。

4． 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果

1．輸入簡(jiǎn)短英文字符串：

（圖五）

2．輸入數(shù)字英文混合串：

第 6 頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

（圖六）

3．混合串：

（圖七）

4．輸入復(fù)雜無(wú)規(guī)則長(zhǎng)串：

（圖八）

第 7 頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

六．課程設(shè)計(jì)小結(jié)(心得體會(huì)、存在問(wèn)題、改進(jìn)措施)

本次程序設(shè)計(jì)使我不僅深化理解了教學(xué)內(nèi)容，進(jìn)一步提高靈活運(yùn)用數(shù)據(jù)結(jié)構(gòu)、算法和程序設(shè)計(jì)技術(shù)的能力，而且在總體分析、總體結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、程序設(shè)計(jì)、上機(jī)操作及程序調(diào)試等基本技能方面受到了綜合訓(xùn)練。

本次實(shí)驗(yàn)我選擇Huffman編譯碼器的課題。幫助我深入研究樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特性及其應(yīng)用。由于課程設(shè)計(jì)著眼于原理與應(yīng)用的結(jié)合，使我學(xué)會(huì)把書(shū)本上和課堂上學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題，從而培養(yǎng)了一部分計(jì)算機(jī)軟件工作所需要的動(dòng)手能力。

我通過(guò)對(duì)Huffman編譯碼原理的學(xué)習(xí)，再通過(guò)分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)，實(shí)現(xiàn)了Huffman編譯碼器的數(shù)據(jù)實(shí)現(xiàn)和界面實(shí)現(xiàn)。在Huffman編譯碼器數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計(jì)中我同時(shí)用到了多種技術(shù)和方法，如算法設(shè)計(jì)的構(gòu)思方法，算法的編碼，遞歸技術(shù)，與二叉樹(shù)和樹(shù)相關(guān)的技術(shù)等。從而幫助我深入學(xué)習(xí)研究了樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特性及其應(yīng)用。

為了實(shí)現(xiàn)界面友好的要求，我決定采用MFC的界面操作，所以必須以C++為基本語(yǔ)言，但是由于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程是基于PASCAL，實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)部分設(shè)計(jì)遇到一些語(yǔ)法沖突。但是通過(guò)課程實(shí)踐學(xué)習(xí)，我又開(kāi)始熟悉C++的編程環(huán)境，從而實(shí)現(xiàn)了在不同語(yǔ)言上數(shù)據(jù)結(jié)構(gòu)思想的統(tǒng)一。

此次課程設(shè)計(jì)并沒(méi)有劃定具體題目，包括算法需求都由我們度量，思路開(kāi)闊。我始終和同學(xué)探討并獨(dú)立研究新的功能的實(shí)現(xiàn)。通過(guò)嘗試來(lái)學(xué)習(xí)，通過(guò)實(shí)踐去理解。

當(dāng)然，通過(guò)多天來(lái)的上機(jī)實(shí)踐，我獲取了一些心得：

一．充分準(zhǔn)備。由于課題寬泛，很多同學(xué)去網(wǎng)上下了界面優(yōu)良的源程序。相對(duì)而言在DOS下編程的我開(kāi)始時(shí)很焦急，不知如何實(shí)現(xiàn)界面友好。準(zhǔn)備充分是很重要的，為了實(shí)現(xiàn)MFC，我重新學(xué)習(xí)了C++語(yǔ)言。

二．冷靜，耐心投入。集中精力地編程，不被外界影響，使自己的思路始終連貫不被打斷。對(duì)待每一個(gè)錯(cuò)誤，都要仔細(xì)分析，太過(guò)焦急，不僅不能及時(shí)的改正錯(cuò)誤，還對(duì)后面的編程造成影響。

三．要有一種堅(jiān)持不懈的毅力，不管自己的程序多么復(fù)雜，多么冗長(zhǎng)，要堅(jiān)持不懈的去完成。冷靜思考。

四．要對(duì)自己有信心，出錯(cuò)是必然的?！皩覒?zhàn)屢敗，屢敗屢戰(zhàn)”，不怕受挫的心理承受能力和從零開(kāi)始的決心是走向成功的必要條件。

五．學(xué)會(huì)與別人學(xué)習(xí)討論，但不依賴別人，可以通過(guò)借鑒思路從而創(chuàng)新，但決不照搬別人的東西。

第 8 頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

通過(guò)查找資料，我發(fā)現(xiàn)我們做Huffman編碼和解碼時(shí)，一般都要在內(nèi)存通過(guò)指針生成Huffman樹(shù)，這是一個(gè)比較費(fèi)時(shí)間、費(fèi)空間的過(guò)程。實(shí)際上，真正的Huffman編碼程序經(jīng)常使用其他更快的數(shù)據(jù)結(jié)構(gòu)來(lái)完成樹(shù)的生成，如散列等。所以我的課題有待繼續(xù)學(xué)習(xí)研究。

?用戶手冊(cè)/使用說(shuō)明

（圖九）

1．在此處輸入要編碼的字符串，點(diǎn)擊進(jìn)行編碼。

2．再次輸入時(shí)再點(diǎn)擊可成功使用，不會(huì)受之前結(jié)果影響。

?附錄(源程序清單)//huffcode.cpp //C編寫(xiě)的源代碼，原來(lái)含有writef()以及printf(),但由于最終用MFC界面實(shí)現(xiàn)，故刪去，只作為一 //些功能子函數(shù)被MFC的對(duì)話框類調(diào)用。//另外，對(duì)于類型申明等已包含于頭文件。#include “stdafx.h” #include “huffcode.h”

/*

統(tǒng)計(jì)字符出現(xiàn)的頻率

*/ int statistic_char(char *text, HTree *t){

int i, j;

int text_len = strlen(text);

t->total = 0;

for(i=0;i

for(j=0;jtotal;j++)

if(t->arr[j].ch == text[i])

{

第 9 頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

t->arr[j].weight ++;

break;

}

if(j==t->total){

t->arr[t->total].ch = text[i];

t->arr[t->total].weight = 1;

t->total ++;

}

}

return t->total;}

int create_htree(HTree *t){

int i;

int total_node = t->total * 2-1;int min1, min2;/* 權(quán)最小的兩個(gè)結(jié)點(diǎn) */

int min1_i, min2_i;/*

權(quán)最小結(jié)點(diǎn)對(duì)應(yīng)的編號(hào)

*/

int leaves = t->total;

for(i=0;i

t->arr[i].parent =-1;

t->arr[i].rchild =-1;

t->arr[i].lchild =-1;

}

while(t->total < total_node){

min1 = min2 = MAX_WEIGHT;

for(i=0;itotal;i++){ /*

對(duì)每一個(gè)結(jié)點(diǎn)

*/

if(t->arr[i].parent ==-1 /*

結(jié)點(diǎn)沒(méi)有被合并

*/

&& t->arr[i].weight < min2){ /*

結(jié)點(diǎn)的權(quán)比最小權(quán)小

*/

if(t->arr[i].weight < min1){ /*

如果它比最小的結(jié)點(diǎn)還小

*/

min2_i = min1_i;min2 = min1;

min1_i = i;

min1 = t->arr[i].weight;

}

else

{

min2_i = i;

min2 = t->arr[i].weight;

}

}

}

t->arr[t->total].weight = min1 + min2;

t->arr[t->total].parent =-1;

t->arr[min1_i].parent = t->total;

t->arr[min2_i].parent = t->total;

t->arr[t->total].ch = ' ';

第10

頁(yè)

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

計(jì)科0403

041106308

雷娜

t->total ++;

}

return 0;} /*

對(duì)哈夫曼樹(shù)進(jìn)行編碼

*/ void coding(HTree *t, int head_i, char *code){

if(head_i ==-1)return;

if(t->arr[head_i].lchild ==-1 && t->arr[head_i].rchild ==-1){

strcpy(t->arr[head_i].code, code);/

}

else {

int len = strlen(code);

strcat(code, “0”);

coding(t, t->arr[head_i].lchild, code);

code[len] = '1';

coding(t, t->arr[head_i].rchild, code);

code[len] = '