哈夫曼編譯碼器課程設(shè)計(jì)報(bào)告(完整版)

1、XXX學(xué)院 本科數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)報(bào)告設(shè)計(jì)題目 ： 實(shí)驗(yàn)一、哈夫曼編 / 譯碼器學(xué)生姓名 ： XXX系別： XXX專業(yè)： XXX班級(jí)： XXX學(xué)號(hào)： XXX指導(dǎo)教師 ： XXXXXX2012年 6 月 21日xxx 學(xué)院課 程設(shè)計(jì)任務(wù)書(shū)題目一、赫夫曼編譯碼器專業(yè)、班級(jí)xxx學(xué)號(hào)xxx姓名xxx主要內(nèi)容、基本要求、主要參考資料等：1. 主要內(nèi)容利用哈夫曼編碼進(jìn)行信息通信可大大提高信道利用率， 縮短信息傳輸時(shí)間， 降低傳輸成本。要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼； 在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原） 。對(duì)于雙工信道（既可以雙向傳輸信息的信道） ，每端都需要一個(gè)完整的編 / 譯碼系統(tǒng)

2、。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編 / 譯碼系統(tǒng)。2. 基本要求系統(tǒng)應(yīng)具有以下功能：（ 1） C：編碼（ Coding）。對(duì)文件 tobetrans中的正文進(jìn)行編碼，然后將結(jié)果存入文件 codefile中，將以此建好的哈夫曼樹(shù)存入文件HuffmanTree 中（ 2）D：解碼（Decoding ）。利用已建好的哈夫曼樹(shù)將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入textfile中。（ 3） P：打印代碼文件（ Print ）。將文件 codefile以緊湊格式顯示在終端上，每行 50 個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件codeprint中。（ 4） T：打印哈夫曼樹(shù)（ Tree

3、 Printing ）。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫入文件treeprint中。3. 參考資料：數(shù)據(jù)結(jié)構(gòu)（ C 語(yǔ)言版） 嚴(yán)蔚敏、吳偉民編著；數(shù)據(jù)結(jié)構(gòu)標(biāo)準(zhǔn)教程胡超、閆寶玉編著完成期限：2012年6月21日指導(dǎo)教師簽名：課程負(fù)責(zé)人簽名：2012年6月21日2一、設(shè)計(jì)題目（任選其一）實(shí)驗(yàn)一、哈夫曼編 / 譯碼器二、實(shí)驗(yàn)?zāi)康? 鞏固和加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識(shí)的能力；2 深化對(duì)算法課程中基本概念、理論和方法的理解；3 鞏固構(gòu)造赫夫曼樹(shù)的算法；4 設(shè)計(jì)試驗(yàn)用程序?qū)嶒?yàn)赫夫曼樹(shù)的構(gòu)造。三、運(yùn)行環(huán)境（軟、硬件環(huán)境）Win

4、dows xp sp3 ，Visual C+ 6.0英文版四、算法設(shè)計(jì)的思想（ 1）初始化赫夫曼樹(shù)，輸入文件tobetrans.txt 中各字符及其權(quán)值，并保存于hfmtree.txt 文件中（ 2）編碼（ Coding）。對(duì)文件 tobetrans中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile 中（ 3） D：解碼（ Decoding）。利用已建好的哈夫曼樹(shù)將文件codefile 中的代碼進(jìn)行譯碼，結(jié)果存入textfile 中。（ 4） P：打印代碼文件（ Print）。將文件codefile 以緊湊格式顯示在終端上，每行 50 個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件codepri

5、nt 中。（ 5）T：打印哈夫曼樹(shù)（ Tree Printing）。將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫入文件treeprint 中。五、 流程圖3六、 算法設(shè)計(jì)分析1. 赫夫曼樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類型定義為：typedef struct/赫夫曼樹(shù)的結(jié)構(gòu)體char ch;int weight;/權(quán)值int parent,lchild,rchild;HTNode,*HuffmanTree;2.void HuffmanCoding(HuffmanTree &,char *,int *,int);建立赫夫曼樹(shù)的算法，此函數(shù)塊調(diào)用了 Select （）函數(shù)。void s

6、elect(HuffmanTree HT,int j,int *x,int *y); 從已建好的赫夫曼樹(shù)中選擇 parent 為 0，weight 最小的兩個(gè)結(jié)點(diǎn)。3利用已建好的哈夫曼樹(shù)從文件 hfmtree.txt 中讀入，對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件 codefile.txt 中。4. coding編碼功能：對(duì)輸入字符進(jìn)行編碼5. Decoding譯碼功能： 利用已建好的哈夫曼樹(shù)將文件codefile.txt中的代碼進(jìn)行譯碼， 結(jié)果存入文件 textfile.txt中。6. Print()打印功能函數(shù)：輸出哈夫曼樹(shù)以及對(duì)應(yīng)的編碼。4七、源代碼/#include #includ

7、e #include / 定義赫夫曼樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)體typedef structchar ch;/增加一個(gè)域，存放該節(jié)點(diǎn)的字符int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;/指向赫夫曼編碼的指針void tips(); /打印操作選擇界面void HuffmanCoding(HuffmanTree &,char *,int *,int); /建立赫夫曼樹(shù)的算法void select(HuffmanTree HT,int j,int *x,int *y); /從已建好的赫夫曼樹(shù)中選

8、擇 parent 為 0，weight 最小的兩個(gè)結(jié)點(diǎn)void Init();void Coding(); /編碼void Decoding();/譯碼void Print_code();/打印譯碼好的代碼void Print_tree();/打印哈夫曼樹(shù)int Read_tree(HuffmanTree &); /從文件中讀入赫夫曼樹(shù)void find(HuffmanTree &HT,char *code,char *text,int i,int m);/譯碼時(shí)根據(jù) 01 字符串尋找相應(yīng)葉子節(jié)點(diǎn)的遞歸算法5void Convert_tree(unsignedchar T100100,ints

9、,int*i,intj);/將內(nèi)存中的赫夫曼樹(shù)轉(zhuǎn)換成凹凸表形式的赫夫曼樹(shù)HuffmanTree HT;/全局變量int n=0;/全局變量，存放赫夫曼樹(shù)葉子結(jié)點(diǎn)的數(shù)目int main()char select;while(1)tips();scanf(%c,&select);switch(select)/選擇操作，根據(jù)不同的序號(hào)選擇不同的操作case 1:Init();break;case 2:Coding();break;case 3:Decoding();break;case 4:Print_code();break;6case 5:Print_tree();break;case 0:ex

10、it(1);default :printf(Input error!n);getchar();return 0;void tips() /操作選擇界面printf( -n);printf( -請(qǐng)選擇操作-n);printf( -n);printf(n);printf( -1初始化赫夫曼樹(shù)-n);printf( -2編碼-n);printf( -3譯碼-n);printf( -4打印代碼文件 -n);printf( -5打印赫夫曼樹(shù) -n);printf( -0退出-n);printf( -n);7/ 初始化函數(shù)，輸入 n 個(gè)字符及其對(duì)應(yīng)的權(quán)值，根據(jù)權(quán)值建立哈夫曼樹(shù)，并將其存于文件 hfmtre

11、e 中void Init()FILE *fp;int i,n,w52; /數(shù)組存放字符的權(quán)值char character52; /存放 n 個(gè)字符printf(n輸入字符個(gè)數(shù) n:);scanf(%d,&n);/輸入字符集大小printf(輸入 %d個(gè)字符及其對(duì)應(yīng)的權(quán)值 :n,n);for (i=0;in;i+)char b=getchar();scanf(%c,&characteri);scanf(%d,&wi);/輸入 n 個(gè)字符和對(duì)應(yīng)的權(quán)值HuffmanCoding(HT,character,w,n);/建立赫夫曼樹(shù)if(fp=fopen(hfmtree.txt,w)=NULL)prin

12、tf(Open file hfmtree.txt error!n);for (i=1;i=2*n-1;i+)if(fwrite(&HTi,sizeof(HTNode),1,fp)!=1)/將建立的赫夫曼樹(shù)存入文件 hfmtree.txt中printf(File write error!n);printf(n赫夫曼樹(shù)建立成功，并已存于文件hfmtree.txt中 n);fclose(fp);8/ 建立赫夫曼樹(shù)的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,x,y;HuffmanTree p;if

13、(n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;ich=*character;p-weight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;ich=0;p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;+i)select(HT,i-1,&x,&y);HTx.parent=i;HTy.parent=i;HTi.lchild=x;HTi.rchild=y;HTi.weight=HTx.w

14、eight+HTy.weight;/ 從 HT1 到 HTj 中選擇 parent 為 0， weight 最小的兩個(gè)結(jié)點(diǎn)，用x 和 y返回其序號(hào)void select(HuffmanTree HT,int j,int *x,int *y)9int i;/ 查找 weight 最小的結(jié)點(diǎn)for (i=1;i=j;i+)if (HTi.parent=0)*x=i;break;for (;i=j;i+)if (HTi.parent=0)&(HTi.weightHT*x.weight)*x=i;HT*x.parent=1;/ 查找 weight 次小的結(jié)點(diǎn)for (i=1;i=j;i+)if (HT

15、i.parent=0)*y=i;break;for (;i=j;i+)if (HTi.parent=0)&(i!=*x)&(HTi.weightHT*y.weight)*y=i;/ 對(duì)文件 tobetrans 中的正文進(jìn)行編碼，然后將結(jié)果存入文件 codefile 中void Coding()FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;if(n=0)10n=Read_tree(HT);/從文件 hfmtree.txt中讀入赫夫曼樹(shù) , 返回葉子結(jié)點(diǎn)數(shù)/ 求赫夫曼樹(shù)中各葉子節(jié)點(diǎn)的字符對(duì)應(yīng)的的編碼，并存于HC指向的空間中HC=(Huff

16、manCode)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 *)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);if(fp=fopen(tobetrans.txt,rb)=NULL)printf(O

17、pen file tobetrans.txt error!n);if(fw=fopen(codefile.txt,wb+)=NULL)printf(Open file codefile.txt error!n);char temp;fscanf(fp,%c,&temp); / 從文件讀入第一個(gè)字符 while(!feof(fp)11for(i=1;i=n;i+)if(HTi.ch=temp) break;/在赫夫曼樹(shù)中查找字符所在的位置for(int r=0;HCir!=0;r+) /將字符對(duì)應(yīng)的編碼存入文件fputc(HCir,fw);fscanf(fp,%c,&temp);/從文件讀入下一

18、個(gè)字符fclose(fw);fclose(fp);printf(n已將文件hfmtree.txt成功編碼 , 并已存入codefile.txt中！nn);/ 將文件 codefile 中的代碼進(jìn)行譯碼，結(jié)果存入文件 textfile 中void Decoding()FILE *fp,*fw;int m,i;char *code,*text,*p;if(n=0)n=Read_tree(HT);/從文件 hfmtree.txt中讀入赫夫曼樹(shù) , 返回葉子結(jié)點(diǎn)數(shù)if(fp=fopen(codefile.txt,rb)=NULL)printf(Open file codefile.txt error!

19、n);if(fw=fopen(textfile.txt,wb+)=NULL)12printf(Open file textfile.txt error!n);code=(char *)malloc(sizeof(char);fscanf(fp,%c,code);/從文件讀入一個(gè)字符for(i=1;!feof(fp);i+)code=(char *)realloc(code,(i+1)*sizeof(char);/增加空間fscanf(fp,%c,&codei);/從文件讀入下一個(gè)字符codei-1=0;/ codefile.txt文件中的字符已全部讀入，存放在code 數(shù)組中text=(cha

20、r *)malloc(100*sizeof(char);p=text;m=2*n-1;if(*code=0)find(HT,code,text,HTm.lchild,m);/從根節(jié)點(diǎn)的左子樹(shù)去找elsefind(HT,code,text,HTm.rchild,m);/從根節(jié)點(diǎn)的右子樹(shù)去找for(i=0;pi!=0;i+)/把譯碼好的字符存入文件textfile.txt中fputc(pi,fw);fclose(fp);fclose(fw);printf(n已將 codefile.txt文件成功譯碼，兵已存入 textfile.txt文件！nn);13/ 將文件 codefi1e 以緊湊格式顯示在

21、終端上 , 每行 50 個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件 codeprint 中。void Print_code()FILE *fp,*fw;char temp;int i;if(fp=fopen(codefile.txt,rb)=NULL)printf(Open file codefile.txt error!n);if(fw=fopen(codeprint.txt,wb+)=NULL)printf(Open file codeprint.txt error!n);printf(n文件 codefi1e 顯示如下 :n);fscanf(fp,%c,&temp);/從文件讀入一個(gè)字符

22、for (i=1;!feof(fp);i+)printf(%c,temp);if(i%50=0) printf(n);fputc(temp,fw);/將該字符存入文件codeprint.txt中fscanf(fp,%c,&temp);/從文件讀入一個(gè)字符printf(nn已將此字符形式的編碼寫入文件codeprint.txt中！ nn);fclose(fp);fclose(fw);14/ 將已在內(nèi)存中的哈夫曼樹(shù)顯示在屏幕上，并將此字符形式的哈夫曼樹(shù)寫入文件 treeprint 中。void Print_tree()unsigned char T100100;int i,j,m=0;FILE *

23、fp;if(n=0)n=Read_tree(HT); / 從文件 hfmtree.txt 中讀入赫夫曼樹(shù) , 返回葉子結(jié)點(diǎn)數(shù)Convert_tree(T,0,&m,2*n-1);/將內(nèi)存中的赫夫曼樹(shù)轉(zhuǎn)換成凹凸表形式的樹(shù)，存于數(shù)組 T 中if(fp=fopen(treeprint.txt,wb+)=NULL)printf(Open file treeprint.txt error!n);printf(n打印已建好的赫夫曼樹(shù)：n);for(i=1;i=2*n-1;i+)for (j=0;Tij!=0;j+)if(Tij= ) printf( );fputc(Tij,fp);elseprintf(%

24、d,Tij);fprintf(fp,%dn,Tij);printf(n);fclose(fp);15printf(n已將該字符形式的哈夫曼樹(shù)寫入文件treeprint.txt中！nn);/ 從文件 hfmtree.txt 中讀入赫夫曼樹(shù)，返回葉子節(jié)點(diǎn)數(shù)int Read_tree(HuffmanTree &HT)FILE *fp;int i,n;HT=(HuffmanTree)malloc(sizeof(HTNode);if(fp=fopen(hfmtree.txt,r)=NULL)printf(Open file hfmtree.txt error!n);for (i=1;!feof(fp);

25、i+)HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode);/增加空間fread(&HTi,sizeof(HTNode),1,fp);/讀入一個(gè)節(jié)點(diǎn)信息fclose(fp);n=(i-1)/2;return n;/ 譯碼時(shí)根據(jù) 01 字符串尋找相應(yīng)葉子節(jié)點(diǎn)的遞歸算法void find(HuffmanTree &HT,char *code,char *text,int i,int m)if(*code!=0)/若譯碼未結(jié)束16code+;if(HTi.lchild=0&HTi.rchild=0)/若找到葉子節(jié)點(diǎn)*text=HTi.ch;/將葉子節(jié)點(diǎn)的字符

26、存入text中text+;if(*code=0)find(HT,code,text,HTm.lchild,m);/從根節(jié)點(diǎn)的左子樹(shù)找elsefind(HT,code,text,HTm.rchild,m);/從根節(jié)點(diǎn)的右子樹(shù)找else/如果不是葉子節(jié)點(diǎn)if(*code=0)find(HT,code,text,HTi.lchild,m);/從該節(jié)點(diǎn)的左子樹(shù)去找elsefind(HT,code,text,HTi.rchild,m);/從該節(jié)點(diǎn)的右子樹(shù)去找else*text=0; /譯碼結(jié)束/ 將文件中的赫夫曼樹(shù)轉(zhuǎn)換成凹凸表形式的赫夫曼樹(shù)打印出來(lái)void Convert_tree(unsigned c

27、har T100100,int s,int *i,int j)int k,l;17l=+(*i);for(k=0;ks;k+)Tlk= ;Tlk=HTj.weight;if(HTj.lchild)Convert_tree(T,s+1,i,HTj.lchild);if(HTj.rchild)Convert_tree(T,s+1,i,HTj.rchild);Tl+k=0;/八、運(yùn)行結(jié)果分析截圖說(shuō)明：1、運(yùn)行后界面如圖（ 1）：圖（ 1）選擇要選擇的操作序號(hào)可以運(yùn)行各個(gè)步驟；2、初始化赫夫曼樹(shù)：18輸入 tobetrans.txt中各元素及其出現(xiàn)頻率，如圖（2）圖（ 2）3、編碼及譯碼，如圖（ 3）

28、圖（ 3）4、打印編碼文件，如圖（4）19圖（ 4）5、打印赫夫曼樹(shù)，如圖（5）圖（ 5）6、各步驟所存的文件內(nèi)容如圖（6）20圖（ 6）九、收獲及體會(huì)課程設(shè)計(jì)是讓我們充分利用我們專業(yè)課程所學(xué)知識(shí)的機(jī)會(huì)， 也是我們邁向社會(huì)，從事工作前一個(gè)必不少的過(guò)程。通過(guò)這次課程設(shè)計(jì)， 我深深體會(huì)到將知識(shí)運(yùn)用到實(shí)踐中的重要作用。 我這兩天的課程設(shè)計(jì)， 是讓我學(xué)會(huì)腳踏實(shí)地邁開(kāi)這一步，也是為明天能穩(wěn)健地在社會(huì)大潮中奔跑打下堅(jiān)實(shí)的基礎(chǔ)。我的課程設(shè)計(jì)題目是赫夫曼編譯碼器。最初做這個(gè)程序的時(shí)候， 讓我覺(jué)得完成這次程序設(shè)計(jì)真的是太難了，然后我查閱了課本，并去圖書(shū)館借了資料， 在寫這個(gè)程序的時(shí)候也參考了網(wǎng)上的設(shè)計(jì)流程， 寫

29、完剛運(yùn)行時(shí)出現(xiàn)了很多問(wèn)題。 尤其是編碼錯(cuò)誤，導(dǎo)致內(nèi)存無(wú)法 read ，通過(guò)同組人員的交流請(qǐng)教，逐漸明白過(guò)來(lái)，然后經(jīng)過(guò)不知道多少次修改才順利運(yùn)行。 本次試驗(yàn)也讓我明白了理論與實(shí)際相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力，培養(yǎng)了基本的、 良好的程序設(shè)計(jì)技能以及合作能力。 通過(guò)對(duì)各個(gè)步驟各個(gè)流程的控制，逐漸讓我產(chǎn)生了興趣， 在實(shí)際編寫過(guò)程中， 和同學(xué)們相互討論讓我學(xué)到的不僅僅是一些解決問(wèn)題的方法，更是解決問(wèn)題的思想。課程設(shè)計(jì)本身也是一種相互學(xué)習(xí)的過(guò)程 ,/21/#include#include/ 為 exit()提供原型#include/ 哈夫曼樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)typedefstruct

30、char ch;/ 該字符域用于存放節(jié)點(diǎn)的關(guān)鍵字intweight;intparent, lchild, rchild; HTNode, *HuffmanTree ;/ 動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)typedefchar * HuffmanCode;/ 動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表voidMenu();/ 顯示菜單voidHuffmanCoding( HuffmanTree &HT, char *character,int * w,int n);/ 建立哈夫曼樹(shù)voidselect( HuffmanTree HT, int j, int *x, int*y);/從已建好的赫夫曼樹(shù)中選擇 paren

31、t為 0， weight 最小的兩個(gè)結(jié)點(diǎn)voidInit();voidCoding();/ 編碼voidDecoding();/ 譯碼voidPrint_code();/ 打印譯碼好的代碼voidPrint_tree();/ 打印哈夫曼樹(shù)intRead_tree(HuffmanTree &); / 從文件中讀入赫夫曼樹(shù)voidfind( HuffmanTree &HT,char *code, char*text,inti,intm);/ 譯碼時(shí)根據(jù) 01 字符串尋找相應(yīng)葉子節(jié)點(diǎn)的遞歸算法voidConvert_tree(unsignedchar T100100,int s,int*i,intj

32、);/ 將內(nèi)存中的赫夫曼樹(shù)轉(zhuǎn)換成凹凸表形式的赫夫曼樹(shù)HuffmanTree HT;/ 全局變量intn = 0;/全局變量，存放赫夫曼樹(shù)葉子結(jié)點(diǎn)的數(shù)目intmain()char select;while (1)Menu();scanf(%c, &select);switch(select)/ 選擇操作，根據(jù)不同的序號(hào)選擇不同的操作case 1 :Init();break ;22case 2 :Coding();break ;case 3 :Decoding();break ;case 4 :Print_code();break ;case 5 :Print_tree();break ;case

33、 0 :exit(1);default:printf(Input error!n);getchar();return0;void Menu()/ 操作選擇界面printf(-n);printf(-請(qǐng)選擇操作-n);printf(-n);printf(n);printf(-1初始化赫夫曼樹(shù)-n);printf(-2編碼-n);printf(-3譯碼-n);printf(-4打印代碼文件 -n);printf(-5打印赫夫曼樹(shù) -n);printf(-0退出-n);printf(-n);/ 初始化函數(shù)，輸入n 個(gè)字符及其對(duì)應(yīng)的權(quán)值，根據(jù)權(quán)值建立哈夫曼樹(shù)，并將其存于文件hfmtree 中void I

34、nit()FILE *fp;inti, n, w52;/ 數(shù)組存放字符的權(quán)值char character52;/ 存放 n 個(gè)字符23printf(n 輸入字符個(gè)數(shù)n: );scanf( %d, &n);/ 輸入字符集大小printf( 輸入 %d個(gè)字符及其對(duì)應(yīng)的權(quán)值:n , n);for (i = 0; in; i+)char b = getchar();scanf( %c, &characteri);scanf( %d, &wi);/ 輸入 n 個(gè)字符和對(duì)應(yīng)的權(quán)值HuffmanCoding(HT, character, w, n);/ 建立赫夫曼樹(shù)if(fp = fopen(hfmtree

35、.txt,w ) =NULL)printf(Open file hfmtree.txt error!n);for (i = 1; i 0），構(gòu)造哈夫曼樹(shù) HT int m, i, x, y;HuffmanTree p;if(n = 1)return ;m = 2 * n - 1;HT = ( HuffmanTree)malloc(m + 1) *sizeof ( HTNode);for (p = HT + 1, i = 1; i ch = *character; p-weight = *w; p-parent = 0; p-lchild = 0; p-rchild = 0;for (;i ch

36、 = 0; p-weight= 0; p-parent= 0; p-lchild= 0; p-rchild=0;for (i = n + 1; i = m; +i)select(HT, i - 1, &x, &y);HTx.parent = i; HTy.parent = i;HTi.lchild = x; HTi.rchild = y;HTi.weight = HTx.weight + HTy.weight;24/ 從 HT1 到 HTj 中選擇 parent 為 0，weight 最小的兩個(gè)結(jié)點(diǎn)，用 x 和 y 返回其序號(hào) void select( HuffmanTree HT, int j , int * x, int * y)inti;/ 查找 weight 最小的結(jié)點(diǎn)for (i = 1; i =j ; i+)if( HTi.parent = 0)* x = i;break ;for (; i =j ; i+)if( HTi.parent = 0) & (HTi.weightHT* x.weight)* x = i;