主题:急!!!求高手指教!!!关于哈夫曼编码的问题!我的程序运行很诡异!
我写了一个关于哈夫曼编码的程序,就是输入字母以及权重,显示出编码,我查不出我的程序出了什么问题,能运行,但结果很诡异,求高手指教!!!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXVALUE 10000 //定义最大权值
#define MAXLEAF 300 //定义哈夫曼中叶子结点个数
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 100
#define TEXTCODELEN 100
#define CODELEN 200 //字符的哈夫曼编码长度
typedef struct{
char ch; //字符
int weight; //权值
int pat; //双亲结点在数组中的序号
int lc; //左孩子在数组中的序号
int rc; //右孩子在数组中的序号
}HNode;
typedef struct{
int bit[MAXBIT]; //存储编码
int start; //表示编码在数组中的开始位置
}HCodeType;
typedef struct{
char ch; //字符
int weight; //权值
char bm[CODELEN +1]; //字符的哈夫曼编码
}ELEM; //元素数据类型
void HaffmanTree(int n,HNode HuffNode[MAXNODE]){ //构造哈夫曼树
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++) //数组HuffNode[]初始化
{
HuffNode[i].ch=0;
HuffNode[i].weight=0;
HuffNode[i].pat=-1;
HuffNode[i].lc=-1;
HuffNode[i].rc=-1;
}
printf("输入结点的的字母及权值:\n");
for(i=0;i<n;i++)
scanf("%c%d",&HuffNode[i].ch,&HuffNode[i].weight); //输入n个叶子结点的权值
for(i=0;i<2*n-1;i++)
{
m1=m2=MAXVALUE;
x1=x2=-1;
for(j=0;j<i;j++)
{
if(HuffNode[j].pat==-1&&HuffNode[j].weight<m1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else
if(HuffNode[j].pat==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight;
x2=j;
}
}
//将找出的两课子数合并为一棵子树
HuffNode[x1].pat= i;
HuffNode[x2].pat=i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lc=x1;
HuffNode[n+i].rc=x2;
}
}
void HaffmanCode(int n,HNode HuffNode[MAXNODE],HCodeType HuffCode[MAXLEAF]){
//哈夫曼编码
HCodeType cd;
int i,j,c,p;
for(i=0;i<n;i++)
{
cd.start=n;
c=i;
p=HuffNode[c].pat;
while(p!=-1)
{if(HuffNode[p].lc==c)
cd.bit[cd.start--]=0;
else
cd.bit[cd.start--]=1;
c=p;
p=HuffNode[c].pat;
}
cd.start++;
HuffCode[i]=cd;
}
for(i=0;i<n;i++)
{
printf("%c的编码是:",HuffNode[i].ch);
for(j=HuffCode[i].start;j<=n;j++)
printf("%d",HuffCode[i].bit[j]);
printf("\n");
}
}
void main()
{
int i; char choice;
HNode HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF];
printf("请输入叶子结点的个数:\n");
scanf("%d",&i);
HaffmanTree(i,HuffNode);
HaffmanCode(i,HuffNode,HuffCode);
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXVALUE 10000 //定义最大权值
#define MAXLEAF 300 //定义哈夫曼中叶子结点个数
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 100
#define TEXTCODELEN 100
#define CODELEN 200 //字符的哈夫曼编码长度
typedef struct{
char ch; //字符
int weight; //权值
int pat; //双亲结点在数组中的序号
int lc; //左孩子在数组中的序号
int rc; //右孩子在数组中的序号
}HNode;
typedef struct{
int bit[MAXBIT]; //存储编码
int start; //表示编码在数组中的开始位置
}HCodeType;
typedef struct{
char ch; //字符
int weight; //权值
char bm[CODELEN +1]; //字符的哈夫曼编码
}ELEM; //元素数据类型
void HaffmanTree(int n,HNode HuffNode[MAXNODE]){ //构造哈夫曼树
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++) //数组HuffNode[]初始化
{
HuffNode[i].ch=0;
HuffNode[i].weight=0;
HuffNode[i].pat=-1;
HuffNode[i].lc=-1;
HuffNode[i].rc=-1;
}
printf("输入结点的的字母及权值:\n");
for(i=0;i<n;i++)
scanf("%c%d",&HuffNode[i].ch,&HuffNode[i].weight); //输入n个叶子结点的权值
for(i=0;i<2*n-1;i++)
{
m1=m2=MAXVALUE;
x1=x2=-1;
for(j=0;j<i;j++)
{
if(HuffNode[j].pat==-1&&HuffNode[j].weight<m1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else
if(HuffNode[j].pat==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight;
x2=j;
}
}
//将找出的两课子数合并为一棵子树
HuffNode[x1].pat= i;
HuffNode[x2].pat=i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lc=x1;
HuffNode[n+i].rc=x2;
}
}
void HaffmanCode(int n,HNode HuffNode[MAXNODE],HCodeType HuffCode[MAXLEAF]){
//哈夫曼编码
HCodeType cd;
int i,j,c,p;
for(i=0;i<n;i++)
{
cd.start=n;
c=i;
p=HuffNode[c].pat;
while(p!=-1)
{if(HuffNode[p].lc==c)
cd.bit[cd.start--]=0;
else
cd.bit[cd.start--]=1;
c=p;
p=HuffNode[c].pat;
}
cd.start++;
HuffCode[i]=cd;
}
for(i=0;i<n;i++)
{
printf("%c的编码是:",HuffNode[i].ch);
for(j=HuffCode[i].start;j<=n;j++)
printf("%d",HuffCode[i].bit[j]);
printf("\n");
}
}
void main()
{
int i; char choice;
HNode HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF];
printf("请输入叶子结点的个数:\n");
scanf("%d",&i);
HaffmanTree(i,HuffNode);
HaffmanCode(i,HuffNode,HuffCode);
}