| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1432 人关注过本帖
标题:一个关于哈夫曼编码的问题,运行结果不正确,看了好几天了,不知道哪里有问 ...
只看楼主 加入收藏
丶木清丶
Rank: 2
等 级:论坛游民
帖 子:7
专家分:22
注 册:2017-11-27
收藏
 问题点数:0 回复次数:1 
一个关于哈夫曼编码的问题,运行结果不正确,看了好几天了,不知道哪里有问题。
输入一个英文字符串,对该字符串中各字符个数进行统计取得各字符的出现次数;以其出现次数作为关键字建立哈夫曼树并进行编码,最后输出各个字符对应的码值。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 30

/*记录字符串的数据结构*/
typedef struct
{
    int len;
    char *string;                   //需要记录的字符串
    char elem[MAXSIZE];             //该字符串所拥有的元素
    int count[MAXSIZE];             //该字符串相应元素的个数
}record;

/*哈夫曼树的数据结构*/
typedef struct
{
     int weight;                             //用来存放各个结点的权值
     int parent;  //指向双亲,孩子结点的指针
     int LChild;
     int RChild;
}HTNode,*HuffmanTree;          //动态分配数组,存储哈弗曼树

typedef char**HuffmanCode;    //动态分配数组,存储哈夫曼编码

void swap(int *x,int *y)
{
    int temp=*x;
    *x=*y;
    *y=temp;
}

void select(HuffmanTree *ht,int n,int *s1,int *s2)
{
    int min1=(*ht)[1].weight,min2=(*ht)[2].weight;
    *s1=1,*s2=2;
    if(min1>min2)
    {
        *s1=2;
        *s2=1;
        swap(&min1,&min2);
    }
    for(int i=3;i<=n;i++)
    {
        if((*ht)[i].weight<min1)
        {
            min2=min1;
            min1=(*ht)[i].weight;
            *s2=*s1;
            *s1=i;
        }
        else if((*ht)[i].weight<min2)
        {
            min2=(*ht)[i].weight;
            *s2=i;
        }
    }
}
void CrtHuffmanTree(HuffmanTree *ht,HuffmanCode *hc,int *w,int n)
{
    int m,i,s1,s2,start,c,p;
    char *cd;
    m=2*n-1;
    *ht=(HTNode *)malloc((m+1)*sizeof(HTNode));
    for(i=1;i<=n;i++)
    {
        (*ht)[i].weight=w[i];
        (*ht)[i].LChild=0;
        (*ht)[i].parent=0;
        (*ht)[i].RChild=0;
    }
    for(i=n+1;i<=m;i++)
    {
        (*ht)[i].LChild=0;
        (*ht)[i].parent=0;
        (*ht)[i].RChild=0;
        (*ht)[i].weight=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));
    cd[n-1]='\0';
    for(i=1;i<=n;i++)
    {
        start=n-1;
        for(c=i,p=(*ht)[i].parent;p!=0;c=p,p=(*ht)[p].parent)
            if((*ht)[p].LChild==c)
                cd[--start]='0';
            else
                cd[--start]='1';
        (*hc)[i]=(char *)malloc((n-start)*sizeof(char));
        strcpy((*hc)[i],&cd[start]);
    }
    free(cd);
}

void trans(record *s,char *p)
{
    int i=0,k=0,j,flag=0;
    s->len=0;
    while(*(p+i)!='\0')
    {
        for(j=1;j<=k;j++)
        {
            flag=0;
            if(*(p+i)==s->elem[j])
            {
                flag=1;
                s->count[j]++;
                break;
            }
        }
        if(flag==0)              
        {
            k++;
            s->len++;
            s->elem[k]=*(p+i);
            s->count[k]=1;
        }
        i++;
    }
}

int main()
{
    char a[20]="abbcccdddd";
    record s;
    HuffmanTree ht;
    char ** hc;
    trans(&s,a);
    CrtHuffmanTree(&ht,&hc,s.count,s.len);
    printf("%s\n",*(hc+1));
    return 0;
}
搜索更多相关主题的帖子: 哈夫曼 int char parent for 
2017-11-28 12:52
Alien_Lee
Rank: 8Rank: 8
来 自:Linux帝国
等 级:蝙蝠侠
威 望:7
帖 子:149
专家分:739
注 册:2016-7-19
收藏
得分:0 
编码太长,我没看,给你一个我以前写的哈夫曼的例子吧,大概能用。
程序代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXIPUT 1024
#define ALPHA_SIZE 26

typedef struct TNODE{
    int times;
    char c;
    int flag;
    struct TNODE *parent;
    struct TNODE *left;
    struct TNODE *right;
}tnode_t;

/*用于选择两个最小的次数的下标,两个下标不能相等*/
void ChooseTwo(tnode_t *array[],int size,int *mmax,int *mmin)
{
    int i;
    int tpm,tpi;
    int iax,iin;
    if(size<=1) return ;
    if(array[1]->times > array[0]->times)
    {
        tpm=array[1]->times;
        tpi=array[0]->times;
        iax=1;
        iin=0;
    }
    else
    {
        tpm=array[0]->times;
        tpi=array[1]->times;
        iax=0;
        iin=1;
    }
    for(i=2;i<size;i++)
    {
        if(array[i]->times < tpi)
        {
            tpm = tpi;
            iax=iin;
            tpi = array[i]->times;
            iin=i;
        }
        else
        {
            if(array[i]->times < tpm)
            {
                tpm = array[i]->times;
                iax=i;
            }
        }
    }
    *mmax=iax;
    *mmin=iin;
}
/*判断c是否已经存在,如果存在返回下标,如果不存在返回-1*/
int ForSearch(tnode_t *array[],int size,char c)
{
    int i;
    if(size<=0) return -1;
    else
    {
        for(i=0;i<size;i++)
        {
            if(array[i]->c == c)
            {
                return i;
            }
        }
        return -1;
    }
}
/*哈夫曼编码,对含父节点的哈夫曼树的递归调用寻找*/
void HallfCode(tnode_t *root)
{
    tnode_t *tp;
    int a[MAXIPUT];
    int idx=0;
    if(root==NULL) return ;
    if(root->left==NULL && root->right==NULL)
    {
        tp=root;
        printf("%c : ",root->c);
        while(tp->flag!=-1)
        {
            a[idx++]=tp->flag;
            tp=tp->parent;
        }
        idx--;
        while(idx>=0)
        {
            printf("%d ",a[idx]);
            idx--;
        }
        printf("\n");
    }
    HallfCode(root->left);
    HallfCode(root->right);
}
int main()
{
    char buf[MAXIPUT];
    tnode_t *array[ALPHA_SIZE];
    tnode_t *node_tp;
    int array_el=0;
    int i,j,tp;
    int mina,mini;
    scanf("%s",buf);
    printf("inputlenght=%d\n",strlen(buf));
    /*统计输入字符串的字符种类,和字符个数,创建子节点*/
    for(i=0;buf[i]!='\0';i++)
    {
        tp=ForSearch(array,array_el,buf[i]);
        if(tp!=-1)  //字符已经存在
        {
            (array[tp]->times)++;
        }
        else
        {
            node_tp=(tnode_t*)malloc(sizeof(tnode_t));
            node_tp->c = buf[i];
            node_tp->times=1;
            //node_tp->flag=0;
            node_tp->parent=NULL;
            node_tp->left=NULL;
            node_tp->right=NULL;
            array[array_el]=node_tp;
            array_el++;
        }
    }

    /*创建哈夫曼树*/
    for(i=array_el;i>1;i--)
    {
        ChooseTwo(array,i,&mina,&mini);
        //printf("choose min=%d:max=%d\n",mini,mina);
        if(mina==mini)
        {
            printf("choose error!:%d\n",mina);
        }
        /*创建一个节点作为选定的两个节点的父节点*/
        node_tp=(tnode_t*)malloc(sizeof(tnode_t));
        node_tp->c='#';
        /*左子树,flag为0*/
        node_tp->left=array[mini];
        array[mini]->flag=0;
        array[mini]->parent=node_tp;
        /*左子树,flag为1*/
        node_tp->right=array[mina];
        array[mina]->flag=1;
        array[mina]->parent=node_tp;
        node_tp->times=array[mini]->times +array[mina]->times;

        /*保证将已经处理的节点放出数组外面,移到数组的尾部*/
        if(mini<i-2 && mina<i-2)
        {
            array[mini]=array[i-1];
            array[mina]=array[i-2];
        }else if(mini>=i-2 && mina>=i-2)
        {
            ;
        }else if(mini==i-1||mina==i-1)
        {
            tp=(mini<mina)?mini:mina;
            array[tp]=array[i-2];
        }
        else if(mini==i-2 ||mina==i-2)
        {
            tp=(mini<mina)?mini:mina;
            array[tp]=array[i-1];
        }
        /*将处理后的两个子节点的父节点假如数组*/
        array[i-2]=node_tp;
    }
    array[0]->parent=NULL;
    array[0]->flag=-1;
    /*校验编码过程*/
    if(array[0]->times != strlen(buf))
    {
        printf("error coding\n");
        exit(1);
    }
    printf("\n============================\n  HALLFMANCODING!\n");
    HallfCode(array[0]);
    return 0;
}

  DEBUG的过程就是进步的过程,每一个小错误都是大问题!...
2017-12-04 19:12
快速回复:一个关于哈夫曼编码的问题,运行结果不正确,看了好几天了,不知道哪里 ...
数据加载中...
 
   



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

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