求哈夫曼树的打印树的代码。能够打印出一颗树的形状 要求输入n=6,字母abcdef ,权值 分别是2,3,4,7,8,9.
利用一下面的代码来画一棵树,在线等。#include<stdio.h>#include<string.h>#include<conio.h>#defineN10#defi...
利用一下面的代码来画一棵树,在线等。
#include <stdio.h>
#include<string.h>
#include<conio.h>
#define N 10
#define M 2*N-1
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode; //动态分配数组储存哈夫曼树
typedef struct{
char data;int weight;
char code [N];
}HTCode; //建立哈夫曼树结点
void Init (HTCode hc[],int*n ){
int i;
printf ("\ninput n=");
scanf("%d",&(*n));
printf("\ninput %d character\n",*n);
for (i=1; i<=*n;i++) hc[i].data=getch();
printf("\ninput %d weight\n",*n);
for (i=1; i<=*n;i++)scanf("%d",&(hc[i].weight));
} //读取每个节点的数据,权值放入字符串数组hc中
//选取权值最先的两个二叉树构成一个新的二叉树
void Select (HTNode ht[],int k,int *s1,int *s2)
{
int i;
for(i=1;i<=k && ht[i].parent!=0 ;i++);
*s1=i;
for(i=1;i<=k;i++)
if (ht[i].parent==0 && ht[i].weight<ht[*s1].weight)
*s1=i;
for(i=1;i<=k;i++)
if (ht[i].parent==0 && i!=*s1)break;
*s2=i;
for(i=1;i<=k;i++)
if(ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight)
*s2=i;
}
void HuffmanCoding (HTNode ht[],HTCode hc[],int n ){
char cd[N];
int i,j,m,c,f,s1,s2,start;
m=2*n-1; //有n个叶子节点的哈夫曼树有2n-1个节点
for(i=1;i<=m;i++){
if(i<=n) ht[i].weight=hc[i].weight;
else ht[i].weight=0;
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
for (i=n+1;i<=m;i++ ){
//在HT[1…i-1]选择parent为0且weight最小的两个结点,其序号分别是s1,s2
Select ( ht,i-1,&s1,&s2);
ht[s1].parent=i;ht[s2].parent=i;
ht[i].lchild=s1; ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
//哈夫曼编码
cd[n-1]='\0';
for (i=1;i<=n;i++)
{
start=n-1;
for (c=i,f=ht[i].parent;f;c=f,f=ht[f].parent) //逐个字符求哈夫曼编码
if(ht[f].lchild==c) cd[-- start]='0';
else cd [--start]='1';
strcpy( hc[i].code,&cd[start]);
}
}
void main()
{
int i,m,n,w[N+1];
HTNode ht[M+1];
HTCode hc[N+1];
Init(hc,&n);
HuffmanCoding(ht,hc,n);
for (i=1;i<=n;i++)
printf("\n%c---%s\n",hc[i].data,hc[i].code);
} 展开
#include <stdio.h>
#include<string.h>
#include<conio.h>
#define N 10
#define M 2*N-1
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode; //动态分配数组储存哈夫曼树
typedef struct{
char data;int weight;
char code [N];
}HTCode; //建立哈夫曼树结点
void Init (HTCode hc[],int*n ){
int i;
printf ("\ninput n=");
scanf("%d",&(*n));
printf("\ninput %d character\n",*n);
for (i=1; i<=*n;i++) hc[i].data=getch();
printf("\ninput %d weight\n",*n);
for (i=1; i<=*n;i++)scanf("%d",&(hc[i].weight));
} //读取每个节点的数据,权值放入字符串数组hc中
//选取权值最先的两个二叉树构成一个新的二叉树
void Select (HTNode ht[],int k,int *s1,int *s2)
{
int i;
for(i=1;i<=k && ht[i].parent!=0 ;i++);
*s1=i;
for(i=1;i<=k;i++)
if (ht[i].parent==0 && ht[i].weight<ht[*s1].weight)
*s1=i;
for(i=1;i<=k;i++)
if (ht[i].parent==0 && i!=*s1)break;
*s2=i;
for(i=1;i<=k;i++)
if(ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight)
*s2=i;
}
void HuffmanCoding (HTNode ht[],HTCode hc[],int n ){
char cd[N];
int i,j,m,c,f,s1,s2,start;
m=2*n-1; //有n个叶子节点的哈夫曼树有2n-1个节点
for(i=1;i<=m;i++){
if(i<=n) ht[i].weight=hc[i].weight;
else ht[i].weight=0;
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
for (i=n+1;i<=m;i++ ){
//在HT[1…i-1]选择parent为0且weight最小的两个结点,其序号分别是s1,s2
Select ( ht,i-1,&s1,&s2);
ht[s1].parent=i;ht[s2].parent=i;
ht[i].lchild=s1; ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
//哈夫曼编码
cd[n-1]='\0';
for (i=1;i<=n;i++)
{
start=n-1;
for (c=i,f=ht[i].parent;f;c=f,f=ht[f].parent) //逐个字符求哈夫曼编码
if(ht[f].lchild==c) cd[-- start]='0';
else cd [--start]='1';
strcpy( hc[i].code,&cd[start]);
}
}
void main()
{
int i,m,n,w[N+1];
HTNode ht[M+1];
HTCode hc[N+1];
Init(hc,&n);
HuffmanCoding(ht,hc,n);
for (i=1;i<=n;i++)
printf("\n%c---%s\n",hc[i].data,hc[i].code);
} 展开
2个回答
展开全部
利用一下面的代码来画一棵树,在线等。
#include <stdio.h>
#include<string.h>
#include<conio.h>
#define N 10
#define M 2*N-1
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode; //动态分配数组储存哈夫曼树
typedef struct{
char data;int weight;
char code [N];
}HTCode; //建立哈夫曼树结点
void Init (HTCode hc[],int*n ){
int i;
printf ("\ninput n=");
scanf("%d",&(*n));
printf("\ninput %d character\n",*n);
for (i=1; i<=*n;i++) hc[i].data=getch();
printf("\ninput %d weight\n",*n);
for (i=1; i<=*n;i++)scanf("%d",&(hc[i].weight));
} //读取每个节点的数据,权值放入字符串数组hc中
//选取权值最先的两个二叉树构成一个新的二叉树
void Select (HTNode ht[],int k,int *s1,int *s2)
{
int i;
for(i=1;i<=k && ht[i].parent!=0 ;i++);
*s1=i;
for(i=1;i<=k;i++)
if (ht[i].parent==0 && ht[i].weight<ht[*s1].weight)
*s1=i;
for(i=1;i<=k;i++)
if (ht[i].parent==0 && i!=*s1)break;
*s2=i;
for(i=1;i<=k;i++)
if(ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight)
*s2=i;
}
void HuffmanCoding (HTNode ht[],HTCode hc[],int n ){
char cd[N];
int i,j,m,c,f,s1,s2,start;
m=2*n-1; //有n个叶子节点的哈夫曼树有2n-1个节点
for(i=1;i<=m;i++){
if(i<=n) ht[i].weight=hc[i].weight;
else ht[i].weight=0;
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
for (i=n+1;i<=m;i++ ){
//在HT[1…i-1]选择parent为0且weight最小的两个结点,其序号分别是s1,s2
Select ( ht,i-1,&s1,&s2);
ht[s1].parent=i;ht[s2].parent=i;
ht[i].lchild=s1; ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
//哈夫曼编码
cd[n-1]='\0';
for (i=1;i<=n;i++)
{
start=n-1;
for (c=i,f=ht[i].parent;f;c=f,f=ht[f].parent) //逐个字符求哈夫曼编码
if(ht[f].lchild==c) cd[-- start]='0';
else cd [--start]='1';
strcpy( hc[i].code,&cd[start]);
}
}
void main()
{
int i,m,n,w[N+1];
HTNode ht[M+1];
HTCode hc[N+1];
Init(hc,&n);
HuffmanCoding(ht,hc,n);
for (i=1;i<=n;i++)
printf("\n%c---%s\n",hc[i].data,hc[i].code);
}
#include <stdio.h>
#include<string.h>
#include<conio.h>
#define N 10
#define M 2*N-1
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode; //动态分配数组储存哈夫曼树
typedef struct{
char data;int weight;
char code [N];
}HTCode; //建立哈夫曼树结点
void Init (HTCode hc[],int*n ){
int i;
printf ("\ninput n=");
scanf("%d",&(*n));
printf("\ninput %d character\n",*n);
for (i=1; i<=*n;i++) hc[i].data=getch();
printf("\ninput %d weight\n",*n);
for (i=1; i<=*n;i++)scanf("%d",&(hc[i].weight));
} //读取每个节点的数据,权值放入字符串数组hc中
//选取权值最先的两个二叉树构成一个新的二叉树
void Select (HTNode ht[],int k,int *s1,int *s2)
{
int i;
for(i=1;i<=k && ht[i].parent!=0 ;i++);
*s1=i;
for(i=1;i<=k;i++)
if (ht[i].parent==0 && ht[i].weight<ht[*s1].weight)
*s1=i;
for(i=1;i<=k;i++)
if (ht[i].parent==0 && i!=*s1)break;
*s2=i;
for(i=1;i<=k;i++)
if(ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight)
*s2=i;
}
void HuffmanCoding (HTNode ht[],HTCode hc[],int n ){
char cd[N];
int i,j,m,c,f,s1,s2,start;
m=2*n-1; //有n个叶子节点的哈夫曼树有2n-1个节点
for(i=1;i<=m;i++){
if(i<=n) ht[i].weight=hc[i].weight;
else ht[i].weight=0;
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
for (i=n+1;i<=m;i++ ){
//在HT[1…i-1]选择parent为0且weight最小的两个结点,其序号分别是s1,s2
Select ( ht,i-1,&s1,&s2);
ht[s1].parent=i;ht[s2].parent=i;
ht[i].lchild=s1; ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
//哈夫曼编码
cd[n-1]='\0';
for (i=1;i<=n;i++)
{
start=n-1;
for (c=i,f=ht[i].parent;f;c=f,f=ht[f].parent) //逐个字符求哈夫曼编码
if(ht[f].lchild==c) cd[-- start]='0';
else cd [--start]='1';
strcpy( hc[i].code,&cd[start]);
}
}
void main()
{
int i,m,n,w[N+1];
HTNode ht[M+1];
HTCode hc[N+1];
Init(hc,&n);
HuffmanCoding(ht,hc,n);
for (i=1;i<=n;i++)
printf("\n%c---%s\n",hc[i].data,hc[i].code);
}
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询