50

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

#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;
    }
     }

}

查看全部
l155555
YoungLee2015
2015/06/25 09:05
  • 哈夫曼编码问题 语言
  • 点赞
  • 收藏
  • 回答
    私信

3个回复