4+四+貪心算法+習(xí)題參考答案

1、第四章作業(yè) 部分參考答案1. 設(shè)有n個顧客同時等待一項服務(wù)。顧客i需要的服務(wù)時間為ti,1 Gn。 應(yīng)該如何安排n個顧客的服務(wù)次序才能使總的等待時間達(dá)到最小？總的等待時 間是各顧客等待服務(wù)的時間的總和。試給出你的做法的理由(證明) 。策略：對ti 1 <H<n進行排序，ti1壬<tin，然后按照遞增順序依次服務(wù)ii,i2,.,in即可。解析：設(shè)得到服務(wù)的顧客的順序為j1, j2,., jn ,則總等待時間為 T =(n -1)tji +(n -2)上+2ty +上工,則在總等待時間T中上的權(quán)重最大，堀 的權(quán)重最小。故讓所需時間少的顧客先得到服務(wù)可以減少總等待時間。證明：設(shè)h安

2、i2苴，下證明當(dāng)按照不減順序依次服務(wù)時，為最優(yōu)策略。記按照i1i2in次序服務(wù)時，等待時間為T ,下證明任意互換兩者的次序，T 都不減。即假設(shè)互換i,j (i<j)兩位顧客的次序，互換后等待總時間為 T ,則有 T -T.由丁T =(n -1)th (n -2)妃.2tg tT =(n-1)ti1(nF. (n-i)tii. (n-j)ti"2虻k,T =(n1)ti1( 2)也 (ni)tij (n j)ti"2"則有 T -T =(j -蝦-匕)一0.同理可證其它次序，都可以由i1i2in經(jīng)過有限次兩兩調(diào)換順序后得到，而 每次交換，總時間不減，從而i2i

3、n為最優(yōu)策略。2. 字符a h出現(xiàn)的頻率分布恰好是前 8個Fibonacci數(shù)，它們的Huffman 編碼是什么？將結(jié)果推廣到n個字符的頻率分布恰好是前n個Fibonacci數(shù)的情 >0 Fibonacci數(shù)的定義為:F。=1，日=任=W + Fn頊n1解：前 8 個數(shù)為 a, b, c, d, e, f, g, h1,1,2,3,5,8, 13, 21Huffman哈夫曼編碼樹為：所以a的編碼為：1111111 b的編碼為：1111110 c的編碼為：111110 d的編碼為：11110 e的編碼為：1110 f的編碼為：110 g的編碼為：10 h的編碼為：0推廣到n個字符：第1個字

4、符：n-1個1,11- 1n第2個字符：n-2個1, 1個0,11,10n/第3個字符：n-3個1, 1個0, 1卜10 ¥ 'n第n-1個字符：1個1 , 1個0,10第n個字符：1個0,03. 設(shè)臼，P2,，Pn是準(zhǔn)備存放到長為L的磁帶上的n個程序，程序Pi需要的n帶長為ai。設(shè)£ aL ,要求選取一個能放在帶上的程序的最大子集合（即其中 i 4含有最多個數(shù)的程序）Q。構(gòu)造Q的一種貪心策略是按ai的非降次序?qū)⒊绦蛴嬋爰稀?）證明這一策略總能找到最大子集 Q ,使得Z a L 02）設(shè)Q是使用上述貪心算法得到的子集合，磁帶的利用率可以小到何種程度？3）試說明1）

5、中提到的設(shè)計策略不一定得到使 £ ai/L取最大值的子集合。Pi - Q1） 證明:不妨設(shè)a1a2.Wan，若該貪心策略構(gòu)造的子集合 Q為a，a?,，a,ss則 s滿足 Z aM L、£ as +as書 a L。 0i =1要證明能找到最大子集，只需說明 s為可包含的最多程序段數(shù)即可。即證不存在多丁 s個的程序集合Q =ai1,ai2,，aj, （ks），使得Z c < L 0Pi - Qk ,一、八一反證法，假設(shè)存在多于 s個的程序集Q =* ,ai2,，ak, （k a s）,滿足a.L。j="因為 a1 <a2 W. <an 非降序排列，貝

6、U a1 + a2 + as + +ak M % +ai2 + +aik M l。因為ks且為整數(shù)，貝U其前s+1項滿足a1 +a2 +as +as書苴L。這與貪心策略構(gòu)造的子集和 Q中s滿足的Z as +as土L矛盾。故假設(shè)不成立，得證。i曾2）磁帶的利用率為Z ai / L;（甚至最小可為0,此時任意aj a L或者£ a< L）3)按照1)的策略可以使磁帶上的程序數(shù)量最多，但程序的總長度不一定是最大的，假設(shè)ai，a2,，a)為Q的最大子集，但是若用a書代替ai ,仍滿足i£ ak +ai < L，貝U匡且,，a, ai書為總長度更優(yōu)子集。 k 44. 答案

7、見后面所附程序。5. 已知n種貨幣SC、，&和有關(guān)兌換率的nxn表R,其中Ri, j是一個單位的 貨幣Ci可以買到的貨幣Cj的單位數(shù)。1) 試設(shè)計一個算法，用以確定是否存在一貨幣序列C1,C2,，Ck使得：Rj,2R，kR i i, i 12) 設(shè)計一個算法打印出滿足1)中條件的所有序列，并分析算法的計算時間。解：基本解題思想： 通過FLO YD算法求出最大環(huán)。判斷最大環(huán)的權(quán)值之積是否大于1,如果大于1說明可以實現(xiàn)套匯，如果不大于1說明不能實現(xiàn)套匯。在求解最大環(huán)的同時記錄下兌換過程中的步驟。算法實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)：int PathMAX_VERTECX_NUMMAX_VERTECX_NUM

8、;/用來記錄套匯過程中要經(jīng)過的路徑float valueMAX_VERTECX_NUMMAX_VERTECX_NUM;/用來記錄經(jīng)過討回操作后得到的值借助圖來實現(xiàn)該算法 typedef structint vexsMAX_VERTECX_NUM; / 頂點向量 每種貨幣對應(yīng)一個頂點float arcMAX_VERTECX_NUMMAX_VERTECX_NUM;/鄰接矩陣存放兌換率信息int vexnum,arcnum;圖中當(dāng)前頂點數(shù)和弧數(shù)MGraph;算法中的關(guān)鍵步驟：for(k=1;k<=G->vexnum;k+)for(i=1;i<=G->vexnum;i+)for

9、(j=1;j<=G->vexnum;j+) if(valueik*valuekj>valueij)/這里判斷是否使兌換率增大，如果增大則記錄下來 valueij=valueik*valuekj; Pathij=Pathkj;)在輸出兌換序列時采用了遞歸算法：這個算法逆序輸出了兌換序列。void Procedure_print(int i,int j)(if(Pathij=i)(printf("%d",i);return;)else if(Pathij=0)/輸出結(jié)點i與結(jié)點j之間不存在通路printf("NO path");else(p

10、rintf("%d ",Pathij);Procedure_print(i,Pathij);/遞歸，貨幣 I 至 J 中間頂點 )此算法的時間復(fù)雜度是：。(畔3)算法實現(xiàn)代碼：#include<stdio.h>#define MAX_VERTECX_NUM 20#define INT_MIN 0 int n;int PathMAX_VERTECX_NUMMAX_VERTECX_NUM;float valueMAX_VERTECX_NUMMAX_VERTECX_NUM;typedef structint vexsMAX_VERTECX_NUM; / 頂點向量 可以

11、存儲每個頂點的信息float arcMAX_VERTECX_NUMMAX_VERTECX_NUM;/鄰接矩陣主要存放關(guān)于邊的信息int vexnum,arcnum;圖中當(dāng)前頂點數(shù)和弧數(shù)MGraph;void CreateDG(MGraph *G)int i,j,k;float w;scanf("%d%d",&(G->vexnum),&(G->arcnum);printf("G->vexnum=%d,G->arcnum=%dn",G->vexnum,G->arcnum);for(i=1;i<=G-&

12、gt;vexnum;i+)G->vexsi=i;for(i=1;i<=G->vexnum;i+)for(j=1;j<=G->vexnum;j+)G->arcij=INT_MIN;)for(k=1;k<=G->arcnum;k+)(scanf("%d%d%f”,&i,&j,&w);G->arcij=w;)void ShortestPath_FLOYD(MGraph *G)(int i,j,k;for(i=1;i<=G->vexnum;i+)(for(j=1;j<=G->vexnum;j

13、+)(if(i=j)valueij=1;elsevalueij=G->arcij;if(G->arcij>INT_MIN)Pathij=i;elsePathij=0;)for(k=1;k<=G->vexnum;k+)(for(i=1;i<=G->vexnum;i+)(for(j=1;j<=G->vexnum;j+)(if(valueik*valuekj>valueij)(valueij=valueik*valuekj;Pathij=Pathkj;)void Procedure_print(int i,int j)(if(Pathij=

14、i)(printf("%d",i);return;)else if(Pathij=0)/輸出結(jié)點i與結(jié)點j之間不存在通路printf("NO path");elseprintf("%d ",Pathij);Procedure_print(i,Pathij);)int main()int i,j;MGraph G;freopen("data.in","r",stdin);freopen("data.out","w",stdout);CreateDG(&

15、;G);ShortestPath_FLOYD(&G);i=1;if(valueii>1)printf("%f ”,valueii);if(Pathii!=0)printf("%d%d ",i,i);printf("兌換順序的逆序輸出： %d ",i);Procedure_print(i,i);printf("n");)4.同學(xué)們的幾種不同答案構(gòu)造哈夫曼樹思想，將所有的節(jié)點放到一個隊列中，用一個節(jié)點替換兩個頻率最低的節(jié) 點，新節(jié)點的頻率就是這兩個節(jié)點的頻率之和。這樣，新節(jié)點就是兩個被替換節(jié)點的父 節(jié)點了。如此循環(huán)

16、，直到隊列中只剩一個節(jié)點(樹根)。答案1)偽代碼：typedef structunsigned int weight;unsigned int parent, lchild, rchild;HTNode, * HuffmanTree;typedef char * HuffmanCode;proc HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) if n<=1 then returnHuffmanTree p;integer s1, s2, i, m, start, c, f;char *cd;m

17、 := 2 * n - 1;HT0.weight := 1000000;p := HT+1;for i to n do(*p).weight := *w;(*p).parent := (*p).lchild := (*p).rchild := 0;+p; +w;end(for)for i to m do(*p).weight = (*p).parent = (*p).lchild = (*p).rchild =0;+p;end(for)for i from n+1 to m doSelect(HT, i-1, s1, s2);HTs1.parent := i;HTs2.parent := i;

18、HTi.lchild := s1;HTi.rchild := s2;HTi.weight := HTs1.weight + HTs2.weight;end(for)cdn-1 = '0'/編碼結(jié)束符for i to n dostart := n - 1;編碼結(jié)束符位置f := i;c := i;for f from HTf.parent to f=0 doif HTf.lchild = ccd-start := '0'elsecd-start := '1'end(else)end(if)end(for)end(for)end(HuffmanCod

19、ing源代碼：#include <stdio.h> #include <stdlib.h>#include <string.h>#include <iostream>using namespace std;#define infinite 50000定義 Huffman樹和Huffman編碼的存儲表示typedef structunsigned int weight; / 字符的頻數(shù)unsigned int parent, lchild, rchild; /雙親結(jié)點，左孩子，右孩 子HTNode, * HuffmanTree;typedef ch

20、ar * HuffmanCode;void Select(HuffmanTree HT, int n, int &s1, int &s2);void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n);void main()int i, n, *w;cout << "enter the size of the code:"cin >> n;cout << endl;w = (int*) malloc( (n+1) * sizeof(i

21、nt);cout << "enter the weight of the code:"<<endl;for(i=1; i<=n; i+)逐個輸入每個字符的出現(xiàn)的頻數(shù)，并用空格隔開cin>>wi;HuffmanTree HT;HuffmanCode HC;HuffmanCoding(HT, HC, w+1, n);cout<< "the huffmancode is: "<< endl;for(i=1; i<=n; i+)cout<<wi<<":&qu

22、ot;cout<<HCi<<" "cout<<endl;system("pause");在HuffmanTree中HT1 - n選擇parent為且 weight最小的兩個結(jié)點，其序 號分別為si和s2void Select(HuffmanTree HT, int n, int &s1, int &s2)(int i;si = s2 =0;for(i=1; i<=n; i+)(if(HTi.parent = 0 && HTs2.weight > HTi.weight)s2 =

23、 i;elseif (HTi.parent = 0 && HTs1.weight > HTi.weight)s1 = i;)構(gòu)造 Huffman樹HT,并求出n個字符的 Huffman編碼HCvoid HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)(if (n <= 1) return;HuffmanTree p;int s1, s2, i, m, start, c, f;char *cd;m = 2 * n - 1;HT = (HuffmanTree)malloc(m+1

24、) * sizeof(HTNode);HT0.weight = infinite;/將號單元置一個較大的數(shù)for(p=HT+1, i=1; i<=n; +i, +p, +w)(*p).weight = *w;/將n個字符的頻數(shù)送到HT.weight1 n(*p).parent = (*p).lchild = (*p).rchild = 0;/ 雙親孩子初始化為)for(; i<=m; +i, +p)(*p).weight = (*p).parent = (*p).lchild = (*p).rchild = 0; /將HuffmanTree結(jié)點權(quán)值 HT.weightn+1 - +

25、1(頻數(shù))及雙親孩子初始化為for(i= n+1; i<=m; +i)/根據(jù) Huffman 編碼原理進行構(gòu)建 Huffman樹(Select(HT, i-1, s1, s2);HTs1.parent = i;HTs2.parent = i;HTi.lchild = s1;HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight;)從葉子到根逆向求每個字符的Huffman編碼HC = (HuffmanCode) malloc (n+1) * sizeof (char *); / 分配 n 個 字符編碼的頭指針向量，注號單元未用cd =

26、(char *) malloc (n * sizeof (char);分配求編碼的工作空間cdn-1 = '0'編碼結(jié)束符for(i=1; i<=n; +i)/逐個字符求 Huffman 編碼(start = n - 1;編碼結(jié)束符位置for(c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) / 從葉 子到根逆向求編碼(if(HTf.lchild = c)cd-start = '0'elsecd-start = '1')HCi = (char *)malloc(n-start) * sizeof(cha

27、r); / 為第 i 個 字符編碼分配空間strcpy_s(HCi,sizeof(&cdstart),&cdstart);)free(cd);)答案2)c語言實現(xiàn)：huffman 編碼解碼#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 100#define M 2*N-1typedef char * HuffmanCode2*M;/haffman編碼typedef struct(int weight;/權(quán)值int parent;/父節(jié)節(jié)點int LChild;

28、/左子節(jié)點int RChild;/右子節(jié)點)HTNode,HuffmanM+1;/huffman 樹typedef struct Node(int weight; /葉子結(jié)點的權(quán)值char c; /葉子結(jié)點int num; /葉子結(jié)點的二進制碼的長度WNode,WeightNodeN;/*產(chǎn)生葉子結(jié)點的字符和權(quán)值*/void CreateWeight(char ch,int *s,WeightNode CW,int *p)int i,j,k;int tag;*p=0;/ 葉子節(jié)點個數(shù)/統(tǒng)計字符出現(xiàn)個數(shù)，放入CWfor(i=0;chi!='0'i+)tag=1;for(j=0;j

29、<i;j+)if(chj=chi)tag=0;break;if(tag)CW+*p.c=chi;CW*p.weight=1;for(k=i+1;chk!='0'k+)if(chi=chk)CW*p.weight+;/權(quán)值累加*s=i;/ 字符串長度/* 創(chuàng)建 HuffmanTree*/void CreateHuffmanTree(Huffman ht,WeightNode w,int n)int i,j;int s1,s2;/初始化哈夫曼樹for(i=1;i<=n;i+)hti.weight =wi.weight;hti.parent=0;hti.LChild=0;

30、hti.RChild=0;for(i=n+1;i<=2*n-1;i+)(hti.weight=0;hti.parent=0;hti.LChild=0;hti.RChild=0;for(i=n+1;i<=2*n-1;i+)(for(j=1;j<=i-1;j+)if(!htj.parent)break;s1=j; /找到第一個雙親不為零的結(jié)點for(;j<=i-1;j+)if(!htj.parent)s1=hts1.weight>htj.weight?j:s1;hts1.parent=i;hti.LChild=s1;for(j=1;j<=i-1;j+)if(!h

31、tj.parent)break;s2=j; /找到第二個雙親不為零的結(jié)點for(;j<=i-1;j+)if(!htj.parent)s2=hts2.weight>htj.weight?j:s2;hts2.parent=i;hti.RChild=s2;hti.weight=hts1.weight+hts2.weight;/權(quán)值累加/*葉子結(jié)點的編碼*/m,intvoid CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,int n)(int i,c,p,start;char *cd;cd=(ch

32、ar *)malloc(n*sizeof(char);cdn-1='0'/ 末尾置 0for(i=1;i<=n;i+)(start=n-1; /cd串每次從末尾開始c=i;p=hti.parent;/p 在 n+1 至 2n-1while(p) / 沿父親方向遍歷，直到為0start-;/依次向前置值if(htp.LChild=c)/與左子相同，置0cdstart='0'else / 否則置1cdstart='1'c=p;二進制碼的長度（包含末尾0）p=htp.parent;weighti.num=n-start; / hi=(char *

33、)malloc(n-start)*sizeof(char);strcpy(hi,&cdstart);/將二進制字符串拷貝到指針數(shù)組free(cd);/ 釋放 cd 內(nèi)存system("pause");/*所有字符的編碼*/m)void CrtHuffmanCode(charch,HuffmanCode h,HuffmanCode hc,WeightNode weight,intn,intint i,k;for(i=0;i<m;i+)for(k=1;k<=n;k+) /*從weightk.c 中查找與chi相等的下標(biāo) K*/if(chi=weightk.c

34、)break;hci=(char *)malloc(weightk.num)*sizeof(char);strcpy(hci,hk); /拷貝二進制編碼/* 解碼 */void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)int i=0,j,p;printf("*StringInformation*n");while(i<m)（p=2*n-1;/從父親節(jié)點向下遍歷直到葉子節(jié)點for(j=0;hcij!='0'j+)if(hcij='0')p=htp.

35、LChild;elsep=htp.RChild;) printf("%c”,wp.c); /*打印原信息 */i+； ) )/* 釋放huffman編碼內(nèi)存*void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m) int i;for(i=1;i<=n;i+)/釋放葉子結(jié)點的編碼free(hi);for(i=0;i<m;i+) /釋放所有結(jié)點的編碼free(hci);) void main() int i,n=0; /*n為葉子結(jié)點的個數(shù) */int m=0; /*m 為字符串 ch的長度*/ char

36、chN; /*chN存放輸入的字符串*/Huffman ht; /*Huffman 二叉數(shù) */HuffmanCode h,hc; /*h 存放葉子結(jié)點的編碼， hc存放所有結(jié)點的編碼*/WeightNode weight; /* 存放葉子結(jié)點的信息 */ printf("t*HuffmanCoding*n"); printf("please input information :");gets(ch); /*輸入字符串*/CreateWeight(ch,&m,weight,&n); /*產(chǎn)生葉子結(jié)點信息,m為字符串 ch的長度*/pri

37、ntf("*WeightInformation*n Node ");for(i=1;i<=n;i+) /*輸出葉子結(jié)點的字符與權(quán)值*/printf("%c ”,weighti.c);printf("nWeight ");for(i=1;i<=n;i+) printf("%d ",weighti.weight); CreateHuffmanTree(ht,weight,n); /*產(chǎn)生 Huffman 樹 */printf("n*HuffamnTreeInformation*n");printf

38、("titweighttparenttLChildtRChildn");for(i=1;i<=2*n-1;i+)/*打印 Huffman 樹的信息 */printf("t%dt%dt%dt%dt%dn”,i,hti.weight,hti.parent,hti.LChild,hti.RChild);CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*葉子結(jié)點的編碼 */printf(" *NodeCode*n"); /*打印葉子結(jié)點的編碼 */for(i=1;i<=n;i+) printf("

39、t%c:",weighti.c); printf("%sn",hi);)CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的編碼*/printf("*StringCode*n"); /*打印字符串的編碼*/for(i=0;i<m;i+)printf("%s",hci);system("pause");TrsHuffmanTree(ht,weight,hc,n,m); /*解碼 */FreeHuffmanCode(h,hc,n,m);system("paus

40、e");)答案3)(1) 偽代碼：Proc HuffmanCode(A)/A1 -n待編碼的數(shù)組,n為數(shù)組長度local h; 最小化堆，內(nèi)含元素為結(jié)點類型，堆初始為空integer i;Node p, q, r; /結(jié)點數(shù)據(jù)結(jié)構(gòu)，內(nèi)含數(shù)值以及分別指向左、右兒子的兩個指針for i from 1 to to n do /將數(shù)組A中的所有元素插入堆Insert(h, A(i);endfor);while h元素個數(shù)大于 1 thenp = DeleteMin(h); /移除最小的兩個結(jié)點q = DeleteMin(h);r = p+q; r.left = min(p, q); r.ri

41、ght = max(p, q); / 構(gòu)造新的結(jié)點 r,其值為 p,q 值之和。左兒子為p和q值較小的，右兒子為較/大的Insert(h, r); /將r插入堆中endwhile;p = DeleteMin(h); /取出最后一個結(jié)點，此節(jié)點即為huffman樹的根節(jié)點。endHuffmanCode(2) java code:樹節(jié)點TreeNode:package graduate;public class TreeNodeprivateTreeNodeleftprivateTreeNoderightprivateintvalue;privateintcode ;publicTreeNode(

42、) setLeft( null );setRight( null );setValue(0);setCode(-1);)public TreeNode getLeft()( return left ;)public void setLeft(TreeNode left)( this . left = left;)public TreeNode getRight()( return right ;)public void setRight(TreeNode right)( this . right = right;)public int getValue() return value ;)pub

43、lic void setValue( int value) this . value = value;)public int getCode() return code ;)public void setCode( int code) this . code = code;)堆節(jié)點HeapNode:package graduate;public class HeapNode private int iData ;public HeapNode( int key) iData = key;public void setKey( int id) ( iData = id;)public int g

44、etKey() ( return iData ;)堆：package graduate;public class Heap(private HeapNode heapArray ; / 堆容器private int maxSize ; / 堆得最大大小private intcurrentSize; / 堆大小publicHeap( int _maxSize) maxSize = _maxSize;heapArray = new HeapNode maxSize ;currentSize = 0;)public void filterDown( int start, int endOfHeap)

45、 int i = start;int j = 2 * i + 1;/ j 是i的左子女位置HeapNode temp = heapArray i;while (j <= endOfHeap) / 檢查是否到最后位置if (j < endOfHeap / 讓j指向兩子女中的小者&& heapArray j.getKey() >heapArray j + 1.getKey() j+;)if (temp.getKey() <=heapArray j.getKey() /小則不做調(diào)整break ;)else / 否則小者上移，i , j下降heapArray i

46、 = heapArray j;i = j;j = 2 * j + 1;)heapArray i = temp;)public void filterUp( int start) ( int j = start;int i = (j - 1) / 2;HeapNode temp = heapArray j;while (j > 0) (/ 沿雙親結(jié)點路徑向上直達(dá)根節(jié)點/雙親結(jié)點值小，不調(diào)整if ( heapArray i.getKey() <= temp.getKey() break ;else /雙親結(jié)點值大，調(diào)整 heapArray j = heapArray i; j = i;

47、i = (i - 1) / 2;heapArray j = temp; / 回送public boolean insert(HeapNode newNode) if (isFull() return false ;else heapArray currentSize = newNode;filterUp( currentSize );currentSize +;return true ;public HeapNode removeMin() if (isEmpty() return null ;HeapNode root = heapArray 0;heapArray 0 = heapArra

48、y currentSize - 1;currentSize -;filterDown(0, currentSize - 1);return root;public boolean isEmpty() return currentSize = 0;public boolean isFull() (return currentSizemaxSize ;publicint getCurrentSize()(turncurrentSize ;public void makeEmpty() (currentSize = 0;Huffman編碼方法:packageimportgraduate;java.u

49、til.HashMap;importjava.util.Iterator;publicclass Huffman( publicpublicpublicHeap minHeap ;HashMap<HeapNode, TreeNodeHashMap<Integer, String>nodeMap ;map;publicHuffman()(minHeapnew Heap(20);nodeMap = new HashMap<HeapNode, TreeNode>();map = new HashMap<Integer, String>();publicvoi

50、d huffmanCode( intarray)(for(int i = 0; i < array.length ; i+)(HeapNode heapNode =new HeapNode(arrayi);TreeNode treeNode =new TreeNode();treeNode.setValue(arrayi);nodeMap .put(heapNode, treeNode);minHeap .insert(heapNode);while ( minHeap .getCurrentSize() > 1) (HeapNode n1 =minHeap .removeMin(

51、);TreeNode tn1 =nodeMap .get(n1);HeapNode n2 =minHeap .removeMin();TreeNode tn2 =nodeMap .get(n2);if (tn1.getValue() < tn2.getValue() tn1.setCode(0);tn2.setCode(1);else tn2.setCode(0);tn1.setCode(1);HeapNode newHeapNode =new HeapNode(n1.getKey()+n2.getKey();TreeNode newTreeNode =new TreeNode();ne

52、wTreeNode.setValue(tn1.getValue()+tn2.getValue();newTreeNode.setLeft(tn1);newTreeNode.setRight(tn2);minHeap .insert(newHeapNode);nodeMap .put(newHeapNode, newTreeNode);HeapNode root = minHeap .removeMin();TreeNode treeRoot =nodeMap .get(root);leftFirst(treeRoot,"" );public void leftFirst(T

53、reeNode node, String code)if (node.getCode() != -1)code += new Integer(node.getCode().toString();if (node.getLeft() =null )map.put( new Integer(node.getValue(), code);return ;leftFirst(node.getLeft(), code);leftFirst(node.getRight(), code);public static void main(String args)Huffman h = new Huffman(

54、);int array = 9,5, 16, 12, 45, 13;h.huffmanCode(array);Iterator<Integer> i = h.map.keySet().iterator();while (i.hasNext()+ h. map.get(num);Integer num = i.next();System. out .println(num +)答案4)偽代碼：void CreateHuffmanTree(HuffmanTree T)(/構(gòu)造哈夫曼樹，Tm-1為其根結(jié)點int i , p1, p2；InitHuffmanTree(T) ； / 將 T 初始化InputWeight(T) ；/麻入葉子權(quán)值至 T0 . n-1的 weight 域for(i=n ； i<m ； i+)(/共進行n-1次合并，新結(jié)點依次存于Ti中SelectMin(T , i-1 , &p1 , &p2);在T0 . . i-1中選擇兩個權(quán)最小的根結(jié)點，其序號分別為p1和p2Tp1.parent=Tp2.parent=i ；TIi.1child=p1 ； /最小權(quán)的根結(jié)點是新結(jié)點的左孩子Tj.