哈夫曼树的应用 输入元素 4 分别输入a 4 b 5 c 6 d 10 输出a--->110 b--->111 c---
来源:学生作业帮 编辑:大师作文网作业帮 分类:综合作业 时间:2024/10/05 04:35:26
哈夫曼树的应用 输入元素 4 分别输入a 4 b 5 c 6 d 10 输出a--->110 b--->111 c--->10 d--->0
#include
#include
#include
#define MAXSIZE 30
#define MAX 100
using namespace std;
typedef struct
{
char data;
int weight;
int parent;
int left;
int right;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct
{
char data;
int weight;
} Tdata;
HuffmanTree HT;
HuffmanCode HC;
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2);
void HuffmanCoding(HuffmanTree HT,Tdata *w,int n);
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2)
{
int i,min1,min2;
*s2=*s1=0;
min1=min2=MAX;
for(i=1; i<=n; i++)
{
if(HT[i].parent==0)
if(HT[i].weight {
min2=min1;
min1=HT[i].weight;
*s2=*s1;
*s1=i;
}
else if(HT[i].weight {
min2=HT[i].weight;
*s2=i;
}
}
}
void HuffmanCoding(HuffmanTree HT,Tdata *w,int n)
{
int m,s1,s2,start,c,f,i;
HTNode *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++)
{
p->data=w[i].data;
p->weight=w[i].weight;
p->left=0;
p->right=0;
p->parent=0;
}
for(; i<=m; i++,p++)
{
p->weight=0;
p->left=0;
p->right=0;
p->parent=0;
}
for(i=n+1; i<=m; i++)
{
SelectMinTree(HT,i-1,&s1,&s2);
HT[s1].parent=i,HT[s2].parent=i;
HT[i].left=s1;
HT[i].right=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].left==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
free(cd);
}
}
int main()
{
Tdata w[MAXSIZE];
int n,i;
cout<<" 请输入元素数:<4>";
cin>>n;
for(i=1; i<=n; i++)
{
cout<<" input"<>";
cin>>w[i].data>>w[i].weight;
}
cout<<" "< HuffmanCoding(HT,w,n);
for(i=1; i<=n; i++)
cout<"< }
#include
#include
#include
#define MAXSIZE 30
#define MAX 100
using namespace std;
typedef struct
{
char data;
int weight;
int parent;
int left;
int right;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct
{
char data;
int weight;
} Tdata;
HuffmanTree HT;
HuffmanCode HC;
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2);
void HuffmanCoding(HuffmanTree HT,Tdata *w,int n);
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2)
{
int i,min1,min2;
*s2=*s1=0;
min1=min2=MAX;
for(i=1; i<=n; i++)
{
if(HT[i].parent==0)
if(HT[i].weight
min2=min1;
min1=HT[i].weight;
*s2=*s1;
*s1=i;
}
else if(HT[i].weight
min2=HT[i].weight;
*s2=i;
}
}
}
void HuffmanCoding(HuffmanTree HT,Tdata *w,int n)
{
int m,s1,s2,start,c,f,i;
HTNode *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++)
{
p->data=w[i].data;
p->weight=w[i].weight;
p->left=0;
p->right=0;
p->parent=0;
}
for(; i<=m; i++,p++)
{
p->weight=0;
p->left=0;
p->right=0;
p->parent=0;
}
for(i=n+1; i<=m; i++)
{
SelectMinTree(HT,i-1,&s1,&s2);
HT[s1].parent=i,HT[s2].parent=i;
HT[i].left=s1;
HT[i].right=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].left==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
free(cd);
}
}
int main()
{
Tdata w[MAXSIZE];
int n,i;
cout<<" 请输入元素数:<4>";
cin>>n;
for(i=1; i<=n; i++)
{
cout<<" input"<
cin>>w[i].data>>w[i].weight;
}
cout<<" "<
for(i=1; i<=n; i++)
cout<
真不容易啊,给你查出问题了.是申请和释放内存出错了.
把
free(cd);
放在 第二个for循环的外面即可.
#include
#include
#include
#define MAXSIZE 30
#define MAX 100
using namespace std;
typedef struct
{
char data;
int weight;
int parent;
int left;
int right;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct
{
char data;
int weight;
} Tdata;
HuffmanTree HT;
HuffmanCode HC;
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2);
void HuffmanCoding(HuffmanTree HT,Tdata *w,int n);
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2)
{
int i,min1,min2;
*s2=*s1=0;
min1=min2=MAX;
for(i=1; iparent=0;
}
for(; iweight=0;
p->left=0;
p->right=0;
p->parent=0;
}
for(i=n+1; i>>>>>>>>>>>>>>>>>
}
int main()
{
Tdata w[MAXSIZE];
int n,i;
coutn;
for(i=1; i
把
free(cd);
放在 第二个for循环的外面即可.
#include
#include
#include
#define MAXSIZE 30
#define MAX 100
using namespace std;
typedef struct
{
char data;
int weight;
int parent;
int left;
int right;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct
{
char data;
int weight;
} Tdata;
HuffmanTree HT;
HuffmanCode HC;
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2);
void HuffmanCoding(HuffmanTree HT,Tdata *w,int n);
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2)
{
int i,min1,min2;
*s2=*s1=0;
min1=min2=MAX;
for(i=1; iparent=0;
}
for(; iweight=0;
p->left=0;
p->right=0;
p->parent=0;
}
for(i=n+1; i>>>>>>>>>>>>>>>>>
}
int main()
{
Tdata w[MAXSIZE];
int n,i;
coutn;
for(i=1; i
哈夫曼树的应用 输入元素 4 分别输入a 4 b 5 c 6 d 10 输出a--->110 b--->111 c---
用c++6做输入a,b,c,d四个整数,输出其中最大的数
输入4个整数a,b,c,d,编写程序,将它们按从大到小的顺序输出
用C语言写一个很简单的程序,输入两个整数a,b,要求输入a-b的值,例如:输入7 4,输出3
c语言:计算A+B 输入 输入数据有多组.每组一行,为两个整数A,B.输入以0 0结束.输出 输出A+B的值
c语言题目:输入正整数a,b,c,输出a/b的小数形式,精确到小数点后c位.例如a=1,b=6,c=4时应输出0.166
按下面程序计算,输入x=3,这输出的答案是( )A.3 B.4 C.5
C语言 输入正整数a,b,c,输出a/b的小数形式,保留小数点后c位.a,b
编程输入两个数x、y,再输入一个字母,当用户输入的字母为A、B、C、D时,分别输出x和y的和、差、积、商
输入a,b,c三个数,输出最大值和最小值.
怎么样编程?输入a,b,c三个整数,输出下列表达式的值 a+b>c&&b==c
C语言编程1.输入一个字母,输出它的后继字母.如输入’a’,则输出’b’.源代码: