實驗三貪心算法設(shè)計與實現(xiàn)實驗報告

1、華北水利水電學(xué)院算法分析與設(shè)計實驗報告20010-2011學(xué)年 第二學(xué)期2008級計算機(jī)科學(xué)與技術(shù)專業(yè)班級：2008109 學(xué)號：200810906姓名：劉景超實驗三貪心算法的設(shè)計與實現(xiàn)一、實驗?zāi)康模?、了解貪心算法的設(shè)計思路與設(shè)計技巧，理解貪心算法的概念，掌握設(shè)計有效的貪心算 法的策略。2、通過實際案例，領(lǐng)會算法的執(zhí)行效率二、試驗內(nèi)容：哈弗曼編碼三、核心程序源代碼：#include#include#include#include#include#include#define OVERFLOW -2#define OK 1#define ERROR 0typedef int ElemType;

2、typedef int Status;/定義 Huffmantreetypedef structint weight;int parent;int lchild;int rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;#define CHLENGTH 27#define WLENGTH 27void HuffmanCoding(HuffmanTree &,HuffmanCode &,int *,int ); 編碼函數(shù)void Select(HuffmanTree ,int ,int &,int &);void HuffmanDecodi

3、ng(char *,HuffmanTree ,HuffmanCode ,int *,int *,int ); 譯碼函數(shù)void Treeprinting(char *,HuffmanTree ,HuffmanCode ,int *,int *,int ); /打印 HuffmanTreevoid preorder(HuffmanTree HT,int root,int i,int sum,int *,int *,FILE *);/主函數(shù) void main(void) int chCHLENGTH= ,A,B,C,D,E,F,G, H,T,J,K,L,M,N,O,P,Q,R,S, T,U, V

4、,W,X,Y,Z;int wWLENGTH=186,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;int i=1;char buff1025;char ch1;int c;FILE *fp_1,*fp_2; int flag=1,legth=0; HuffmanTree HT; HuffmanCode HC;while(1) printf(*n);printf(1.進(jìn)行編碼 n);printf(2.譯碼工作n);printf(3.打印 CodeFile.txtn);printf(4.打印

5、HuffmanTree n);printf(5.退出程序)； printf(*n);scanf(%d”,&c);getchar();switch(c)case 1:編碼HuffmanCoding(HT,HC,w,WLENGTH);if(fp_1=fopen(”CodeFile.txt”,”w”)= NULL) printf(can not open the filen);getch();exit(0);for(i=1;iWLENGTH+1;i+)printf(%c”,chi-1);printf();fputs(HCi,fp_1); /存儲在文件中puts(HCi); /打印在屏幕上fclose

6、(fp_1);break;case 2:譯碼if(fp_1=fopen(”CodeFile.txt”,”r”)= NULL)printf(can not open the filen);getch();exit(0);i=0;while( !feof(fp_1)fgets(buff,1024,fp_1);HuffmanDecoding(buff,HT,HC,w,ch,WLENGTH);break;case 3:/打印 CodeFile.txti=0;if(fp_1=fopen(”CodeFile.txt”,”r”)= NULL)printf(can not open the filen);ge

7、tch();exit(0);if(fp_2=fopen(”CodePin.txt”,”w”)= NULL)printf(can not open the filen);getch();exit(0);ch1=fgetc(fp_1);while( !feof(fp_1) )i+;putchar(ch1);fprintf(fp_2,%c”,ch1);if(i%50 = 0)printf(n);fprintf(fp_2,%c”,n);ch1=fgetc(fp_1);printf(n);break;case 4:打印 HuffmanTreeTreeprinting(buff,HT,HC,w,ch,WL

8、ENGTH);break;case 5:/退出程序exit(0);構(gòu)造哈夫曼樹HT,并求出n個字符的哈夫曼編碼HCvoid HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) int i, j, m, s1, s2, start;char *cd;int c, f;if (n=1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); /0 號單元未用for (i=1; i=n; i+)初始化HTi.weight=wi-1;HTi.par

9、ent=0;HTi.lchild=0;HTi.rchild=0;for (i=n+1; i=m; i+) /初始化HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;printf(n哈夫曼樹的構(gòu)造過程如下所示：n);printf(HT 初態(tài):n 結(jié)點 weight parent lchild rchild);for (i=1; i=m; i+)printf(n%4d%8d%8d%8d%8d”,i,HTi.weight, HTi.parent,HTi.lchild, HTi.rchild);for (i=n+1; i=m; i+) /建立哈夫曼

10、樹Select(HT, i-1, s1, s2);HTs1.parent = i; HTs2.parent = i;HTi.lchild = s1; HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight;printf(nselect: s1=%d s2=%dn”, s1, s2);printf( 結(jié)點 weight parent lchild rchild);for (j=1; j=i; j+)printf(n%4d%8d%8d%8d%8d,j,HTj.weight, HTj.parent,HTj.lchild, HTj.rchild);

11、HC = (HuffmanCode)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,

12、&cdstart);printf(n);free(cd);選擇函數(shù)void Select(HuffmanTree HT,int x,int &s1,int &s2)int firstmin=HT1.weight,secondmin=HT1.weight;int firstnummin=1,secondnummin=1;int i=1,count=1,j=1;while(1)if(HTi.parent = 0)為其賦初值firstmin=HTi.weight;secondmin=HTi.weight;firstnummin=i;secondnummin=i;聲break;i+;for(+i;i=

13、x;i+)取出最小值if(HTi.weight firstmin & HTi.parent = 0)firstmin=HTi.weight;firstnummin=i;i=j；for(+i;i firstmin & HTi.weight secondmin & HTi.parent = 0)secondmin=HTi.weight;secondnummin=i;elseif(secondmin = firstmin & HTi.parent = 0)當(dāng)權(quán)值相等的時候，特殊考慮secondnummin=i;break;s1=firstnummin;s2=secondnummin;譯碼函數(shù)void

14、 HuffmanDecoding(char *buff,HuffmanTree HT,HuffmanCode HC,int *w,int *ch,int n) int root=0,i=0,j=0,lchild=0,rchild=0,k=1;char result100;FILE *fp;root=2*n-1;if(fp=fopen(TextFile.txt,w) = NULL)printf(can not open the filen);exit(0);while(buffi!=0)if(buffi = 0)resultj=buffi;/把編碼存入這個結(jié)果的數(shù)組中j+;root=HTroot

15、.lchild;if( HTroot.lchild = 0 )resultj=0;while( strcmp(HCk,result) != 0) k+;printf(%c”,chk-1);fprintf(fp,%c”,chk-1);寫入文件j=0；k=1;root=2*n-1;+i；elseif(root != 2*n-1) +i;elseif(buffi = 1)root=HTroot.rchild;resultj=buffi;j+;if(HTroot.rchild = 0 ) resultj=0;while( strcmp(HCk,result) != 0) k+;printf(%c”,c

16、hk-1);fprintf(fp,%c”,chk-1);j=0;k=1;root=2*n-1;+i;elseif(root != 2*n-1) +i;fclose(fp);printf(nn);/打印 HuffmanTreevoid Treeprinting(char *buff,HuffmanTree HT,HuffmanCode HC,int *w,int *ch,int n) int root=0,i=1,j=0,lchild=0,rchild=0,k=1,space=0; /space 是空格數(shù) FILE *fp;if(fp=fopen(”TextFile.txt”,”w”)= NUL

17、L)printf(can not open the filen);exit(0);root=2*n-1;preorder(HT,root,i,i,ch,w,fp);fclose(fp);n)；printf(n/void preorder(HuffmanTree HT,int root,int i,int sum,int *ch,int *w,FILE *fp) int lchild=0,rchild=0;if(HT = NULL)return;if(i = 1)sum=sum+i;while(isum)printf();fprintf(fp,);i+;i=1;if( HTroot.lchild = 0 & HTroot.rchild = 0 )fprintf(fp,*%dn”,HTroot.weight);printf(*%dn”,HTroot.weight);if( HTroot.lchild != 0 |