文档介绍：数据结构实验报告三——哈夫曼文件压缩实验题目:哈夫曼文件压缩实验目标:输入一个有10k单词的英文文档。输出压缩后的二进制文件,并计算压缩比。数据结构:栈和哈夫曼树。定义栈()typedefstruct{ char*elem; intstacksize; inttop;}STACK;定义哈夫曼树()typedefstruct{ intweight; intleft,right; intparent;}HTNode;需要的操作有:(Initstack)voidInitstack(STACK*s){ s->elem=(char*)malloc(sizeof(int)*1000); s->stacksize=1000; s->top=-1;}(push)voidpush(STACK*s,inte){ s->elem[++s->top]=e;}(pop)voidpop(STACK*s,int*e){ if(s->top!=-1) *e=s->elem[s->top--];}(Inithuffman)voidInithuffman(intwset[n],intk,HuffTreeHT[]){//构造哈夫曼树 inti,m; ints1,s2; m=k*2-1; for(i=0;i<m;i++){//初始化HT数组 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++){//主循环,完成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)(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); }}(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;//记录其下标 while(HT[j]->parent!=-1){ if(HT[HT[j]->p