| 网站首页 | 业界新闻 | 群组 | 人才 | 技术文章 | 下载频道 | 博客 | 代码贴 | 编程论坛
绝地游戏外挂辅助教学千里之行 始于足下
共有 205 人关注过本帖
标题:哈夫曼树编码的问题,求大神赐教
只看楼主 收藏
踏月光
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2017-11-13
结帖率:0
  已结贴   问题点数:20  回复次数:4   
哈夫曼树编码的问题,求大神赐教
(1)输入一串包含abcdefgh  8种字符的字符串,统计并输出每种字符出现的次数,并据此创建相应的哈夫曼树
(2)输出每种字符的哈夫曼编码
(3)输入一个字符串,其可能出现的字符有abcdefgh  8种,输出该字符串的编码结果
2017-11-25 09:14
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:25
帖 子:3978
专家分:11322
注 册:2016-10-22
  得分:20 
不用感谢我,要感谢的话就感谢我们的数据结构老师~
这排版,我也醉了,最好自己整理消化一下~
程序代码:

#include<stdio.h>
#include<stdlib.h>
#include <string.h>#define  N  6                /* 叶子结点数 */#define  MAX_NODE  2*N-1    /* 总结点数=2n-1  */ #define  M  MAX_NODE+1        /* 数组大小=总结点数+1,下标0废弃 */typedef struct{         int Weight;    /*  权值域  */    int Parent , Lchild , Rchild ;} HTNode ;void main(){    int i;    char *MyHC[M];  //存放每个叶子结点Huffman编码的指针    HTNode MyHT[M];    void Create_Huffman(int n, HTNode HT[ ], int m);  //n叶子结点数,m总结点数(2*n-1)    void Huff_coding(   int n, HTNode HT[ ], int m,char *HC[]);    /*  m应为n+1,编码的最大长度n加1 */    Create_Huffman(N, MyHT, M);    printf("Huffman树结点数组HT[]:\n");    printf("HT[i]\t权\t父\t左\t右\t\n");    for (i=1; i<M; i++)  //输出Huffman结点数组MyHT[]        printf("%d\t%d\t%d\t%d\t%d\n",i,MyHT[i].Weight,MyHT[i].Parent,MyHT[i].Lchild,MyHT[i].Rchild);    Huff_coding(N, MyHT, M, MyHC);    printf("\n Huffman编码如下:\n");    printf("权值:\t");    for (i=1; i<N+1; i++)        printf("(%d)%d\t",i,MyHT[i]);    printf("\n");    printf("编码:\t");    for (i=1; i<N+1; i++)        printf("%s\t",MyHC[i]);    printf("\n");}        void Create_Huffman(int n, HTNode HT[ ], int m)  //n叶子结点数,m总结点数(2*n-1)   /*  创建一棵叶子结点数为n的Huffman树  */{      int  w , k , j ;    for (k=1 ; k<m ; k++) //初始化HT[ ]向量    {           if  (k<=n)  //创建n个叶子结点的权值        {              printf("请输入权值W%d即HT[%d]=:",k,k);            scanf("%d", &w) ;            HT[k].Weight=w ;          }        /*  输入时,所有叶子结点都有权值  */        else  HT[k].Weight=0;  /*  非叶子结点没有权值 */               HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ;    }        /* 初始化向量HT */        for (k=n+1; k<m ; k++)    {           int w1=32767 , w2=w1 ;        /*  w1 , w2分别保存权值最小的两个权值  */        int  p1=0 , p2=0 ;            /* p1 , p2保存两个最小权值的下标*/        for (j=1 ; j<=k-1 ; j++)        {               if (HT[j].Parent==0)    /* 尚未合并 */            {                   if (HT[j].Weight<w1)/*  找到权值最小的两个值及其下标  */                    {                         w2=w1 ; p2=p1 ; w1=HT[j].Weight ; p1=j ;                    }                else if (HT[j].Weight<w2)                     {  w2=HT[j].Weight ;  p2=j ;   }                                 }            }        HT[k].Lchild=p1 ; HT[k].Rchild=p2 ;        HT[k].Weight=w1+w2 ;        HT[p1].Parent=k ; HT[p2].Parent=k ;     }//end for}void Huff_coding(int n , HTNode HT[] , int m,char * HC[])    /*  m应为n+1,编码的最大长度n加1 */{      int  k , sp ,fp, p ;    char *cd;// , *HC[M] ;    cd=(char *)malloc(m*sizeof(char)) ;         /*  动态分配求编码的工作空间  */    cd[n]='\0';                                    /*  编码的结束标志 */    for (k=1 ; k<n+1 ; k++)                        /*  逐个求字符的编码    */    {             sp=n ; p=k ; fp=HT[k].Parent ;         for (  ; fp!=0 ;p=fp , fp=HT[p].Parent)        /*   从叶子结点到根逆向求编码,逐次压站,正向输出即为正向编码  */             if  (HT[fp].Lchild==p)  cd[--sp]='0';            else                    cd[--sp]='1';        HC[k]=(char *)malloc((n-sp)*sizeof(char)) ;    /*  为第k个字符分配保存编码的空间 */        strcpy(HC[k] , &cd[sp]) ;    }    free(cd) ;}

[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~2017-11-07更~*/[/code]
2017-11-25 13:45
踏月光
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2017-11-13
  得分:0 
太感谢你啦!但是请问一下,你这个和我的题目是一样的吗,你运行成功了没有?我之前写的编码没有成功。。。
2017-11-25 14:22
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:25
帖 子:3978
专家分:11322
注 册:2016-10-22
  得分:0 
回复 3楼 踏月光
这是老师的代码,正常来说应该可以运行,我是用手机打开的复制粘贴排版有问题~

抱歉说我没啥功夫自己进行排版,至于测试运行就要看自己造化了~当然方便直接的还是上网搜吧,毕竟这么经典的题目参考资料还是挺多的~

还有嘛,功能方面可以自己改改看,直接给个现成品你也太直接了吧,自己试试排版弄弄看或者可以加深理解~

[此贴子已经被作者于2017-11-25 15:01编辑过]


[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~2017-11-07更~*/[/code]
2017-11-25 14:59
踏月光
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2017-11-13
  得分:0 
嗯嗯,我晚上再在电脑上看看吧,谢谢你了!
2017-11-25 15:17







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.085357 second(s), 8 queries.
Copyright©2004-2017, BCCN.NET, All Rights Reserved