精华内容
下载资源
问答
  • 实验名 实 验 方 实 验 实验六 哈夫曼编码和译码的算法设计与实现 称 案 成绩 实验日 实 验 信息系统设计与仿 实 验 操 2012-04-22 期 室 真室 I 作 实验台 班 级 姓 信工 11-1BF 李煌 实 验 结 34 号 号 名 峰 果 ...
  • 用C语言实现算术编码译码,是自己编的一个小程序~~~~~~~~~望大家支持啊
  • 设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼...(4)显示指定的编码文件和文本文件; (5)把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算进行真正的数据压缩,并求压缩比。(此选项选作)
  • 哈夫曼编码的c语言实现,代码中有注释。有编码和译码功能,能输出每个字符的Huffman码。可以输入一段Huffman码反应成文本,也可以输入一段文本翻译成Huffman码。计算了信源熵,编码效率,平均编码长度。
  • 压缩包中包含实验报告,运行视频,...其中功能包括输入字母及频率,然后生成相应的哈夫曼编码,然后编码txt文件中的文本,输出,并且会把输出结果存入文件。重新打开控制台,可以通过读取文件重新建立哈夫曼树,就很强
  • 通过读取文件data.txt编译,输出有字符频度表,哈夫曼树,编码表,把编码保存到文件中,再读取文件进行译码。此压缩包内涵使用方法,代码。运行:VS2010 语言:C
  • 1、输入一段100—200字的英文短文,存入一文件a中。 2、写函数统计短文出现的字母个数n及每个字母的出现次数 ...5、用Haffman树对b中码文进行译码,结果存入文件c中,比较a,c是否一致,以检验编码译码的正确性。
  • 文本串的哈夫曼编码和译码 哈夫曼编码是最基本的字符压缩编码。对文本进行哈夫曼编码后再进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据...

    文本串的哈夫曼编码和译码

    哈夫曼编码是最基本的字符压缩编码。对文本进行哈夫曼编码后再进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。 请设计一个程序,输入一行字符文本串(最大长度为10000个字符),构造其哈夫曼编码。根据需要(传输前)选择对字符文本进行编码(将字符文本转换为哈夫曼0-1编码),或对已编码的数据(接收后)进行译码(将0-1编码还原为字符文本)。
    具体:
    (1)初试化(I):读入一行文本,根据字符分布建立哈夫曼树,构造字符的哈夫曼编码(用于编码和译码),输出“Huffman code established!“”;
    (2)编码(C):使用得到的哈夫曼编码对原始字符文本进行编码,输出;
    (3)译码(D)::对编码后的0-1文本进行译码(还原为原来的字符文本),输出;
    (4)退出(X):结束;注:如果编码或译码时,哈夫曼编码还没建立,应提示"Huffman code does not exist!”
    例如:
    样例输入:
    I
    Welcome to the school of computer science and technology.
    C
    D
    11011001100100001000101101110111001001011100001101110111010000001110010000101011001101111010001000101111100011100111000111110101011101000011101101101000000111011111000100111101101110001100000110100100001010011111011111101010
    X
    样例输出:
    Huffman code established!
    11011001100100001000101101110111001001011100001101110111010000001110010000101011001101111010001000101111100011100111000111110101011101000011101101101000000111011111000100111101101110001100000110100100001010011111011111101010
    Welcome to the school of computer science and technology.

    要注意:
    string不能malloc,要用new! string不能malloc,要用new! string不能malloc,要用new!
    就是因为这个,codeblocks上边可以运行通过,OJ上不行,两天的段错误啊……
    建立哈夫曼树的方法:
    1.找到两个权值最小的点(若权值一样,则选择前面的),然后将这两个点连接到一个“根”上(根的权值是两个点权值之和),将“根”放到原序列最后,将选择的两个点从原序列删除(原序列指删除重复字符后的给定序列);
    2.重复上述操作,直至原序列剩余一个点,将其标记为根节点。

    包括空格的字符串这样输入:

    getchar();
    char c;
    scanf("%c",&c);
    int i=0;
    while(c!='\n')
    {
        str[i]=c;
        i++;
        scanf("%c",&c);
        }
    len=i;
    

    完整代码如下:

    #pragma GCC optimize(3,"Ofast","inline")
    #pragma G++ optimize(3)
    #include <bits/stdc++.h>
    #include <iostream>
    #include <cstdio>
    #include <fstream>
    #include <algorithm>
    #include <cmath>
    #include <deque>
    #include <vector>
    #include <queue>
    #include <string>
    #include <cstring>
    #include <map>
    #include <stack>
    #include <set>
    #include <sstream>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<ll,ll> pll;
    typedef pair<int,int> pii;
    typedef queue<int> q_i;
    typedef queue<string> q_s;
    typedef queue<double> q_d;
    typedef queue<ll> q_ll;
    typedef queue<char> q_c;
    typedef priority_queue<int> pq_i;
    typedef priority_queue<string> pq_s;
    typedef priority_queue<double> pq_d;
    typedef priority_queue<ll> pq_ll;
    typedef stack<int> s_i;
    typedef stack<string> s_s;
    typedef stack<double> s_d;
    typedef stack<ll> s_ll;
    typedef stack<char> s_c;
    typedef map<ll,ll> m_ll_ll;
    typedef map<int,ll> m_i_ll;
    typedef map<string,ll> m_s_ll;
    typedef map<char,int> m_c_i;
    typedef map<char,ll> m_c_ll;
    #define rep(i,l,r) for(ll i=l;i<=r;i++)
    #define per(i,l,r) for(ll i=r;i>=l;i--)
    #define eif else if
    #define N 3005
    #define mm(dp) memset(dp,0,sizeof(dp))
    #define mm1(dp) memset(dp,-1,sizeof(dp))
    #define mm2(dp) memset(dp,0x3f,sizeof(dp))
    #define IT set<int>::iterator
    #define fs(n) fixed<< setprecision(n)
    #define inf 0x3f3f3f3f
    const double e=2.71828182845;
    const double pi = acos(-1.0);
    map<char,int>mapp;
    map<char,string>mapp1;
    typedef struct
    {
        string s1;
        int num;
    }STU;
    typedef struct
    {
        string s1,s0;
        int num;
    }STU1;
    bool cmp(STU x,STU y)
    {
        return x.num>y.num;
    }
    typedef struct node
    {
        string data;
        struct node *left,*right;
    }HuffmanTreeNode,*PtrHuffman;
    class Haffman
    {
        public:
        PtrHuffman head=NULL;
        PtrHuffman p[100005];
        void create1(int nm,STU *stu)
        {
            int u=0;
            rep(i,1,nm)
            {
                PtrHuffman t=new HuffmanTreeNode;
                t->data = stu[i].s1;
                t->left = t->right = NULL;
                p[i]= t;
            }
            rep(i,1,nm-1)
            {
                int fi=inf,se=inf;
                int fi1=0,se1=0;
                rep(j,1,nm+u)
                {
                    if(stu[j].num>0&&stu[j].num<fi)
                    {
                        fi=stu[j].num;
                        fi1=j;
                    }
                }
                rep(j,1,nm+u)
                {
                    if(stu[j].num>0&&stu[j].num<se&&j!=fi1)
                    {
                        se=stu[j].num;
                        se1=j;
                    }
                }
                PtrHuffman q=new HuffmanTreeNode;
                q->data=p[fi1]->data+p[se1]->data;
                q->left=p[fi1];
                q->right=p[se1];
                u++;
                stu[nm+u].s1=stu[fi1].s1+stu[se1].s1;
                stu[nm+u].num=stu[fi1].num+stu[se1].num;
                p[nm+u]=q;
                stu[fi1].num=-1;
                stu[se1].num=-1;
                head=q;
            }
        }
        void bianli(struct node *t1,int u)
        {
            if(t1==NULL)
                return;
            if(u==0)
                cout<<t1->data<<endl;
            else
            {
                cout<<u<<" ";
                cout<<t1->data<<endl;
            }
            bianli(t1->left,u+1);
            bianli(t1->right,u+1);
        }
    
        void bianli1(struct node *t1,char ch,string str)
        {
            if(t1==NULL)
                return;
            string s1="";
            s1+=ch;
            string ss=t1->data;
            if(ss==s1)
            {
                mapp1[ch]=str;
                return;
            }
            else
            {
                string s=t1->data;
                int len=s.size();
                int flag=0;
                rep(i,0,len)
                {
                    if(s[i]==ch)
                    {
                        flag=1;
                        break;
                    }
                }
                if(flag==0)
                    return;
                else
                {
                    bianli1(t1->left,ch,str+"0");
                    bianli1(t1->right,ch,str+"1");
                }
            }
        }
        STU1 bianli2(struct node *t1,string str)
        {
            if(t1->data.size()==1)
            {
                STU1 stu;
                stu.s1=t1->data;
                int len=str.size();
                stu.s0=str;
                return stu;
            }
            char ch=str[0];
            int len=str.size();
            str=str.substr(1,len-1);
            if(ch=='0')
            {
                return bianli2(t1->left,str);
            }
            if(ch=='1')
            {
                return bianli2(t1->right,str);
            }
        }
    };
    int len;
    int main()
    {
        //ios::sync_with_stdio(false);
        //cin.tie(0);
        //cout.tie(0);
        Haffman ha;
        char str[10005];
        int uu=0;
        while(1)
        {
            char ch;
            cin>>ch;
            if(ch=='X')
                break;
            eif(ch=='I')
            {
                getchar();
                char c;
                scanf("%c",&c);
                int i=0;
                while(c!='\n')
                {
                    str[i]=c;
                    i++;
                    scanf("%c",&c);
                }
                len=i;
                string ss="";
                rep(i,0,len-1)
                {
                    if(mapp[str[i]]==0)
                    {
                        mapp[str[i]]=1;
                        ss+=str[i];
                    }
                    eif(mapp[str[i]]!=0)
                    {
                        mapp[str[i]]++;
                    }
                }
                int len1=ss.size();
                STU stu[10005];
                rep(i,0,len1-1)
                {
                    string s0="";
                    char c=ss[i];
                    s0+=c;
                    stu[i+1].s1=s0;
                    stu[i+1].num=mapp[c];
                }
                ha.create1(len1,stu);
                cout<<"Huffman code established!"<<endl;
                uu=1;
            }
            eif(ch=='C')
            {
                if(uu==0)
                {
                    cout<<"Huffman code does not exist!"<<endl;
                }
                else{
                rep(i,0,len-1)
                {
                    char cc=str[i];
                    ha.bianli1(ha.head,cc,"");
                    cout<<mapp1[str[i]];
                }
                cout<<endl;
            }}
            eif(ch=='D')
            {
                if(uu==0)
                {
                    cout<<"Huffman code does not exist!"<<endl;
                }
                else{
    
                string s2;
                cin>>s2;
                while(1)
                {
                    if(s2=="")
                        break;
                    STU1 huan=ha.bianli2(ha.head,s2);
                    cout<<huan.s1;
                    s2=huan.s0;
                }
                cout<<endl;
            }}
        }
        return 0;
    }
    
    展开全文
  • 建立哈夫曼树得出每个字母的编码,输入的报文中每个字符查找其编码,生成报文编码译码即对二进制编码进行区分匹配报文字符。
  • 基于哈夫曼树的编码和译码

    千次阅读 2018-12-09 00:22:22
    利用哈夫曼编码:要传输一些数据(比如英文单词), 设计一个利用哈夫曼算法的编码系统, 为这些单词编码, 并在接收端进行译码. 基本要求: (1).将需要传输的数据存放在数据文件data.txt 中. (2).读入数据文件并为其编码, ...

    1.实验要求:

    利用哈夫曼编码:要传输一些数据(比如英文单词), 设计一个利用哈夫曼算法的编码系统, 为这些单词编码, 并在接收端进行译码.
    基本要求:
    (1).将需要传输的数据存放在数据文件data.txt 中.
    (2).读入数据文件并为其编码, 将编码后的内容存入文件code.txt中.
    (3).读入code.txt, 译码, 并将译码后的内容输出在屏幕上.

    2.基本思路:

    (1).编码: 统计 date.txt 中不同种类的字符的数目, 以及同一字符出现的次数, 以该次数作为字符的权值. 根据这些权值建立哈夫曼树, 并且为每个字符编码.
    遍历 date.txt 中的字符, 为每个字符匹配编码, 保存所有匹配得到的编码, 最后存入code.txt中.
    (2).译码:从 code.txt 读取编码, 根据每段编码匹配对应的字符, 储存所有匹配到的字符, 并输出.

    3.代码和注释如下:

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<sys/stat.h>
    #include<sys/types.h>
    #include<fcntl.h>
    #include<unistd.h>
    #include<errno.h>
    
    #define    N          10000
    
    int count = 0;        //每增加一个新的字符, count增加1, 可表示a中的字符种类数, 也即哈夫曼树叶子点个数 
    
    /*定义哈夫曼树结构体*/
    typedef struct HuffmanTree{
      int weight;
      int parent;
      int Lchild;
      int Rchild;
    }HuffmanTree[2*N];
    
    /*定义储存字符及其出现次数的结构体*/
    typedef struct DifferentCharacter{
      char char_date;
      int num;           //相同字符出现的次数
      char a_code[100];  //每种字符对应的编码
    }difcha[N];
    
    /*在一定范围内选择两个weight最小的结点, 并将两个结点的序号赋给s1, s2*/
    void select_two(HuffmanTree ht, int j, int *s1, int *s2) {
      int i = 1, temp;
      int min1 = 0, min2 = 0;
      while( (ht[i].parent != 0) && (i <= j) )
        i++;
      *s1 = i;
      min1 = ht[i++].weight;
      
      while( (ht[i].parent != 0) && (i <= j) )
        i++;
      *s2 = i;
      min2 = ht[i++].weight;
      
      if(min1 > min2){
        temp = min1;
        min1 = min2;
        min2 = temp;
      }                                    
      
      for(; i <= j; i++){                    //遍历parent不为0的结点
        if(ht[i].parent != 0)
          continue;
        if(ht[i].weight <= min1){
          min2 = min1;
          min1 = ht[i].weight;
          *s2 = *s1;
          *s1 = i;
        }
        else if( (ht[i].weight < min2) && (ht[i].weight > min1) ) {
          min2 = ht[i].weight;
          *s2 = i;
        }
      }
    }
             
    /*建哈夫曼树*/
    void EstHuffmanTree(HuffmanTree ht, int *w, int n){
      int i;
      int s1 = 0, s2 = 0;
      for(i = 1; i <= n; i++){                 //初始化哈夫曼树, 前n个单元存放叶子点
        ht[i].weight = w[i];
        ht[i].parent = 0;
        ht[i].Lchild = 0;
        ht[i].Rchild = 0;
      }
      for(i = n+1; i <= 2*n-1; i++){           //后n-1个单元存放非叶子点
        ht[i].weight = 0;
        ht[i].parent = 0;
        ht[i].Lchild = 0;
        ht[i].Rchild = 0;
      }
    
      for(i = n+1; i <= 2*n-1; i++){
        select_two(ht, i-1, &s1, &s2);         //创建非叶子点, 建立哈夫曼树, 每次在ht[1]~ht[i-1]范围内选两个最小的weight结点,并将其序号赋给s1, s2
        
        ht[i].weight = ht[s1].weight + ht[s2].weight;
        ht[i].Lchild = s1;
        ht[i].Rchild = s2;
        ht[s1].parent = i;
        ht[s2].parent = i;
      }                                       //哈夫曼树建立完毕
    }
    
    /*求哈弗曼编码*/
    void CrtHuffmanCode(HuffmanTree ht, char **hcd, int n){
      int start = 0, c = 0, p = 0, i;
      char *cd = (char*)malloc(n*sizeof(char));      //分配求当前编码的工作空间
      cd[n-1] = '\0';                                //从左向右存放编码
      for(i = 1; i <= n; i++) {
        start = n-1;                                 //初始化编码起始指针
        c = i;
        p = ht[i].parent;
        while(p != 0){
          start--;
          if(ht[p].Lchild == c)
    	cd[start] = '0';          //左分支标0
          else
    	cd[start] = '1';          //右分支标1
    
          c = p;                      //向上倒推                      
          p = ht[c].parent;
        }
        hcd[i] = (char*)malloc((n-start)*sizeof(char));
        strcpy(hcd[i], &cd[start]);
      }
      free(cd);
    }
    
    /*自定义错误处理函数*/
    void my_err(char *err_string, int line){
      printf("Line %d:\n", line);
      perror(err_string);
      exit(1);
    }
    
    /*从 buf_read 中统计每个字符出现的次数,将次数作为该字符的权值*/
    void Statistics(difcha a, char *buf_read){
      int i, j = 0;
      
      for(i = 0; i < strlen(buf_read) - 1; i++){        //对buf_read中的字符遍历
        for(j = 0; j < count; j++){                     //检查是否是新的字符
          if(a[j].char_date == buf_read[i]){
    	a[j].num++;                                 //若是旧字符, 则num++;
    	break;
          }
        }
        if(j == count){                                 //若是新字符, 则记录到a中, 且对应的num++
          a[count].char_date = buf_read[i];
          a[count].num++;
          count++;                                      //更新count
        }
      }
    }
    
    /*从 date.txt 读取数据到 buf_read */
    void ReadFile(char *pathName, char *buf_read){
      int fd_date;
      int len = 0;
      
      if( (fd_date = open(pathName, O_RDWR)) < 0)   //以读写方式打开date.txt文件
          my_err("open date.txt", __LINE__);
      
      if(lseek(fd_date, 0, SEEK_END) < 0)             //获取文件长度,并保持文件读写指针在文件开始处
        my_err("lseek", __LINE__);
      if( (len = lseek(fd_date, 0, SEEK_CUR)) < 0 )
        my_err("lseek", __LINE__);
      if(lseek(fd_date, 0, SEEK_SET) < 0)
        my_err("lseek", __LINE__);
      
      if(read(fd_date, buf_read, len) > len)         //从date.txt中读取内容
        my_err("read date.txt", __LINE__);
    }
     
    /*将 buf_code 写入 code.txt 中*/
    void WriteFile(char *pathName, char *buf_code){
      int fd_code;
      
      if((fd_code = open(pathName, O_CREAT|O_TRUNC|O_RDWR, S_IRWXU)) < 0)      //创建code.txt文件
        my_err("open code.txt", __LINE__); 
      if( write(fd_code, buf_code, strlen(buf_code)) != strlen(buf_code) )       //将 buf_code 写入code.txt
        my_err("write code.txt", __LINE__);
    }
    
    /*主函数*/
    void main(){
      char buf_read[N] = {'\0'};
      char buf_code[N] = {'\0'};
      char buf_yima[N] = {'\0'};
      char *hcd[N];
      char temp[50] = {'\0'};
      difcha a;
      int i, j, n, k = 0, m = 0;
      int w[N] = {0};
      HuffmanTree ht;
      
      ReadFile("date.txt", buf_read);
      Statistics(a, buf_read);
      for(i = 0; i < count; i++)
        w[i+1] = a[i].num;
      EstHuffmanTree(ht, w, count);             //建HuffmanTree
      CrtHuffmanCode(ht, hcd, count);           //对树中字符进行编码
      for(i = 1; i <= count; i++)               //将每个字符对应的编码存入结构体 a 中
        strcpy(a[i-1].a_code, hcd[i]);
      
      /*for(i = 0; i < count; i++)                //查看每个字符的权值和对应的编码
        printf("%c  %d  %s\n", a[i].char_date, a[i].num, a[i].a_code);*/
      
      for(i = 0; i < strlen(buf_read) - 1; i++){                   //遍历 buf_read, 给 date.txt 中每个字符匹配编码, 存入 buf_code 中
        for(j = 0; j < count; j++){                                
          if(buf_read[i] == a[j].char_date){
    	strcat(buf_code, a[j].a_code);
    	break;
          }
        }
        if(j == count)                          //匹配异常
          printf("Unknown Character: %c\n", buf_read[i]);
      }
      
      WriteFile("code.txt", buf_code);                      //将 buf_code 写入 code.txt 中  
      ReadFile("code.txt", buf_read);                       //从 code.txt 中读取全部编码
      n = strlen(buf_read);
      for(i = 0; i < n; i++){                               //为 code.txt 中的编码匹配字符
        temp[k++] = buf_read[i];
        for(j = 0; j < count; j++){
          if(strcmp(temp, a[j].a_code) == 0){
    	buf_yima[m++] = a[j].char_date;
    	break;
          }
        }
        if(j < count){                                      //匹配成功, 对 temp 初始化
          for(;k > 0; k--)
    	temp[k] = '\0';
        }
      }
      printf("The result of decoding is:\n\n%s\n", buf_yima);
    }
    

    4.运行截图如下:

    待编码的英文
    编码后的英文待编码的中文编码后的中文

    5.几点说明:

    (1).目前可以给英文, 汉字, 数字, 以及一些常见的符号编码, 并译码, 其他语言和某些特殊符号未测试过.
    (2).运行需要:需要自己创建一个和源码在同一目录下, 且名称是 date.txt 的文本. 在 date.txt 中输入需要编码的内容.
    (3).由于代码完成的比较匆忙, 难免有错误和待优化的地方, 请不吝指正!

    展开全文
  • 这是哈夫曼树的设计,还有编码和译码的实现。这个是我的课程设计,我上传了代码,希望给大家帮助,没有资源分,给个赞吧
  • 哈夫曼编码/译码实现

    2010-11-14 18:23:51
    压缩文件即读文件,统计文件中的字符个数,对文件进行哈夫曼编码译码,并将编码译码后的字符存储在文件中。 完成功能的详细说明: 1.统计文本文件中各字符的频率(涉及读文件,统计字符个数); 2.对文件中的...
  • 一、  Huffman于1952年提出一种编码方法,... 1951年,霍夫曼他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是,查找最有效的二进制编码。由于无法证明哪个已
    一、
        Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般称为哈夫曼编码(有时也称为霍夫曼编码)。

    二、背景:
          1951年,霍夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是,查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,霍夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。
          由于这个算法,学生终于青出于蓝,超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树,避免了次优算法香农-范诺编码的最大弊端──自顶向下构建树。

    三、
        哈夫曼编码是一种统计编码,属于无损压缩编码。它也是一种变长编码,也就是说,对于出现频率高的信息,对应的编码长度较短,反之较长。通过这样的编码处理,表示全部信息所用的总码长一定小于表示实际信息的所用的符号总长度。

    四、
        哈夫曼树,又称最优二叉树,是指带权路径长度最小的二叉树。树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度的积之和。

    五、
        哈夫曼树中的权值可以理解为:字符的出现频率

    六、如何构造哈夫曼树:
    a、给定n个权值为{w1,w2,w3,...,wn},先构造n棵只有根结点(带有相应的权值)的二叉树(其左右子树为空);
    b、在森林中选取两棵根结点的权值最小的二叉树,将它们作为左右子树并构造一棵新的二叉树。然后置这棵新的二叉树的根结点的权值为其左右子树的根结点的权值之和;
    c、在该森林中删除这两颗二叉树,将该新的二叉树加入该森林中;
    d、重复b、c,直到最终森林中只有一棵二叉树为止,这棵二叉树就是哈夫曼树。

    七、实现和应用:(一个小型的哈夫曼编码/译码系统)

    (1)实现一个含有如下功能项的主菜单:
            I-----Initialization(初始化、建立哈夫曼树)
            T-----Tree printing(打印哈夫曼树)
            C-----Huffman code printing(打印哈夫曼编码)
            E-----Encoding(编码)
            P-----Print(打印编码文件)
            D-----Decoding(译码)
            Q-----Quit(退出)

    (2)实现所有功能项对应的具体功能: 
      a、初始化、建立哈夫曼树:从终端读入字符集大小n、n个字符、n个权值,建立起哈夫曼树,并将其存于文件hfmTree.txt中;

      b、打印哈夫曼树:将内存中的哈夫曼树以直观的形式(这里使用横向打印的树结构)显示在终端上,同时将该形式的哈夫曼树写入文件TreePrint.txt中;

      c、打印哈夫曼编码:将字符集对应的哈夫曼编码显示在终端;

      d、编码(有两种方式):

       *利用已经建立好的哈夫曼树(如果不在内存中,则从文件hfmTree.txt中读入)对文件ToBeTran.txt中的文本进行编码。然后将结果存入文件CodeFile.txt中;

       *利用已经建立好的哈夫曼树(如果不在内存中,则从文件hfmTree.txt中读入)对实时输入的文本进行编码,然后将结果显示在终端上。

      e、打印编码文件:将文件CodeFile.txt以紧凑格式显示在终端上,每行50个代码,同时将该字符形式的编码文件写入文件CodePrint.txt中;

      f、译码(也有两种方式):

       *利用已经建立好的哈夫曼树(如果不在内存中,则从文件hfmTree.txt中读入)对文件CodeFile.txt中的文本进行译码,然后将结果存入文件TextFile.txt中;

       *利用已经建立好的哈夫曼树(如果不在内存中,则从文件hfmTree.txt中读入)对实时输入的文本进行译码,然后将结果显示在终端上。

      g、退出;


    (3)代码实现:
    #include<iostream>
    #include<fstream>
    #include<string>
    #include<Windows.h>
    
    using namespace std;
    
    //哈夫曼树结点类
    struct hfmNode
    {
    	int leftChild, rightChild, parent;
    
    	double weight;
    
    	hfmNode() :parent(0), weight(0.0) {}
    };
    
    int hfmSize = 0;  //哈夫曼树的规模
    
    char *characters = nullptr; //字符集
    double *weight = nullptr;  //权值
    string *huffmanCodeStrings = nullptr; //字符集对应的哈夫曼编码
    hfmNode* hfmTree = nullptr;  //结构体数组形式的哈夫曼树
    
    //分隔线
    void printLine()
    {
    	cout << "-----------------------------------------------" << endl;
    }
    
    //通过读取已经存在于文件hfmTree.txt中哈夫曼树的相关数据进行初始化
    void initByFile()
    {
    	ifstream in("D:\\hfmTree.txt", ios::in | ios::binary);
    	if (!in.is_open())
    	{
    		cerr << "文件打开失败!" << endl;
    		return;
    	}
    
    	in.read((char*)&hfmSize, sizeof(int));//一定要先从文件中读取哈夫曼树的大小!
    
    	//0号单元不用,起始下标从1开始
    	int m = 2 * hfmSize - 1;
    	hfmTree = new hfmNode[m + 1];
    
    	characters = new char[hfmSize + 1];
    	weight = new double[hfmSize + 1];
    	huffmanCodeStrings = new string[hfmSize + 1];
    
    	in.read(characters, sizeof(char)*(hfmSize + 1));
    	in.read((char*)weight, sizeof(double)*(hfmSize + 1));
    	in.read((char*)huffmanCodeStrings, sizeof(string)*(hfmSize + 1));
    	in.read((char*)hfmTree, sizeof(hfmTree[0])*(m + 1));
    
    	in.close();
    }
    
    
    //从哈夫曼树的n个结点中选出权值最小的结点,并返回该结点的索引
    int minInhuffmanTree(hfmNode hfmTree[], int n)
    {
    	int minIndex = 0;
    	int minWeight = INT_MAX;
    
    	for (int i = 1; i <= n; i++)
    	{
    		if (hfmTree[i].weight < minWeight&&hfmTree[i].parent == 0)
    		{
    			minWeight = hfmTree[i].weight;
    			minIndex = i;
    		}
    	}
    
    	hfmTree[minIndex].parent = 1; //设置其parent为1,表示该结点已经“使用过”
    	return minIndex;
    }
    
    //从哈夫曼树的n个结点中选出权值最小的两个结点,并通过参数引用带回对应的索引
    void selectTwoMinsFromhfmTree(hfmNode hfmTree[], int n, int& min1, int& min2)
    {
    	min1 = minInhuffmanTree(hfmTree, n);
    	min2 = minInhuffmanTree(hfmTree, n);
    
    	//使得min1保存权值最小的两个结点hfmTree[min1], hfmTree[min2]中最小的索引
    	if (min1 > min2) swap(min1, min2);
    }
    
    //通过建立哈夫曼树得到字符集的相应哈夫曼编码
    void huffmanCoding(hfmNode hfmTree[], string huffmanCodeStrings[], double weight[], int n)
    {
    	int min1, min2;
    	if (n <= 1) return;
    	int m = 2 * n - 1;
    
    
    	//初始化各个结点的权值
    	for (int i = 1; i <= n; i++)
    	{
    		hfmTree[i].weight = weight[i];
    		hfmTree[i].parent = hfmTree[i].leftChild = hfmTree[i].rightChild = 0;
    	}
    
    	for (int i = n + 1; i <= m; i++) hfmTree[i].parent = 0;
    
    	for (int i = n + 1; i <= m; i++)
    	{
    		selectTwoMinsFromhfmTree(hfmTree, i - 1, min1, min2);
    		hfmTree[min1].parent = hfmTree[min2].parent = i;
    		hfmTree[i].leftChild = min1;
    		hfmTree[i].rightChild = min2;
    		hfmTree[i].weight = hfmTree[min1].weight + hfmTree[min2].weight;
    	}
    
    	//从哈夫曼树的n个叶节点出发,自底向上沿着通往根结点的路径,最终分别得到n个不同字符对应的哈夫曼编码
    	int parent, current;
    	for (int i = 1; i <= n; i++)
    	{
    		string huffmanCodeString = "";
    		int length = 0;
    		current = i;
    		parent = hfmTree[current].parent;
    		while (parent != 0)
    		{
    			if (hfmTree[parent].leftChild == current) huffmanCodeString = '0' + huffmanCodeString;
    			else huffmanCodeString = '1' + huffmanCodeString;
    
    			current = parent;
    			parent = hfmTree[current].parent;
    		}
    
    		huffmanCodeStrings[i] = huffmanCodeString;
    	}
    }
    
    
    //I-----Initialization(初始化、建立哈夫曼树)
    void init()
    {
    	int sum;
    
    	cout << "请输入您所要编码的字符种类总数:";
    	cin >> sum;
    	hfmSize = sum;
    
    	//0号单元不用,起始下标从1开始
    	characters = new char[sum + 1];
    	weight = new double[sum + 1];
    	huffmanCodeStrings = new string[sum + 1];
    
    	int m = 2 * sum - 1;
    	hfmTree = new hfmNode[m + 1];
    
    	cout << endl << "请您按顺序输入每种字符以及其对应的权值:" << endl;
    	printLine();
    
    	cin.get();//吃掉回车
    	for (int i = 1; i <= sum; i++)
    	{
    		cout << "请您输入第 " << i << " 个字符:";
    		characters[i] = getchar();
    		cin.get(); //吃掉回车
    
    		cout << "请您输入该字符所所应的权值:";
    		cin >> weight[i];
    		cin.get(); //吃掉回车
    		printLine();
    	}
    
    	cout << "字符集为:" << endl;
    	for (int i = 1; i <= sum; i++)
    	{
    		cout << characters[i] << ":" << weight[i] << endl;
    	}
    	cout << endl;
    
    	huffmanCoding(hfmTree, huffmanCodeStrings, weight, sum);
    
    	printLine();
    
    
    	//将各种字符的哈夫曼编码写入文件hfmTree.txt中
    	cout << "下面将各种字符的哈夫曼编码写入文件hfmTree.txt中......" << endl;
    	ofstream out("D:\\hfmTree.txt", ios::out | ios::binary);
    
    	if (!out.is_open())
    	{
    		cerr << "文件打开失败!" << endl;
    		return;
    	}
    
    	out.write((char*)&hfmSize, sizeof(int));
    	out.write(characters, sizeof(char)*(hfmSize + 1));
    	out.write((char*)weight, sizeof(double)*(hfmSize + 1));
    	out.write((char*)huffmanCodeStrings, sizeof(string)*(hfmSize + 1));
    	out.write((char*)hfmTree, sizeof(hfmTree[0])*(m + 1));
    
    	cout << "写入文件hfmTree.txt成功!" << endl;
    
    	out.close();
    }
    
    
    //T-----Tree printing(打印哈夫曼树)
    //将要用来打印的树枝,注意其中:branches[0]=" "; branches[2]="\\"(占一个字节)
    char branches[] = { " /\\<" };
    
    void printHfmTree(int root, int height, ostream& out)
    {
    	if (root != 0)
    	{
    		//先打印当前结点的右子树,并且深度+1
    		printHfmTree(hfmTree[root].rightChild, height + 1, out);
    
    		//通过跳格符来表现当前节点的深度,深度越大的结点会越往右
    		for (int i = 0; i < height; i++) out << "\t";
    
    		//输出当前结点的权值
    		out << hfmTree[root].weight;
    
    		//如果当前结点是叶结点,则再打印出相应的字符
    		if (hfmTree[root].leftChild == 0 && hfmTree[root].rightChild == 0) out << "(" << characters[root] << ")";
    
    		//打印树枝
    		out << branches[((hfmTree[root].leftChild != 0) << 1) | (hfmTree[root].rightChild != 0)];
    
    		//换行,打印当前结点的左子树
    		out << endl;
    		printHfmTree(hfmTree[root].leftChild, height + 1, out);
    	}
    }
    
    void PrintHfmTree()
    {
    
    	cout << "该哈夫曼树打印如下(横向打印):" << endl << endl;
    
    	printHfmTree(2 * hfmSize - 1, 0, cout);
    
    	ofstream out("D:\\TreePrint.txt", ios::out);
    	if (!out.is_open())
    	{
    		cerr << "文件打开失败!" << endl;
    		exit(1);
    	}
    
    	printHfmTree(2 * hfmSize - 1, 0, out);
    	cout << "写入文件TreePrint.txt成功!" << endl;
    	out.close();
    }
    
    
    
    
    //C---- - Huffman code printing(打印哈夫曼编码)
    void printHfmCodeStrings()
    {
    	cout << "该字符集的编码如下:" << endl << endl;
    	for (int i = 1; i <= hfmSize; i++)
    	{
    		cout << "字符 " << characters[i] << "(权值为" << weight[i] << ")" << " :   " << huffmanCodeStrings[i] << endl;
    	}
    }
    
    
    //E-----Encoding(编码),对文本进行编码(支持含空格的文本)
    void encodeText()
    {
    	char inputType,ch=' ';
    	string textToBeEncoded = "", encodeString = "";
    
    	cout << "您有如下两种方式提供待编码文本:" << endl << endl;
    	cout << "1-----读取文件ToBeTran.txt中的待编码文本;" << endl;
    	cout << "2-----读取实时输入的待编码文本;" << endl;
    	printLine();
    	cout << "您选择方式: " << endl;
    	cin >> inputType;
    
    	if (inputType == '1')
    	{
    		ifstream in("D:\\ToBeTran.txt", ios::in);
    		if (!in.is_open())
    		{
    			cerr << "文件打开失败!" << endl;
    			exit(1);
    		}
    
    		ofstream out("D:\\CodeFile.txt", ios::out);
    		if (!out.is_open())
    		{
    			cerr << "文件打开失败!" << endl;
    			exit(1);
    		}
    
    		cin.get();//吃掉回车
    		while ((ch = in.get()) != EOF)
    		{
    			textToBeEncoded = textToBeEncoded + ch;
    		}
    
    		for (int i = 0; i < textToBeEncoded.length(); i++)
    		{
    			for (int j = 1; j <= hfmSize; j++)
    			{
    				if (characters[j] == textToBeEncoded[i]) encodeString = encodeString + huffmanCodeStrings[j];
    			}
    		}
    
    		out << encodeString;
    		cout << "该段文本被编码后写入文件CodeFile.txt成功!" << endl;
    
    		in.close();
    		out.close();
    
    	}
    	else if (inputType == '2')
    	{
    		cout << "请您输入待编码文本:" << endl;
    
    		cin.get();//吃掉回车
    		while (cin.get(ch) && ch != '\n')
    		{
    			textToBeEncoded = textToBeEncoded + ch;
    		}
    
    		for (int i = 0; i < textToBeEncoded.length(); i++)
    		{
    			for (int j = 1; j <= hfmSize; j++)
    			{
    				if (characters[j] == textToBeEncoded[i]) encodeString = encodeString + huffmanCodeStrings[j];
    			}
    		}
    		cout << "该段文本被编码为如下:" << endl;
    		cout << encodeString << endl;
    	}
    }
    
    
    //P---- - Print(打印编码文件)
    void printEncodeFile()
    {
    	ifstream in("D:\\CodeFile.txt", ios::in);
    	if (!in.is_open())
    	{
    		cerr << "文件打开失败!" << endl;
    		exit(1);
    	}
    
    	ofstream out("D:\\CodePrint.txt", ios::out);
    	if (!out.is_open())
    	{
    		cerr << "文件打开失败!" << endl;
    		exit(1);
    	}
    
    	string encodeString = "";
    	in >> encodeString;
    	for (int i = 0; i < encodeString.length(); i++)
    	{
    		cout << encodeString[i];
    		out << encodeString[i];
    
    		//每行50个代码
    		if ((i + 1) % 50 == 0)
    		{
    			cout << endl;
    			out << endl;
    		}
    	}
    
    	cout << endl;
    	cout << "写入文件CodePrint.txt成功!" << endl;
    
    	in.close();
    	out.close();
    }
    
    //D-----Decoding(译码),对文本进行译码(支持含空格的文本)
    void decodeText()
    {
    	char inputType, ch = ' ';
    	string textToBeDecoded, decodeString = "";
    
    	cout << "您有如下两种方式提供待译码文本:" << endl << endl;
    	cout << "1-----读取文件CodeFile.txt中的待译码文本;" << endl;
    	cout << "2-----读取实时输入的待译码文本;" << endl;
    	printLine();
    	cout << "您选择方式: " << endl;
    	cin >> inputType;
    
    	if (inputType == '1')
    	{
    		ifstream in("D:\\CodeFile.txt", ios::in);
    		if (!in.is_open())
    		{
    			cerr << "文件打开失败!" << endl;
    			exit(1);
    		}
    
    		ofstream out("D:\\TextFile.txt", ios::out);
    		if (!out.is_open())
    		{
    			cerr << "文件打开失败!" << endl;
    			exit(1);
    		}
    
    		cin.get();//吃掉回车
    		while ((ch = in.get()) != EOF)
    		{
    			textToBeDecoded = textToBeDecoded + ch;
    		}
    
    		int m = 2 * hfmSize - 1;
    		for (int i = 0; i < textToBeDecoded.length(); i++)
    		{
    			if (textToBeDecoded[i] == '0')
    			{
    				m = hfmTree[m].leftChild;
    
    				//如果已经走到哈夫曼树的叶结点
    				if (hfmTree[m].leftChild == 0)
    				{
    					decodeString = decodeString + characters[m];
    					m = 2 * hfmSize - 1;
    				}
    			}
    			else if (textToBeDecoded[i] == '1')
    			{
    				m = hfmTree[m].rightChild;
    
    				//如果已经走到哈夫曼树的叶结点
    				if (hfmTree[m].leftChild == 0)
    				{
    					decodeString = decodeString + characters[m];
    					m = 2 * hfmSize - 1;
    				}
    			}
    		}
    
    		out << decodeString;
    		cout << "该段文本被译码后写入文件TextFile.txt成功!" << endl;
    
    		in.close();
    		out.close();
    	}
    	else if (inputType == '2')
    	{
    		cout << "请您输入待译码文本:" << endl;
    
    		cin.get();//吃掉回车
    		while (cin.get(ch) && ch != '\n')
    		{
    			textToBeDecoded = textToBeDecoded + ch;
    		}
    
    		int m = 2 * hfmSize - 1;
    		for (int i = 0; i < textToBeDecoded.length(); i++)
    		{
    			if (textToBeDecoded[i] == '0')
    			{
    				m = hfmTree[m].leftChild;
    
    				//如果已经走到哈夫曼树的叶结点
    				if (hfmTree[m].leftChild == 0)
    				{
    					decodeString = decodeString + characters[m];
    					m = 2 * hfmSize - 1;
    				}
    			}
    			else if (textToBeDecoded[i] == '1')
    			{
    				m = hfmTree[m].rightChild;
    
    				//如果已经走到哈夫曼树的叶结点
    				if (hfmTree[m].leftChild == 0)
    				{
    					decodeString = decodeString + characters[m];
    					m = 2 * hfmSize - 1;
    				}
    			}
    		}
    
    		cout << "该段文本被译码为如下:" << endl;
    		cout << decodeString << endl;
    	}
    }
    
    int main(void)
    {
    
    	bool back = true;
    	char handle, choice;
    
    	while (back)
    	{
    		system("cls");
    
    		cout << "********Welcome to use the Huffman Encoding System!!!********" << endl << endl;
    		cout << "\t" << "I-----Initialization(初始化、建立哈夫曼树)" << endl << endl;
    		cout << "\t" << "T-----Tree printing(打印哈夫曼树)" << endl << endl;
    		cout << "\t" << "C-----Huffman code printing(打印哈夫曼编码)" << endl << endl;
    		cout << "\t" << "E-----Encoding(编码)" << endl << endl;
    		cout << "\t" << "P-----Print(打印编码文件)" << endl << endl;
    		cout << "\t" << "D-----Decoding(译码)" << endl << endl;
    		cout << "\t" << "Q-----Quit(退出)" << endl << endl;
    		cout << endl;
    
    		cout << "请输入您想进行的操作: ";
    		cin >> handle;
    
    		switch (handle)
    		{
    		case 'I':
    		{
    			system("cls");
    
    			init();
    
    			cout << endl;
    			cout << "是否返回主菜单? Y/N" << endl;
    			cin >> choice;
    			if (choice == 'Y') back = true;
    			else exit(1);
    
    			break;
    		}
    		case 'T':
    		{
    			system("cls");
    
    			if (hfmTree == nullptr) initByFile();
    
    			PrintHfmTree();
    
    			cout << endl;
    			cout << "是否返回主菜单? Y/N" << endl;
    			cin >> choice;
    			if (choice == 'Y') back = true;
    			else exit(1);
    
    			break;
    		}
    
    		case 'C':
    		{
    			system("cls");
    
    			if (hfmTree == nullptr) initByFile();
    
    			printHfmCodeStrings();
    
    			cout << endl;
    			cout << "是否返回主菜单? Y/N" << endl;
    			cin >> choice;
    			if (choice == 'Y') back = true;
    			else exit(1);
    
    			break;
    		}
    		case 'E':
    		{
    			system("cls");
    
    			if (hfmTree == nullptr) initByFile();
    
    			encodeText();
    
    			cout << endl;
    			cout << "是否返回主菜单? Y/N" << endl;
    			cin >> choice;
    			if (choice == 'Y') back = true;
    			else exit(1);
    
    			break;
    		}
    		case 'P':
    		{
    			system("cls");
    
    			printEncodeFile();
    
    			cout << endl;
    			cout << "是否返回主菜单? Y/N" << endl;
    			cin >> choice;
    			if (choice == 'Y') back = true;
    			else exit(1);
    
    			break;
    		}
    		case 'D':
    		{
    			system("cls");
    
    			if (hfmTree == nullptr) initByFile();
    
    			decodeText();
    
    			cout << endl;
    			cout << "是否返回主菜单? Y/N" << endl;
    			cin >> choice;
    			if (choice == 'Y') back = true;
    			else exit(1);
    
    			break;
    		}
    		case 'Q':
    		{
    			system("cls");
    
    			exit(1);
    
    			break;
    		}
    		}
    	}
    	return 0;
    }


    (经测试,以上代码可以正常运行)

    展开全文
  • BCH码 编码译码 能编译!!!! 能运行
  • 基于matlab生成GUI的霍夫曼编码译码,霍夫曼(Huffman)编码是一种编码方式,主要用于数据文件的压缩。它的主要思想是放弃文本文件的普通保存方式:不再使用7位或8位二进制数表示每一个字符,而是用较少的比特表示...
  • 哈夫曼编码译码

    2020-11-24 11:10:47
    从文件中读入任意一篇英文文本文件,分别统计英文文本...将哈夫曼编码文件译码文本文件,并与原文件进行比较。 利用堆结构,优化的哈夫曼编码算法 #include<stdio.h> #include<stdlib.h> #define MAXLE.
    1. 从文件中读入任意一篇英文文本文件,分别统计英文文本文件中各字符(包 括标点符号和空格)的使用频率;
    2. 根据已统计的字符使用频率构造哈夫曼编码树,并给出每个字符的哈夫曼编 码(字符集的哈夫曼编码表);
    3. 将文本文件利用哈夫曼树进行编码,存储成压缩文件(哈夫曼编码文件);
    4. 计算哈夫曼编码文件的压缩率;
    5. 将哈夫曼编码文件译码为文本文件,并与原文件进行比较。
    6. 利用堆结构,优化的哈夫曼编码算法
    #include<stdio.h>
    #include<stdlib.h>
    #define MAXLEAF 50
    #define MAXNODE 2*MAXLEAF-1
    #define MAXWEIGHT 10000
    #define MAXBIT 100
    typedef struct character
    {
        char ch;
        int count=0;
    }CHARACTER;             //记录原文本文件中出现的字符及相应出现次数的类型
    typedef struct hnodetype
    {
        int weight;
        int parent;
        int lchild;
        int rchild;
        char value;
        int i;
    }HNodeType;             //哈夫曼树的结点定义
    typedef struct huffcodetype
    {
        int bit[MAXBIT];
        int start;
    }HCodeType;             //记录每个字符哈夫曼编码
    typedef struct heap
    {
        HNodeType node[MAXNODE+1];
        int n;
    }HEAP;                  //最小堆的类型定义
    void Statistic(CHARACTER chars[],int &n);                       //统计原文本中出现的字符及其使用频率
    void Display(CHARACTER chars[],int n);                          //打印原文本中出现的字符及其使用频率
    void CreateHT(HNodeType huffnode[],int n,CHARACTER chars[]);    //构建哈夫曼树
    void Coding(HNodeType huffnode[],HCodeType huffcode[],int n);   //构建哈夫曼编码表
    void Calculate(CHARACTER chars[],int n,int chnum);              //计算压缩率
    void Display(HNodeType huffnode[],HCodeType huffcode[],int n);  //打印哈夫曼编码表
    void CodingFile(HNodeType huffnode[],HCodeType huffcode[],int n,int &chnum);    //将文本编码并存入文件
    void Decoding(HNodeType huffnode[],int n);                                      //将编码文件译码恢复
    
    void Insert(HEAP &heap,HNodeType item);     //向堆里插入元素
    HNodeType Delete(HEAP &heap);               //取堆顶元素并删除
    void CreateHT_heap(HNodeType huffnode[],CHARACTER chars[],int n,HEAP &heap);    //用最小堆优化构建哈夫曼树的过程
    int main()
    {
        CHARACTER chars[MAXLEAF];
        HNodeType huffnode[MAXNODE];
        HCodeType huffcode[MAXLEAF];
        HEAP heap;heap.n=0;
        int n=0,chnum=0;
        Statistic(chars,n);
        Display(chars,n);
        //CreateHT_heap(huffnode,chars,n,heap);
        CreateHT(huffnode,n,chars);
        Coding(huffnode,huffcode,n);
        Display(huffnode,huffcode,n);
        CodingFile(huffnode,huffcode,n,chnum);
        Calculate(chars,n,chnum);
        Decoding(huffnode,n);
    }
    void Statistic(CHARACTER chars[],int &n)    //统计原文本中出现的字符及其使用频率
    {
        FILE *f=NULL;
        if((f=fopen("original.txt","r"))==NULL)
        {
            printf("Fail to open original.txt!\n");
            exit(0);
        }
        char ch;
        int i=0,j=0,flag=0;;
        fscanf(f,"%c",&ch);
        chars[i].ch=ch;
        chars[i].count++;
        //printf("%c",chars[i].ch);
        i++;
        while(ch!='#')  //从文件读入文本,以#标记结束
        {
            fscanf(f,"%c",&ch);
            flag=0;
            if(ch!='#')
            {
                for(j=0;j<i;j++)
                {
                    if(ch==chars[j].ch)  //如果读入的字符已被记录,则将出现次数+1
                    {
                        chars[j].count++;
                        flag=1;
                        //printf("%c",chars[j].ch);
                        break;
                    }
                }
                if(flag==0)
                {
                    chars[i].ch=ch;
                    chars[i].count++;
                    //printf("%c",chars[i].ch);
                    i++;
                }
            }
        }
        n=i;
        fclose(f);
    }
    void CreateHT(HNodeType huffnode[],int n,CHARACTER chars[])     //构建哈夫曼树
    {
        int i,j,w1,w2,x1,x2;
        for(i=0;i<2*n-1;i++)        //初始化
        {
            huffnode[i].weight=chars[i].count;
            huffnode[i].parent=-1;
            huffnode[i].lchild=-1;
            huffnode[i].rchild=-1;
            huffnode[i].value=chars[i].ch;
        }
        for(i=0;i<n-1;i++)
        {
            w1=w2=MAXWEIGHT;
            x1=x2=0;
            for(j=0;j<n+i;j++)      //寻找权值最小的两个结点
            {
                if(huffnode[j].parent==-1&&huffnode[j].weight<w1)
                {
                    w2=w1;
                    x2=x1;
                    w1=huffnode[j].weight;
                    x1=j;
                }
                else if(huffnode[j].parent==-1&&huffnode[j].weight<w2)
                {
                    w2=huffnode[j].weight;
                    x2=j;
                }
            }
            huffnode[x1].parent=n+i;
            huffnode[x2].parent=n+i;
            huffnode[n+i].lchild=x1;
            huffnode[n+i].rchild=x2;
            huffnode[n+i].weight=w1+w2;
        }
    }
    void CreateHT_heap(HNodeType huffnode[],CHARACTER chars[],int n,HEAP &heap)  //利用堆优化哈夫曼树的构建
    {
        int i;
        HNodeType node1,node2;
        for(i=0;i<2*n-1;i++)
        {
            huffnode[i].weight=chars[i].count;
            huffnode[i].parent=-1;
            huffnode[i].lchild=-1;
            huffnode[i].rchild=-1;
            huffnode[i].value=chars[i].ch;
            huffnode[i].i=i;
            if(i<n)
                Insert(heap,huffnode[i]);
        }
        for(i=0;i<n-1;i++)
        {
            node1=Delete(heap);
            node2=Delete(heap);
            huffnode[node1.i].parent=n+i;
            huffnode[node2.i].parent=n+i;
            huffnode[n+i].lchild=node1.i;
            huffnode[n+i].rchild=node2.i;
            huffnode[n+i].weight=node1.weight+node2.weight;
            huffnode[n+i].i=n+i;
            Insert(heap,huffnode[n+i]);
        }
    }
    void Coding(HNodeType huffnode[],HCodeType huffcode[],int n)        //构建字符的哈夫曼编码表
    {
        HCodeType temp;
        int p,c;
        for(int i=0;i<n;i++)
        {
            huffcode[i].start=MAXBIT-1;
            c=i,p=huffnode[i].parent;
            while(p!=-1)
            {
                if(c==huffnode[p].lchild)
                    huffcode[i].bit[huffcode[i].start]=0;
                else
                    huffcode[i].bit[huffcode[i].start]=1;
                c=p;
                p=huffnode[p].parent;
                huffcode[i].start--;
            }
            huffcode[i].start++;
        }
    }
    void Display(HNodeType huffnode[],HCodeType huffcode[],int n) //打印哈夫曼编码表
    {
        for(int i=0;i<n;i++)
        {
            printf("%c: ",huffnode[i].value);
            for(int j=huffcode[i].start;j<MAXBIT;j++)
            {
                printf("%d",huffcode[i].bit[j]);
            }
            printf("\n");
        }
    }
    void CodingFile(HNodeType huffnode[],HCodeType huffcode[],int n,int &chnum)     //对原文本编码并将编码写入文件
    {
        FILE *fo=NULL;
        FILE *fc=NULL;
        if((fo=fopen("original.txt","r"))==NULL)
        {
            printf("Fail to open original.txt!\n");
            exit(0);
        }
        if((fc=fopen("compressed.txt","w"))==NULL)
        {
            printf("Fail to open compressed.txt!\n");
            exit(0);
        }
        char ch;
        do
        {
            fscanf(fo,"%c",&ch);
            if(ch!='#')
            {
                for(int i=0;i<n;i++)
                {
                    if(huffnode[i].value==ch)
                    {
                        for(int j=huffcode[i].start;j<MAXBIT;j++)
                        {
                            fprintf(fc,"%d",huffcode[i].bit[j]);
                            chnum++;
                        }
                    }
                }
            }
        } while (ch!='#');
        fclose(fo);
        fclose(fc);
    }
    void Decoding(HNodeType huffnode[],int n)   //译码
    {
        FILE *fc=NULL,*fd=NULL;
        if((fc=fopen("compressed.txt","r"))==NULL)
        {
            printf("Fail to open compressed.txt!\n");
            exit(0);
        }
        if((fd=fopen("decoding.txt","w"))==NULL)
        {
            printf("Fail to open decoding.txt!\n");
            exit(0);
        }
        char code[100000];
        fscanf(fc,"%s",code);
        int i=0,j=0,temp;
        for(i=0;code[i]!='\0';i++);
        while(j<i)
        {
            temp=2*n-2;
            while(huffnode[temp].lchild!=-1&&huffnode[temp].rchild!=-1)
            {
                if(code[j]=='0')
                    temp=huffnode[temp].lchild;
                else
                    temp=huffnode[temp].rchild;
                j++;
            }
            fprintf(fd,"%c",huffnode[temp].value);
        }
        fclose(fc);
        fclose(fd);
    }
    void Display(CHARACTER chars[],int n)   
    {
        int total=0;
        double f=0;
        for(int i=0;i<n;i++)
        {
            total=total+chars[i].count;
        }
        for(int i=0;i<n;i++)
        {
            printf("frequency of %c is %f\n",chars[i].ch,chars[i].count*1.0/total);
        }
    }
    void Calculate(CHARACTER chars[],int n,int chnum)   //计算压缩率
    {
        int total=0;
        for(int i=0;i<n;i++)
        {
            total+=chars[i].count;
        }
        printf("Compression rate is %f%%",chnum*1.0/8/total*100);
    }
    void Insert(HEAP &heap,HNodeType item)
    {
        int i;
        if(heap.n<MAXNODE-1)
        {
            i=heap.n+1;
            while(i!=1&&item.weight<heap.node[i/2].weight)
            {
                heap.node[i]=heap.node[i/2];
                i/=2;
            }
            heap.node[i]=item;
            heap.n++;
        }
    }
    HNodeType Delete(HEAP &heap)
    {
        int parent=1,child=2;
        HNodeType item,temp;
        if(heap.n>0)
        {
            item=heap.node[1];
            temp=heap.node[heap.n--];
            while(child<=heap.n)
            {
                if(child<heap.n&&heap.node[child].weight>heap.node[child+1].weight)
                    child++;
                if(temp.weight<=heap.node[child].weight) break;
                heap.node[parent]=heap.node[child];
                parent=child;
                child*=2;
            }
            heap.node[parent]=temp;
            return item;
        }
    }
    

    测试数据与运行结果:
    输入格式:输入一篇英文文本,以#结尾
    输入:
    在这里插入图片描述

    各字符出现的频率:
    在这里插入图片描述

    在这里插入图片描述

    字符集的哈夫曼编码表:

    在这里插入图片描述
    在这里插入图片描述

    哈夫曼编码文件:

    在这里插入图片描述

    哈夫曼编码文件的压缩率:
    在这里插入图片描述

    译码结果:

    在这里插入图片描述

    展开全文
  • (1)读取文本文件即使用C编译系统所提供的库函数对给定的文本文件(wejian.txt)进行...(5)编写译码函数对前面的编码进行译码处理,打开存储编码的文件(code.txt)根据所读取的编码文件中的每个字符(0、1组成的),
  • 简单实现哈夫曼编码译码过程,简单易懂` #include<stdio.h> #include<string.h> #include<stdlib.h> #include<conio.h> typedef struct{ char ch; //字符 int weight; //权值 int ...
  • 要求根据给定的权值,构建哈夫曼树,并实现哈夫曼编码和译码。 直接上代码: #include<stdio.h> #include<malloc.h> #define maxval 10000.0 #define maxsize 100 //哈夫曼编码的最大位数 typedef ...
  • 哈夫曼编码和译码

    2020-02-09 19:22:52
    试题描述:输入为:一段英文或中文的文章(原文),对输入的文章构造哈夫曼树,生成对应的编码,输出为:原文所对应的编码(译文),根据已经生成的编码表,输入任意的译文可以得到对应的原文。要求有运行结果截图。...
  • 哈工大数据结构实验二——哈夫曼编码译码方法

    千次阅读 多人点赞 2020-10-22 22:00:03
    对于本次实验,无非要解决的就是以下几个问题: 用什么数据结构去表示哈夫曼树 如何构造哈夫曼树 构造了哈夫曼树之后如何根据哈夫曼树将文本文件进行哈夫曼编码以及如何解码 本文将逐一阐述上述问题如何解决 首先,...
  • 哈夫曼树的编码译码(含代码)

    千次阅读 2019-07-23 10:39:10
    此程序是利用哈夫曼树实现对文本文件的加密与解密,程序所能达到的内容:使用从文件中读取显示原文本文件、使用哈夫曼树编码文本文件进行加密、使用哈夫曼表显示字符编码、显示加密文件、使用哈夫曼树译码文本文件...
  • 数据结构——Huffman编码译码

    千次阅读 2018-10-23 16:33:21
    Huffman编码译码 1.掌握二叉树的二叉链表存贮结构。 2.掌握Huffman算法。   要求: 使用文件保存初始的文本数据及最终的结果。 文件名为inputfile1.txt的文件保存的是一段英文短文; 文件名为inputfile2...
  • 哈夫曼编码译码,支持读取文件进行译码,大家参考啊!!!!!
  • 哈夫曼树的建立、编码译码的详解实现

    千次阅读 多人点赞 2020-12-05 13:49:02
    简单哈夫曼树的建立,及其编码译码的详解实现 基本术语 二叉树的带权路径长度 二叉树中所有叶子结点的带权路径长度之 根到结点的路径长度 从根到结点的路径上的分支数 哈夫曼树二叉树 又称最优二叉树,是一带...
  • 【问题描述】 设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(压缩文件,后缀名.cod);反过来,可将一个压缩文件译码还原为一个文本文件(.txt)。 【基本要求】 (1) 输入一个待...
  • 哈夫曼编码--英语文章的编码&译码(c/c++)

    千次阅读 多人点赞 2019-10-27 10:56:40
    一.Huffman编码与解码 (Huffman编码、二叉树) [问题描述] 对一篇英文文章(大于...(2) 在Huffman编码后,要将编码英文文章编码结果保存到文件中,编码结果必须是二进制形式,即0 1的信息用比特位表示,不...
  • 设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理“要求”中项目,直到选择退出为止。 要求: (1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中) (2)分别采用动态静态存储...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,005
精华内容 1,602
关键字:

文本的编码和译码