数据结构——哈夫曼编码译码器_一个完整的系统应具有以下功能: 1)初始化(initialzation)。从数据文件datafile

题目5: 哈夫曼编/译码器 [问题描述]
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
[基本要求] 一个完整的系统应具有以下功能：
1、I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
2、 E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），
对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
3、D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 1、
P：打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。 2、 T：打印哈夫曼树（Tree
Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入
表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

代码：

//要编码的正文存储在tobetran.txt文件中，得到的结果存入codefile文件中
//译码的结果存在于textfile.txt文件中
//二进制编码存在于codeprin中
//哈夫曼树存在于treeprin中
//-abcdefghijklmnopqrstuvwxyz
//186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1
//this problem is my favourite

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef struct
{
    int weight; //节点权值
    int lchild,rchild,parent; //左右孩子和双亲的下标
} HTNode,*HuffmanTree;

void menu()
{
    cout<<"================================================="<<endl;
    cout<<"|        ******哈夫曼树编码与译码******         |"<<endl;
    cout<<"|                1.创建哈夫曼树                 |"<<endl;
    cout<<"|                2.生成二进制码                 |"<<endl;
    cout<<"|                3.哈夫曼编码                   |"<<endl;
    cout<<"|                4.哈夫曼译码                   |"<<endl;
    cout<<"|                5.显示代码文件                 |"<<endl;
    cout<<"|                6.打印哈夫曼树                 |"<<endl;
    cout<<"|                7.退出                         |"<<endl;
    cout<<"================================================="<<endl;
}

void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
    int i=1;
    while(HT[i].parent!=0&&i<=n)
        i++;
    if(i==n+1)
        return ;
    s1=i;
    i++;
    while(HT[i].parent!=0&&i<=n)
        i++;
    if(i==n+1)
        return ;
    s2=i;
    i++;
    if(HT[s1].weight>HT[s2].weight)
        swap(s1,s2);
    for(; i<=n; i++)
    {
        if(HT[i].parent==0)
        {
            if(HT[i].weight<HT[s1].weight)
                s2=s1,s1=i;
            else if(HT[i].weight<HT[s2].weight)
                s2=i;
        }
    }
    return ;
}

void CreatHuffmanTree(HuffmanTree &HT,int n)
{
    if(n<=1)
        return ;
    int m=2*n-1;
    HT=(HuffmanTree)malloc(sizeof(HTNode)*(m+1));
    for(int i=1; i<=m; i++)
    {
        HT[i].lchild=0;
        HT[i].parent=0;
        HT[i].rchild=0;
        HT[i].weight=0;
    }
    for(int i=1; i<=n; i++)
        cin>>HT[i].weight;
    int s1,s2;
    for(int i=n+1; i<=m; i++)
    {
        Select(HT,i-1,s1,s2);
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    return ;

}

void CreatHuffmanCode(HuffmanTree &HT,char ** &HC,int n)
{
    char *col;
    HC=(char **)malloc(sizeof(char *)*(n+1));  //分配n个字符编码的头指针向量
    col=(char *)malloc(sizeof(char)*n);   //分配求编码的工作空间
    col[n-1]='\0';
    for(int i=1; i<=n; i++)
    {
        int str=n-1;
        int p=i,f=i;
        while(HT[f].parent!=0)      //从叶子到根逆向求编码
        {
            f=HT[f].parent;
            if(HT[f].lchild==p)
                col[--str]='0';
            else if(HT[f].rchild==p)
                col[--str]='1';
            p=f;
        }
        HC[i]=(char *)malloc(sizeof(char)*(n-str));    //为第i个字符编码分配空间
        strcpy(HC[i],&col[str]);   //把编码串复制到HC中
    }
    free(col);
    return ;
}

void TransCode(HuffmanTree HT,char b[],char a[],char c[],int n)
{
    //b数组是要翻译的二进制编码
    //a数组是叶子对应的字符
    //c数组存储翻译得到的内容
    FILE *fw;
    int q=2*n-1;   //初始化为根结点的下标
    int k=0;
    int len=strlen(b);
    if((fw=fopen("textfile.txt","w"))==NULL)
        cout<<"Open file error!"<<endl;
    for(int i=0; i<len; i++)
    {
        if(b[i]=='0')
            q=HT[q].lchild;
        else if(b[i]=='1')
            q=HT[q].rchild;
        if(HT[q].lchild==0&&HT[q].rchild==0)   //叶子节点，此时可以译出字符
        {
            c[k++]=a[q];
            fputc(a[q],fw);
            q=2*n-1;
        }
        c[k]='\0';
    }
    return ;
}

void Coding(HuffmanTree &HT,char ** &HC,int n,char a[])
{
    FILE *fp,*fw;
    char c;
    int k;
   /* char c,*cd;
    int k,j,jj;
    HC=(char **)malloc((2*n-1)*sizeof(char *));
    cd=(char *)malloc((2*n-1)*sizeof(char));
    cd[n-1]='\0';
    for(int i=1;i<=n;i++)
    {
        int str=n-1;
        for(j=i,jj=HT[i].parent;j!=0;j=jj,jj=HT[jj].parent)
            if(HT[jj].lchild==j)
                cd[--str]='0';
            else
                cd[--str]='1';
        HC[i]=(char *)malloc((n-str)*sizeof(char));
        strcpy(HC[i],&cd[str]);
    }
    free(cd);
    */
    if((fp=fopen("tobetran.txt","r"))==NULL)
        cout<<"Open file error!"<<endl;
    if((fw=fopen("codefile.txt","w"))==NULL)
        cout<<"Open file error!"<<endl;
    fscanf(fp,"%c",&c);
    while(!feof(fp))
    {
        for(int i=1; i<=n; i++)
            if(a[i]==c)
            {
                k=i;
                break;
            }
        for(int i=0; HC[k][i]!='\0'; i++)
            fputc(HC[k][i],fw);
        fscanf(fp,"%c",&c);
    }
    fclose(fp);
    fclose(fw);
    return ;
}

void printf_code()
{
    FILE *fp,*fw;
    char temp;
    if((fp=fopen("codefile.txt","r"))==NULL)
        cout<<"Open file error!"<<endl;
    if((fw=fopen("codeprin.txt","w"))==NULL)
        cout<<"Open file error!"<<endl;
    cout<<"文件codefile.txt的内容显示如下："<<endl;
    fscanf(fp,"%c",&temp);
    for(int i=1;!feof(fp);i++)
    {
        printf("%c",temp);
        if(i%50==0)
            cout<<endl;
        fputc(temp,fw);
        fscanf(fp,"%c",&temp);
    }
    cout<<endl;
    cout<<"该编码文件已存入文件codeprin.txt中！"<<endl;
    fclose(fp);
    fclose(fw);
}

void co_tree(unsigned char T[100][100],int s,int *m,int j,HuffmanTree HT)
{
    int k,l;
    l=++(*m);
    for(k=0;k<s;k++)
        T[l][k]=' ';
    T[l][k]=HT[j].weight;
  //    itoa(HT[j].weight,T[l][k],10);
  /*  int weishu=log10(HT[j].weight);
    int base=10;
     while(weishu)
     {
         base*=base;
         weishu--;
     }
    while(HT[j].weight)
    {
       T[l][k]=HT[j].weight/base;
       HT[j].weight/=10;
       base/=10;
       k++;
    }
    */
    if(HT[j].lchild)
        co_tree(T,s+1,m,HT[j].lchild,HT);
    if(HT[j].rchild)
        co_tree(T,s+1,m,HT[j].rchild,HT);
    T[l][++k]='\0';
    return ;
}

void printf_tree(int num,HuffmanTree HT)
{
    unsigned char T[100][100];
    FILE *fp;
    int m=0;
    co_tree(T,0,&m,2*num-1,HT);
    if((fp=fopen("treeprin.txt","w"))==NULL)
        cout<<"Open file error!"<<endl;
    for(int i=1;i<=2*num-1;i++)
    {
        for(int j=0;T[i][j]!='\0';j++)
        {
            if(T[i][j]==' ')
               printf(" "),fputc(T[i][j],fp);
            else
                printf("%u",T[i][j]),fprintf(fp,"%u",T[i][j]);
        }
         cout<<endl;
         fputc(10,fp);
    }
    cout<<"该哈夫曼树已保存到treeprin.txt文件中！"<<endl;
    fclose(fp);
    return ;
}

int main()
{
    char a[300]; //存储要编码的所有字符
    char b[300];  //存储要翻译的二进制编码
    char c[300]; //存储翻译出来的结果
    HuffmanTree HT=NULL;
    char ** HC;
    while(1)
    {
        char s1[]= {"结点"};
        char s2[]= {"字符"};
        char s3[]= {"权值"};
        char s4[]= {"双亲"};
        char s5[]= {"左孩子"};
        char s6[]= {"右孩子"};
        int flag=1;
        menu();
        int choose;
        int num;
        char temp;
        int cc=0;
        cout<<"请选择你要进行的操作(1-4):";
        cin>>choose;
        switch(choose)
        {
        case 1:
            cout<<"请输入字符的个数：";
            cin>>num;
            cout<<"请依次输入"<<num<<"个字符:(空格用-来代替)";
            for(int i=1; i<=num; i++)
                cin>>a[i];
            cout<<"请依次输入"<<num<<"个字符的权值:";
            CreatHuffmanTree(HT,num);
            cout<<"创建哈夫曼树成功，下面输出该哈夫曼树的参数。"<<endl;
            cout<<"结点i"<<"\t字符"<<"\t权值"<<"\t双亲"<<"\t左孩子"<<"\t右孩子"<<endl;
            for(int i=1; i<=num*2-1; i++)
                cout<<i<<"\t"<<a[i]<<"\t"<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<endl;
            FILE *fp;
            if((fp=fopen("hfmtree.txt","w"))==NULL)
                cout<<"Open file hfmtree error!"<<endl;
            // char ceshi[10];
            // scanf("%s",ceshi);
            // fwrite(&ceshi,sizeof(ceshi),1,fp);
            fwrite(&s1,sizeof(s1),1,fp);
            fwrite(&s2,sizeof(s2),1,fp);
            fwrite(&s3,sizeof(s3),1,fp);
            fwrite(&s4,sizeof(s4),1,fp);
            fwrite(&s5,sizeof(s5),1,fp);
            fwrite(&s6,sizeof(s6),1,fp);
            fputc(10,fp);
            for(int i=1; i<=2*num-1; i++)
            {
                fprintf(fp,"%-3d  ",i);
                fwrite(&a[i],1,1,fp);
                fprintf(fp,"    %-3d    ",HT[i].weight);
                fprintf(fp,"%-3d    ",HT[i].parent);
                fprintf(fp,"%-3d    ",HT[i].lchild);
                fprintf(fp,"%-3d    ",HT[i].rchild);
                fputc(10,fp);
            }
            fclose(fp);
            cout<<"哈夫曼树已建成并存入文件中！"<<endl;
            break;
        case 2:
            CreatHuffmanCode(HT,HC,num);
            cout<<"哈夫曼编码表已生成，下面输出哈夫曼编码表！"<<endl;
            cout<<"结点i\t"<<"字符\t"<<"权值\t"<<"编码\t"<<endl;
            for(int i=1; i<=num; i++)
                cout<<i<<"\t"<<a[i]<<"\t"<<HT[i].weight<<"\t"<<HC[i]<<endl;
            break;
        case 3:
            cout<<"从文件tobetran.txt中读取正文进行编码"<<endl;
            Coding(HT,HC,num,a);
            cout<<"已编码成功，对应二进制编码已存入文件codefile.txt中!"<<endl;
            break;
        case 4:
            cout<<"从codefile.txt文件中读取一串二进制进行翻译:"<<endl;
            if((fp=fopen("codefile.txt","rb"))==NULL)
                cout<<"Open file error!"<<endl;
            while(1)
            {
                temp = fgetc(fp); //读一个字节。
                if(temp == EOF) break; //到文件尾，退出循环。
                b[cc++] =temp ;//赋值到字符数组中。
            }
            b[cc]='\0';
            cout<<"该二进制是：";
            printf("%s\n",b);
            fclose(fp);
            TransCode(HT,b,a,c,num);
            cout<<"翻译成功，翻译结果为:";
            printf("%s\n",c);
            cout<<"该翻译结果已存入文件textfile.txt中！"<<endl;
            break;
        case 5:
            printf_code();
            break;
        case 6:
            cout<<"下面打印哈夫曼树："<<endl;
            printf_tree(num,HT);
            break;
        case 7:
            flag=0;
            break;
        default:
            cout<<"输入不合法,请重新输入！"<<endl;
            continue;
        }
        if(flag==0)
            break;
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387