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

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

2、i1 ti2tin, ，下證明當(dāng)按照不減順序依次服務(wù)時，為最優(yōu)策略。記按照 i1i2 in 次序服務(wù)時， 等待時間為 T ，下證明任意互換兩者的次序， T 都不減。即假設(shè)互換 i, j (i j) 兩位顧客的次序，互換后等待總時間為 T ，則有T T.由于T(n 1)ti1(n 2)ti22tin2tin 1 ,T(n1)ti1(n2)ti2(n i)tii(n j)tij2t tin 2in 1T(n1)ti1(n2)ti2(n i)tij(n j)tii2titiin 2in 1則有T T (j i)(tijtii ) 0.同理可證其它次序，都可以由 i1i2 in 經(jīng)過有限次兩兩調(diào)換順序

3、后得到，而每次交換，總時間不減，從而 i1i 2in 為最優(yōu)策略2.字符ah出現(xiàn)的頻率分布恰好是前 8個Fibo nacci數(shù)，它們的Huffman編碼是什么？將結(jié)果推廣到n個字符的頻率分布恰好是前n個Fibonacci數(shù)的情形。Fib on acci 數(shù)的定義為：Fo 1,Fi 1, FnFn 2 Fn 1 if n 1解：前8個數(shù)為a，b，1， 1,Huffman哈夫曼編碼樹為：c， d, e, f， g.2，3，5，8， 13， 21541033200f:812e:501d:312C:2h:21所以a的編碼為：1111111 b的編碼為：1111110 c的編碼為：111110 d的編碼

4、為：11110 e的編碼為：1110 f的編碼為：110 g的編碼為：10 h的編碼為：0推廣到 n 個字符：第 1 個字符： n-1 個 1 ，11 1n1第 2 個字符： n-2 個 1 ，1 個 0，11 10n2第 3 個字符： n-3 個 1 ，1 個 0，11 10n3第n-1個字符：1個1 ，1 個 0，10第 n 個字符： 1 個 003 設(shè) p1,p2, ,pn 是準(zhǔn)備存放到長為 L 的磁帶上的 n 個程序，程序 pi 需要的 n帶長為 ai 。設(shè) ai L ，要求選取一個能放在帶上的程序的最大子集合（即其中i1含有最多個數(shù)的程序）Q。構(gòu)造Q的一種貪心策略是按ai的非降次序?qū)?/p>

5、程序計入 集合。集合。1）證明這一策略總能找到最大子集 Q ，使得ai L 。pi Q2）設(shè)Q是使用上述貪心算法得到的子集合，磁帶的利用率可以小到何種程度？3）試說明1）中提到的設(shè)計策略不一定得到使a/L取最大值的子集合。pi Q1）證明：不妨設(shè)印a2 . an，若該貪心策略構(gòu)造的子集合 Q為印,玄2, ,a$，ss則 s 滿足ai L、as as 1 L。i 1i 1要證明能找到最大子集，只需說明s為可包含的最多程序段數(shù)即可。即證不存在多于s個的程序集合Q ail ,ai2, ，a （k s），使得 a Lpi Qk反證法，假設(shè)存在多于 s個的程序集Q ai ,ai2, ,aik, （k s

6、），滿足a” L。j1因?yàn)?a1a2 . an 非降序排列，則 a1a2asakai1ai2aik L 。因?yàn)?ks 且為整數(shù)，則其前 s+1 項滿足 a1 a2asas 1L。s這與貪心策略構(gòu)造的子集和Q中s滿足的asi1as 1L 矛盾。故假設(shè)不成立，得證。2）磁帶的利用率為 ai / L;（甚至最小可為0，此時任意ai L或者 ai L） pi Qpi Q3) 按照 1)的策略可以使磁帶上的程序數(shù)量最多，但程序的總長度不一定是最大 的，假設(shè) a1,a2, ,ai 為 Q 的最大子集，但是若用ai 1 代替 ai ，仍滿足i1ak ai i L,則 佝耳，a,aii為總長度更優(yōu)子集。k14

7、. 答案見后面所附程序。5. 已知n種貨幣56丄，Cn和有關(guān)兌換率的n n表R,其中Ri，j是一個單位的貨幣 ci 可以買到的貨幣 cj 的單位數(shù)。1) 試設(shè)計一個算法,用以確定是否存在一貨幣序列ci1,ci2,L ,cik 使得：Ri1,i2Ri2,i3L Rik,i1 12) 設(shè)計一個算法打印出滿足 1)中條件的所有序列,并分析算法的計算時間。解：基本解題思想：通過 FLOYD 算法求出最大環(huán)。 判斷最大環(huán)的權(quán)值之積是否大于 1,如果大于 1 說明可以實(shí)現(xiàn)套匯, 如果不 大于 1 說明不能實(shí)現(xiàn)套匯。在求解最大環(huán)的同時記錄下兌換過程中的步驟。算法實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)：int PathMAX_VER

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

9、(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=i)printf("%d",i); return;else if(Pathij=0)/ 輸出結(jié)點(diǎn) i 與結(jié)點(diǎn) j 之間不存

10、在通路 printf("NO path");else printf("%d ",Pathij);Procedure_print(i,Pathij);/ 遞歸，貨幣 I 至 J 中間頂點(diǎn) 此算法的時間復(fù)雜度是：0("3)算法實(shí)現(xiàn)代碼： #include<stdio.h> #define MAX_VERTECX_NUM 20#define INT_MIN 0int n;int PathMAX_VERTECX_NUMMAX_VERTECX_NUM; float valueMAX_VERTECX_NUMMAX_VERTECX_NUM; ty

11、pedef structint vexsMAX_VERTECX_NUM; / 頂點(diǎn)向量 可以存儲每個頂點(diǎn)的信息float arcMAX_VERTECX_NUMMAX_VERTECX_NUM;/ 鄰接矩陣 主要存放關(guān)于邊的信息 int vexnum,arcnum;/圖中當(dāng)前頂點(diǎn)數(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=%d

12、n",G->vexnum,G->arcnum); for(i=1;i<=G->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;fo

13、r(i=1;i<=G->vexnum;i+)for(j=1;j<=G->vexnum;j+)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=P

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

15、;data.out","w",stdout);CreateDG(&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é)點(diǎn)放到一個隊列中，用一個節(jié)點(diǎn)替換

16、兩個頻率最低的節(jié) 點(diǎn)，新節(jié)點(diǎn)的頻率就是這兩個節(jié)點(diǎn)的頻率之和。這樣，新節(jié)點(diǎn)就是兩個被替換節(jié)點(diǎn)的父 節(jié)點(diǎn)了。如此循環(huán)，直到隊列中只剩一個節(jié)點(diǎn)(樹根) 。答案 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 return

17、HuffmanTree p;integer s1, s2, i, m, start, c, f;char *cd;m := 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;endforfor i to m do(*p).weight = (*p).parent = (*p).lchild = (*p).rchild =0;+p;endforfor i from n+1 to m doSele

18、ct(HT, i-1, s1, s2);HTs1.parent := i;HTs2.parent := i;HTi.lchild := s1;HTi.rchild := s2;HTi.weight := HTs1.weight + HTs2.weight;endforcdn-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 := 

19、9;1'endelseendifendforendforendHuffmanCoding源代碼：#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

20、; / 雙親結(jié)點(diǎn)，左孩子，右孩 子HTNode, * HuffmanTree;typedef char * 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

21、 << endl;w = (int*) malloc( (n+1) * sizeof(int);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;f

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

23、arent = 0 && HTs2.weight > HTi.weight) s2 = 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

24、;char *cd;m = 2 * n - 1;HT = (HuffmanTree)malloc(m+1) * 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 =

25、 (*p).rchild = 0; /將 HuffmanTree 結(jié)點(diǎn)權(quán)值 HT.weightn+1 m+1 (頻數(shù))及雙親孩子初始化為for(i= n+1; i<=m; +i)/根據(jù) Huffman 編碼原理進(jìn)行構(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+

26、1) * sizeof (char *);/ 分配 n 個 字符編碼的頭指針向量，注號單元未用cd = (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

27、'HCi = (char *)malloc(n-start) * sizeof(char); / 為第 i 個 字符編碼分配空間strcpy_s(HCi,sizeof(& cdstart), &cdstart);free(cd);答案2)c語言實(shí)現(xiàn)：huffman 編碼解碼#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 100編碼#define M 2*N-1typedef char * HuffmanCode2*M;/haffmantypedef s

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

29、CWfor(i=0;chi!='0'i+)tag=1;for(j=0;j<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;/ 字符串長度/*倉寸建 HuffmanTree*/void CreateHuffmanTree(Huffman ht,WeightNode w,int n) int i,j;int s1,s2;/初始化哈夫曼樹for(i=1;i<=n;i+)hti

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

31、=i;hti. LChild=s1;for(j=1;j<=i-1;j+)if(!htj.parent)break;s2=j; /找到第二個雙親不為零的結(jié)點(diǎn)for(;j<=i-1;j+)if(!htj.parent)s2=hts2.weight>htj.weight?j:s2;hts2.parent=i;權(quán)值累加hti.RChild=s2;hti.weight=hts1.weight+hts2.weight; 葉子結(jié)點(diǎn)的編碼 */m,intcdn-1='0' for(i=1;i<=n;i+) start=n-1; /cd c=i;p=hti.parent;

32、/pvoid CrtHuffmanNodeCode(Huffman ht,char ch,HuffmanCode h,WeightNode weight,intn)int i,c,p,start;char *cd;cd=(char *)malloc(n*sizeof(char);末尾置0串每次從末尾開始在 n+1 至 2n-1while(p) / 沿父親方向遍歷，直到為0start-;/ 依次向前置值if(htp.LChild=c)與左子相同,置 0cdstart='O：else / 否則置1cdstart='1'c=p;p=htp.parent;weighti.num

33、=n-start; /二進(jìn)制碼的長度(包含末尾 0)hi=(char *)malloc(n-start)*sizeof(char);m)strcpy(hi, &cdstart);/free(cd);/ 釋放 cd 內(nèi)存 system("pause");/*所有字符的編碼void CrtHuffmanCode(char*/ch,HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,intint i,k;for(i=0;i<m;i+)for(k=1;k<=n;k+) /* 從 weightk.c 中查找與

34、chi 相等的下標(biāo) K*/ if(chi=weightk.c)break;hci=(char *)malloc(weightk.num)*sizeof(char);strcpy(hci,hk); /拷貝二進(jìn)制編碼/*解軍碼*/將二進(jìn)制字符串拷貝到指針數(shù)組h中void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m) int i=0,j,p;printf("*Stringlnformation*n");while(i<m)p=2*n-1;/從父親節(jié)點(diǎn)向下遍歷直到葉子節(jié)點(diǎn)for(j=0;h

35、cij!='0'j+)if(hcij='0')p=htp.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é)點(diǎn)的編碼free(hi);for(i=0;i<m;i+) /釋放所有結(jié)點(diǎn)的編碼free(hci);void main()int i,n=0; /*n為葉子

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

37、n);/*產(chǎn)生葉子結(jié)點(diǎn)信息，m為字符串ch的長度*/printf("*Weightlnformation*n Node ");for(i=1;i<=n;i+) /*輸出葉子結(jié)點(diǎn)的字符與權(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*Huffam

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

39、編碼*/for(i=1;i<=n;i+)printf("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); /*解碼 */FreeHuff

40、manCode(h,hc,n,m);system("pause");答案3)(1) 偽代碼：Proc HuffmanCode(A)/A1r是待編碼的數(shù)組，n為數(shù)組長度local h;最小化堆，內(nèi)含元素為結(jié)點(diǎn)類型，堆初始為空integer i;Node p, q, r; /結(jié)點(diǎn)數(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é)點(diǎn)q = DeleteMin(h);r =

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

42、t;privateintcode ;publicTreeNode() setLeft( null ); setRight( null ); setValue(O); setCode(-l);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 getV

43、alue()return value ;public void setValue( int value) this . value = value;public int getCode()return code ;public void setCode( int code) this . code = code;堆節(jié)點(diǎn) HeapNode:package graduate;public class HeapNodeprivate int iData ;public HeapNode( int key) iData = key;public void setKey( int id) iData =

44、 id;public int getKey() return iData堆：package graduate;public class Heapprivate HeapNodeheapArray ; / 堆容器privateint maxSize ; / 堆得最大大小privateint currentSize/ 堆大小publicHeap( int _maxSize) maxSize = _maxSize;heapArray = new HeapNode maxSize ; currentSize = 0;public void filterDown(int start, int endOf

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

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

47、 = i;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 =

48、heapArray currentSize currentSize-;filterDown(0, currentSize - 1); return root;public boolean isEmpty() return currentSize = 0;public boolean isFull() maxSizereturn currentsizepublic int getCurrentSize() return currentSizepublic void makeEmpty() currentSize = 0;Huffman編碼方法: package graduate;import j

49、ava.util.HashMap;import java.util.Iterator;public class Huffmanpublic Heap minHeap ;public HashMapvHeapNode, TreeNode>nodeMap ;public HashMapvInteger, String>map;public Huffman()minHeap =nodeMap =new Heap(20);new HashMapvHeapNode, TreeNode>();map = new HashMapvInteger, String>();public v

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

51、n();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();

52、newTreeNode.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 leftFirs

53、t(TreeNode 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 Huff

54、man();int array = 9, 5, 16, 12, 45, 13;h.huffmanCode(array);Iterator<Integer> i = h.map.keySet().iterator();while (i.hasNext()Integer num = i.next();+ h. map.get(num);System. out .println(num +答案 4)偽代碼：void CreateHuffmanTree(HuffmanTree T)/構(gòu)造哈夫曼樹， Tm-1 為其根結(jié)點(diǎn)int i ， p1，p2；InitHuffmanTree(T) ； / 將 T 初始化InputWeight(T) ；/輸入葉子權(quán)值至 T0 . n-1的 weight