精华内容
下载资源
问答
  • 哈夫曼编码/译码器
    千次阅读 多人点赞
    2019-12-25 10:32:44

    哈夫曼(Huffman)编/译码器(限1人完成)
    【问题描述】
    利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。首先输入一段包含27个字符(包含空格)的文字(可以存在一个文件中),然后统计出各个字符出现的次数,以每个字符出现的次数为权值构造哈夫曼树,求得哈夫曼编码。
    【基本要求】
    一个完整的系统应具有以下功能:
    1、 O: 输入一段字符(要包含27各字符)存入文件chartexfile中,统计出各个字符出现的次数并以表格的形式存入文件charsumfile中.
    例如如下表:
    字符 空格 A B C D E F G H I J K L M
    频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
       
    字符 N O P Q R S T U V W X Y Z  
    频度 57 63 15 1 48 51 80 23 8 18 1 16 1

    2、I:初始化(Initialization)。从终端读入字符集大小n,n个字符及n个权值,建立哈夫曼树,并将它存于文件hfmTree中。
    3、 E:编码(Encoding)。利用以建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),
    对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
    4、D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。
    5. P:打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。
    同时将此字符形式的编码文件写入文件CodePrin中。
    4、 T:打印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入
    表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
    【测试数据】
    用文件charsumfile给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。
    测试数据要求:
    要求使用1、全部合法数据;2、整体非法数据;3、局部非法数据。进行程序测试,以保证程序的稳定

    #include<stdio.h>
    #include<string.h>
    
    #define maxval 10000.0
    #define maxsize 10000   //哈夫曼编码的最大位数
    typedef struct
    {
        char ch;
        float weight=-1;
        int lchild,rchild,parent;
    } hufmtree;
    typedef struct
    {
        char bits[10000];   //位串
        int start;      //编码在位串中的起始位置
        char ch;        //字符
    } codetype;
    int n,m;
    hufmtree tree[20000];
    codetype code[10000];
    void TongJi(); //统计字符个数
    void huffman(hufmtree tree[]);//建立哈夫曼树
    void huffmancode(codetype code[],hufmtree tree[]);//根据哈夫曼树求出哈夫曼编码
    void decode(hufmtree tree[]);//依次读入电文,根据哈夫曼树译码
    void print(); //打印代码文件,输出 CodeFile.txt
    void TreePrinting();//打印哈夫曼树
    int main()
    {
        while(1)
        {
            int t;
            printf("---------------菜单-------------------\n");
            printf("1.输入一段字符,统计出各个字符出现的次数.\n");
            printf("2.建立哈夫曼树.\n");
            printf("3.编码.\n");
            printf("4.译码.\n");
            printf("5.打印编码\n");
            printf("6.打印哈夫曼树\n");
            printf("7.退出\n");
            printf("---------------------------------------\n");
            printf("请选择你要进行的操作:");
            scanf("%d",&t);
            switch(t)
            {
            case 1:
                TongJi();
                break;
            case 2:
                huffman(tree);//建立哈夫曼树
                printf("哈夫曼树已建立!\n");
                break;
            case 3:
                huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码
                break;
            case 4:
                decode(tree);//依次读入电文,根据哈夫曼树译码*/
                break;
            case 5:
                print();
                break;
            case 6:
                TreePrinting();
                break;
            case 7:
                return 0;
            }
        }
        return 0;
    }
    void TongJi()  //统计字符个数
    {
        FILE *out1,*out2;
        out1=fopen("chartexfile.txt","w");
        out2=fopen("charsumfile.txt","w");
        if(out1==NULL||out2==NULL)
        {
            printf("打开文件失败\n");
        }
        char s[1000];
        int i=0;
        char zf[1000]= {0}, z[1000];
        int cnt=1,k,num[1000]= {0};
        printf("请输入字符串(空格以-代替,按回车结束):");
        scanf("%s",s);
        k=strlen(s);
        fprintf(out1,"%s",s);
        for(i=0; i<k; i++)
        {
            if(zf[s[i]]==0)
            {
                zf[s[i]]=cnt++;
                z[cnt-1]=s[i];
            }
            num[zf[s[i]]]++;
        }
        printf("字符    频率\n");
        fprintf(out2,"字符    频率\n");
        for(int i=1; i<cnt; i++)
        {
            if(z[i]!='-')
                printf("%3c     %4d\n",z[i],num[zf[z[i]]]);
            else printf(" 空格   %4d\n",num[zf[z[i]]]);
            fprintf(out2,"%3c     %4d\n",z[i],num[zf[z[i]]]);
        }
        fclose(out1);
        fclose(out2);
    }
    void huffman(hufmtree tree[]) //建立哈夫曼树
    {
        int i,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标
        float small1,small2,f;
        char c;
        FILE *fp,*in;
        in=fopen("charsumfile.txt","r");
        fp=fopen("hfmTree.txt","w");
        if(fp==NULL)
        {
            printf("打开文件失败\n");
            return ;
        }
        for(i=0; i<20000; i++)  //初始化
        {
            tree[i].parent=0;
            tree[i].lchild=-1;
            tree[i].rchild=-1;
            tree[i].weight=0.0;
        }
        int t;
        printf("(1)根据字符频率文件 charsumfile.txt 生成哈夫曼树\n(2)手动输入字符频率生成哈夫曼树\n 请选择你要进行的操作:");
        scanf("%d",&t);
        if(t==2)
        {
            printf("请输入字符个数:");
            scanf("%d",&n);
            getchar();
            m=2*n-1;
            printf("请依次输入前 %d 个字符(中间用空格隔开,空格用‘-’代替):",n);
            for(i=0; i<n; i++)
            {
                tree[i].ch=getchar();
                getchar();
            }
            printf("请依次输入前 %d 个权值(中间用空格隔开)\n",n);
            for(i=0; i<n; i++) //读入前n个结点的字符及权值
            {
                scanf("%f",&f);
                tree[i].weight=f;
            }
        }
        else if(t==1)
        {
            i=0;
            char na[10];
            fscanf(in,"%s %s",na,na);
            while(EOF!=fscanf(in," %c %lf",&tree[i].ch,&tree[i].weight))
            {
                i++;
            }
            n=i;
            m=n*2-1;
        }
        for(i=n; i<m; i++)    //进行n-1次合并,产生n-1个新结点
        {
            p1=0;
            p2=0;
            small1=maxval;
            small2=maxval;   //maxval是float类型的最大值
            for(j=0; j<i; j++)  //选出两个权值最小的根结点
                if(tree[j].parent==0)
                    if(tree[j].weight<small1)
                    {
                        small2=small1;  //改变最小权、次小权及对应的位置
                        small1=tree[j].weight;
                        p2=p1;
                        p1=j;
                    }
                    else if(tree[j].weight<small2)
                    {
                        small2=tree[j].weight;  //改变次小权及位置
                        p2=j;
                    }
            tree[p1].parent=i;
            tree[p2].parent=i;
            tree[i].lchild=p1;  //最小权根结点是新结点的左孩子
            tree[i].rchild=p2;  //次小权根结点是新结点的右孩子
            tree[i].weight=tree[p1].weight+tree[p2].weight;
        }
        for(i=0; i<m; i++)
        {
            fprintf(fp,"%3d %3c %3.1f %3d %3d %3d\n",i+1,tree[i].ch,tree[i].weight,tree[i].parent,tree[i].lchild,tree[i].rchild);
        }
        fclose(fp);
        fclose(in);
    }//huffman
    
    void huffmancode(codetype code[],hufmtree tree[]) //根据哈夫曼树求出哈夫曼编码
    {
    //codetype code[]为求出的哈夫曼编码
    //hufmtree tree[]为已知的哈夫曼树
        if(tree[0].weight==-1)  //如不在内存,则从文件hfmTree中读入
        {
            printf("\n未建立哈夫曼树,已从 hfmTree.txt 中读取哈夫曼树\n");
            FILE *fp;
            fp=fopen("hfmTree.txt","r");
            if(fp==NULL)
            {
                printf("打开 hfmTree.txt 文件失败!\n");
                return ;
            }
            int i=0,T;
            while(EOF!=fscanf(fp,"%d %c %f %d %d %d\n",&T,&tree[i].ch,&tree[i].weight,&tree[i].parent,&tree[i].lchild,&tree[i].rchild))
            {
                i++;
            }
            m=i;
            n=(m+1)/2;
            printf("%d %d\n\n",n,m);
            fclose(fp);
        }
        int i,c,j,p;
        codetype cd;   //缓冲变量
        for(i=0; i<n; i++)
        {
            cd.start=n;
            cd.ch=tree[i].ch;
            c=i;       //从叶结点出发向上回溯
            p=tree[i].parent;   //tree[p]是tree[i]的双亲
            while(p!=0)
            {
                cd.start--;
                if(tree[p].lchild==c)
                    cd.bits[cd.start]='0';   //tree[i]是左子树,生成代码'0'
                else
                    cd.bits[cd.start]='1';   //tree[i]是右子树,生成代码'1'
                c=p;
                p=tree[p].parent;
            }
            code[i]=cd;    //第i+1个字符的编码存入code[i]
        }
        printf("每个字符的哈夫曼编码如下:\n");
        for(i=0; i<n; i++)
        {
            if(code[i].ch=='-')
                printf("空格: ");
            else
            printf("%4c: ",code[i].ch);
            for(j=code[i].start; j<n; j++)
                printf("%c",code[i].bits[j]);
            printf("\n");
        }
    
        FILE *in,*out;
        in=fopen("ToBeTran.txt","r");
        out=fopen("CodeFile.txt","w");
        if(in==NULL||out==NULL)
        {
            printf("打开文件失败\n");
            return ;
        }
        printf("请选择你的操作 从文件 ToBeTran.txt 中读取(1)/手动输入字符(2):");
        int T,cnt=0;
        char s[10000];
        scanf("%d",&T);
        getchar();
        if(T==1)
        {
            while(EOF!=fscanf(in,"%c",&s[cnt]))
            {
                if(s[cnt]==' ')
                    s[cnt]='-';
                cnt++;
            }
            s[cnt]=0;
            printf("字符串为:%s\n",s);
        }
        else if(T==2)
        {
            printf("请输入你要输入的字符串(空格用'-'代替):");
            scanf("%s",s);
        }
        printf("编码为:");
        for(int k=0; s[k]; k++)
        {
            for(int i=0; i<n; i++)
            {
                if(s[k]==code[i].ch)
                {
                    for(int j=code[i].start; j<n; j++)
                    {
                        fprintf(out,"%c",code[i].bits[j]);
                        printf("%c",code[i].bits[j]);
                    }
                }
            }
        }
        printf("\n");
        fclose(in);
        fclose(out);
    }//huffmancode
    
    void decode(hufmtree tree[]) //依次读入电文,根据哈夫曼树译码
    {
        int i=0,j,t;
        char b[maxsize];
        char endflag='2';    //电文结束标志取2
        FILE *in,*out;
        in=fopen("CodeFile.txt","r");
        out=fopen("TextFile.txt","w");
        if(in==NULL)
        {
            printf("打开 CodeFile.txt 文件失败!\n");
        }
        printf("请选择你的操作,从CodeFile.txt读入电文(1)/手动输入电文(2):");
        scanf("%d",&t);
        getchar();
        if(t==1)
        {
            printf("编码为:");
            i=0;
            while(EOF!=fscanf(in,"%c",&b[i]))
            {
                printf("%c",b[i]);
                i++;
            }
            b[i]='2';
            printf("%c\n\n",b[i]);
        }
        else if(t==2)
        {
            printf("请输入电文以 ‘2’ 结束:");
            scanf("%s",b);
        }
        else
        {
            printf("输入错误!请重新输入\n");
            decode(tree);
            return ;
        }
        i=m-1;             //从根结点开始往下搜索
        j=0;
        printf("译码后的字符为");
        while(b[j]!='2')
        {
            if(b[j]=='0')
                i=tree[i].lchild;   //走向左孩子
            else
                i=tree[i].rchild;   //走向右孩子
            if(tree[i].lchild==-1)     //tree[i]是叶结点
            {
                printf("%c",tree[i].ch);
                fprintf(out,"%c",tree[i].ch);
                i=m-1;      //回到根结点
            }
            j++;
        }
        printf("\n");
        if(tree[i].lchild!=-1&&b[j]!='2')   //电文读完,但尚未到叶子结点
            printf("\nERROR\n");  //输入电文有错
        fclose(in);
        fclose(out);
    }//decode
    void print()  //输出 Codefile.txt
    {
        FILE *in,*out;
        char ch;
        int cnt=0;
        in=fopen("CodeFile.txt","r");
        out=fopen("CodePrin.txt","w");
        if(in==NULL||out==NULL)
        {
            printf("打开文件失败\n");
            return ;
        }
        while(EOF!=fscanf(in,"%c",&ch))
        {
            if(++cnt%50==0)
            {
                printf("\n");
                fprintf(out,"\n");
            }
            printf("%c",ch);
            fprintf(out,"%c",ch);
        }
        printf("\n");
        fprintf(out,"\n");
        fclose(in);
        fclose(out);
    }
    void TreePrinting()  //打印哈夫曼树
    {
        FILE *in,*out;
        int num;
        in=fopen("hfmTree.txt","r");
        out=fopen("TreePrint.txt","w");
        if(in==NULL||out==NULL)
        {
            printf("打开文件失败\n");
            return ;
        }
        hufmtree a;
        printf("|--------------------------------------------|\n");
        fprintf(out,"|--------------------------------------------|\n");
        printf("|节点 字符 | 权值 | 父节点 | 左孩子 | 右孩子 |\n");
        fprintf(out,"|节点 字符 | 权值 | 父节点 | 左孩子 | 右孩子 |\n");
        while(EOF!=fscanf(in,"%d %c %f %d %d %d\n",&num,&a.ch,&a.weight,&a.parent,&a.lchild,&a.rchild))
        {
            printf("|%4d %3c %7.1f %7d %8d %7d   |\n",num,a.ch,a.weight,a.parent,a.lchild,a.rchild);
            fprintf(out,"|%4d %3c %7.1f %7d %8d %7d   |\n",num,a.ch,a.weight,a.parent,a.lchild,a.rchild);
        }
        printf("|--------------------------------------------|\n");
        fprintf(out,"|--------------------------------------------|\n");
        fclose(in);
        fclose(out);
    }
    
    
    更多相关内容
  • 设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(后缀名.cod);反过来,可将一个编码文件还原为一个文本文件(.txt)。 要求: (1)输入一个待编码的文本文件名,统计文本文件中...
  • 哈夫曼编码/译码器

    千次阅读 2022-05-13 16:48:38
    哈夫曼编码/译码器


    一、设计任务及要求

    哈夫曼编码是一种最优变长码,即带权路径最小。这种编码有很强的应用背景,是数据压缩中的一个重要理论依据。对输入的一串文字符号实现哈夫曼编码,再对哈夫曼编码生成的代码串进行译码,输出电文字符串。要求完成以下功能:

    1. 针对给定的字符串,建立哈夫曼树。
    2. 生成哈夫曼编码。
    3. 对编码文件译码。

    二、设计导向

    1. 设计目的

    (1) 巩固和加深对数据结构课程所学知识的理解,了解并掌握数据结构与算法的设计方法;
    (2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
    (3) 提高综合运用所学的理论知识和方法,独立分析和解决问题的能力;
    (4) 训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风;
    (5) 培养查阅资料,独立思考问题的能力。

    2. 设计课题

    哈夫曼编译码器的主要功能是先建立哈夫曼树,然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。在数据通信中,通常需要将传送文字转换成由二进制字符0,1组成的二进制串,称之为编码。构建一个哈夫曼树,设定哈夫曼树中的左分支为0,右分支代表1,则从根结点到每个叶子节点所经过的路径组成的0和1的序列便为该节点对应字符的编码,称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码,让出现频率高的字符具有较短的编码,让出现频率低的字符具有较长的编码,这样可以有效缩短传送文字的总长度。哈夫曼树则是用于构造使编码总长最短,最节省空间成本的编码方案。

    设计包含几个方面:
    (1)哈夫曼树的建立
    哈夫曼树的建立由哈夫曼算法的定义可知,初始森林中共有n课只含有根节点的二叉树,算法的第二步是:当前森林中两颗根节点权值最小的二叉树,合并为一个新的二叉树,每合并一次,森林中就减少一棵树,产生一个新节点,要进行n-1次的合并,共产生n-1个新节点,他们都是具有两个孩子的分支节点。由此可知,最终得到的哈夫曼树中一共有2n-1个节点,其中n个节点是由初始森林的n个孤立节点,哈夫曼树中没有度数为1的分支节点,我们可以利用一个大小为2n-1的一维数组来存储哈夫曼树中的节点。

    (2)哈夫曼编码
    首先定义哈夫曼编码类型,根据实际需要定义类型如下:

    Typedef struct//结点的结构
    {
    	unsigned int weight;
    	unsigned int parent,lchild,rchild;
    }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
    Typedef char * *HuffmanCode;//动态分配数组存储哈夫曼树
    

    (3)代码文件的译码
    译码的思路是:读取文件中的编码,并与原先生成的哈夫曼编码表进行比较,遇到相等时,取出相应字符存入一个新字符串中。

    3. 总体设计方案

    设计哈夫曼编码译码器的总体思路:
    (1)首先建立哈夫曼树,将哈夫曼树初始化,输入权值及字符建立哈夫曼树。
    (2)输出哈夫曼的被编码的字符及对应的编码。
    (3)输入要译码的哈夫曼编码字符串进行译码。

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

    4. 详细设计

    (1) 建树模块
    在建立哈夫曼树时需要录入字符及其权值。

    (2) 设计思路
    在建立哈夫曼树时输入的字符及权值的个数不确定,因此采用了动态分配存储的方法。因为在后面要输出编码的字符及对应的哈夫曼编码,要统计输入了几个字符所以输入字符函数有一个返回值,返回所输入字符的个数。并且在选最初的两个结点时,要找两个权值最小的两个,则该两个结点从原来结点中删除,在此用了给它们赋最大权值。

    (3) 流程图
    建树模块流程图

    (4) 编码模块
    ① 设计思路
    在已建立的哈夫曼的基础上,逆向求哈夫曼编码。利用动态分配存储的方式,因为是逆向存储,所以也应逆向存储哈夫曼编码。

    ② 流程图
    在这里插入图片描述
    (5) 译码模块
    ① 设计思路
    动态分配存储输入的编码,遍历哈夫曼树,若编码等于0,向左遍历其左子树,并判断其左右孩子是否为零,若为都零则输出其data域中的字符并存储。并判断输入的编 码是否读到‘\0’ ,是也退出循环,并判断退出时结点的左右孩子是否都为零,是则为完全译码否就为不完全译码。

    ② 流程图
    译码模块流程图

    5. 系统测试与结果分析

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

    三、课程设计总结

    1. 这次课程设计的心得体会通过实践我的收获如下:
      ① 巩固和加深了对数据结构的理解,提高综合运用本课程所学知识的能力。
      ② 培养了我选用参考书,查阅手册及文献资料的能力。培养独立思考,深入研究,分析问题、解决问题的能力。
      ③ 通过实际编译系统的分析设计、编程调试,掌握应用软件的分析方法和工程设计方法。
      ④ 通过课程设计,培养了我严肃认真的工作作风,逐步建立正确的生产观念、经济观念和全局观念。

    2. 根据我在实习中遇到得问题,我将在以后的学习过程中注意以下几点:
      ① 认真上好专业实验课,多在实践中锻炼自己。
      ② 写程序的过程中要考虑周到,严密。
      ③ 在做设计的时候要有信心,有耐心,切勿浮躁。
      ④ 认真的学习课本知识,掌握课本中的知识点,并在此基础上学会灵活运用。
      ⑤ 在课余时间里多写程序,熟练掌握在调试程序的过程中所遇到的常见错误,以便能节省调试程序的时间。

    通过这次课程设计,让我对一个程序的数据结构有更全面更进一步的认识,根据不同的需求,采用不同的数据存储方式,不一定要用栈,二叉树等高级类型有时用基本的一维数组,只要运用得当,也能达到相同的效果,甚至更佳,就如这次的课程设计,通过用for的多重循环,舍弃多余的循环,提高了程序的运行效率。在编写这个程序的过程中,我复习了之前学的基本语法,哈弗曼树最小路径的求取,哈弗曼编码及译码的应用范围,程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中,体现出自己单独设计模具的能力以及综合运用知识的能力,体会了学以致用、突出自己劳动成果的喜悦心情,也从中发现自己平时学习的不足和薄弱环节,从而加以弥补。

    通过本次数据结构的课设计,我学习了很多在上课没懂的知识,并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解,更巩固了课堂中学习有关于哈夫曼编码的知识,真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做,而是首先要先对它有个大概的了解,接着再详细地分析每一步怎么做,无论自己以前是否有处理过相似的问题,只要按照以上的步骤,必会顺利地做出来。

    这次课程设计,我在编辑中犯了不应有的错误,设计统计字符和合并时忘记应该怎样保存数据,对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏,我的程序有了更高的质量。

    四、 附录:源程序清单

    #include<iostream>
    #include<string.h>
    #define MAX_MA 1000
    #define MAX_ZF 100
    using namespace std;
    
    //哈夫曼树的顺序储存表示
    typedef struct 
    {
        int weight;  //结点的权值
        int parent,lchild,rchild;  //结点的双亲,左孩子,右孩子的下标
    } HTNode,*HuffmanTree;  //动态分配数组来储存哈夫曼树的结点
    //哈夫曼编码表的储存表示
    typedef char **HuffmanCode;  //动态分配数组来储存哈夫曼编码
    
    //在哈夫曼树HT中选择两个双亲域为0且权值最小的两个结点,并返回它们在HT中的序号s1和s2
    void Select(HuffmanTree HT,int len,int &s1,int &s2) 
    {  //len代表HT数组的长度
        int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;  //先赋予最大值
        for(i=1; i<=len; i++) 
    	{
            if(HT[i].weight<min1 && HT[i].parent==0)
    		{
                min1=HT[i].weight;
                s1=i;
            }
        }
        int temp=HT[s1].weight;  //将原值存放起来,然后先赋予最大值,防止s1被重复选择
        HT[s1].weight=0x3f3f3f3f;
        for(i=1; i<=len; i++) 
    	{
            if(HT[i].weight<min2 && HT[i].parent==0) 
    		{
                min2=HT[i].weight;
                s2=i;
            }
        }
        HT[s1].weight=temp;  //恢复原来的值
    }
    
    //构造哈夫曼树HT
    void CreatHuffmanTree(HuffmanTree &HT,int n) 
    {
        int s1,s2;
        if(n<=1)
            return;
        int m=2*n-1;  //当n大于1时,n个叶子结点需要2*n-1个结点
        HT=new HTNode[m+1];  //0号单元未用,所以需要动态分配m+1个单元,HT[m]表示根结点
        //将1~m号单元中的双亲、左孩子,右孩子的下标都初始化为0
        for(int i=1; i<=m; ++i) 
    	{
            HT[i].parent=0;
            HT[i].lchild=0;
            HT[i].rchild=0;
        }
        cout<<"请输入叶子结点的权值:";
        //输入前n个单元中叶子结点的权值
        for(int i=1; i<=n; ++i) 
    	{
            cin>>HT[i].weight;
        }
        //通过n-1次的选择、删除、合并来创建哈夫曼树
        for(int i=n+1; i<=m; ++i) 
    	{
            //在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,并返回它们在HT中的序号s1和s2
            Select(HT,i-1,s1,s2);
            //得到新结点i,从森林中删除s1,s2,将s1和s2的双亲域由0改为i
            HT[s1].parent=i;
            HT[s2].parent=i;
            //s1,s2分别作为i的左右孩子
            HT[i].lchild=s1;
            HT[i].rchild=s2;
            //i的权值为左右孩子权值之和
            HT[i].weight=HT[s1].weight+HT[s2].weight;
        }
    }
    
    //哈夫曼编码
    void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n) 
    {
        //从叶子到根逆向求每个字符的哈夫曼编码,存储在编码表HC中
        HC=new char*[n+1];  //分配n个字符编码的编码表空间(头指针矢量)
        char *cd=new char[n];  //分配临时存放编码的动态数组空间
        cd[n-1]='\0';  //编码结束符
        //从叶子开始逐个字符求哈夫曼编码
        for(int i=1; i<=n; ++i) 
    	{
            int start=n-1;  //start开始时指向最后,即编码结束符位置
            int c=i;
            int f=HT[i].parent;  //f是指向结点c的双亲结点
            //从叶子结点开始向上回溯,直到根结点
            while(f!=0) 
    		{
                --start;  //回溯一次,start向前指向一个位置
                //判断是结点c是f的左孩子还是右孩子
                if(HT[f].lchild==c) 
    			{
                    cd[start]='0';  //结点c是f的左孩子,则生成代码0
                } 
    			else 
    			{
                    cd[start]='1';  //结点c是f的右孩子,则生成代码1
                }
                c=f;
                f=HT[f].parent;  //继续向上回溯
            }  //求出第i个字符的编码
            HC[i]=new char[n-start];  //为第i个字符编码分配空间
            strcpy(HC[i],&cd[start]);  //将求得的编码从临时空间cd复制到HC的当前行中
        }
        delete cd;  //释放临时空间
    }
    
    //哈夫曼译码
    void HuffmanDecoding(HuffmanTree HT,char a[],char zf[],char b[],int n) 
    {
        //a[]用来传入二进制编码,b[]用来记录译出的字符
        //zf[]是与哈夫曼树的叶子对应的字符,n是字符个数相当于zf[]数组的长度
        int q=2*n-1;  //q初始化为根结点的下标
        int k=0;  //记录存储译出字符数组的下标
        for(int i=0; a[i]!='\0'; i++) 
    	{  //for循环结束条件是读入的字符是结束符
            //判断读入的二进制字符是0还是1
            if(a[i]=='0') 
    		{
                //读入0,把根结点(HT[q])的左孩子的下标值赋给q,
                //下次循环的时候把HT[q]的左孩子作为新的根结点
                q=HT[q].lchild;
            } else if(a[i]=='1') 
    		{
                //读入1,把根结点(HT[q])的右孩子的下标值赋给q,
                //下次循环的时候把HT[q]的右孩子作为新的根结点
                q=HT[q].rchild;
            }
            //判断HT[q]是否为叶子结点
            if(HT[q].lchild==0 && HT[q].rchild ==0) 
    		{
                //如果读到一个结点的左孩子和右孩子都为0,是叶子结点,
                //说明已经译出一个字符,该字符的下标就是找到的叶子结点的下标
                b[k++]=zf[q];  //把下标为q的字符赋给字符数组b[]
                q=2*n-1;  //初始化q为根结点的下标
            } //继续译下一个字符的时候从哈夫曼树的根结点开始
        }
        //译码完成之后,用来记录译出字符的数组由于没有结束符输出的时候会报错,
        //所以紧接着把一个结束符加到数组最后
        b[k] = '\0';
    }
    
    void menu() 
    {
        int n;//记录要编码的字符个数
        char a[MAX_MA];//储存输入的二进制字符
        char b[MAX_ZF];//存储译出的字符
        char zf[MAX_ZF];//储存要编码的字符
        HuffmanTree HT=NULL;//初始化树为空树
        HuffmanCode HC=NULL;//初始化编码表为空表
            cout<<" =============================================================================\n";
            cout<<"||                ★★★★★★★哈夫曼编码与译码★★★★★★★                ||\n";
            cout<<"||============================================================================||\n";
            cout<<"||============================================================================||\n";
            cout<<"||                     【1】--- 创建哈夫曼树                                  ||\n";
            cout<<"||                     【2】--- 进行哈夫曼编码                                ||\n";
            cout<<"||                     【3】--- 进行哈夫曼译码                                ||\n";
            cout<<"||                     【4】--- 退出程序                                      ||\n";
            cout<<" ==============================================================================\n";
            cout<<"请输入数字来选择对应的功能:";
        while(1) 
    	{
            int num;
            if(!(cin>>num)) 
    		{
                cout<<"输入格式错误!请重新输入:"<<endl;
            } 
    		else 
    		{
                switch(num) 
    			{
                    case 1:
                        cout<<"请输入字符个数:";
                        cin>>n;
                        cout<<"请依次输入"<<n<<"个字符: ";
                        for(int i=1; i<=n; i++)
                            cin>>zf[i];
                        CreatHuffmanTree(HT,n);
                        cout<<endl;
                        cout<<"创建哈夫曼成功!下面是该哈夫曼树的参数输出:"<<endl;
                        cout<<endl;
                        cout<<"结点"<<"\t"<<"字符"<<"\t"<<"权值"<<"\t"<<"双亲"<<"\t"<<"左孩子"<<"\t"<<"右孩子"<<endl;
                        for(int i=1; i<=2*n-1; i++) 
    					{
                            cout<<i<<"\t"<<zf[i]<<"\t"<<HT[i].weight<<"\t"<<HT[i].parent <<"\t"<< HT[i].lchild<<"\t"<<HT[i].rchild<<endl;
                        }
                        cout<<"请输入数字来选择对应的功能:";
                        break;
                    case 2:
                        HuffmanCoding(HT, HC, n);
                        cout<<"生成哈夫曼编码表成功!下面是该编码表的输出:"<<endl;
                        cout<<endl;
                        cout<<"结点"<<"\t"<<"字符"<<"\t"<<"权值"<<"\t"<<"编码"<<endl;
                        for(int i=1; i<=n; i++) 
    					{
                            cout<<i<<"\t"<<zf[i]<<"\t"<<HT[i].weight<<"\t"<<HC[i]<<endl;
                        }
                        cout<<"请输入数字来选择对应的功能:";
                        break;
                    case 3:
                        cout<<"请输入想要翻译的一串二进制编码:";
                        cin>>a;
                        HuffmanDecoding(HT,a,zf,b,n);
                        cout<<"译码成功!翻译结果为:"<<b<<endl;
                        cout<<"请输入数字来选择对应的功能:";
                        break;
                    case 4:
                        cout<<"\n\n";
                        cout<<"\n*************************************************"<<endl;
                        cout<<"\n******                                     ******"<<endl;
                        cout<<"\n******     谢谢使用哈夫曼编码与译码程序    ******"<<endl;
                        cout<<"\n******                                     ******"<<endl;
                        cout<<"\n*************************************************"<<endl;
                        exit(0);
                    default:
                        cout<<"输入错误!没有此功能!请重新输入!"<<endl;
                        cout<<endl;
                }
            }
        }
    }
    
    int main() 
    {
        menu();
        return 0;
    }
    
    展开全文
  • windows程序
  • 题目8:哈夫曼编码/译码器 实验类型(验证/设计/创新):设计 学时:16 课程设计内容: 设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件;反过来,可将一个编码文件译码还原为一...

    题目8:哈夫曼编码/译码器 实验类型(验证/设计/创新):设计 学时:16
    课程设计内容:
    设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件;反过来,可将一个编码文件译码还原为一个文本文件(.txt)。要求:
    7.输入一个待压缩的文本文件名, 统计文本文件中各字符的个数作为权值,生成哈夫曼树;
    8.将文本文件利用哈夫曼树进行编码,生成压缩文件;
    9.输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码;
    10.可显示指定的压缩文件和文本文件;
    课程设计要求:
    熟练掌握哈夫曼树的构建方法;能够运用哈夫曼树实现哈夫曼编码和译码。
    重点难点:
    【本课程设计重点】哈夫曼树的构建和哈夫曼编码。
    【本课程设计难点】各字符出现频率的统计、哈夫曼树的构建和哈夫曼译码。

    //
    // Created by andyzhong on 2021/7/1.
    //
    #include<iostream>
    
    #include<cstdio>
    
    #include<cstring>
    
    #include<cstdlib>
    
    
    
    using namespace std;
    
    
    
    char filenamemi[100];
    
    char filefile[100];
    
    char filebian[100];
    
    
    
    typedef struct
    
    {
        int weight;
    
        char flag;
    
        int parent, lchild, rchild;
    
    } HTNode, *HuffmanTree;
    
    typedef struct ASCII
    
    {
        char flag;
    
        int c;
    
        struct ASCII *next;
    
    } ASCII, *LinkList;
    
    typedef struct txt
    
    {
        char flag;
    
        char huffman[5000];
    
    } txtNode;
    
    
    
    LinkList L;
    
    typedef char **HuffmanCode;
    
    
    
    bool InitList(LinkList &L)//初始化链表
    
    {
        L = new ASCII;
    
        L->c  = 1;
    
        L->next = NULL;
    
        return true;
    
    }
    
    
    
    void Show(LinkList L)//显示链表
    
    {
        LinkList p;
    
        p = L->next;
    
        while(p)
    
        {
            printf("  %c, %d\n", p->flag, p->c);
    
            p = p->next;
    
        }
    
        cout<<endl;
    
    }
    
    
    
    int Choice() //选择文件以及创建权重值
    
    {
        FILE *fp;
    
        char a;
    
        int num = 0, key = 0;
    
        int instance = 0;
    
        LinkList  p, s, m;
    
        InitList(L);
    
        s = L;
    
        m = L;
    
        getchar();
    
        //char filefile[100] ;
    
        while(!key)
    
        {
            printf("请输入你要打开的文件名及路径,如c:\\users\\lenovo\\desktop\\7\\1.txt\n");
    
            gets(filefile);
    
            if ((fp=fopen(filefile,"r"))==NULL)
    
            {
                printf("打开文件%s出现错误\n",filefile);
    
                key = 0;
    
                return 0;
    
            }
    
            key = 1;
    
        }
    
    
    
        while((a = fgetc(fp)) != EOF)
    
        {
            s = L->next;
    
            printf("%c ", a);
    
            while(s)
    
            {
                if(s->flag == a)//如果在文本中出现了, 当前字符, 那么当前字符的权重值++
    
                {
                    s->c++;
    
                    instance = 1;
    
                    break;
    
                }
    
                s = s->next;
    
            }
    
            if(instance == 0)//如果当前文本没有该字符, 那么, 创建该字符,插入到文本当中
    
            {
                p = new ASCII;
    
                p->flag = a;
    
                p->c = 1;
    
                m->next = p;
    
                p->next = NULL;
    
                m = p;
    
                num++;//文本中多少结点
    
            }
    
            instance = 0;
    
        }
    
        cout<<endl;
    
        Show(L);
    
        fclose(fp);
    
        return num;
    
    }
    
    
    
    void Select(HuffmanTree &HT, int num, int *s1, int *s2) //寻找两个最小的且双亲为0的最小节点
    
    {
        int i, sec = 0, fir = 0;//a是次小, b是最小
    
        int second = -1, first = -1;
    
        HTNode L1, L2;//L1次小, L2最小
    
        for(i = num; i >= 1; i--)//选择两个双亲部不为0的结点
    
        {
            if(HT[i].parent == 0 && second == -1) second = i;
    
            else if(HT[i].parent == 0 && first == -1) first = i;
    
    
    
            if(first!=-1 && second!=-1) break;
    
        }
    
        //cout<<second<<" "<<first<<endl;
    
        if(HT[second].weight > HT[first].weight)
    
        {
            L1 = HT[second];
    
            L2 = HT[first];
    
            sec = second;
    
            fir = first;
    
        }
    
        else
    
        {
            L1 = HT[first];
    
            L2 = HT[second];
    
            sec = first;
    
            fir = second;
    
        }
    
    
    
        for(i = num; i >= 1; i--)//从剩下的节点中找到两个最小的节点
    
        {
            if( (HT[i].weight < L2.weight) &&(HT[i].parent == 0) && i!=second && i!=first)
    
            {
                L1 = L2;
    
                L2 = HT[i];
    
                sec = fir;
    
                fir = i;
    
            }
    
            else if( (HT[i].weight < L1.weight) && (HT[i].parent == 0) && i!=second && i!=first)
    
            {
                L1 = HT[i];
    
                sec = i;
    
            }
    
        }
    
        *s1 = fir;
    
        *s2 = sec;
    
    }
    
    
    
    bool CreatHuffmanaTree(HuffmanTree &HT, int num) //创建哈夫曼树
    
    {
        int m, i;
    
        LinkList p;
    
        p = L->next;
    
        if(num <= 1) return false;
    
        m = 2*num-1;
    
        HT = new HTNode[m+1];
    
        for(i = 1; i <= m; i++)
    
        {
            HT[i].parent = 0;
    
            HT[i].lchild = 0;
    
            HT[i].rchild = 0;
    
        }
    
        for(i = 1; i <= num; i++)
    
        {
            HT[i].weight = p->c;
    
            HT[i].flag = p->flag;
    
            p = p->next;
    
        }
    
    
    
        int s1=0, s2=0;
    
        for(i = num+1; i <= m; i++)
    
        {
            Select(HT, i-1, &s1, &s2);
    
            //cout<<s1<<" "<<s2<<endl;
    
            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 true;
    
    }
    
    
    
    bool CreatHuffmanaCode(HuffmanTree HT, int num) //创建哈夫曼编码
    
    {
        char  *cd;
    
        int i, c, f, start, key = 0;
    
        FILE *fp;
    
        char flag;
    
        getchar();
    
        while(!key)
    
        {
            printf("请输入你要保存密码本的文件名及路径,如c:\\users\\lenovo\\desktop\\7\\密码本.txt\n");
    
            gets(filenamemi);
    
            if ((fp=fopen(filenamemi,"w"))==NULL)
    
            {
                printf("保存文件%s出现错误, 请重新输入\n",filenamemi);
    
                key = 0;
    
            }
    
            key = 1;
    
        }
    
        cd = new char[num];
    
        cd[num-1] = '\0';
    
        for(i = 1; i <= num; i++)
    
        {
            start = num-1;
    
            c = i;
    
            f = HT[i].parent;
    
            flag = HT[i].flag;
    
            while(f != 0)
    
            {
                --start;
    
                if(HT[f].lchild == c) cd[start] = '0';
    
                else cd[start] = '1';
    
                c = f;
    
                f = HT[f].parent;
    
            }
    
            printf("%c %s\n", flag, &cd[start]);
    
            fprintf(fp,"%c %s\n", flag, &cd[start]);
    
        }
    
        delete cd;
    
        fclose(fp);
    
    }
    
    bool CreatTxtCode(int num)//创建文本编码
    
    {
        FILE *fp, *fp1, *fp2;
    
        int key = 0;
    
        //char filename[100];
    
        txtNode txt[257];
    
        char a;
    
        getchar();
    
        while(!key)
    
        {
            printf("请输入你要保存编码的文件名及路径,如c:\\users\\lenovo\\desktop\\7\\1.cod\n");
    
            gets(filebian);
    
            if ((fp=fopen(filebian,"w"))==NULL)
    
            {
                printf("保存文件%s出现错误, 请重新输入\n",filebian);
    
                key = 0;
    
            }
    
            key = 1;
    
    
    
        }
    
        int i = 0, nu = 1, j;
    
        fp1 = fopen(filenamemi,"r");
    
        fp2 = fopen(filefile,"r");
    
        char interim[1000];
    
        fgets(interim, 100, fp1);
    
        while(!feof(fp1))
    
        {
            txt[nu-1].flag = interim[0];
    
            i = strlen(interim);
    
            for(j = 2; j < i-1; j++)
    
            {
                txt[nu-1].huffman[j-2] = interim[j];
    
            }
    
            fgets(interim, 100, fp1);
    
            nu++;
    
        }
    
        for(i = 0; i <= nu; i++)
    
        {
            cout<<txt[i].flag<<"  "<<txt[i].huffman<<endl;
    
        }
    
        while((a = fgetc(fp2)) != EOF)
    
        {
            for(i = 0; i <= nu; i++)
    
            {
                if(a == txt[i].flag)
    
                {
                    fprintf(fp,"%s",txt[i].huffman);
    
                }
    
            }
    
        }
    
        fclose(fp);
    
        fclose(fp1);
    
        fclose(fp2);
    
        return true;
    
    }
    
    bool ReductionTxt(HuffmanTree HT, int num)//创建文本节点
    
    {
        FILE *fp, *fp1;//fp----编码文件    fp1------还原之后的文件
    
        int key = 0;
    
        char filename[100],  filename1[100];
    
        char a;
    
        getchar();
    
        if ((fp=fopen(filebian,"r"))==NULL)
    
        {
            printf("打开文件%s出现错误\n",filebian);
    
            key = 0;
    
            return false;
    
        }
    
        while(!key)
    
        {
            printf("请输入你要保存的文件名及路径,如c:\\users\\lenovo\\desktop\\7\\2.txt\n");
    
            gets(filename1);
    
            if ((fp1=fopen(filename1,"w"))==NULL)
    
            {
                printf("打开文件%s出现错误\n",filename1);
    
                key = 0;
    
                return false;
    
            }
    
            key = 1;
    
        }
    
    
    
        int kk = 2*num-1;
    
        while((a = fgetc(fp)) != EOF)
    
        {
            if(a == '0')
    
            {
                kk = HT[kk].lchild;
    
            }
    
            else
    
            {
                kk = HT[kk].rchild;
    
            }
    
    
    
            if( (HT[kk].lchild == 0)  && (HT[kk].rchild == 0) )
    
            {
                fprintf(fp1,"%c", HT[kk].flag);
    
                kk = 2*num-1;
    
            }
    
        }
    
        fclose(fp);
    
        fclose(fp1);
    
        return true;
    
    }
    
    
    
    void zip()//压缩文件
    
    {
        int fpnumber=0,fp1number=0;
    
        FILE *fp, *fp1;//fp----编码文件    fp1------压缩文件
    
        int key = 0, in, i;
    
        char filename[100],  filename1[100];
    
        char a;
    
        int twopower[11] = {1,2,4,8,16,32,64,128,256,512,1024};
    
        getchar();
    
        if ((fp=fopen(filebian,"r"))==NULL)
    
        {
            printf("打开文件%s出现错误\n",filebian);
    
            key = 0;
    
            return;
    
        }
    
        key = 0;
    
        while(!key)
    
        {
            printf("请输入保存的文件名及路径,如C:\\users\\lenovo\\desktop\\7\\2.cod\n");
    
            gets(filename1);
    
            if ((fp1=fopen(filename1,"w"))==NULL)
    
            {
                printf("打开文件%s出现错误\n",filename1);
    
                key = 0;
    
                return ;
    
            }
    
            key = 1;
    
        }
    
        //fp1=fopen("C:\\users\\lenovo\\desktop\\7\\2.cod","w");
    
        in = 0;
    
        int sum = 0, fla = 2;
    
        a = fgetc(fp);
    
        while(!feof(fp))
    
        {
            sum = sum + int(a-'0')*twopower[7-in];
    
            //cout<<int(a-'0')<<" "<<twopower[in]<<" "<<sum<<endl;
    
            in++;
    
            a = fgetc(fp);
    
            if(in == 8 || feof(fp))
    
            {
                in = 0;
    
                fprintf(fp1, "%d ", sum);
    
                sum = 0;
    
            }
    
        }
    
        fseek(fp,0L,SEEK_END);   /*利用fseek函数将指针定位在文件结尾的位置*/
    
        fpnumber=ftell(fp);   /*利用ftell函数返回指针相对于文件开头的位置,以字节计算*/
    
        printf("原文件所占的字节数为%ld个\n",fpnumber);   /*进行输出*/
    
        fseek(fp1,0L,SEEK_END);   /*利   用fseek函数将指针定位在文件结尾的位置*/
    
        fp1number=ftell(fp1);   /*利用ftell函数返回指针相对于文件开头的位置,以字节计算*/
    
        printf("压缩后所占的字节数为%ld个\n",fp1number);   /*进行输出*/
    
        printf("压缩比为%d/%d",fp1number,fpnumber);
    
        fclose(fp);
    
        fclose(fp1);
    
    }
    
    
    
    
    
    int main()
    
    {
        int num;
    
        HuffmanTree L;
    
        start:
    
        printf("******************************************************************\n\n");
    
        printf("哈夫曼编码译码器\n\n");
    
        printf("*\t1、选择需要进行编码的文件\t\t*\n\n");
    
        printf("*\t2、建立哈夫曼树\t\t\t\t*\n\n");
    
        printf("*\t3、建立密码本并对文件编码\t\t*\n\n");
    
        printf("*\t4、选择需要进行解码的文件并解码\t\t*\n\n");
    
        printf("*\t5、按位压缩方式对文件进行压缩\t\t*\n\n\n");
    
        printf("******************************************************************\n\n");
    
        int option = 0;
    
        cin>>option;
    
        while(1)
    
        {
            switch(option)
    
            {
                case 1:
    
                    num = Choice();
    
                    break;
    
                case 2:
    
                    if(CreatHuffmanaTree(L, num))cout<<"成功"<<endl;
    
                    break;
    
                case 3:
    
                    CreatHuffmanaCode(L, num);
    
                    if(CreatTxtCode(num)) cout<<"成功"<<endl;
    
                    break;
    
                case 4:
    
                    if(ReductionTxt(L, num)) cout<<"成功"<<endl;
    
                    break;
    
                case 5:
    
                    zip();
    
                    cout<<"压缩成功";
    
                    break;
    
            }
    
            goto start;
    
        }
    
        return 0;
    
    }
    

    运行结果:
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 哈夫曼编/译码器 问题描述:给定电文进行哈夫曼编码,给定编码进行哈夫曼译码。要求电文存储在文件1中,编码后的结果存储在文件2中,给定编码存储在文件3中,译码后的结果存储在文件4中。
  • 哈夫曼编/译码系统

    2018-03-06 09:08:17
    问题描述:利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(解码)。对于双工信道(即...
  • [问题描述] 打开一篇英文文章,统计该... 以每个字符出现的次数为权值,建立哈夫曼树,求出哈夫曼编码, 对文件yuanwen中的正文进行编码,将结果存到文件yiwen中,再对文件yiwen中的代码进行译码,结果存到textfile中。
  • 哈夫曼编/译码器

    2021-12-29 09:55:09
    #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 100 #define M 2 * N - 1 typedef struct { char ch; //字符 int weight; //权值 ... //哈夫曼树,0号

    哈夫曼编/译码器

    • 建立哈夫曼树:读入文件(*.source),统计文件中字符出现的频度,并以这些字符的频度作为权值,建立哈夫曼树。
    • 编码:利用已建立好的哈夫曼树,获得各个字符的哈夫曼编码,并对正文进行编码,然后输出编码结果,并存入文件(*.code)中。
    • 译码:利用已建立好的哈夫曼树将文件(.code)中的代码进行译码,并输出译码结果,并存入文件(.decode)中。
    • 以下代码可以实现对大部分中文和英文的编码和译码

    代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define N 100
    #define M 2 * N - 1
    
    
    typedef struct
    {
    	char ch[3];      //字符
    	int weight;     //权值
    	int Parent, Lchild, Rchild;     //双亲,左孩子,右孩子
    }HTNode, HuffmanTree[M + 1];    //哈夫曼树,0号不使用
    
    
    typedef struct
    {
    	char ch[3];     //字符
    	int WEI;     //权值
    }weighting;     //权值
    
    
    typedef struct    //堆串
    {
    	char* s;
    	int len;
    }HString;      //堆串
    
    
    typedef char* HuffmanCode[N];
    
    
    void read(FILE* fp, char str[]);         //读入文件
    weighting* getweight(char str[], weighting w[]);     //计算权值
    void Printvalue(weighting w[]);      //打印权值列表
    void CrtHuffmanTree(HuffmanTree ht, weighting w[], int n);      //建立哈夫曼树
    void select(HuffmanTree ht, int k, int* s1, int* s2);     //选择ht前i-1项中双亲为零且权值最小的两节点s1,s
    void PrintTree(HuffmanTree ht, int n);     //打印哈夫曼树
    void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n);    //哈夫曼编码
    void PrintCode(HuffmanCode hc, int n);     //打印哈夫曼编码
    HString* Coding(char str[], weighting w[], HuffmanCode hc);     //编码并打印,并将编码保存至指定文件
    void Decoding(char code[], HuffmanTree ht, int n);     //译码并保存至Decode.txt文件
    
    
    int main()
    {
    	HuffmanTree H;
    	HuffmanCode T;
    	weighting WEI[10000];
    	HString* STR;
    	FILE* fp = NULL;
    	char str[10000];
    	char code[10000];
    	weighting* W;
    	printf("请输入获取电文的文件:");
    	read(fp, str);
    	W = getweight(str, WEI);     //计算权值
    	int len = W[0].WEI;      //字符串数组长度
    	CrtHuffmanTree(H, W, len);       //建立哈夫曼树
    	CrtHuffmanCode(H, T, len);       //哈夫曼编码
    	PrintCode(T, len);       //打印哈夫曼编码
    	STR = Coding(str, W, T);     //编码并打印
    	printf("请输入获取编码的文件:");
    	read(fp, code);    //读入编码,将编码存入code
    	Decoding(code, H, 2 * len - 1);     //译码
    	return 0;
    }
    
    
    //读入文件
    void read(FILE* fp, char str[])
    {
    	char filename[40];
    	gets_s(filename);
    	fp = fopen(filename, "r");
    	if (fp == NULL)
    	{
    		printf("\nERROR!\n");
    		exit(0);
    	}
    	int i = 0;
    	char c;
    	c = fgetc(fp);
    	if (c == EOF)
    	{
    		printf("文件为空!!!");
    		exit(0);
    	}
    	str[0] = c;
    	i++;
    	while (1)
    	{
    		c = fgetc(fp);
    		if (feof(fp))
    		{
    			str[i] = '\0';
    			break;
    		}
    		str[i] = c;
    		i++;
    	}
    	//fscanf(fp, "%s", str);
    	printf("文件中读出内容为:\n");
    	puts(str);
    	fclose(fp);
    }
    
    
    //构造哈夫曼树
    void CrtHuffmanTree(HuffmanTree ht, weighting w[], int n)
    {
    	int m;
    	m = 2 * n - 1;
    	int i;
    	//初始化哈夫曼树
    	for (i = 1; i <= n; i++)
    	{
    		strcpy(ht[i].ch, w[i].ch);
    		//ht[i].ch = w[i].ch;
    		ht[i].weight = w[i].WEI;
    		ht[i].Rchild = 0;
    		ht[i].Lchild = 0;
    		ht[i].Parent = 0;
    	}
    	for (i = n + 1; i <= m; i++)
    	{
    		ht[i].ch[0] = NULL;
    		ht[i].weight = 0;
    		ht[i].Rchild = 0;
    		ht[i].Lchild = 0;
    		ht[i].Parent = 0;
    	}
    	//给后面的结点赋值
    	for (i = n + 1; i <= m; i++)
    	{
    		//选择树中双亲为0最小的两个值
    		int s1, s2;
    		select(ht, i - 1, &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;
    	}
    	int len = w[0].WEI;
    	PrintTree(ht, 2 * len - 1);
    }
    
    
    //选择ht前i-1项中双亲为零且权值最小的两节点s1,s2
    void select(HuffmanTree ht, int k, int* s1, int* s2)
    {
    	int i;
    	int j = 0;
    	int min1 = 10000;
    	int min2 = 10000;
    	for (i = 1; i <= k; i++)
    	{
    		if (ht[i].weight <= min1 && ht[i].Parent == 0)
    		{
    			*s1 = i;
    			j = i;
    			min1 = ht[i].weight;
    		}
    	}
    	for (i = 1; i <= k; i++)
    	{
    		if (i == j) continue;
    		else
    		{
    			if (ht[i].weight <= min2 && ht[i].Parent == 0)
    			{
    				*s2 = i;
    				min2 = ht[i].weight;
    			}
    		}
    
    	}
    }
    
    
    //哈夫曼编码
    void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n)
    {
    	char* cd;
    	int i;
    	int c;
    	int p;
    	int start;
    	cd = (char*)malloc(n * sizeof(char));      //临时编码数组
    	cd[n - 1] = '\0';      //从叶子节点开始遍历到根,所以首先放置\0
    	for (i = 1; i <= n; i++)      //求每个叶子结点的编码,共有n个叶子结点
    	{
    		start = n - 1;      //从后开始编写编码
    		c = i;      //c为当前节点
    		p = ht[i].Parent;     //p为其双亲
    		while (p != 0)       //当其不为根节点时
    		{
    			start--;          //临时编码数组start指针向前挪动
    			if (ht[p].Rchild == c)
    			{
    				cd[start] = '1';
    			}
    			else
    			{
    				cd[start] = '0';
    			}
    			c = p;
    			p = ht[p].Parent;
    		}
    		hc[i] = (char*)malloc((n - start) * sizeof(char));
    		strcpy(hc[i], &cd[start]);
    	}
    	free(cd);
    }
    
    
    //打印哈夫曼树
    void PrintTree(HuffmanTree ht, int n)
    {
    	int i;
    	printf("\nPrinthuffmantree:\n");
    	printf("字符\tweight\tParent\tLchild\tRchild\n");
    	for (i = 1; i <= n; i++)
    	{
    		if (ht[i].ch[0] == '\n')
    			printf("\\n\t%d\t%d\t%d\t%d\n", ht[i].weight, ht[i].Parent, ht[i].Lchild, ht[i].Rchild);
    		else if (ht[i].ch[0] == NULL)
    			printf("NULL\t%d\t%d\t%d\t%d\n", ht[i].weight, ht[i].Parent, ht[i].Lchild, ht[i].Rchild);
    		else if (ht[i].ch[0] == ' ')
    			printf("' '\t%d\t%d\t%d\t%d\n", ht[i].weight, ht[i].Parent, ht[i].Lchild, ht[i].Rchild);
    		else if (ht[i].ch[2] == '\0')           //判断是否为汉字
    			printf("%s\t%d\t%d\t%d\t%d\n", ht[i].ch, ht[i].weight, ht[i].Parent, ht[i].Lchild, ht[i].Rchild);
    		else
    			printf("%c\t%d\t%d\t%d\t%d\n", ht[i].ch[0], ht[i].weight, ht[i].Parent, ht[i].Lchild, ht[i].Rchild);
    	}
    	printf("\n\n");
    }
    
    
    //打印哈夫曼编码
    void PrintCode(HuffmanCode hc, int n)
    {
    	int i;
    	printf("\nPrintcode:\n");
    	for (i = 1; i <= n; i++)
    	{
    		puts(hc[i]);
    	}
    	printf("\n\n");
    }
    
    
    //计算权值
    weighting* getweight(char str[], weighting* w)
    {
    	int i = 0;
    	int j = 0;
    	int k;
    	int m;
    	char s[3];
    	int len = strlen(str);      //字符串长度
    	for (i = 0, k = 1; i < len; i++, k++)     //遍历字符串,将每一个字符记录下来,并赋初值为1
    	{
    		if ((str[i] < 65 || (str[i] > 90 && str[i] < 97) || str[i] > 122) && str[i] != ' ' && str[i] != '\n' && str[i] != '\0')      //如果是汉字
    		{
    			s[0] = str[i];           //依次存入字符串
    			s[1] = str[i + 1];
    			s[2] = '\0';
    			i++;
    			strcpy(w[k].ch, s);         //拷贝当前字符串到权值列表的字符位置
    			w[k].WEI = 1;
    		}
    		else                   //如果不是汉字
    		{
    			w[k].ch[0] = str[i];        //只接受一个字节放入w[k].ch[0]的位置
    			w[k].WEI = 1;
    		}
    	}
    	char str1[3];
    	int chinese = 0;     //记录汉字的个数
    	for (i = 0, k = 1; i < len; i++, k++)
    	{
    		if ((str[i] < 65 || (str[i] > 90 && str[i] < 97) || str[i] > 122) && str[i] != ' ' && str[i] != '\n' && str[i] != '\0')     //如果是汉字
    		{
    			str1[0] = str[i];
    			str1[1] = str[i + 1];
    			str1[2] = '\0';
    			strcpy(w[k].ch, str1);
    			i++;
    			chinese++;     //记录中文的个数
    		}
    		else
    		{
    			w[k].ch[0] = str[i];
    		}
    		for (j = i + 1; j <= len; j++)
    		{
    			if ((str[j] < 65 || (str[j] > 90 && str[j] < 97) || str[j] > 122) && str[j] != ' ' && str[j] != '\n' && str[j] != '\0')
    			{
    				s[0] = str[j];
    				s[1] = str[j + 1];
    				s[2] = '\0';
    				j++;                 //j向后移动一个字节,移到汉字的下一个字节
    				if (strcmp(str1, s) == 0)
    				{
    					w[k].WEI++;
    				}
    			}
    			else       // 不是汉字的话,直接比较
    			{
    				if (str[i] == str[j])        
    				{
    					w[k].WEI++;
    				}
    			}
    		}
    	}
    	for (i = 1; i <= k; i++)     //遍历数组,去重
    	{
    		for (j = i + 1; j <= k; j++)
    		{
    			if (w[i].ch[2] == '\0')          //之前存储汉字的时候将字符串最后一个字节为'\0',所以判断最后一个字节是否为'\0',就可以知道当前字符是否为汉字,然后确定比较方式
    			{
    				if (strcmp(w[i].ch, w[j].ch) == 0)
    				{
    					w[j].WEI = 0;
    				}
    
    			}
    			else
    			{
    				if (w[i].ch[0] == w[j].ch[0])
    				{
    					w[j].WEI = 0;
    				}
    			}
    		}
    	}
    	k = 1;
    	weighting wnew[10000];      //建立一个新的权值列表
    	for (i = 1; i <= len - chinese; i++)       //长度为原本字符串的长度减去汉字的个数
    	{
    		if (w[i].WEI == 0)  continue;           //将重复字符的跳过
    		else
    		{
    			wnew[k] = w[i];
    			k++;
    		}
    	}
    	wnew[0].WEI = k - 1;                 //权值列表的第0位的WEI值为该权值列表的长度
    	w = wnew;
    	Printvalue(w);
    	return &w[0];
    }
    
    
    //打印权值列表
    void Printvalue(weighting w[])
    {
    	int i;
    	int len = w[0].WEI;
    	printf("\nPrintvalue:\n");
    	printf("字符\tweight\n");
    	for (i = 1; i <= len; i++)
    	{
    		if (w[i].ch[0] == '\n')
    			printf("\\n\t%d\n", w[i].WEI);
    		else if (w[i].ch[0] == ' ')
    			printf("' '\t%d\n", w[i].WEI);
    		else
    		{
    			if (w[i].ch[2] == '\0')               //判断是否为汉字
    			{
    				printf("%s\t%d\n", w[i].ch, w[i].WEI);
    			}
    			else
    			{
    				printf("%c\t%d\n", w[i].ch[0], w[i].WEI);
    			}
    		}
    	}
    	printf("\n\n");
    }
    
    
    //编码并打印
    HString* Coding(char str[], weighting w[], HuffmanCode hc)   //字符串、权值列表、哈夫曼编码
    {
    	HString HS[1000];    //堆串
    	HS->len = 0;
    	int i;
    	FILE* fp;
    	char filename[40];
    	int len = strlen(str);
    	int length = w[0].WEI;
    	int j;
    	char s[3];
    	int k = 0;
    	char ch;
    	int flag;
    	for (i = 0; i < len; i++)     //遍历字符串
    	{
    		if ((str[i] < 65 || (str[i] > 90 && str[i] < 97) || str[i] > 122) && str[i] != ' ' && str[i] != '\n' && str[i] != '\0')
    		{
    			s[0] = str[i];
    			s[1] = str[i + 1];
    			s[2] = '\0';
    			i++;
    			flag = 1;
    		}
    		else
    		{
    			flag = 0;
    		}
    		for (j = 1; j <= length; j++)
    		{
    			if (strcmp(s, w[j].ch) == 0 && flag == 1)
    			{
    				HS[k].s = hc[j];
    				k++;
    				HS->len++;
    				break;
    			}
    			if (w[j].ch[0] == str[i] && flag == 0)
    			{
    				HS[k].s = hc[j];
    				k++;
    				HS->len++;
    				break;
    			}
    
    		}
    	}
    	printf("编码结果:");
    	for (i = 0; i < HS->len; i++)
    	{
    		//puts(HS[i].s);
    		printf("%s", HS[i].s);
    	}
    	printf("\n");
    	printf("请输入要保存编码的文件:");
    	gets_s(filename);
    	printf("\n");
    	fp = fopen(filename, "w");
    	if (fp == NULL)
    	{
    		printf("\nERROR!\n");
    		exit(0);
    	}
    	for (i = 0; i < HS->len; i++)
    	{
    		fprintf(fp,"%s",HS[i].s);
    	}
    	fclose(fp);
    	return HS;
    }
    
    
    
    //译码并保存至Decode.txt文件
    void Decoding(char code[], HuffmanTree ht, int n)
    {
    	printf("译码结果将保存至Decode.txt文件\n");
    	FILE* fp;
    	fp = fopen("Decode.txt", "w");      //打开Decode.txt文件
    	int i;
    	int j;
    	int start = n;
    	int len = strlen(code);
    	for (i = 0; i < len; i++)
    	{
    		if (code[i] == '1')
    		{
    			for (j = start; j > 0; j++)     //从哈夫曼树的最底下开始遍历
    			{
    				if (ht[j].Rchild != 0)
    				{
    					start = ht[j].Rchild;
    					break;
    				}
    			}
    			if (ht[start].Lchild == 0)
    			{
    				if (ht[start].ch[2] == '\0')
    				{
    					printf("%s", ht[start].ch);
    					fprintf(fp, "%s", ht[start].ch);
    					start = n;
    				}
    				else
    				{
    					printf("%c", ht[start].ch[0]);
    					fprintf(fp, "%c", ht[start].ch[0]);
    					start = n;
    				}
    			}
    		}
    		if (code[i] == '0')
    		{
    			for (j = start; j > 0; j++)     //从哈夫曼树的最底下开始遍历
    			{
    				if (ht[j].Lchild != 0)
    				{
    					start = ht[j].Lchild;
    					break;
    				}
    			}
    			if (ht[start].Lchild == 0)
    			{
    				if (ht[start].ch[2] == '\0')
    				{
    					printf("%s", ht[start].ch);
    					fprintf(fp, "%s", ht[start].ch);
    					start = n;
    				}
    				else
    				{
    					printf("%c", ht[start].ch[0]);
    					fprintf(fp, "%c", ht[start].ch[0]);
    					start = n;
    				}
    			}
    		}
    	}
    	fclose(fp);
    }
    
    
    
    展开全文
  • 利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向...
  • 哈夫曼编/译码器的设计与实现(结合文件) 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行...
  • 本文主要完成哈夫曼树的建立、哈夫曼编码译码的功能。我们主要运用的数据结构是哈夫曼结点结构和编码结构,采用顺序链表形式存储。整体思路清晰明了,算法通俗易懂,通过调试运行,执行结果真确。
  • 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。该代码设计一个哈夫曼编译码系统: (1)初始化(Initialzation)。从数据文件DataFile.data中读入字符及每个字符的权值,建立...
  • C++实现哈夫曼编码/译码器(数据结构)

    千次阅读 多人点赞 2019-01-19 19:24:07
    设计一个哈夫曼编码译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码,生成编码文件;反过来,可将编码文件译码还原为一个文本文件。 (1) 从文件中读入任意一篇英文短文(文件为ASCII编码,扩展名为...
  • 写一个哈夫曼码的编/译码系统,要求能对要传输的报文进行编码和解码。构造哈夫曼树时,权值小的放左子树,权值大的放右子树,编码时右子树编码为 1,左子树编码为0。 输入表示字符集大小为 n(n <= 100)的正整数...
  • 利用数据结构知识编写哈夫曼编/译码器的程序。 二、需求分析 [题目概述] 利用哈夫曼编码进行通信可以大大提高信道利用率,这要求在发送端通过一个编码系统对待传输预先编码,在接收端将传来的数据进行译码。对于双工...
  • 哈夫曼编/译码器.zip

    2019-10-31 15:12:14
    利用哈夫曼编码进行信息通讯可以大大提高信道利用率, 缩短信息传输时间,降低传输成本。但是, 这要求在发送端通过一个编码系统对待传数据预先编码; 在接收端将传来的数据进行译码( 复原 )。对于双工信道( 即可以双向...
  • ◆5.2③哈夫曼编/译码器

    千次阅读 2020-05-14 17:06:07
    ◆5.2③哈夫曼编/译码器 ** [问题描述] 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成 本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数 据进行译码...
  • 这是本人参考教材以后完成的,感觉这题难度不算很大,但是需要注意的细节较为多一点。 #include #include ...typedef struct //定义哈夫曼树的结构体变量 { int weight; int parent; int LChild; i
  • HUF.zip,HUF,HUF,HUF.vcxproj.filters,hfmtree.dat,新建文本文档.txt,Create_Tree.h,HUF.vcxproj,codefile.dat,Get_Code.h,treeprint.dat,哈夫曼.cpp,De_Code.h,textfile.dat,Debug,HUF.tlog,CL.write.1.tlog,CL....
  • 二叉树的基本操作及哈夫曼编码/译码系统的实现 实验目的和要求 掌握二叉树的二叉链表存储表示及遍历操作实现方法。 实现二叉树遍历运算的应用:求二叉树中叶结点个数、结点总数、二叉树的高度,交换二叉树的左右...
  • 解码 利用已建好的哈夫曼树将文件codefile中的代码进行译码,结果存入文件textfile中 打印 将文件codefile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中 打印哈夫曼树 将已...
  • NOJ数据结构实验007——哈夫曼编/译码器

    千次阅读 多人点赞 2021-04-30 23:24:26
    本题简单思路: 1.先建立一棵哈夫曼树,在建立时需要将叶结点对应的字符记录在树中。 2.我们需要建立一套译码系统,...众所周知,哈夫曼编码是前缀编码,所以我们只需要将记录报文的字符串code与刚才字符串数组hc中每.
  • [NOJ]数据结构实验3.1 哈夫曼编码器 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct HTNode { int weight; int parent,lchild,rchild; char data; }HTNode; ...

空空如也

空空如也

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

哈夫曼编码/译码器