| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2870 人关注过本帖
标题:赫夫曼树编码的实现(无栈非递归遍历)
只看楼主 加入收藏
kemingjie
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2017-4-24
结帖率:0
收藏
已结贴  问题点数:20 回复次数:1 
赫夫曼树编码的实现(无栈非递归遍历)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree HT, int u, int &s1, int &s2) {
    int j;
    j=1;
    while(j<=u && HT[j].parent!=0) j++;
    s1=j;
    while(j<=u) {
        if(HT[j].parent==0 && HT[j].weight<HT[s1].weight) s1=j;
        j++;
    }
    HT[s1].parent = u+1;
    j = 1;
    while(j<=u && HT[j].parent!=0) j++;
    s2 = j;
    while(j<=u) {
        if(HT[j].parent==0 && HT[j].weight<HT[s2].weight) s2=j;
        j++;
    }
    if (s1>s2) {
        j=s1; s1=s2; s2=j;
    }
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
    int m,i,s1,s2,cdlen,p;
    char *cd;
    m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for(i=1;i<=n;i++){
        HT[i].weight=w[i-1];
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    for(;i<=m;i++){
        HT[i].weight=0;
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    for(i=n+1;i<=m;i++){
        Select(HT,i-1,s1,s2);
        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;
    }
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
    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=0;p=HT[p].parent;--cdlen;
        }
    }
    free(cd);
}
void printHuffman(HuffmanTree HT,int n){
    int k;
    printf("  结点    weight    parent    lchild    rchild\n");
    for(k=1;k<=2*n-1;k++){
        printf("%4d",k);printf("%8d",HT[k].weight);   
        printf("%8d",HT[k].parent);printf("%8d",HT[k].lchild);printf("%8d",HT[k].rchild);
        printf("\n");
    }
}
void printHuffmanCode(HuffmanCode HC,int n,int *w){
    int k,m;
    for(k=1;k<=n;k++){
        printf("频率为%d的编码:%d—>",w[k-1],k);
        puts(HC[k]);
    }
}
void main() {
    int w[]={7,19,2,6,32,3,21,10},n=8;
    HuffmanTree HT;
    HuffmanCode HC;
    HuffmanCoding(HT,HC,w,n);
    printf("建立赫夫曼树:\n");
    printHuffman(HT,n);
    printf("无栈非递归遍历赫夫曼树:\n");
    printHuffmanCode(HC,n,w);
}
搜索更多相关主题的帖子: include parent 
2017-05-08 15:43
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:20 
看过哈夫曼树很多版本都是用数组代替树的指针~这样当然也不存在递归问题咯~这个可以参考一下~等久久弄完线索二叉树就要啃这块内容了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-15 12:37
快速回复:赫夫曼树编码的实现(无栈非递归遍历)
数据加载中...
 
   



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

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