吉吉国王0920
2018-12-26 18:55
采纳率: 50%
浏览 815

数据结构(C++版)哈弗曼 编码

问题描述:利用哈夫曼编码进行信息通讯可以大大提高信道的利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码;在接受端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码编码/译码系统。
基本要求:根据某字符文件统计字符出现频度,构造Huffman 树,编制Huffman编码,并将给定字符文件编码,生成编码文件;再将给定编码文件解码,生成字符文件(要求按二进制位表示编码)。
提高要求:改进Huffman编码,产生两种以上的编码方案,对同一组测试数据,用不同的编码方案编码,并从文件长度、算法复杂度等方面进行比较分析。
测试数据:找一个英文文档文件或中文文档文件。
用C++来编写,能实现基本要求和提高要求的。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • 吉吉国王0920 2019-01-06 19:05
    已采纳

    #include
    using namespace std;
    HuffmanTree::HuffmanTree() //初始化空树
    {
    Node=NULL; //将树结点初始化为空
    Info=NULL; //将字符数组初始化为空
    LeafNum=0; //将叶子数初始化为0
    }
    HuffmanTree::~HuffmanTree() //析构函数
    {
    delete[] Node; //释放结点空间
    delete[] Info; //释放字符存储空间
    }
    /////////////////////////////////////////
    //初始化函数
    void HuffmanTree::Initialization(int WeightNum)

    {
    int i,j,pos1,pos2,max1,max2;
    Node=new HuffmanNode[2*WeightNum-1]; //为哈夫曼树所需的结点申请空间

    Info=new char[2*WeightNum-1];
    for(i=0;i {
    cout cin>>Info[i];
    cout<<"请输入该字符的权值或频度";
    cin>>Node[i].weight; //输入权值
    Node[i].parent=-1; //为根结点
    Node[i].lchild=-1; //无左孩子
    Node[i].rchild=-1; //无右孩子
    }
    //这里构造出weightnum个带权结点

    for(i=WeightNum;i {
    pos1=-1;
    pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号
    max1=32767; //32767为整型数的最大值
    max2=32767;
    for(j=0;j if(Node[j].parent==-1)
    if(Node[j].weight {
    max2=max1; //原最小值变为次小值
    max1=Node[j].weight; //存放最小值
    pos2=pos1; //修改次小值所在单元编号
    pos1=j; //修改最小值所在单元编号
    }
    else
    if(Node[j].weight {
    max2=Node[j].weight; //存放次小值
    pos2=j; //修改次小值所在的单元编号
    }
    Node[pos1].parent=i; //修改父亲位置
    Node[pos2].parent=i;
    Node[i].lchild=pos1; //修改儿子位置
    Node[i].rchild=pos2;
    Node[i].parent=-1; //表示新结点应该是根结点
    Node[i].weight=Node[pos1].weight+Node[pos2].weight;
    }
    LeafNum=WeightNum;
    char ch;
    cout cin>>ch;
    if(ch=='y'||ch=='Y')
    {
    ofstream fop; //以二进制方式打开hfmTree.dat文件,并当重新运行时覆盖原文件
    fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);
    if(fop.fail()) //文件打开失败
    cout<<"文件打开失败!\n";
    fop.write((char*)&WeightNum,sizeof(WeightNum)); //写入WeightNum
    for(i=0;i {
    fop.write((char*)&Info[i],sizeof(Info[i]));
    flush(cout);
    }
    for(i=0;i {
    fop.write((char*)&Node[i],sizeof(Node[i]));
    flush(cout);
    }
    fop.close(); //关闭文件
    }
    cout }
    //编码函数
    void HuffmanTree::Encoder()
    {
    if(Node==NULL)
    {
    ifstream fip;
    fip.open("hfmTree.dat",ios::binary|ios::in); //以二进制方式打开hfmTree.dat文件
    if(fip.fail()) //文件打开失败
    {
    cout return; //结束本函数
    }
    fip.read((char*)&LeafNum,sizeof(LeafNum)); //读取叶子数
    Info=new char[LeafNum];
    Node=new HuffmanNode[2*LeafNum-1];
    for(int i=0;i fip.read((char*)&Info[i],sizeof(Info[i]));
    for(int i=0;i fip.read((char*)&Node[i],sizeof(Node[i]));
    }
    char *Tree; //用于存储需编码内容
    int i=0,num;
    char Choose;
    cout cin>>Choose;
    if(Choose=='1') //读取文件ToBeTran.txt
    {
    ifstream fip1("ToBeTran.txt");
    if(fip1.fail()) //文件不存在
    {
    cout<<"文件打开失败!\n";
    return; //结束本函数
    }
    char ch;
    int k=0;
    while(fip1.get(ch))

    {
    k++;

    }
    fip1.close();

    Tree=new char[k+1];
    ifstream fip2("ToBeTran.txt");
    k=0;
    while(fip2.get(ch))
    {
    Tree[k]=ch; //读取文件内容,并存到Tree中
    k++;
    }
    fip2.close();
    Tree[k]='\0'; //结束标志
    cout<<"需编码内容为:";
    cout<<Tree<<endl;
    } //if(Choose=='2')
    else

    {
    string tree;

    cin.ignore();
    cout<<"请输入需要编码的内容(可输入任意长,结束时请按2下回车):\n";
    getline(cin,tree,'\n'); //输入任意长字符串,

    while(tree[i]!='\0')
    i++;
    num=i; //计算tree长度
    i=0;
    Tree=new char[num+1];
    while(tree[i]!='\0') //将tree中的字符转存到Tree中
    {
    Tree[i]=tree[i];
    i++;
    }
    Tree[i]='\0'; //结束标志符
    }
    ofstream fop("CodeFile.dat",ios::trunc);

    i=0;
    int k=0;
    char *code;
    code=new char[LeafNum]; //为所产生编码分配容量为LeafNum的存储空间

    while(Tree[k]!='\0') //对每一个字符编码
    {
    int j,start=0;
    for(i=0;i<LeafNum;i++)
    if(Info[i]==Tree[k])

    break;
    j=i;
    while(Node[j].parent!=-1) //结点j非树根
    {
    j=Node[j].parent; //求结点j的双亲结点
    if(Node[j].lchild==i) //是左子树,则生成代码0
    code[start++]='0';
    else

    code[start++]='1'; //是右子树,则生成代码1
    i=j;
    }
    code[start]='\0'; //置串结束符

    for(i=0;i<start/2;i++) //对二进制序列进行逆置
    {
    j=code[i];
    code[i]=code[start-i-1];
    code[start-i-1]=j;
    }
    i=0;
    while(code[i]!='\0') //存储代码
    {
    fop<<code[i];
    i++;
    }
    k++;
    }
    fop.close();
    cout<<"编码完成!且存到文件CodeFile.dat中!\n\n";
    }

    /////////////////////////////////////////////////////////////////////////////
    //解码函数

    void HuffmanTree::Decoder()
    {
    int i=0,k=0;
    int j=LeafNum*2-1-1;

    char* BitStr;

    ifstream fip1("CodeFile.dat"); //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码
    if(fip1.fail())

    {
    cout<< "请先编码!\n";
    return;
    }
    cout<<"经译码,原内容为:";
    char ch;
    while(fip1.get(ch))

    {
    k++;

    }
    fip1.close();

    BitStr=new char[k+1];
    ifstream fip2("CodeFile.dat");
    k=0;
    while(fip2.get(ch))
    {
    BitStr[k]=ch; //读取文件内容
    k++;
    }
    fip2.close();

    BitStr[k]='\0'; //结束标志符
    if(Node==NULL) //还未建哈夫曼树
    {
    cout<<"请先编码!\n";
    return;
    }
    ofstream fop("TextFile.dat"); //将字符形式的编码文件写入文件CodePrin中
    while(BitStr[i]!='\0')
    {
    if(BitStr[i]=='0')
    j=Node[j].lchild; //往左走
    else
    j=Node[j].rchild; //往右走
    if(Node[j].rchild==-1) //到达叶子结点
    {
    cout<<Info[j]; //输出叶子结点对应的字符
    j=LeafNum*2-1-1;

    fop<<Info[j]; //存入文件
    }

    i++;
    }
    fop.close();
    cout<<"\n译码成功且已存到文件TextFile.dat中!\n\n";
    }

    //////////////////////////////////////////////////////////////////////////////////////////
    //输出编码函数

    void HuffmanTree::Print()
    {
    char ch;
    int i=1;
    ifstream fip("CodeFile.dat");

    ofstream fop("CodePrin.dat");

    if(fip.fail())
    {
    cout<<"没有文件,请先编码!\n";
    return;
    }
    while(fip.get(ch))
    {
    cout<<ch; //读取文件内容
    fop<<ch; //存到文件中
    if(i==50)

    {
    cout<<endl;
    i=0;
    }
    i++;
    }
    cout<<endl;
    fip.close(); //关闭CodeFile.dat文件
    fop.close(); //关闭CodePrin.dat文件

    }
    //输出哈夫曼树

    void HuffmanTree::TreePrinting()
    {
    if(Node==NULL)

    {
    cout<<"请先建立哈夫曼树!\n";
    return;
    }
    ofstream fop("TreePrint.dat");
    cout<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n";
    fop<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n";
    int i;
    for(i=(2*LeafNum-2);i>LeafNum-1;i--)

    {
    cout< fop }
    for(;i>=0;i--)
    {
    cout<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
    fop<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
    }
    }

    点赞 评论
  • devmiao 2018-12-26 15:57
    点赞 评论

相关推荐 更多相似问题