求赫夫曼编码的另一种算法

无栈非递归遍历赫夫曼树,求赫夫曼编码
比从叶子到根逆向求每个字符的赫夫曼编码的算法要复杂些
算法如下:
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历赫夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p)
{
    if (HT[p].weight==0)// 向左
    {  
        HT[p].weight = 1;
        if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
        else if (HT[p].rchild == 0)// 登记叶子结点的字符的编码
        {
            HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
            cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
        }
    }
    else if (HT[p].weight==1)  // 向右
    {
        HT[p].weight = 2;
        if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
    }
    else // HT[p].weight==2,退回退到父结点,编码长度减1
    {    
        HT[p].weight = 0; p = HT[p].parent; --cdlen;
    }
}



文章来自: 本站原创
引用通告: 查看所有引用 | 我要引用此文章
Tags: 数据结构 C语言
相关日志:
评论: 0 | 引用: 0 | 查看次数: -
发表评论
昵 称:
密 码: 游客发言不需要密码.
内 容:
验证码: 验证码
选 项:
虽然发表评论不用注册,但是为了保护您的发言权,建议您注册帐号.