霍夫曼树的几个小问题
[code=C/C++][/code]#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define n 100
#define m 2*n-1
typedef struct
{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode;
typedef struct{
char ch;
char bits;
}CodeNode;
typedef struct
{
char cha;
int number;
}COUNTER;
int Init(HTNode ht[])
{
int i,s=1;
COUNTER counter[26];
char ch;
printf("请输入一段字符来确定权值：(限大写字母,以'!'号为结束标志)\n");
scanf("%c",&ch);
counter[1].cha='A';
counter[2].cha='B';
counter[3].cha='C';
counter[4].cha='D';
counter[5].cha='E';
counter[6].cha='F';
counter[7].cha='G';
counter[8].cha='H';
counter[9].cha='I';
counter[10].cha='J';
counter[11].cha='K';
counter[12].cha='L';
counter[13].cha='M';
counter[14].cha='N';
counter[15].cha='O';
counter[16].cha='P';
counter[17].cha='Q';
counter[18].cha='R';
counter[19].cha='S';
counter[20].cha='T';
counter[21].cha='U';
counter[22].cha='V';
counter[23].cha='W';
counter[24].cha='X';
counter[25].cha='Y';
counter[26].cha='Z';
for(i=1;i<=26;i++)
counter[i].number=0;
while(ch!='!')
{
switch(ch)
{
case 'A':counter[1].number++;break;
case 'B':counter[2].number++;break;
case 'C':counter[3].number++;break;
case 'D':counter[4].number++;break;
case 'E':counter[5].number++;break;
case 'F':counter[6].number++;break;
case 'G':counter[7].number++;break;
case 'H':counter[8].number++;break;
case 'I':counter[9].number++;break;
case 'J':counter[10].number++;break;
case 'K':counter[11].number++;break;
case 'L':counter[12].number++;break;
case 'M':counter[13].number++;break;
case 'N':counter[14].number++;break;
case 'O':counter[15].number++;break;
case 'P':counter[16].number++;break;
case 'Q':counter[17].number++;break;
case 'R':counter[18].number++;break;
case 'S':counter[19].number++;break;
case 'T':counter[20].number++;break;
case 'U':counter[21].number++;break;
case 'V':counter[22].number++;break;
case 'W':counter[23].number++;break;
case 'X':counter[24].number++;break;
case 'Y':counter[25].number++;break;
case 'Z':counter[26].number++;break;
}
scanf("%c",&ch);
}
for(i=1;i<=26;i++)
{
if(counter[i].number!=0)
{
ht[s].weight=counter[i].number;
ht[s].ch=counter[i].cha;
s++;
}
}
s=s-1;
return s;
}
void select(HTNode ht[],int q,int *p1,int *p2) //select函数，选出HT树到s为止，权值最小且parent为0的2个节点
{
int i,j,x,y;
for(j=1;j<=q;++j)
{
if(ht[j].parent==0)
{
x=j;
break;
}
}
for(i=j+1;i<=q;++i)
{
if(ht[i].weight<ht[x].weight&&ht[i].parent==0)
{
x=i; //选出最小的节点
}
}
for(j=1;j<=q;++j)
{
if(ht[j].parent==0&&x!=j)
{
y=j;
break;
}
}
for(i=j+1;i<=q;++i)
{
if(ht[i].weight<ht[y].weight&&ht[i].parent==0&&x!=i)
{
y=i; //选出次小的节点
}
}
if(x>y)
{
*p1=y;
*p2=x;
}
else
{
*p1=x;
*p2=y;
}
}
void huffman_setup(HTNode ht[],int s) //构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC
{
int i,a;
int p1,p2;
a=2*s-1;
for(i=1;i<=a;i++)
{
if(i<=s)
{
ht[i].weight=ht[i].weight;
}
else
{
ht[i].weight=0;
}
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
for(i=s+1;i<=m;++i) //建立赫夫曼树
{
select(ht,i-1,&p1,&p2);
ht[p1].parent=i;
ht[p2].parent=i;
ht[i].lchild=p1;
ht[i].rchild=p2;
ht[i].weight=ht[p1].weight+ht[p2].weight;
}
}
void huffman_code(CodeNode hc[],HTNode ht[],int s)
{
char cd[m];
int i,start,c,f;
cd[s-1]='\0';
for(i=1;i<=n;++i) //给n个字符编码
{
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';
}
else
{
cd[--start]='1';
}
}
hc[i].ch=ht[i].ch;
hc[i].bits=cd[m];
}
}
void huffman_code(CodeNode hc[])
{
int i=1;
char c;
printf("请输入您想要进行霍夫曼编码的信息(以'!'为结束标志，必须包含霍夫曼树中原有的元素)：\n");
c=getchar();
while(c!='!')
{
while(c!=hc[i].bits)
{
i++;
}
printf("%s",hc[i].bits);
c=getchar();
}
}
void huffman_read(HTNode ht[],int s)
{
int i,j,t;
char b;
t=2*s-1;
i=t;
printf("请输入霍夫曼代码,为您进行编译!\n");
scanf("%c",&b);
printf("解码后的信息是：");
while(b!='!')
{
if(b=='0')
i=ht[i].lchild;
else i=ht[i].rchild;
if(ht[i].lchild==0)
{
printf("%c",ht[i].ch);
j=i;
i=t;
}
scanf("%c",&b);
}
}
int main()
{
int s,i;
int choice,flag=1;
HTNode ht[m];
CodeNode hc[n];
printf("***********构建霍夫曼树***********\n");
s=Init(ht);//初始化
huffman_setup(ht,s);
printf("根据输入的信息，已确定相应的霍夫曼树：\n");
for(i=0;i<s;i++)
{
printf("%c ---> %s ",hc[i].ch,hc[i].bits);
}
while(flag)
{
printf("请输入您想要进行的操作：\n 1 输入密码信息，输出霍夫曼代码\n 2 输入霍夫曼代码，给出翻译\n");
switch(choice)
{
case 1:huffman_code(hc);
case 2:huffman_read(ht,s);
case 3:flag=0;
}
}
return 0;
}
自己写的霍夫曼编码，但有问题，总是中断，请高手指教！
[解决办法]
调代码,是基本技能!
[解决办法]
越界了、
