精华内容
下载资源
问答
  • 摘要:作为一种常用的编码方式即哈夫曼编码,很多人在它的原理即应用方面都弄不不清楚,本文主要以哈夫曼编码原理与应用实例及算法流程图俩进一步说明。哈夫曼编码定义哈夫曼编码(Huffman Coding),又称霍夫曼编码,...

    摘要:作为一种常用的编码方式即哈夫曼编码,很多人在它的原理即应用方面都弄不不清楚,本文主要以哈夫曼编码原理与应用实例及算法流程图俩进一步说明。

    哈夫曼编码定义

    哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

    哈夫曼编码原理

    设某信源产生有五种符号u1、u2、u3、u4和u5,对应概率P1=0.4,P2=0.1,P3=P4=0.2,P5=0.1。首先,将符号按照概率由大到小排队,如图所示。编码时,从最小概率的两个符号开始,可选其中一个支路为0,另一支路为1。这里,我们选上支路为0,下支路为1。再将已编码的两支路的概率合并,并重新排队。多次重复使用上述方法直至合并概率归一时为止。从图(a)和(b)可以看出,两者虽平均码长相等,但同一符号可以有不同的码长,即编码方法并不唯一,其原因是两支路概率合并后重新排队时,可能出现几个支路概率相等,造成排队方法不唯一。一般,若将新合并后的支路排到等概率的最上支路,将有利于缩短码长方差,且编出的码更接近于等长码。这里图(a)的编码比(b)好。

    赫夫曼码的码字(各符号的代码)是异前置码字,即任一码字不会是另一码字的前面部分,这使各码字可以连在一起传送,中间不需另加隔离符号,只要传送时不出错,收端仍可分离各个码字,不致混淆。

    实际应用中,除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外,主要问题是解决小符号集合的统计匹配,例如黑(1)、白(0)传真信源的统计匹配,采用0和1不同长度游程组成扩大的符号集合信源。游程,指相同码元的长度(如二进码中连续的一串0或一串1的长度或个数)。按照CCITT标准,需要统计2&mes;1728种游程(长度),这样,实现时的存储量太大。事实上长游程的概率很小,故CCITT还规定:若l表示游程长度,则l=64q+r。其中q称主码,r为基码。编码时,不小于64的游程长度由主码和基码组成。而当l为64的整数倍时,只用主码的代码,已不存在基码的代码。

    长游程的主码和基码均用赫夫曼规则进行编码,这称为修正赫夫曼码,其结果有表可查。该方法已广泛应用于文件传真机中。

    哈夫曼编码算法流程图

    哈夫曼编码的算法是查找最优路径的一种算法,首先在所有未分配parent域的节点中找出最小的两个节点,将他们的全值相加,组成新的节点,并且将它标记为原来两个最小节点的parent。这样调用递归,最后就能够成一颗完整的哈夫曼树。然后对 每个节点进行遍历编码,得到最终的哈夫曼编码库。流程图如下:

    基于哈夫曼编码原理的压缩算法

    哈夫曼算法的过程为:统计原始数据中各字符出现的频率;所有字符按频率降序排列;建立哈夫曼树:将哈夫曼树存入结果数据;重新编码原始数据到结果数据。哈夫曼算法实现流程如图3所示。

    哈夫曼算法的实质是针对统计结果对字符本身重新编码,而不是对重复字符或重复子串编码。实用中.符号的出现频率不能预知,需要统计和编码两次处理,所以速度较慢,无法实用。而自适应(或动态)哈夫曼算法取消了统计,可在压缩数据时动态调整哈夫曼树,这样可提高速度。因此,哈夫曼编码效率高,运算速度快,实现方式灵活。

    采用哈夫曼编码时需注意的问题:

    (1)哈夫曼码无错误保护功能,译码时,码串若无错就能正确译码;若码串有错应考虑增加编码,提高可靠性。

    (2)哈夫曼码是可变长度码,因此很难随意查找或调用压缩文件中间的内容,然后再译码,这就需要在存储代码之前加以考虑。

    (3)哈夫曼树的实现和更新方法对设计非常关键。

    哈夫曼编码应用实例

    哈夫曼编码,主要用途是实现数据压缩。

    设给出一段报文:CAST CAST SAT AT A TASA。字符集合是 { C, A, S, T },各个字符出现的频度(次数)是 W={ 2, 7, 4, 5 }。若给每个字符以等长编码A : 00 T : 10 C : 01 S : 11,则总编码长度为 ( 2+7+4+5 ) * 2 = 36。

    若按各个字符出现的概率不同而给予不等长编码,可望减少总编码长度。各字符出现概率为{ 2/18, 7/18, 4/18, 5/18 },化整为 { 2, 7, 4, 5 }。以它们为各叶结点上的权值, 建立霍夫曼树。左分支赋 0,右分支赋 1,得霍夫曼编码(变长编码)。A : 0 T : 10 C : 110 S : 111。它的总编码长度:7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。霍夫曼编码是一种无前缀编码。解码时不会混淆。带权路径长度达到最小的二叉树即为霍夫曼树。在霍夫曼树中,权值大的结点离根最近。

    霍夫曼算法

    1.由给定的 n 个权值 {w0, w1, w2, …, wn-1},构造具有 n 棵扩充二叉树的森林 F = { T0, T1, T2, …, Tn-1 },其中每棵扩充二叉树 TI 只有一 个带权值 wi 的根结点, 其左、右子树均为空。

    2.重复以下步骤, 直到 F 中仅剩下一棵树为止:

    ① 在 F 中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

    ② 在 F 中删去这两棵二叉树。

    ③ 把新的二叉树加入 F。

    #include 《stdio.h》

    #include 《stdlib.h》

    #include 《string.h》

    #define MAX 32767

    typedef char *HuffmanCode;

    typedef struct

    {

    int Weight;//字母的权

    int Parent,Leftchild,Rightchild;

    }HuffmanTree;

    void Select(HuffmanTree *HT,int n,int *s1,int *s2)

    {

    int min1=MAX;

    int min2=MAX;

    int pos1, pos2;

    int i;

    for(i=0;i《n;i++)

    {

    if(HT[i].Parent==-1)//选择还没有父亲的节点

    {

    if(HT[i].Weight《=min1)

    {

    pos2 = pos1; min2 = min1;

    pos1 = i; min1=HT[i].Weight;

    }

    else if(HT[i].Weight《=min2)

    {

    pos2 = i; min2=HT[i].Weight;

    }

    }

    }

    *s1=pos1;*s2=pos2;

    }

    void CreateTree(HuffmanTree *HT,int n,int *w)

    {

    int m=2*n-1;//总的节点数

    int s1,s2;

    int i;

    for(i=0;i《m;i++)

    {

    if(i《n)

    HT[i].Weight=w[i];

    else

    HT[i].Weight=-1;

    HT[i].Parent=-1;

    HT[i].Leftchild=-1;

    HT[i].Rightchild=-1;

    }

    for(i=n;i《m;i++)

    {

    Select(HT,i,&s1,&s2);//这个函数是从0到n-1中选两个权最小的节点

    HT[i].Weight=HT[s1].Weight+HT[s2].Weight;

    HT[i].Leftchild=s1;

    HT[i].Rightchild=s2;

    HT[s1].Parent=i;

    HT[s2].Parent=i;

    }

    }

    void Print(HuffmanTree *HT,int m)

    {

    if(m!=-1)

    {

    printf(“%d ”,HT[m].Weight);

    Print(HT,HT[m].Leftchild);

    Print(HT,HT[m].Rightchild);

    }

    }

    void Huffmancoding(HuffmanTree *HT,int n,HuffmanCode *hc,char *letters)

    {

    char *cd;

    int start;

    int Current,parent;

    int i;

    cd=(char*)malloc(sizeof(char)*n);//用来临时存放一个字母的编码结果

    cd[n-1]=‘\0’;

    for(i=0;i《n;i++)

    {

    start=n-1;

    for(Current=i,parent=HT[Current].Parent; parent!=-1; Current=parent,parent=HT[parent].Parent)

    if(Current==HT[parent].Leftchild)//判断该节点是父节点的左孩子还是右孩子

    cd[--start]=‘0’;

    else

    cd[--start]=‘1’;

    hc[i]=(char*)malloc(sizeof(char)*(n-start));

    strcpy(hc[i],&cd[start]);

    }

    free(cd);

    for(i=0;i《n;i++)

    {

    printf(“letters:%c,weight:%d,编码为 %s\n”,letters[i],HT[i].Weight,hc[i]);

    printf(“\n”);

    }

    }

    void Encode(HuffmanCode *hc,char *letters,char *test,char *code)

    {

    int len=0;

    int i,j;

    for(i=0;test[i]!=‘\0’;i++)

    {

    for(j=0;letters[j]!=test[i];j++){}

    strcpy(code+len,hc[j]);

    len=len+strlen(hc[j]);

    }

    printf(“The Test : %s \nEncode to be :”,test);

    printf(“%s”,code);

    printf(“\n”);

    }

    void Decode(HuffmanTree *HT,int m,char *code,char *letters)

    {

    int posiTIon=0,i;

    printf(“The Code: %s \nDecode to be :”,code);

    while(code[posiTIon]!=‘\0’)

    {

    for(i=m-1;HT[i].Leftchild!=-1&&HT[i].Rightchild!=-1;position++)

    {

    if(code[position]==‘0’)

    i=HT[i].Leftchild;

    else

    i=HT[i].Rightchild;

    }

    printf(“%c”,letters[i]);

    }

    }

    int main()

    {

    int n=27;

    int m=2*n-1;

    char letters[28]={‘a’,‘b’,‘c’,‘d’,‘e’,‘f’,‘g’,‘h’,‘i’,‘j’,‘k’,‘l’,‘m’,

    ‘n’,‘o’,‘p’,‘q’,‘r’,‘s’,‘t’,‘u’,‘v’,‘w’,‘x’,‘y’,‘z’,‘ ’};

    int w[28]={64,13,22,32,103,21,15,47,57,1,5,32,20,

    57,63,15,1,48,51,80,23,8,18,1,16,1,168};

    char code[200];

    char test[50]={“this is about build my life”};

    HuffmanTree *HT;

    HuffmanCode *hc;

    HT=(HuffmanTree *)malloc(m*sizeof(HuffmanTree));

    hc=(HuffmanCode *)malloc(n*sizeof(char*));

    CreateTree(HT,n,w);

    Print(HT,m-1);

    printf(“\n”);

    Huffmancoding(HT,n,hc,letters);

    Encode(hc,letters,test,code);

    Decode(HT,m,code,letters);

    printf(“\n”);

    return 0;

    }

    推荐阅读:

    展开全文
  • 哈工程本科算法实验哈夫曼编码【数据+代码+说明+流程图+测试用例】
  • 哈夫曼编码应用实例哈夫曼编码,主要用途是实现数据压缩。设给出一段报文:CAST CAST SAT AT A TASA。字符集合是 { C, A, S, T },各个字符出现的频度(次数)是 W={ 2, 7, 4, 5 }。若给每个字符以等长编码A :...

    哈夫曼编码应用实例

    哈夫曼编码,主要用途是实现数据压缩。

    设给出一段报文:CAST CAST SAT AT A TASA。字符集合是 { C, A, S, T },各个字符出现的频度(次数)是 W={ 2, 7, 4, 5 }。若给每个字符以等长编码A : 00 T : 10 C : 01 S : 11,则总编码长度为 ( 2+7+4+5 ) * 2 = 36。

    若按各个字符出现的概率不同而给予不等长编码,可望减少总编码长度。各字符出现概率为{ 2/18, 7/18, 4/18, 5/18 },化整为 { 2, 7, 4, 5 }。以它们为各叶结点上的权值, 建立霍夫曼树。左分支赋 0,右分支赋 1,得霍夫曼编码(变长编码)。A : 0 T : 10 C : 110 S : 111。它的总编码长度:7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。霍夫曼编码是一种无前缀编码。解码时不会混淆。带权路径长度达到最小的二叉树即为霍夫曼树。在霍夫曼树中,权值大的结点离根最近。

    霍夫曼算法

    1.由给定的 n 个权值 {w0, w1, w2, …, wn-1},构造具有 n 棵扩充二叉树的森林 F = { T0, T1, T2, …, Tn-1 },其中每棵扩充二叉树 TI 只有一 个带权值 wi 的根结点, 其左、右子树均为空。

    2.重复以下步骤, 直到 F 中仅剩下一棵树为止:

    ① 在 F 中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

    ② 在 F 中删去这两棵二叉树。

    ③ 把新的二叉树加入 F。

    #include 《stdio.h》

    #include 《stdlib.h》

    #include 《string.h》

    #define MAX 32767

    typedef char *HuffmanCode;

    typedef struct

    {

    int Weight;//字母的权

    int Parent,Leftchild,Rightchild;

    }HuffmanTree;

    void Select(HuffmanTree *HT,int n,int *s1,int *s2)

    {

    int min1=MAX;

    int min2=MAX;

    int pos1, pos2;

    int i;

    for(i=0;i《n;i++)

    {

    if(HT[i].Parent==-1)//选择还没有父亲的节点

    {

    if(HT[i].Weight《=min1)

    {

    pos2 = pos1; min2 = min1;

    pos1 = i; min1=HT[i].Weight;

    }

    else if(HT[i].Weight《=min2)

    {

    pos2 = i; min2=HT[i].Weight;

    }

    }

    }

    *s1=pos1;*s2=pos2;

    }

    void CreateTree(HuffmanTree *HT,int n,int *w)

    {

    int m=2*n-1;//总的节点数

    int s1,s2;

    int i;

    for(i=0;i《m;i++)

    {

    if(i《n)

    HT[i].Weight=w[i];

    else

    HT[i].Weight=-1;

    HT[i].Parent=-1;

    HT[i].Leftchild=-1;

    HT[i].Rightchild=-1;

    }

    for(i=n;i《m;i++)

    {

    Select(HT,i,&s1,&s2);//这个函数是从0到n-1中选两个权最小的节点

    HT[i].Weight=HT[s1].Weight+HT[s2].Weight;

    HT[i].Leftchild=s1;

    HT[i].Rightchild=s2;

    HT[s1].Parent=i;

    HT[s2].Parent=i;

    }

    }

    void Print(HuffmanTree *HT,int m)

    {

    if(m!=-1)

    {

    printf(“%d ”,HT[m].Weight);

    Print(HT,HT[m].Leftchild);

    Print(HT,HT[m].Rightchild);

    }

    }

    void Huffmancoding(HuffmanTree *HT,int n,HuffmanCode *hc,char *letters)

    {

    char *cd;

    int start;

    int Current,parent;

    int i;

    cd=(char*)malloc(sizeof(char)*n);//用来临时存放一个字母的编码结果

    cd[n-1]=‘\0’;

    for(i=0;i《n;i++)

    {

    start=n-1;

    for(Current=i,parent=HT[Current].Parent; parent!=-1; Current=parent,parent=HT[parent].Parent)

    if(Current==HT[parent].Leftchild)//判断该节点是父节点的左孩子还是右孩子

    cd[--start]=‘0’;

    else

    cd[--start]=‘1’;

    hc[i]=(char*)malloc(sizeof(char)*(n-start));

    strcpy(hc[i],&cd[start]);

    }

    free(cd);

    for(i=0;i《n;i++)

    {

    printf(“letters:%c,weight:%d,编码为 %s\n”,letters[i],HT[i].Weight,hc[i]);

    printf(“\n”);

    }

    }

    void Encode(HuffmanCode *hc,char *letters,char *test,char *code)

    {

    int len=0;

    int i,j;

    for(i=0;test[i]!=‘\0’;i++)

    {

    for(j=0;letters[j]!=test[i];j++){}

    strcpy(code+len,hc[j]);

    len=len+strlen(hc[j]);

    }

    printf(“The Test : %s \nEncode to be :”,test);

    printf(“%s”,code);

    printf(“\n”);

    }

    void Decode(HuffmanTree *HT,int m,char *code,char *letters)

    {

    int posiTIon=0,i;

    printf(“The Code: %s \nDecode to be :”,code);

    while(code[posiTIon]!=‘\0’)

    {

    for(i=m-1;HT[i].Leftchild!=-1&&HT[i].Rightchild!=-1;position++)

    {

    if(code[position]==‘0’)

    i=HT[i].Leftchild;

    else

    i=HT[i].Rightchild;

    }

    printf(“%c”,letters[i]);

    }

    }

    int main()

    {

    int n=27;

    int m=2*n-1;

    char letters[28]={‘a’,‘b’,‘c’,‘d’,‘e’,‘f’,‘g’,‘h’,‘i’,‘j’,‘k’,‘l’,‘m’,

    ‘n’,‘o’,‘p’,‘q’,‘r’,‘s’,‘t’,‘u’,‘v’,‘w’,‘x’,‘y’,‘z’,‘ ’};

    int w[28]={64,13,22,32,103,21,15,47,57,1,5,32,20,

    57,63,15,1,48,51,80,23,8,18,1,16,1,168};

    char code[200];

    char test[50]={“this is about build my life”};

    HuffmanTree *HT;

    HuffmanCode *hc;

    HT=(HuffmanTree *)malloc(m*sizeof(HuffmanTree));

    hc=(HuffmanCode *)malloc(n*sizeof(char*));

    CreateTree(HT,n,w);

    Print(HT,m-1);

    printf(“\n”);

    Huffmancoding(HT,n,hc,letters);

    Encode(hc,letters,test,code);

    Decode(HT,m,code,letters);

    printf(“\n”);

    return 0;

    }

    推荐阅读:

    展开全文
  • 哈夫曼译码流程图

    2014-03-28 18:52:33
    哈夫曼译码流程图,数据结构课程设计需要,用visio画的
  • 哈夫曼编码课程设计报告.doc》由会员分享,可在线阅读,更多相关《哈夫曼编码课程设计报告.doc(24页珍藏版)》请在装配网上搜索。1、 湖南科技学院 数据结构 课程设计报告课 题 霍夫曼编码 专业班级 信计1202 学 ...

    《哈夫曼编码课程设计报告.doc》由会员分享,可在线阅读,更多相关《哈夫曼编码课程设计报告.doc(24页珍藏版)》请在装配图网上搜索。

    1、 湖南科技学院 数据结构 课程设计报告课 题 霍夫曼编码 专业班级 信计1202 学 号 201205001239 姓 名 黄思琪 指导教师 牛志毅 1 课程设计的目的和意义在当今信息爆炸时代,如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码,这就是。

    2、哈夫曼编码。通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时,总希望总长度尽可能最短,即采用最短码。 2需求分析 课 题哈夫曼编码译码器系统问题描述打开一篇英文文章,统计该文章中每个字符出现的次数,然后以它们作为权值,对每一个字符进行编码,编码完成后再对其编码进行译码。问题补充1. 从硬盘的一个文件里读出一段英语文章;2. 统计这篇文章中的每个字符出现的次数;3. 以字符出现字数作为权值,构建哈夫曼树4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破译。具体介绍在本课题中,我们在硬盘D盘中预先建立一个xuzhimo.tx。

    3、t文档,在里面编辑一篇文章大写。然后运行程序,调用fileopen函数读出该文章,显示在界面;再调用tongji函数对该文章的字符种类进行统计,并对每个字符的出现次数进行统计,并且在界面上显示;然后以每个字符出现次数作为权值,调用Create_huffmanTree函数构建哈夫曼树。然后调用Huffman_bianma函数对哈夫曼树进行编码,调用coding函数将编码写入文件。 3 系统(项目)设计 1设计思路及方案本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。假设每种字符在电文中出现的次数为Wi,编码长度为Li,电文中有n种字符,则电文编码总长度为W1*L1W2*L2Wi*Li。

    4、。若将此对应到二叉树上,Wi为叶结点,Li为根结点到叶结点的路径长度。那么,W1*L1W2*L2Wi*Li恰好为二叉树上带权路径长度。因此,设计电文总长最短的二进制前缀编码,就是以n种字符出现的频率作权,构造一棵哈夫曼树,此构造过程称为哈夫曼编码。该系统将实现以下几大功能从硬盘读取字符串,建立哈夫曼树,输出哈夫曼树的存储结构的初态和终态,输出各种字符出现的次数以及哈夫曼编码的译码等。 2模块的设计及介绍1从硬盘读取字符串fileopen参数 实现命令; 打印输出;2建立HuffmanTree通过三个函数来实现void select_min参数 初始化; for 接受命令; 处理命令;说明在ht。

    5、1k中选择parent为0且权值最小的两个根结点的算法int tongji参数 初始化; for 接受命令; 处理命令; 说明统计字符串中各种字母的个数以及字符的种类void Create_huffmanTree 初始化; for 接受命令; 处理命令; 输出字符统计情况;说明构造哈夫曼树3哈夫曼编码void Huffman_bianma参数 定义变量; 处理命令;说明哈夫曼编码 3主要模块程序流程图下面介绍三个主要的程序模块流程图 主函数流程图结束统计字符种类及频率字符总数num建立哈夫曼树哈夫曼编码打开文件开始否是 图3.1流程图注释该图比较简单,主要是调用各个函数模块,首先代开已经存在的。

    6、文件,然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树,接着在哈夫曼树的基础上对其进行编码。最后输出结束。构造哈夫曼树开始结束第i个结点权值inum创建哈夫曼树输出字符统计情况第i个根结点i2*num-1inum否是否是否是 图3.2流程图注释该图是表示构造哈夫曼树的过程。首先输入num个叶结点的权值,当inum是循环结束。然后进行哈夫曼树的构建,当i2*num-1是循环结束。最后输出所得到的字符统计情况。哈夫曼编码结束开始Tp.leftcinumCdstart0,startnumCdstart0Cdstart1否否是是 图3.3流程图解释该流程图表四哈夫曼编码情况。首先初始。

    7、化,Cdstart0,startnum。然后进行编码,当cdstartTp.lchild c时,cdstart0;当cdstartTp.left c时,cdstart1。这个编码循环一直到inum时结束。4 系统实现各模块关键代码及算法的解释 主调函数 代码解释这是main函数里的各个函数调用情况。fileopenstring; 从硬盘中读取文件numtongjistring,cishu,str; 统计字符种类及各类字符出现的频率Create_huffmanTreeHT,HC,cishu,str;建立哈夫曼树 Huffman_bianmaHT,HC; 生成哈夫曼编码 建立HuffmanTree。

    8、代码解释该函数为在ht1k中选择parent为0且权值最小的两个根结点的算法,其序号为s1和s2。void select_minHuffmanTree T,int k,int int min11000; fori1;ik;i ifTi.weightmin1 Ti.parent0 ji;min1Ti.weight;x1j;min11000;for i1;ik;i ifTi.weightmin1 Ti.parent0 ix1ji;min1Ti.weight;x2j;代码解释下面函数用来统计字符串中各种字母的个数以及字符的种类。当字符在A和Z之间时即被计数,并用strj保存字母到数组中,用cntj统。

    9、计每种字符个数。j返回总共读取的字符数目。int tongjichar *s,int cishu,char str int i,j,k; char *p;int t27; fori1;i26;iti0; forps; *p0;p if*pA*pZk*p-64;tk; fori1,j0;i26;iifti0 j;strji64; cishujti; return j; 代码解释下面函数用来构造哈夫曼树HT。首先初始化哈夫曼树,然后输入前面统计的各结点的权值,用for循环来构造哈夫曼树。void Create_huffmanTreeHuffmanTree ht,HuffmanCode hc,in。

    10、t cishu,char str 生成哈夫曼树HTint i,s1,s2;fori0;i2*num-1;i hti.left0;hti.right0;hti.parent0;hti.weight0;fori1;inum;i 输入num个叶结点的权值hti.weightcishui;forinum1;i2*num-1;i 选择parent为0且权值最小的两个根结点,其序号为s1和s2,i为双亲select_minht,i-1,s1,s2;hts1.parenti;hts2.parenti;hti.lefts1; hti.rights2;hti.weighthts1.weighthts2.weig。

    11、ht;fori0;inum;i hci.chstri; 字符的种类i1;whileinumprintf字符c次数8dn,hci.ch,cishui; 生成Huffman编码并写入文件代码解释根据哈夫曼树T求哈夫曼编码H。void Huffman_bianmaHuffmanTree T,HuffmanCode H 根据哈夫曼树T求哈夫曼编码H int child,parent,i; child和parent分别指示t中孩子和双亲char coden; 存放编码int start; 指示码在code中的起始位置codenum0; 最后一位(第num个)放上串结束符fori1;inum;istart。

    12、num; 初始位置childi; 从叶子结点到根结点进行遍历whileparentTchild.parent0 直至tchild是树根为止 若tchild是tparent的左孩子,则生成0;否则生成1ifTparent.leftchildcodestart0;elsecodestart1;childparent;strcpyHi.co,Hi.lennum-start;代码解释对str所代表的字符串进行编码并写入文件。将翻译的二进制码写入文本文件。void codingHuffmanCode hc ,char *str 对str所代表的字符串进行编码 并写入文件int i,j;FILE *fp;。

    13、fpcodefile.txt,w;while*strfori1;inum;iifhci. ch*strforj0;jhci.len;jfputchci.coj,fp;break;str;fclosefp;5 系统调试本次测试是在我的电脑的D盘中建立一个名为file.txt的文本文档,其中有大写字母IAMASTUDENT,期望程序能将其读出至界面并实现其他相关的功能。运行程序后,我们可以见到一下的运行界面。从硬盘中读出已有的文本文件 输出所读字符的种类和每种字符的个数 输出编码 小 结通过一周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解,也使我更加明白哈夫曼编码译码在信息技术中的重。

    14、要性和地位。首先我谈谈我在设计期间我遇到的难点。开始的时候,代码中有许多的错误,特别是有一个“无法找到文件”的错误让我束手无策,最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时,由于对文件不是太熟悉,只好翻开C语言书本仿照其模式编写,但后来进入了死循环,最后的解决方式是把main函数里的一个dowhile循环去掉。许多的错误让我明白了一个道理-细心是非常重要的。同时,对于编程者而言,思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。这次课程设计不但让我学得了一些编程知识,还学会了系统的做一份课程设计报告,学会了如何截图,学会了。

    15、如何更好的画流程图,明白了做事情只有认真,才能真正做得更好通过这次课程设计,我看清楚了自己的编程功底和动手能力还很不足,这主要是平时实践太少的缘故。我想,在未来的暑假中,我会努力尝试编写一些程序。在这个程序中,还有许多地方值得完善。比如,读出文本只能是大写的文档,空格和小写不能识别。由于时间问题,暂时不能实现了,我想在暑假里好好研究这个问题。未完成哈夫曼译码附录 源程序include stdio.hinclude string.hinclude stdlib.hincludefstream.h类型相关变量的定义define n 100 define m 2*n-1 typedef struct。

    16、char ch;char co9; 存放编码int len; CodeNode;typedef CodeNode HuffmanCoden1;typedef struct int weight; int left,right,parent; HTNode;typedef HTNode HuffmanTreem1; int num;void select_minHuffmanTree T,int k,int int min11000; fori1;ik;i 找最小值ifTi.weightmin1 Ti.parent0 ji;min1Ti.weight;x1j;min11000;for i1;ik。

    17、;i 找次小值ifTi.weightmin1 Ti.parent0 ix1ji;min1Ti.weight;x2j;int tongjichar *s,int cishu,char str 统计字符串中各种字母的个数以及字符的种类int i,j,k; char *p;int t27; fori1;i26;iti0; forps; *p0;p 统计各种字符的个数 if*pA*pZk*p-64;tk; fori1,j0;i26;iifti0 j;strji64; 送对应的字母到数组中cishujti; 存入对应字母的权值return j; j是输入字母种数void Create_huffmanT。

    18、reeHuffmanTree ht,HuffmanCode hc,int cishu,char str 生成哈夫曼树HTint i,s1,s2;fori0;i2*num-1;i hti.left0;hti.right0;hti.parent0;hti.weight0;fori1;inum;i 输入num个叶结点的权值hti.weightcishui;forinum1;i2*num-1;i 选择parent为0且权值最小的两个根结点,其序号为s1和s2,i为双亲select_minht,i-1,s1,s2;hts1.parenti;hts2.parenti;hti.lefts1; hti.rig。

    19、hts2;hti.weighthts1.weighthts2.weight;fori0;inum;i hci.chstri; 字符的种类i1;whileinumprintf字符c次数8dn,hci.ch,cishui;void Huffman_bianmaHuffmanTree T,HuffmanCode H 根据哈夫曼树T求哈夫曼编码H int child,parent,i; child和parent分别指示t中孩子和双亲char coden; 存放编码int start; 指示码在code中的起始位置codenum0; 最后一位(第num个)放上串结束符fori1;inum;istartn。

    20、um; 初始位置childi; 从叶子结点到根结点进行遍历whileparentTchild.parent0 直至tchild是树根为止 若tchild是tparent的左孩子,则生成0;否则生成1ifTparent.leftchildcodestart0;elsecodestart1;childparent;strcpyHi.co,Hi.lennum-start;void codingHuffmanCode hc ,char *str 对str所代表的字符串进行编码 并写入文件int i,j;FILE *fp;fpcodefile.txt,w;while*strfori1;inum;iifh。

    21、ci. ch*strforj0;jhci.len;jfputchci.coj,fp;break;str;fclosefp;void output 输出编码FILE *fp;char ch;iffpcodefile.txt,rNULLprintferrorn;exit0;printf编码为n;chfgetcfp;whilefeoffpputcharch;chfgetcfp; printfn;int fileopenchar string 读入文件FILE *fp; iffpD数据结构课程设计file.txt,rNULLprintf不能打开文件n;exit1;whilefgetsstring,10。

    22、0,fpNULL printfsn,string;fclosefp;return 0;主函数void main char string100;char *s,str27;int cishu27; HuffmanTree HT;HuffmanCode HC;int x;printfn;printf* 哈夫曼编码 *n;printfn;while1printf请选择; printft 1.开始n; printft 2.输出各字符统计个数n; printft 3.编码n; printft 4.输出编码n;printft 5.退出n; scanfd, switchx case 1 printf读出文本为n; fileopenstring; break; case 2 numtongjistring,cishu,str; 统计字符的种类及各类字符出现的次数Create_huffmanTreeHT,HC,cishu,str; break; case 3 Huffman_bianmaHT,HC; 生成哈夫曼编码 codingHC,string; 建立电文哈夫曼编码文件 break;case 4output;break;case 5exit0;freeHT;defaultprintf输入错误n;continue; 23。

    展开全文
  • #include"stdio.h"#defineN010#defineinfi1000000structnode{intw,lch,rch,parent;}ht[2*N0];structnode1{charch;unsignedcharcode[N0+1];intstart;//codelength}hc[N0+1];intn,m,roo...#include "stdio.h"#define N...

    #include"stdio.h"#defineN010#defineinfi1000000structnode{intw,lch,rch,parent;}ht[2*N0];structnode1{charch;unsignedcharcode[N0+1];intstart;//codelength}hc[N0+1];intn,m,roo...

    #include "stdio.h"

    #define N0 10

    #define infi 1000000

    struct node

    { int w, lch, rch, parent;

    }ht[2*N0];

    struct node1

    { char ch;

    unsigned char code[N0+1];

    int start;// code length

    }hc[N0+1];

    int n, m, root;

    void readData()

    { int i, a[256]={ 0 };

    char ch;

    freopen("huffman.in", "r", stdin);

    while( (ch=getchar()) != EOF )

    a[ch]++;

    n=0;

    for(i=0; i<256; i++)

    if( a[i] )

    { ht[ ++n ].w=a[i];

    hc[ n ].ch=i;

    }

    m=root=2*n-1;

    }

    void select3(int t, int *s1, int *s2 )

    { int i, w1=infi, w2=infi;

    for( i=1; i<=t; i++)

    if( ht[i].parent==0 )

    if( ht[i].w

    { w2=w1;

    *s2=*s1;

    w1=ht[i].w;

    *s1=i;

    }

    else if( ht[i].w

    { w2=ht[i].w;

    *s2=i;

    }

    }

    void create_ht_hc()

    { int i, s1, s2, child, parent;

    for( i=n+1; i<=m; i++ )

    { select3( i-1, &s1, &s2);

    ht[i].w=ht[s1].w+ht[s2].w;

    ht[i].lch=s1;

    ht[i].rch=s2;

    ht[s1].parent=ht[s2].parent=i;

    }

    for( i=1; i<=n; i++)

    { child=i;

    parent=ht[child].parent;

    while( child != root )

    { if( child==ht[parent].lch )

    hc[i].code[hc[i].start++]='0';

    else hc[i].code[hc[i].start++]='1';

    child=parent;

    parent=ht[child].parent;

    }

    }

    }

    void showCode()

    { int i,j;

    for( i=1; i<=n; i++)

    { printf("%c:", hc[i].ch);

    for(j=hc[i].start-1; j>=0; j--)

    printf("%c", hc[i].code[j]);

    printf("\n");

    }

    }

    void showTree(int root, int tab)

    { if(root)

    { int i;

    for( i=1; i<=tab; i++)

    printf(" ");

    printf("%d", ht[root].w);

    if( ht[root].lch==0 )

    printf("%c\n", hc[root].ch);

    else printf("\n");

    showTree( ht[root].lch, tab+3 );

    showTree( ht[root].rch, tab+3 );

    }

    }

    void str2code()

    { int i,j,ch;

    freopen("huffman.in", "r", stdin);

    freopen("huffman.code", "w", stdout);

    while( (ch=getchar() )!=EOF )

    { for(i=1; i<=n; i++)

    if( hc[i].ch==ch )

    for(j=hc[i].start-1; j>=0; j--)

    printf("%c", hc[i].code[j]);

    }

    }

    void code2str()

    { int i=root,ch;

    freopen("huffman.code", "r", stdin);

    freopen("huffman.txt", "w", stdout);

    while( (ch=getchar() )!=EOF )

    { if( ch=='0' ) i=ht[i].lch;

    else i=ht[i].rch;

    if(ht[i].lch==0)

    { printf("%c", hc[i].ch);

    i=root;

    }

    }

    }

    int main()

    {

    readData();

    create_ht_hc();

    showTree(root, 0);

    showCode();

    str2code();

    code2str();

    return 0;

    }

    符合要求的多加分(qq:873485472)

    c语言描述的Huffman

    展开

    展开全文
  • 信息论与编码课程大作业题 目: 二进制哈夫曼编码学生姓名: 学 号: 2010020200 专业班级: 2010级电子信息班2013年 5月 18日二进制哈夫曼编码1、二进制哈夫曼编码的原理及步骤1、1信源编码的计算设有N个码元组成的...
  • 作者 孟欢 包海燕 潘飞 电子科技大学 微电子与固体电子学院(四川 成都 610054)本文...摘要:在图像处理、文件传真、视频压缩编码中,哈夫曼编码是最常用的一种编码方式。本文设计并实现了对一段数字序列进行哈夫曼...
  • 这个程序是研一上学期的课程大作业。当时,跨专业的我只有一点 C...源码托管在 Github:点此打开链接以下为完整的作业报告:一、问题描述:名称:基于哈夫曼编码的文件压缩解压目的:利用哈夫曼编码压缩存储文件,节...
  • MATLAB实现哈夫曼编码,简单易懂。能帮助理解信息论信源编码的相关知识。
  • nbsp软件工程Huffman编码软件实现.doc8页本文档一共被下载:次,您可全文免费在线阅读后下载本文档。 下载提示1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。2.该...
  • 用MATLAB实现哈夫曼编码的例程-Huffman.rar 用MATLAB实现哈夫曼编码的例程(以子函数形式给出), NORM2HUFF 哈夫曼编码器 对于输入向量, NORM2HUFF 返回向量的哈夫曼编码后的码串。
  • 动态哈夫曼树,算法注释详细,用Javafx8做了个GUI界面,所以如果main无法运行可能是需要java8,如果不想运行GUI界面,GUI代码和算法在两个不同的包里,可以把算法代码拿出来直接调用。github地址 ...
  • 哈夫曼编码的编程 源程序 大家可是看看, ,,不会的人直接只用稍微修改下就行了
  • 哈夫曼编码

    2014-04-24 23:25:26
    输入字符串,生成对应的哈弗曼数编码……大一数据结构课程实验。
  • 哈夫曼编码 MATLAB程序

    2021-04-18 03:05:21
    %矩阵c 中第n-i 行第j+1 列的值等于对应于a 矩阵中第n-i+1 行中值为j+1 的前面一个元素的位置在c 矩阵中的编码值 end end for i=1:n hm(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n);%用hm表示最后的...
  • 由于时间仓促,编码风格比较怪,读程序的人可能会觉得比较痛苦吧。设计报告中的流程图画得也不是很规范。不过有一点必须指出来:互联网上像课件一样关于逐步分解huffman码树绘制的程序几乎没有。 NOTE: 如果您想要...
  • 哈夫曼树的创建构造二、设计思路三、软件流程图四、核心代码1.sort排序函数2.建立各概率符号的位置索引矩阵Index3.初始化存放矩阵4.回溯过程的代码实现五、运行效果截图及相关说明 一、背景介绍 1.哈夫曼树的定义与...
  • 哈夫曼树建立.cpp

    2020-01-04 17:30:41
    自己码的C语言哈弗曼树的建立,代码格式整齐,清晰易懂,能正确运行,包含文件的编码解码和压缩功能,很不错的代码,很容易用其他语言复现
  • 原理介绍什么是Huffman压缩Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了,它是一种无损压缩方法,在压缩过程中不会丢失信息熵。并且能够证明 Huffman 算法在无损压缩算法中是最优的。Huffman 原理简单,实现...
  • 信息论相关编码算法程序C语言版(哈夫曼编码、算术编码、信道容量迭代算法),完全可运,供大家参考。
  • 哈夫曼树和哈夫曼编码详解(C语言实现)

    万次阅读 多人点赞 2020-04-15 12:36:48
    1 中,从根结点到结点 a 之间的通路就是一条路径。路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 ...
  • 本发明属于图片处理技术领域,尤其涉及一种基于Huffman编码的图像再压缩处理方法。背景技术:目前,业内常用的现有技术是这样的:由于各种新型传感器的出现,图像质量得到了巨大的提升,随之而来的数据量对图像的...
  • 举例理解哈夫曼树与哈夫曼编码

    万次阅读 2020-07-02 08:52:56
    举例理解哈夫曼树,C语言实现哈夫曼
  • 《信息论与编码课程大作业二进制哈夫曼编码》由会员分享,可在线阅读,更多相关《信息论与编码课程大作业二进制哈夫曼编码(7页珍藏版)》请在人人文库网上搜索。1、信息论与编码课程大作业题 目: 二进制哈夫曼编码 ...
  • 哈夫曼编码的MATLAB实现

    千次阅读 2020-04-25 16:50:24
    在手动计算时,对哈夫曼编码流程还是非常熟悉的,所以难点就是代码实现。在实现以前,我考虑了以下一些问题:一个符号的哈夫曼编码值可以用一个向量进行存储,符号合并以后的结果用什么表示,对其赋值0,1如何作用...
  • 哈夫曼编码程序介绍程序整体设计思想程序详解数据结构动态存储静态存储编码译码编码核心思想核心代码译码核心思想核心代码哈夫曼树可视化核心思想核心代码完整代码头文件main函数程序程序部分截图程序演示资源文件...
  • 哈夫曼编码/译码实现

    2010-11-14 18:23:51
    压缩文件即读文件,统计文件中的字符个数,对文件进行哈夫曼编码和译码,并将编码译码后的字符存储在文件中。 完成功能的详细说明: 1.统计文本文件中各字符的频率(涉及读文件,统计字符个数); 2.对文件中的...
  • 一、什么是哈夫曼编码? 1.文件编码 文件是由字符构成的,ACSII码中大概包含100个可打印的字符,每一个字符都有其特定的编码,扩展ACSII码为8位,也就是说不同的字符都需要用8位二进制位来编码,这是一种等长码。 ...
  • 在这里晒晒了设计报告内容:一、课程设计名称《哈夫曼编码的算法》二、使用工具TC(C语言环境)三、课程设计内容简介(1) 此课程设计是关于“哈夫曼编码算法的实现”。课程目的是为了了解哈夫曼算法的思路核心,掌握...

空空如也

空空如也

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

哈夫曼编码的程序流程图