哈夫曼树对文件进行译码-白红宇

哈夫曼树对文件进行译码

阅读量：5734 次

发布时间：2019-06-18

本文共 4743 字，大约阅读时间需要 15 分钟。

1 #include "stdio.h"  2 const int maxlen = 1000;  3 #define infinity 65535  4   5 struct encode{  6     char  Data[maxlen];//存储编码(字符类型)  7     int count;//编码的位数  8 };  9 struct bnode 10 { 11     int data;//数据 12     char ch;//字符 13     bnode *lchild,*rchild;//左孩子，右孩子结点 14     encode code;//存储编码信息 15     bool flags;//使用标志 16 }; 17  18 struct FileChar{ 19     char ch;//字符 20     int count;//字符在文章出现的次数 21 }; 22  23 bnode *tree[maxlen]; 24 FileChar CharNum[maxlen];//存放字符以及字符出现的次数 25 int num_char= 0;//不同字符的总数 26  27 /* 28 * int A[]:存放字符的频度 29 *int N:字符的个 30 *bnode *tree[maxlen]//树 31 */ 32 void initialization(int N,bnode *tree[maxlen])//初始化 33 { 34     int i; 35     for(i=0;i
     
      data = CharNum[i].count;//结点的值 39         tree[i]->ch = CharNum[i].ch;//结点的字符 40         tree[i]->flags = true;//标识未使用 41         tree[i]->code.count = 0;//编码位数为0 42         tree[i]->lchild = NULL;//左子树为空 43         tree[i]->rchild = NULL;//右子树为空 44     } 45 } 46  47 void merge(int &n,bnode *tree[maxlen])//寻找当前根结点值最小的两个子树将其合并 48 { 49     int i,num1,num2,min1,min2; 50     min1 = infinity; 51     min2 = infinity; 52     for(i=0;i
      
       data
       
        flags) 55         { 56             min1 = tree[i]->data; 57             num1 = i; 58         } 59     } 60     tree[num1]->flags = false;//设置标识已使用过 61  62     for(i=0;i
        
         data
         
          flags) 65         { 66             min2 = tree[i]->data; 67             num2 = i; 68         } 69     } 70     tree[num2]->flags = false;//设置标识已使用过 71     //将两个子树合并 72     tree[n] = new bnode; 73     tree[n]->data = tree[num1]->data + tree[num2]->data; 74     tree[n]->flags = true; 75     tree[n]->code.count = 0;//编码位数为0 76     tree[n]->lchild = tree[num1]; 77     tree[n]->rchild = tree[num2]; 78     n++; 79 } 80  81 void Huffmantree(int &n,bnode *tree[maxlen])//构造哈夫曼树 82 { 83     int i,num; 84     bool flags = true;//标识 85     while(flags) 86     { 87         num = 0;//计数 88         for(i=0;i
          
           flags) 91 { 92 num++; 93 } 94 } 95 if(num>=2) 96 { 97 merge(n,tree);//合并当前根结点值最小的两棵子树 98 }else{ 99 flags = false;//哈夫曼树构造完成标识100 }101 }102 }103 104 void HFTree(bnode *Tree)//中序输出哈夫曼树105 {106 if(Tree)107 {108 HFTree(Tree->lchild);109 printf(" %d",Tree->data);110 HFTree(Tree->rchild);111 }112 }113 114 void Encode(bnode *Tree)//每个结点进行编码115 {116 int i,count;117 if(Tree)118 {119 if(Tree->lchild)//左子树根结点添加0120 {121 count = Tree->code.count;122 for(i=0;i
           
            lchild->code.Data[i] = Tree->code.Data[i];125 Tree->lchild->code.count++;126 }127 128 Tree->lchild->code.Data[count] = '0';//再添加0129 Tree->lchild->code.count++;130 }131 if(Tree->rchild)//右子树根结点添加1132 {133 count = Tree->code.count;134 for(i=0;i
            
             rchild->code.Data[i] = Tree->code.Data[i];137 Tree->rchild->code.count++;138 }139 Tree->rchild->code.Data[count] = '1';//再添加1140 Tree->rchild->code.count++;141 }142 Encode(Tree->lchild);//左子树继续143 Encode(Tree->rchild);//右子树继续144 }145 146 }147 148 //进行统计各个字符出现的次数149 void analyse(FILE *fp)150 { 151 int i;152 bool flags;//标志，是否为新的字符153 char ch;//字符154 155 while((ch = fgetc(fp))!=EOF)//从文件内读取字符156 { 157 flags = true;158 for(i=0;i
             
              ch)//找到字符194 {195 fprintf(fp,"%c\t",CharNum[i].ch);//字符存入文件196 printf("%c\t",CharNum[i].ch);197 for(k=0;k
              
               code.count;k++)198 {199 fprintf(fp,"%c",tree[j]->code.Data[k]);//字符编码存入文件200 printf("%c",tree[j]->code.Data[k]);201 }202 fprintf(fp,"%c",'\n');//换行符添加到文件中203 printf("\n");204 }205 }206 }207 fclose(fp);208 }209 }210 211 void translate(char file[])//译码212 {213 FILE *fp,*fout;214 char ch;215 int i,k;216 int Line =0;//标识217 if((fp=fopen(file,"r+"))==NULL)218 {219 printf("文件操作出错!\n"); 220 221 }else{222 if((fout=fopen("D:/decode.txt","w+"))==NULL)223 {224 printf("文件不存在\n");225 226 }else{227 printf("[译码结果显示]\n");228 while((ch = fgetc(fp))!=EOF)//从文件内读取字符229 { 230 Line++;//字符数+1231 for(i=0;i
               
                ch)//找到tree中对应的字符234 {235 for(k=0;k
                
                 code.count;k++)236 {237 fprintf(fout,"%c",tree[i]->code.Data[k]);//字符编码存入文件238 printf("%c",tree[i]->code.Data[k]);239 }240 fprintf(fout,"%c",' ');//换行符添加到文件中241 printf(" ");242 }243 }244 if(Line%10==0)245 {246 fprintf(fout,"%c",'\n');//每个10个换行247 printf("\n");248 }249 }250 }251 printf("\n");252 fclose(fout);253 }254 }255 256 int main()257 {258 int n;259 FILE *fp;260 printf("输入文件路径:");261 char file[30];262 scanf("%s",&file);//输入文件路径263 if((fp=fopen(file,"r+"))==NULL)264 {265 printf("文件操作出错!\n"); 266 267 }else{268 analyse(fp); 269 }270 271 n = num_char;272 initialization(n,tree);//左右子树初始化273 Huffmantree(n,tree);//构造哈夫曼树274 printf("[哈夫曼树中序输出\:");275 HFTree(tree[n-1]);276 printf("\n");277 278 Encode(tree[n-1]);279 Save_Code();280 printf("[编码已经保存!]\n");281 translate(file);282 printf("[译码已经保存!]\n");283 return 0;284 }