课程设计四之Huffman编译码器

课设要求

(1)初始化 (Initialization)：从终端读入n个字符，建立哈夫曼树；
(2)编码 (Coding)：利用已建好的哈夫曼树，对字符进行编码，然后将正文编码结果存入文件codefile中；
(3)译码 (Decoding)：利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。

上代码

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;

typedef struct {
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedef char * * HuffmanCode;

//Select 2 smallest-weight nodes for merging
void Select(HuffmanTree &HT, int n, int& s1){
    int maxx = inf;
    for(int i = 0; i <= n; i++){
        if(HT[i].weight<=maxx && HT[i].parent == 0){
            maxx = HT[i].weight;
            s1 = i;
        }
    }
    HT[s1].parent = -1;
    return;
}

//construct Huffman Tree
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){
    if(n<1) return;
    int m = 2*n-1;
    HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
    HuffmanTree p = HT; int i;
    for(i = 0; i < n; i++, p++, w++){
        *p = {*w, 0, 0,0};                  //存入初始权重
    }
    for(;i< m; i++,p++) *p={0, 0, 0, 0};     //初始化
    for(i = n; i < m; i++){
        //1-i-1中找到最小两个合并
        int s1 = -1, s2 = -1;
        Select(HT, i-1,s1);
        Select(HT, i-1,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;
    }

    /*for(int k = 0; k < m; k++){
        printf("%d : parent: %d\n", k, HT[k].parent);
        printf("lcc: %d  rcc: %d\n", HT[k].lchild, HT[k].rchild);
    }*/

    //从叶到根求每个字符编码
    char * cd = new char[n];

    cd[n-1]='\0'; int start;
    for(i=0; i < n; i++){
        start = n-1; //最长也就n-1条边
        int f, c;
        for(c = i, f = HT[i].parent; f!= 0; c = f, f = HT[f].parent){
            if(HT[f].lchild == c) cd[--start] = '0';
            else cd[--start] = '1';
        }

        HC[i] = new char[n-start];
        strcpy(HC[i], &cd[start]);
        //printf("Code； %s", HC[i]);
    }
    delete cd;
}

void Menu(){
    int opt;
    printf("*****************************************************\n");
    printf("|              Huffman编/译码系统                   |\n");
    printf("|-----------------*系统执行步骤：*------------------|\n");
    printf("|          1. 读入文本字符，建HuffmanTree           |\n");
    printf("|          2.        编码存档                       |\n");
    printf("|          3.        译码读出                       |\n");
    printf("*****************************************************\n");
    printf("\n请输入字符文本：('*'为结束符)\n");

    string ss,s1;ss="";
    while(getline(cin, s1) && s1!="*"){ss+=s1;ss+='\n';}
    //getline(cin, ss);
    int len = ss.size();
    int t[len+1];memset(t, 0, sizeof(t));
    char w[len+1]; //w存字符，t计权重

    int cnt = 0;
    for(int i = 0; i<len; i++){
        bool flag = false;
        for(int j = 0; j < cnt; j++){
            if(ss[i]==w[j]){
                t[j]++;
                flag = true;
                break;
            }
        }
        if(!flag){
            w[cnt] = ss[i];
            t[cnt++] = 1;
        }
    }
    //printf("cnt   %d\n",cnt);

    printf("字符与权值信息：\n");
    for(int i = 0; i < cnt; i++){
        printf("%c : %d\n", w[i],t[i]);
    }

    HuffmanTree HT;
    HuffmanCode HC;
    HuffmanCoding(HT, HC, t, cnt);

    //cout<<ss<<endl;
    printf("\n请输入正文编码的文件地址：\n");
    string fn;
    cin>>fn;
    ofstream out(fn.c_str());
    //cout<<ss<<endl;
    for(int i = 0; i < len;i++){
        for(int j = 0; j < cnt; j++){
            if(ss[i]==w[j]){
                //cout<<"!  "<<ss[i]<<endl;
                out<<HC[j]<<endl;
                break;
            }
        }
    }

    out.close();
    printf("\n请输入译码文档的文件地址：\n");
    string s2;
    cin>>s2;
    ofstream out2(s2.c_str());

    ifstream in(fn.c_str());
    string buff;
    if(in.is_open()){
        while(in>>buff){
            for(int i = 0; i < cnt; i++){
                if(!strcmp(buff.c_str(), HC[i])){
                    out2<<w[i];
                    break;
                }
            }
        }
    }

    in.close();
    out2.close();
    return ;
}

int main(){
    Menu();

    return 0;

}

/*
..\课程资料\数据结构课程设计\课程设计四\课设4
*/

/*
hi,this is your first huffman-test.
Nobody grows old merely by living a number of years;
people grow old only by deserting their ideals.
*/