哈夫曼文件壓縮實驗報告

數(shù)據(jù)結構試驗匯報三——哈夫曼文件壓縮試驗題目：哈夫曼文件壓縮試驗目標：輸入一個有10k單詞英文文檔。輸出壓縮后二進制文件，并計算壓縮比。數(shù)據(jù)結構：棧和哈夫曼樹。定義棧（）typedefstruct{ char*elem; intstacksize; inttop;}STACK;定義哈夫曼樹（）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.結構哈夫曼樹（Inithuffman）voidInithuffman(intwset[n],intk,HuffTreeHT[]){//結構哈夫曼樹 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為最小兩個結點，其下標分別為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; }}其中用到另一個基本操作：找到哈夫曼樹中最小和次小結點（select）5.找到哈夫曼樹中最小和次小結點（select）voidselect(HuffTreeHT[255],inta,inti,int*p,int*q){ intj=0,k=0,*HT1,temp; HT1=(int*)malloc(sizeof(int)*(i-1));//存放權值 for(j=0;j<i;j++){ if(HT[j]->parent==-1){ HT1[k]=HT[j]->weight;//把沒有parent結點權值放在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){//找到權值最小和第二小結點 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){//將最小權值賦到*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){//將第二小權值賦到*q中 *q=j; k++; } j++; // printf("%4d%4d%4d%4d\n",HT[i]->parent,HT[i]->left,HT[i]->right,HT[i]->weight); }}6.依照哈夫曼樹得到各字符對應哈夫曼編碼（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){//找一個葉子結點 Initstack(&st); HT[i]->right=HT[i]->left==-2; j=i;//統(tǒng)計其下標 while(HT[j]->parent!=-1){ if(HT[HT[j]->parent]->right==j)//找到一個葉子結點，假如他是其parent結點右結點，就將此邊記為1 push(&st,'1'); else push(&st,'0');//在左邊記為0 j=HT[j]->parent;//循環(huán)操作直到抵達根結點 } c=i; printf("\t%c",c);//打印此字符 for(;st.top!=-1;){ pop(&st,&e); printf("%c",e);//打印其二進制編碼 str[t1][t2]=e;//將二進制編碼存放在str中 t2++; } putchar('\n'); str[t1][t2]='\0'; t2=0; t1++; } }}算法設計：1.從文件中逐一讀取字符，統(tǒng)計其出現(xiàn)次數(shù)以及文件總字符數(shù)，由此確定其頻率高低。2.依照字符頻率創(chuàng)建哈夫曼樹，然后求出哈夫曼編碼。3.將哈夫曼編碼輸出到另一個文件中，并統(tǒng)計字數(shù)，求出壓縮率。源程序#include<stdio.h>#include<malloc.h>#include<process.h>#definen127typedefstruct{ intweight; intleft,right; intparent;}HTNode;//哈夫曼數(shù)組結構類型typedefHTNode*HuffTree;typedefstruct{ char*elem; intstacksize; inttop;}STACK;//棧結構類型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){//找到哈夫曼樹中權值最小和次小結點并返回指針 intj=0,k=0,*HT1,temp; HT1=(int*)malloc(sizeof(int)*(i-1));//存放權值 for(j=0;j<i;j++){ if(HT[j]->parent==-1){ HT1[k]=HT[j]->weight;//把沒有parent結點權值放在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){//找到權值最小和第二小結點 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){//將最小權值賦到*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){//將第二小權值賦到*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[]){//結構哈夫曼樹 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為最小兩個結點，其下標分別為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]){//依照哈夫曼樹得到各字符對應哈夫曼編碼 inti,j,e,t1=0,t2=0; charc; STACKst; for(i=0;i<k;i++){ if(HT[i]->right==-1&&HT[i]->left==-1){//找一個葉子結點 Initstack(&st); HT[i]->right=HT[i]->left==-2; j=i;//統(tǒng)計其下標 while(HT[j]->parent!=-1){ if(HT[HT[j]->parent]->right==j)//找到一個葉子結點，假如他是其parent結點右結點，就將此邊記為1 push(&st,'1'); else push(&st,'0');//在左邊記為0 j=HT[j]->parent;//循環(huán)操作直到抵達根結點 } c=i; printf("\t%c",c);//打印此字符 for(;st.top!=-1;){ pop(&st,&e); printf("%c",e);//打印其二進制編碼 str[t1][t2]=e;//將二進制編碼存放在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)計字符頻率 } 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);//對文章進行哈夫曼編碼if((f