#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define n 5
#define m 2*n-1
typedef struct
{ int weight;
int lchild,rchild,parent;
}HTNode;
typedef HTNode Huffmantree[m];
typedef struct
{ char ch;
char bits[n+1];
}CodeNode;
typedef CodeNode HuffmanCode[n];
void InitHuffmanTree(HuffmanTree t)
{ int i;
for (i=0;i<m;i++)
{ t[i].weight=0;
t[i].lchild=[i].rchild=[i].parent=0;
}
}
void InputWeight(HuffmanTree t)
{int i;
char noslip;
for(i=o;i<n;i++)
{
printf("请输入第%d个权值:".i+1);
scanf("%d",&t[i].weight);
}
noslip=getchar();printf("%c",noslip);
}
void SelectMin(HuffmanTree t,int i,int *p1,int *p2)
{int j,min1,min2;
min1=min2=-1;
for(j=0;j<=i;j++)
if(t[j].parent==0)
{
if(t[j].weight<min1||min2==-1)
{if(min1!=-1)
{
min2=min1; *p2=*p1; }
min1=t[j].weight; *p1=j;
}
else
if(t[j].weight<min2||min2==-1)
{min2=t[j].weight;
*p2=j;
}
}
}
viod CreateHuffmanTree(HuffmanTree t)
{int i,p1,p2;
InitHuffmanTree(t);
Inputweught(t);
for(i=n;i<m;i++)
{selectmin(t,i-1,&p1,&p2);
t[p1].parent=T[p2].parent=i;
t[i].lchild=p1;
t[i].rchild=p2;
t[i].weight=t[p1].weight+t[p2].weight;
}
}
void HuffmanCode(Huffmantree t,HuffmanCode h)
{int c,p,i;
char cd[n+1];
int start;
cd[n]='\0';
printf("请输入字符")；
for(i=0;i<n;i++)
{ //printf("%d",i);
h[i].ch=getchar();
start=n;
c=i;
while((p=t[c].parent) !=NULL)
{
ch[--start]=(t[p].lchild==c)?'0';'1';
c=p;
}
strcpy(h[i].bits,&cd[start]);
}
printf("\n");
for(i=0;i<n;i++)
printf("第%d个字符%c的编码为%s\n",i+1,h[i].ch,h[i].bits);
}
void main()
{HuffmanTree t;
HuffmanCode h;
printf("\n请输入5个权值\n");
CreateHuffmanTree(t);
HuffmanCode(t,h);
}
请帮我把这题修改下
要求；
测试情况；
请输入5个权值
请输入第1个权值:8
请输入第2个权值:5
请输入第3个权值:7
请输入第4个权值:12
请输入第5个权值:15
请输入字符 ABCDE
第1个字符A的编码为：00
第2个字符B的编码为：100
第3个字符C的编码为：101
第4个字符D的编码为：01
第5个字符E的编码为：11
看程序代码：
#include"stdlib.h"
#include <iostream.h>
#include <iomanip.h>
const int N=10;//字符的最大个数
struct Hufnode
{
char elem;
int m_weight;
int parent,lchild,rchild; //两个叶子节点回溯到跟节点
};
typedef struct Hufnode HTNode;
typedef HTNode *HuffmanTree;
typedef char** HuffmanCode;
//定义结构字段来存放输入的字符及其权值
struct Weight
{
char elem; //字符
int m_weight; //权值
};
//字符串拷贝
char * strcpy(char *s1,char *s2)
{
for(int i=0;s2[i]!='\0';i++)s1[i]=s2[i];
s1[i]='\0';
return s1;
}
//选择所提供字符中出现频率次数最少的两个
void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
(*s1)=(*s2)=0;
for(int i=1;i<=n;i++)
{
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
}
if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{
if((*s1)==0) (*s1)=i;
else if((*s2)==0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
}
}
}
if((*s1)>(*s2)) //字符出现次数比较
{
i=(*s1);
(*s1)=(*s2);
(*s2)=i;
}
return;
}
//根据字符权值求哈夫曼编码
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
int i,m,s1,s2,start,c,f;
char *cd;
// HuffmanTree p;
if(n<=1) return;
m=2*n-1;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=n;++i)
{
(*HT)[i].elem=w[i-1].elem;
(*HT)[i].m_weight=w[i-1].m_weight;
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(;i<=m;++i)
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(i=n+1;i<=m;++i)
{
Select(*HT,i-1,&s1,&s2);
(*HT)[s1].parent=i;(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight; //将两个最小的合并
}
(*HC)=(HuffmanCode)malloc(n*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';
else cd[--start]='1';
}
(*HC)[i]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
}
}
void main()
{
Weight w[N];
int i;
cout<<"请输入字符的个数:";
int n; cin>>n;
cout<<"请输入字符及其权值(用空格分开)"<<endl;
for(i=0;i<n;i++)
{
char c; int wei;
cin>>c>>wei;
//保存到结构中
w[i].elem=c;
w[i].m_weight=wei;
}
cout<<endl;
//编码
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(&HT,&HC,w,n);
//编码输出
cout<<"哈夫曼编码:"<<endl;
cout<<"字符序号---字符---相应权值---哈夫曼编码"<<endl;
for(i=1;i<=n;i++)
cout<<" "<<i<<" "<<HT[i].elem<<" "<<HT[i].m_weight<<" "<<HC[i]<<endl;
}
执行结果：