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

數(shù)據(jù)結(jié)構(gòu)試驗(yàn)匯報(bào)三——哈夫曼文件壓縮試驗(yàn)題目：哈夫曼文件壓縮試驗(yàn)?zāi)繕?biāo)：輸入一個(gè)有10k單詞英文文檔。輸出壓縮后二進(jìn)制文件，并計(jì)算壓縮比。數(shù)據(jù)結(jié)構(gòu)：棧和哈夫曼樹(shù)。定義棧（）typedefstruct{ char*elem; intstacksize; inttop;}STACK;定義哈夫曼樹(shù)（）typedefstruct{ intweight; intleft,right; intparent;}HTNode;需要操作有：1.初始化棧（Initstack）voidInitstack(STACK*s){ s->elem=(char*)malloc(sizeof(int)*1000); s->stacksize=1000; s->top=-1;}2.壓棧（push）voidpush(STACK*s,inte){ s->elem[++s->top]=e;}3.彈棧（pop）voidpop(STACK*s,int*e){ if(s->top!=-1) *e=s->elem[s->top--];}4.結(jié)構(gòu)哈夫曼樹(shù)（Inithuffman）voidInithuffman(intwset[n],intk,HuffTreeHT[]){//結(jié)構(gòu)哈夫曼樹(shù) inti,m; ints1,s2; m=k*2-1; for(i=0;i<m;i++){//初始化HT數(shù)組 HT[i]=(HuffTree)malloc(sizeof(HTNode)); HT[i]->weight=(i<k?wset[i]:0); HT[i]->parent=-1; HT[i]->left=HT[i]->right=-1; } for(i=k;i<m;i++){//主循環(huán)，完成n-1次合并 select(HT,k,i,&s1,&s2);//在HT[1...i-1]中選擇parent為0且weight為最小兩個(gè)結(jié)點(diǎn)，其下標(biāo)分別為s1和s2 HT[i]->left=s1; HT[i]->right=s2; HT[i]->weight=HT[s1]->weight+HT[s2]->weight; HT[s1]->parent=HT[s2]->parent=i; }}其中用到另一個(gè)基本操作：找到哈夫曼樹(shù)中最小和次小結(jié)點(diǎn)（select）5.找到哈夫曼樹(shù)中最小和次小結(jié)點(diǎn)（select）voidselect(HuffTreeHT[255],inta,inti,int*p,int*q){ intj=0,k=0,*HT1,temp; HT1=(int*)malloc(sizeof(int)*(i-1));//存放權(quán)值 for(j=0;j<i;j++){ if(HT[j]->parent==-1){ HT1[k]=HT[j]->weight;//把沒(méi)有parent結(jié)點(diǎn)權(quán)值放在HT1中 k++; } // printf("%4d%4d%4d%4d%4d\n",HT[j]->parent,HT[j]->left,HT[j]->right,HT[j]->weight,HT1[k-1]); } j=0; while(j<2){//找到權(quán)值最小和第二小結(jié)點(diǎn) for(k=j;k<(i-(i-a)*2);k++){ if(HT1[j]>HT1[k]){ temp=HT1[k]; HT1[k]=HT1[j]; HT1[j]=temp; } } j++; } k=0; for(j=0;j<i;){ if(HT[j]->parent==-1) if(HT[j]->weight==HT1[0]&&k<1){//將最小權(quán)值賦到*p中 *p=j; k++; } j++; } for(j=0;j<i;){ if(HT[j]->parent==-1) if(j!=*p) if(HT[j]->weight==HT1[1]&&k<2){//將第二小權(quán)值賦到*q中 *q=j; k++; } j++; // printf("%4d%4d%4d%4d\n",HT[i]->parent,HT[i]->left,HT[i]->right,HT[i]->weight); }}6.依照哈夫曼樹(shù)得到各字符對(duì)應(yīng)哈夫曼編碼（Huffman）voidHuffman(HuffTreeHT[2*n-1],intk,charstr[][20]){ inti,j,e,t1=0,t2=0; charc; STACKst; for(i=0;i<k;i++){ if(HT[i]->right==-1&&HT[i]->left==-1){//找一個(gè)葉子結(jié)點(diǎn) Initstack(&st); HT[i]->right=HT[i]->left==-2; j=i;//統(tǒng)計(jì)其下標(biāo) while(HT[j]->parent!=-1){ if(HT[HT[j]->parent]->right==j)//找到一個(gè)葉子結(jié)點(diǎn)，假如他是其parent結(jié)點(diǎn)右結(jié)點(diǎn)，就將此邊記為1 push(&st,'1'); else push(&st,'0');//在左邊記為0 j=HT[j]->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)制編碼 str[t1][t2]=e;//將二進(jìn)制編碼存放在str中 t2++; } putchar('\n'); str[t1][t2]='\0'; t2=0; t1++; } }}算法設(shè)計(jì)：1.從文件中逐一讀取字符，統(tǒng)計(jì)其出現(xiàn)次數(shù)以及文件總字符數(shù)，由此確定其頻率高低。2.依照字符頻率創(chuàng)建哈夫曼樹(shù)，然后求出哈夫曼編碼。3.將哈夫曼編碼輸出到另一個(gè)文件中，并統(tǒng)計(jì)字?jǐn)?shù)，求出壓縮率。源程序#include<stdio.h>#include<malloc.h>#include<process.h>#definen127typedefstruct{ intweight; intleft,right; intparent;}HTNode;//哈夫曼數(shù)組結(jié)構(gòu)類(lèi)型typedefHTNode*HuffTree;typedefstruct{ char*elem; intstacksize; inttop;}STACK;//棧結(jié)構(gòu)類(lèi)型voidInitstack(STACK*s){ s->elem=(char*)malloc(sizeof(int)*1000); s->stacksize=1000; s->top=-1;}//初始化棧voidpush(STACK*s,inte){ s->elem[++s->top]=e;}//壓棧voidpop(STACK*s,int*e){ if(s->top!=-1) *e=s->elem[s->top--];}//彈棧voidselect(HuffTreeHT[255],inta,inti,int*p,int*q){//找到哈夫曼樹(shù)中權(quán)值最小和次小結(jié)點(diǎn)并返回指針 intj=0,k=0,*HT1,temp; HT1=(int*)malloc(sizeof(int)*(i-1));//存放權(quán)值 for(j=0;j<i;j++){ if(HT[j]->parent==-1){ HT1[k]=HT[j]->weight;//把沒(méi)有parent結(jié)點(diǎn)權(quán)值放在HT1中 k++; } // printf("%4d%4d%4d%4d%4d\n",HT[j]->parent,HT[j]->left,HT[j]->right,HT[j]->weight,HT1[k-1]); } j=0; while(j<2){//找到權(quán)值最小和第二小結(jié)點(diǎn) for(k=j;k<(i-(i-a)*2);k++){ if(HT1[j]>HT1[k]){ temp=HT1[k]; HT1[k]=HT1[j]; HT1[j]=temp; } } j++; } k=0; for(j=0;j<i;){ if(HT[j]->parent==-1) if(HT[j]->weight==HT1[0]&&k<1){//將最小權(quán)值賦到*p中 *p=j; k++; } j++; } for(j=0;j<i;){ if(HT[j]->parent==-1) if(j!=*p) if(HT[j]->weight==HT1[1]&&k<2){//將第二小權(quán)值賦到*q中 *q=j; k++; } j++; // printf("%4d%4d%4d%4d\n",HT[i]->parent,HT[i]->left,HT[i]->right,HT[i]->weight); }}voidInithuffman(intwset[n],intk,HuffTreeHT[]){//結(jié)構(gòu)哈夫曼樹(shù) inti,m; ints1,s2; m=k*2-1; for(i=0;i<m;i++){//初始化HT數(shù)組 HT[i]=(HuffTree)malloc(sizeof(HTNode)); HT[i]->weight=(i<k?wset[i]:0); HT[i]->parent=-1; HT[i]->left=HT[i]->right=-1; } for(i=k;i<m;i++){//主循環(huán)，完成n-1次合并 select(HT,k,i,&s1,&s2);//在HT[1...i-1]中選擇parent為0且weight為最小兩個(gè)結(jié)點(diǎn)，其下標(biāo)分別為s1和s2 HT[i]->left=s1; HT[i]->right=s2; HT[i]->weight=HT[s1]->weight+HT[s2]->weight; HT[s1]->parent=HT[s2]->parent=i; }}voidHuffman(HuffTreeHT[2*n-1],intk,charstr[][20]){//依照哈夫曼樹(shù)得到各字符對(duì)應(yīng)哈夫曼編碼 inti,j,e,t1=0,t2=0; charc; STACKst; for(i=0;i<k;i++){ if(HT[i]->right==-1&&HT[i]->left==-1){//找一個(gè)葉子結(jié)點(diǎn) Initstack(&st); HT[i]->right=HT[i]->left==-2; j=i;//統(tǒng)計(jì)其下標(biāo) while(HT[j]->parent!=-1){ if(HT[HT[j]->parent]->right==j)//找到一個(gè)葉子結(jié)點(diǎn)，假如他是其parent結(jié)點(diǎn)右結(jié)點(diǎn)，就將此邊記為1 push(&st,'1'); else push(&st,'0');//在左邊記為0 j=HT[j]->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)制編碼 str[t1][t2]=e;//將二進(jìn)制編碼存放在str中 t2++; } putchar('\n'); str[t1][t2]='\0'; t2=0; t1++; } }}voidmain(){ FILE*fp1,*fp2;HuffTreeHT[2*n-1]; inti=0,sum1=0,sum2=0; floatcompress; charstr[n][20]; charelem,ch; intcount[n]={0};if((fp1=fopen("text1.txt","r"))==NULL){ printf("can'topenthefile!\n"); exit(0); } while(!feof(fp1)){//讀取文件中字符 elem=fgetc(fp1); i=elem; count[i]++;//統(tǒng)計(jì)字符頻率 } Inithuffman(count,n,HT); //for(i=0;i<253;i++) //printf("%4d%4d%4d%4d\n",HT[i]->parent,HT[i]->left,HT[i]->right,HT[i]->weight); Huffman(HT,2*n-1,str);//對(duì)文章進(jìn)行哈夫曼編碼if((f