2 l155555 l155555 于 2015.06.25 17:05 提问

求大神更正一下哈夫曼编码,重谢! 50C

#include
#include
#include

static float weights[]={12.702 ,9.056 ,8.167 ,7.507 ,6.966 ,6.749 ,6.327 ,
6.094 ,5.987 ,4.253 ,4.025 ,2.782 ,2.758 ,2.406 ,
2.360 ,2.228 ,2.105 ,1.974 ,1.929 ,1.492 ,0.978 ,
0.722 ,0.153 ,0.150 ,0.095 ,0.074 };//权值信息数组

static char values[]={'e','t','a','o','i','n','s',
'h','r','d','l','c','u','m',
'w','f','g','y','p','b','v',
'k','j','x','q','z'}; //字符数组信息
typedef struct{
float weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树

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

int min(HuffmanTree t,int i){
int j,mark;
float k=26.4170;

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

    if(t[j].weight<k&&t[j].parent==0){
        k=t[j].weight;
        mark=j;
    }
}                     //逐个迭代求解求小权值

t[mark].parent=1;     //对选中节点进行标记,防止二次访问
return mark;          //返回选中节点的索引值

} //返回i个节点中权值最小的树的根节点序号

void select(HuffmanTree t,int i,int &s1,int &s2){
int temp; //中间变量
s1=min(t,i);
s2=min(t,i);
if (s1>s2){
temp=s1;
s1=s2;
s2=temp;
}

} //从i个节点中选择两个权值最小的节点

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,float *w,int n){
int m,i,s1,s2,start; //中间变量
unsigned c,f;
HuffmanTree p;
char *cd;
if (n<=1){
return;
}
m=2*n-1; //所需节点总数
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

for (p=HT+1,i=1;i<=n;++i,++p,++w){
    (*p).weight=*w;
    (*p).parent=0;
    (*p).lchild=0;
    (*p).rchild=0;
}   //初始化终端节点

for(;i<=m;++i,++p){
    (*p).weight=0.0;
    (*p).parent=0;
    (*p).lchild=0;
    (*p).rchild=0;
}   //初始化非终端节点

for (i=n+1;i<=m;++i){
    select(HT,i-1,s1,s2);
    HT[s1].parent=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,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
        if(HT[f].lchild==c){
            cd[--start]='0';//左分支为'0'
        }
        else{
            cd[--start]='1';//右分支为'1'
        }
    }//根据节点的父节点索引值求解节点的哈夫曼编码

    HC[i]=(char*)malloc((n-start)*sizeof(char));
           //动态分配对应编码存储空间大小
    strcpy(HC[i],&cd[start]);//字符串拷贝
}
free(cd);//释放内存空间

}
void coding(HuffmanCode HC){
int index;//索引变量
int textIndex;//电报正文索引值
int valueIndex;//电报正文字符的索引值
int teleLength;//电报正文包含的字符个数
int *codeIndex;//电报正文字符对应的哈夫曼编码表中的索引呢
char *teleText;//中间变量,存储电报正文
char *huCoding;//中间变量,用于存储电报正文的哈夫曼编码
int codeLength=0;//电报正文对应哈夫曼编码的总长度,初始化长度为0

printf("请输入电报正文长度:");
    scanf("%d",&teleLength);
codeIndex=(int*)malloc(teleLength*sizeof(int));//分配用于存储编码表索引值的存储空间
teleText=(char*)malloc(teleLength*sizeof(char));
printf("请输入电报正文:");
    scanf("%s",teleText);//输入电报正文字符串

for(textIndex=0;textIndex<strlen(teleText);textIndex++){
    char textChar;
    textChar=teleText[textIndex];
    if((textChar<65)||(textChar>122)||(textChar<97&&textChar>90)){
        printf("您输入了不合法字符%s!\n",teleText);
    return;
    }//如果输入非法字符,程序返回
    if (textChar<96){
        textChar=textChar+32;
    }//如果电报正文为大写则进行转化

    for(valueIndex=1;valueIndex<=26;valueIndex++){
        if(values[valueIndex-1]==textChar){
        codeIndex[textIndex]=valueIndex;//累计编码的索引值
        codeLength+=strlen(HC[valueIndex]);//找到对应字符,累计编码长度值
        break;
        }
    }//依次查找对应字符
}  //根据哈夫曼编码表对电报正文进行编码
huCoding=(char*)malloc((codeLength+1)*sizeof(char));//动态分配存储电文编码的内存空间

for(index=0;index<=codeLength;index++){
    huCoding[index]='\0';//字符串结束符
}//初始化上述内存数据

for(textIndex=0;textIndex<strlen(teleText);textIndex++)//strlen计数
{
    huCoding=strcat(huCoding,HC[codeIndex[textIndex]]);//编码字符串连接
}//组装电文编码信息
printf("电报正文的哈夫曼编码:%s\n",huCoding);
free(teleText);
free(codeIndex);
free(huCoding);//释放内存空间

}

void decoding(HuffmanTree HT){
int index;//索引变量
int tempIndex=47;//记录临时索引值
char huCode;//单个编码
int huCodeLen;//电文编码的长度
char huCodes;//电文字符串
HTNode htNode;//哈夫曼树的节点
printf("请输入电报正文哈夫曼编码长度:");
scanf("%d",&huCodeLen);
huCodes=(char
)malloc(huCodeLen*sizeof(char));//分配用于存储电文字符编码的存储空间
printf("请输入电报正文的哈夫曼编码字符串:");
scanf("%s",huCodes);//输入电报正文的编码字符串

htNode=HT[47];
for(index=0;index<strlen(huCodes);index++){
    huCode=huCodes[index];//获取单个编码字符
    if(tempIndex<=0){
        printf("您输入的哈夫曼编码%s不合法!\n",huCodes);
        return;
    }//没有找到对应编码字符
    if(huCode=='1'){
        if(HT[htNode.rchild].lchild==0 && HT[htNode.rchild].rchild==0){
            tempIndex=htNode.rchild;
            printf("%c",values[tempIndex-1]);////遍历至叶子节点,找到一个电文子字符
            htNode=HT[47];//再次指向根节点
        }
        else{
            tempIndex=htNode.rchild;
            htNode=HT[tempIndex];////继续遍历,记录当前节点的信息
        }
    }   //向右遍历
    else if(huCode=='0'){
        if(HT[htNode.lchild].lchild==0 && HT[htNode.lchild].rchild==0){
            tempIndex=htNode.lchild;
            printf("%c",values[tempIndex-1]);//遍历至叶子节点,找到一个电文子字符
            htNode=HT[47];//再次指向根节点
        }
        else{
            tempIndex=htNode.lchild;
            htNode=HT[tempIndex];//继续遍历,记录当前节点的信息
        }
    }   //向左遍历
    else{
        printf("您输入的电报正文编码%s不合法!",huCodes);
        return;
    }
}
printf("\n");

} //将电报正文的哈夫曼编码进行译码操作

void printfHuffmanTree(HuffmanTree HT){
int index;
HTNode htNode;//哈夫曼树节点
printf("*************哈夫曼树表***********\n");
printf(" 权值 根节点 左子树 右子树\n");
for(index=1;index<48;index++){
htNode=HT[index];//获取当前树节点
printf("%12.4f%5d%6d%7d\n",htNode.weight,htNode.parent,htNode.lchild,htNode.rchild);
}
} //打印哈夫曼树表

void printfHuffmanCode(HuffmanCode HC){
int index;
printf("*******哈夫曼编码表*******\n");
for(index=1;index<=26;index++){
printf("%7c ------ ",values[index-1]);
printf("%s\n",HC[index]);
}
} //打印哈夫曼编码表

int main(){
HuffmanTree HT;
HuffmanCode HC;

HuffmanCoding(HT,HC,weights,26);//构造哈夫曼树
while(1){
int a;
printf("*******欢迎使用哈夫曼编码程序!*******\n");
printf("*********请输入您需要进行的操作*********\n");
printf("-->1.对电报正文编码     -->2.对电报编码译码\n");
printf("-->3.打印哈夫曼编码     -->4.打印哈夫曼树\n");
printf("****************选择0退出程序****************\n");    

scanf("%d",&a);
     getchar();


switch(a){
case 0:
    return 0;
    break;
case 1:
coding(HC);//编码,对已建好的哈夫曼树,对电报正文进行编码
break;

case 2:
decoding(HT);//译码,对电文的内容进行编码翻译处理
break;
case 3:
printfHuffmanCode(HC);
break;
case 4:
printfHuffmanTree(HT);
break;
default:
    printf("您的输入有误!\n");
    break;
    }
     }

}

3个回答

u012736907
u012736907   2015.06.25 17:12
 // 哈夫曼树及编码.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#define MAX 10000
#define NUM 10000


typedef struct
{
    int weight;
    int parent;
    int lchild;
    int rchild;
}HNodeType;

typedef struct
{
    int bit[MAX];
    int start;
}HCodeType;
HNodeType HFMTree[MAX];
HCodeType HuffCode[MAX];

/*创建哈夫曼树*/
void Create_HuffMTree(HNodeType HFMTree[],int n)
{
    int m1,m2,x1,x2;
    for(int i=0;i<2*n-1;i++)
    {
        HFMTree[i].weight=0;
        HFMTree[i].parent=-1;
        HFMTree[i].lchild=-1;
        HFMTree[i].rchild=-1;
    }
    for(int i=0;i<n;i++)
    {
        printf("添加的第%d个叶子值为:",i+1);
        scanf_s("%d",&HFMTree[i].weight);
    }
    for(int i=0;i<n-1;i++)
    {
        x1=x2=MAX;
        m1=m2=0;
        for(int j=0;j<n+i;j++)
        {
            if(HFMTree[j].parent==-1&&HFMTree[j].weight<x1)
            {
                x2=x1;
                m2=m1;
                x1=HFMTree[j].weight;
                m1=j;
            }
            else if(HFMTree[j].parent==-1&&HFMTree[j].weight<x2)
            {
                x2=HFMTree[j].weight;
                m2=j;
            }

        }
        HFMTree[m1].parent=n+i;
        HFMTree[m2].parent=n+i;
        HFMTree[n+i].weight=HFMTree[m1].weight+HFMTree[m2].weight;
        HFMTree[n+i].lchild=m1;
        HFMTree[n+i].rchild=m2;
    }
}

/*哈夫曼编码*/
void HaffmanCode(HNodeType HFMTree[],HCodeType HuffCode[],int n)
{
    HCodeType cd;
    int c,p;
    for(int i=0;i<n;i++)
    {
        cd.start=n-1;
        c=i;
        p=HFMTree[c].parent;
        while(p!=-1)
        {
            if(HFMTree[p].lchild==c)
            {
                cd.bit[cd.start]=0;
            }
            else if(HFMTree[p].rchild==c)
            {
                cd.bit[cd.start]=1;
            }
            cd.start--;
            c=p;
            p=HFMTree[c].parent;
        }

        for(int j=cd.start+1;j<n;j++)
        {
            HuffCode[i].bit[j]=cd.bit[j];
        }
        HuffCode[i].start=cd.start+1;
    }
    for(int i=0;i<n;i++)
    {
        printf("\n叶子的值为%d的编码:",HFMTree[i].weight);
        for(int j=HuffCode[i].start;j<n;j++)
        {
            printf("%d",HuffCode[i].bit[j]);
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int n=5;
    printf("哈夫曼树的叶子结点个数n=");
    scanf_s("%d",&n);
    Create_HuffMTree(HFMTree,n);
    printf("\n哈夫曼树表示为:\n");
    for (int i=0;i<2*n-1;i++)
        printf("i=%d\tweight:%d\tlchild=%d\trchild=%d\tparent=%d\n",i,HFMTree[i].weight,HFMTree[i].lchild,HFMTree[i].rchild,HFMTree[i].parent);
    printf("\n哈夫曼树的叶子节点的编码为:");
    HaffmanCode(HFMTree,HuffCode,n);
    printf("\n\n");
    return 0;
}

Lijinquan01
Lijinquan01   2015.06.25 17:38

你去翻翻紫色那本数据结构的那本书,看上面怎么写的霍夫曼算法

cyxhahaha
cyxhahaha   2015.06.25 19:42

写得太长了吧……其实写竞赛风格的代码简洁清晰得多,而且这个算法可以用堆实现的,更加简单,建议看看书重写。

Csdn user default icon
上传中...
上传图片
插入图片