问题描述
- 哈夫曼树运行错误 但调试却正确 一直找不成错误
-
估计问题是出在HuffmanCoding 但怎么都找不出来#include "stdio.h" #include "stdlib.h" #include "string.h" char alphabet[]={'A','B','C','D'}; typedef struct { int weight; //权值 int parent; //父节点序号 int left ; int right; }HuffmanTree; typedef char *HuffmanCode; //Huffman编码指针 void SelectNode (HuffmanTree *ht,int n,int *bt1,int *bt2) //从n个节点中选择parent节点为0，权重最小的两个节点 { int i; HuffmanTree *ht1,*ht2,*t; ht1=ht2=NULL; for(i=1;i<=n;i++) { if(!ht[i].parent) //父节点为空 { if(ht1==NULL) { ht1=ht+i; // continue; } if(ht2==NULL) { ht2=ht+i; if(ht1->weight>ht2->weight) { t=ht2; ht2=ht1; ht1=t; //让ht1指向最小节点 ht2指向第二小 } continue; } if(ht1 &&ht2) { if(ht[i].weight<=ht1->weight) { ht2=ht1; //如果还有比ht1更小的则把ht1赋给ht2 ，ht1继续等于最小 ht1=ht+i; } else if(ht[i].weight<ht2->weight){ ht2=ht+i; //没有比ht1更小的 但有比ht2小的 } } } } if(ht1>ht2){ //按数组最初的位置排序 *bt2=ht1-ht; *bt1=ht2-ht; } else { *bt1=ht1-ht; *bt2=ht2-ht; } } void CreateTree(HuffmanTree *ht,int n,int *w) { int i,m=2*n-1; //总节点数 int bt1,bt2; if(n<=1) return ; for(i=1;i<=n;++i) { ht[i].weight=w[i-1]; ht[i].parent=0; ht[i].left=0; ht[i].right=0; } for(;i<=m;++i) { ht[i].weight=0; ht[i].parent=0; ht[i].left=0; ht[i].right=0; } for(i=n+1;i<=m;++i) { SelectNode(ht,i-1,&bt1,&bt2); ht[bt1].parent=i; ht[bt2].parent=i; ht[i].left=bt1; ht[i].right=bt2; ht[i].weight=ht[bt1].weight+ht[bt2].weight; } } void HuffmanCoding(HuffmanTree *ht,int n,HuffmanCode *hc) { char *cd; int start,i; int current,parent; cd=(char*)malloc(sizeof(char)*n); cd[n-1]=''; for(i=1;i<=n;i++) { start=n-1; current=i; //获得当前节点序号 parent=ht[current].parent; //获得当前节点父亲的序号 while(parent) //当父节点不为空 { if(current==ht[parent].left) //若当前节点是父亲的左节点 cd[--start]='0'; //字符最后编码为0 注意这个编码是逆序的 最后其实根节点 else cd[--start]='1'; current=parent; //从当前节点向根节点寻找 parent=ht[parent].parent; } hc[i-1]=(char*)malloc(sizeof(char*)*(n-start)); //分配保存编码的内存 strcpy(hc[i-1],&cd[start]); //复制生成的编码 } free(cd); } void Encode(HuffmanCode *hc,char *alphabet,char *str,char *code) { int len=0,i=0,j; code[0]=''; while(str[i]) { j=0; while(alphabet[j]!=str[i]) //搜索字母在编码表的位置 j++; strcpy(code+len,hc[j]); //字母在叶节点的编号到根节点的编号全部复制给code len=len+strlen(hc[j]); // 扩大len的长度（也就是节点深度） i++; } code[len]=''; } void Decode(HuffmanTree *ht,int m,char *code,char *alphabet,char *decode)//解码 { int position=0,i,j=0; m=2*m-1; while(code[position]) { for(i=m;ht[i].left &&ht[i].right;position++ ) { if(code[position]=='0') i=ht[i].left; else i=ht[i].right; } decode[j]=alphabet[i-1]; j++; } decode[j]=''; } int main() { int i,n=4,m; char test[]="DBDBDABDCDADBDADBDADACDBDBD"; char code[100],code1[100]; int w[]={5,7,2,13}; HuffmanTree *ht; HuffmanCode *hc; m=2*n-1; ht=(HuffmanTree *)malloc((m+1)*sizeof(HuffmanTree)); if(!ht) { printf("分配内存失败n"); exit(0); } CreateTree(ht,n,w); HuffmanCoding(ht,n,hc); for(i=1;i<=n;i++) printf("字母:%c，权重:%d，编码:%sn",alphabet[i-1],ht[i].weight,hc[i-1]); Encode(hc,alphabet,test,code); printf("n字符串：n%sn转换后：n%sn",test,code); Decode(ht,n,code,alphabet,code1); printf("n编码：n%sn转换后：n%sn",code,code1); return 0; }
解决方案
我帮你看看~~~~~~~~~~~~·
解决方案二：
简单帮你修改了下。请采纳！
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
char alphabet[]={'A','B','C','D'};
typedef struct
{
int weight; //权值
int parent; //父节点序号
int left ;
int right;
}HuffmanTree;
typedef char *HuffmanCode; //Huffman编码指针
void SelectNode (HuffmanTree *ht,int n,int *bt1,int *bt2)
//从n个节点中选择parent节点为0，权重最小的两个节点
{
int i;
HuffmanTree *ht1,*ht2,*t;
ht1=ht2=NULL;
for(i=1;i<=n;i++)
{
if(!ht[i].parent) //父节点为空
{
if(ht1==NULL)
{
ht1=ht+i; //
continue;
}
if(ht2==NULL)
{
ht2=ht+i;
if(ht1->weight>ht2->weight)
{
t=ht2;
ht2=ht1;
ht1=t; //让ht1指向最小节点 ht2指向第二小
}
continue;
}
if(ht1 &&ht2)
{
if(ht[i].weight<=ht1->weight)
{
ht2=ht1; //如果还有比ht1更小的则把ht1赋给ht2 ，ht1继续等于最小
ht1=ht+i;
}
else if(ht[i].weight<ht2->weight){
ht2=ht+i; //没有比ht1更小的 但有比ht2小的
}
}
}
}
if(ht1>ht2){ //按数组最初的位置排序
*bt2=ht1-ht;
*bt1=ht2-ht;
}
else
{
*bt1=ht1-ht;
*bt2=ht2-ht;
}
}
void CreateTree(HuffmanTree *ht,int n,int *w)
{
int i,m=2*n-1; //总节点数
int bt1,bt2;
if(n<=1)
return ;
for(i=1;i<=n;++i)
{
ht[i].weight=w[i-1];
ht[i].parent=0;
ht[i].left=0;
ht[i].right=0;
}
for(;i<=m;++i)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].left=0;
ht[i].right=0;
}
for(i=n+1;i<=m;++i)
{
SelectNode(ht,i-1,&bt1,&bt2);
ht[bt1].parent=i;
ht[bt2].parent=i;
ht[i].left=bt1;
ht[i].right=bt2;
ht[i].weight=ht[bt1].weight+ht[bt2].weight;
}
}
void HuffmanCoding(HuffmanTree *ht,int n,HuffmanCode *hc)
{
char *cd;
int start,i;
int current,parent;
cd=(char*)malloc(sizeof(char)*n);
cd[n-1]='';
for(i=1;i<=n;i++)
{
start=n-1;
current=i; //获得当前节点序号
parent=ht[current].parent; //获得当前节点父亲的序号
while(parent) //当父节点不为空
{
if(current==ht[parent].left) //若当前节点是父亲的左节点
cd[--start]='0'; //字符最后编码为0 注意这个编码是逆序的 最后其实根节点
else
cd[--start]='1';
current=parent; //从当前节点向根节点寻找
parent=ht[parent].parent;
}
hc[i-1]=(char*)malloc(sizeof(char)*(n-start)); //分配保存编码的内存
strcpy(hc[i-1],&cd[start]); //复制生成的编码
}
free(cd);
}
void Encode(HuffmanCode *hc,char *alphabet,char *str,char *code)
{
int len=0,i=0,j;
code[0]='';
while(str[i])
{
j=0;
while(alphabet[j]!=str[i]) //搜索字母在编码表的位置
j++;
strcpy(code+len,hc[j]); //字母在叶节点的编号到根节点的编号全部复制给code
len=len+strlen(hc[j]); // 扩大len的长度（也就是节点深度）
i++;
}
code[len]='';
}
void Decode(HuffmanTree *ht,int m,char *code,char *alphabet,char *decode)//解码
{
int position=0,i,j=0;
m=2*m-1;
while(code[position])
{
for(i=m;ht[i].left &&ht[i].right;position++ )
{
if(code[position]=='0')
i=ht[i].left;
else
i=ht[i].right;
}
decode[j]=alphabet[i-1];
j++;
}
decode[j]='';
}
int main()
{
int i,n=4,m;
char test[]="DBDBDABDCDADBDADBDADACDBDBD";
char code[100],code1[100];
int w[]={5,7,2,13};
HuffmanTree *ht;
HuffmanCode *hc;
m=2*n-1;
ht=(HuffmanTree *)malloc((m+1)*sizeof(HuffmanTree));
hc=(HuffmanCode *)malloc((n+1)*sizeof(HuffmanCode));
if(!ht)
{
printf("分配内存失败n");
exit(0);
}
CreateTree(ht,n,w);
HuffmanCoding(ht,n,hc);
for(i=1;i<=n;i++)
printf("字母:%c，权重:%d，编码:%sn",alphabet[i-1],ht[i].weight,hc[i-1]);
Encode(hc,alphabet,test,code);
printf("n字符串：n%sn转换后：n%sn",test,code);
Decode(ht,n,code,alphabet,code1);
printf("n编码：n%sn转换后：n%sn",code,code1);
free(hc);
hc = NULL;
free(ht);
ht = NULL;
return 0;
}
解决方案三：
时间： 2024-08-30 08:07:02
