「哈夫曼文件壓縮實(shí)驗(yàn)報(bào)告」.doc

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告三哈夫曼文件壓縮實(shí)驗(yàn)題目：哈夫曼文件壓縮實(shí)驗(yàn)?zāi)繕?biāo)：輸入一個(gè)有10k單詞的英文文檔。輸出壓縮后的二進(jìn)制文件，并計(jì)算壓縮比。數(shù)據(jù)結(jié)構(gòu)：棧和哈夫曼樹。1. 定義棧（）typedef structchar *elem;int stacksize;int top;STACK;2. 定義哈夫曼樹（）typedef structint weight;int left,right;int parent;HTNode;需要的操作有：1.初始化棧（Initstack）void Initstack(STACK *s)s-elem=(char *)malloc(sizeof(int)*1000);s-stacksize=1000;s-top=-1;2.壓棧（push）void push(STACK *s,int e)s-elem+s-top=e;3.彈棧（pop）void pop(STACK *s,int *e)if(s-top!=-1)*e=s-elems-top-;4.構(gòu)造哈夫曼樹（Inithuffman）void Inithuffman(int wsetn,int k,HuffTree HT) /構(gòu)造哈夫曼樹int i,m;int s1,s2;m=k*2-1;for(i=0;iweight=(iparent=-1;HTi-left=HTi-right=-1;for(i=k;ileft=s1;HTi-right=s2;HTi-weight=HTs1-weight+HTs2-weight;HTs1-parent=HTs2-parent=i;其中用到另一個(gè)基本操作：找到哈夫曼樹中最小和次小的結(jié)點(diǎn)（select）5.找到哈夫曼樹中最小和次小的結(jié)點(diǎn)（select）void select(HuffTree HT255,int a,int i,int *p,int *q)int j=0,k=0,*HT1,temp;HT1=(int *)malloc(sizeof(int)*(i-1); /存放權(quán)值for(j=0;jparent=-1)HT1k=HTj-weight; /把沒有parent的結(jié)點(diǎn)的權(quán)值放在HT1中k+;/printf(%4d%4d%4d%4d%4dn,HTj-parent,HTj-left,HTj-right,HTj-weight,HT1k-1);j=0;while(j2) /找到權(quán)值最小和第二小的結(jié)點(diǎn)for(k=j;kHT1k) temp=HT1k;HT1k=HT1j;HT1j=temp;j+;k=0;for(j=0;jparent=-1)if(HTj-weight=HT10&k1) /將最小的權(quán)值賦到*p中*p=j;k+;j+;for(j=0;jparent=-1)if(j!=*p)if(HTj-weight=HT11&kparent,HTi-left,HTi-right,HTi-weight);6.根據(jù)哈夫曼樹得到各字符對(duì)應(yīng)的哈夫曼編碼（Huffman）void Huffman(HuffTree HT2*n-1,int k,char str20) int i,j,e,t1=0,t2=0;char c;STACK st;for(i=0;iright=-1&HTi-left=-1) /找一個(gè)葉子結(jié)點(diǎn)Initstack(&st);HTi-right=HTi-left=-2; j=i; /記錄其下標(biāo)while(HTj-parent!=-1) if(HTHTj-parent-right=j) /找到一個(gè)葉子結(jié)點(diǎn)，如果他是其parent結(jié)點(diǎn)的右結(jié)點(diǎn)，就將此邊記為1push(&st,1); elsepush(&st,0); /在左邊記為0j=HTj-parent; /循環(huán)操作直到到達(dá)根結(jié)點(diǎn)c=i;printf(t%c ,c); /打印此字符for(;st.top!=-1;)pop(&st,&e);printf(%c,e); /打印其二進(jìn)制編碼strt1t2=e; /將二進(jìn)制編碼存放在str中t2+;putchar(n);strt1t2=0; t2=0; t1+;算法設(shè)計(jì)：1.從文件中逐個(gè)讀取字符，記錄其出現(xiàn)次數(shù)以及文件總字符數(shù)，由此確定其頻率高低。2.根據(jù)字符頻率創(chuàng)建哈夫曼樹，然后求出哈夫曼編碼。3.將哈夫曼編碼輸出到另一個(gè)文件中，并統(tǒng)計(jì)字?jǐn)?shù)，求出壓縮率。源程序#include#include#include#define n 127typedef structint weight;int left,right;int parent;HTNode;/哈夫曼數(shù)組結(jié)構(gòu)類型typedef HTNode *HuffTree;typedef structchar *elem;int stacksize;int top;STACK;/棧的結(jié)構(gòu)類型void Initstack(STACK *s)s-elem=(char *)malloc(sizeof(int)*1000);s-stacksize=1000;s-top=-1;/初始化棧void push(STACK *s,int e)s-elem+s-top=e;/壓棧void pop(STACK *s,int *e)if(s-top!=-1)*e=s-elems-top-;/彈棧void select(HuffTree HT255,int a,int i,int *p,int *q)/找到哈夫曼樹中權(quán)值最小和次小的結(jié)點(diǎn)并返回指針int j=0,k=0,*HT1,temp;HT1=(int *)malloc(sizeof(int)*(i-1); /存放權(quán)值for(j=0;jparent=-1)HT1k=HTj-weight; /把沒有parent的結(jié)點(diǎn)的權(quán)值放在HT1中k+;/printf(%4d%4d%4d%4d%4dn,HTj-parent,HTj-left,HTj-right,HTj-weight,HT1k-1);j=0;while(j2) /找到權(quán)值最小和第二小的結(jié)點(diǎn)for(k=j;kHT1k) temp=HT1k;HT1k=HT1j;HT1j=temp;j+;k=0;for(j=0;jparent=-1)if(HTj-weight=HT10&k1) /將最小的權(quán)值賦到*p中*p=j;k+;j+;for(j=0;jparent=-1)if(j!=*p)if(HTj-weight=HT11&kparent,HTi-left,HTi-right,HTi-weight);void Inithuffman(int wsetn,int k,HuffTree HT) /構(gòu)造哈夫曼樹int i,m;int s1,s2;m=k*2-1;for(i=0;iweight=(iparent=-1;HTi-left=HTi-right=-1;for(i=k;ileft=s1;HTi-right=s2;HTi-weight=HTs1-weight+HTs2-weight;HTs1-parent=HTs2-parent=i;void Huffman(HuffTree HT2*n-1,int k,char str20) /根據(jù)哈夫曼樹得到各字符對(duì)應(yīng)的哈夫曼編碼int i,j,e,t1=0,t2=0;char c;STACK st;for(i=0;iright=-1&HTi-left=-1) /找一個(gè)葉子結(jié)點(diǎn)Initstack(&st);HTi-right=HTi-left=-2; j=i; /記錄其下標(biāo)while(HTj-parent!=-1) if(HTHTj-parent-right=j) /找到一個(gè)葉子結(jié)點(diǎn)，如果他是其parent結(jié)點(diǎn)的右結(jié)點(diǎn)，就將此邊記為1push(&st,1); elsepush(&st,0); /在左邊記為0j=HTj-parent; /循環(huán)操作直到到達(dá)根結(jié)點(diǎn)c=i;printf(t%c ,c); /打印此字符for(;st.top!=-1;)pop(&st,&e);printf(%c,e); /打印其二進(jìn)制編碼strt1t2=e; /將二進(jìn)制編碼存放在str中t2+;putchar(n);strt1t2=0; t2=0; t1+;void main()FILE *fp1,*fp2; HuffTree HT2*n-1;int i=0,sum1=0,sum2=0;float compress;char strn20;char elem,ch;int countn=0; if(fp1=fopen(text1.txt,r)=NULL)printf(cant open the file!n);exit(0);while(!feof(fp1) /讀取文件中字符elem=fgetc(fp1);i=elem;counti+; /記錄字符頻率Inithuffman(count,n,HT);/for(i=0;iparent,HTi-left,HTi-right,HTi-weight);Huffman(HT,2*n-1,str); /對(duì)文章進(jìn)行哈夫曼編碼 if(fp1=fopen(text1.txt,r)=NULL)printf(cant open the file!n);exit(0); if(fp2=fopen(text2.txt,w)=NULL)printf(cant open the file!n);exit(0);while(!feof(fp1)ch=fgetc(fp1); /讀取text1中字符i=ch;fputs(stri,fp2); /將此字符的二進(jìn)制編碼輸出到text2中sum1+; if(fp2=fopen(text2.txt,r)=NULL)printf(cant open the file!n);exit(0);while(!feof(fp2)ch=fgetc(fp2);sum2+;compress=(float)sum2/(float)(sum1*8)