画出哈夫曼树，并求出每个字符的哈夫曼编码

哈夫曼树及哈夫曼编码的C程序实现(数据结构题)~

去年做的课程设计，有什么不合要求的自己改改

#include
#include
#include

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表

void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 算法6.13
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("
哈夫曼树的构造过程如下所示：");
printf("HT初态:
结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("
%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1);
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;
printf("
select: s1=%d s2=%d
", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("
%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}

//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("输入结点数:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值
",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("
各结点的哈夫曼编码:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s
",i,w[i-1],HC[i]);
getchar();
}

哈夫曼树是：
1
/ \
0.42 0.58
/ \ / \
0.15 0.27 F0.28 G0.30
/ \ / \
0.05 C0.10 D0.13 E0.14
/ \
A0.02 B 0.03
哈夫曼编码是：
A： 0000 B：0001 C：001 D：010 E：011 F：10 G：11

哈夫曼树           74

                                  / \

                   42                               32

                  /    \                            /    \

           23         19                     12     20  

         /    \        /   \

      15     8     9   10

      /   \

    8    7 

  / \

 3   5 

编码：A（010）B（00000）C（00001）D（001）E（10）F（11）G（0001）H（011）

带权路径长度值为：（3+5）*5+7*4+（8+9+10）*3+（12+20）*2=213     

     This is  it！！！  求采纳

上一个回答有误，画哈夫曼树遵循的原则是找出两个频率最小的数，它们相加的和与剩下的数重新排序，继续找出两个最小的数，以此类推。百度经验里讲得很清楚网页链接

---

栾川县18390865802： 假定某系统在通信联络中只可能出现8种字符a,b,c,d,e,f,g,h,各字符出现的概率分别为0.03,0.28.0.06,0.070.14,0.24,0.08,0.10(1)画出哈夫曼树(2)给出每个字... - ？
庾淑瑞芝：[答案] a:0110; b:10; c:0111; d:1111; e:110; f:00; g:1110; h:010. WPL=2*0.24+3*0.1+4*0.03+4*0.06+4*0.07+4*0.08+3*0.14+2*0.28=2.72 注:树传不上来,你可以根据编码自己画,谢谢!

栾川县18390865802： 已知在一段文字中共有A,B,C,D,E,F,G,H八种字母,它们出现的次数分别是9,3,5,8,12,20,7,10, - ？
庾淑瑞芝： 哈夫曼树 74 / \ 42 32 / \ / \ 23 19 12 20 / \ / \ 15 8 9 10 / \ 8 7 / \ 3 5 编码:A(010)B(00000)C(00001)D(001)E(10)F(11)G(0001)H(011) 带权路径长度值为:(3+5)*5+7*4+(8+9+10)*3+(12+20)*2=213 这个就是哈夫曼树及其编码,是计算机中数据结构的一个概念,一种特殊的树、 This is it ~~~ 求采纳

栾川县18390865802： 哈夫曼树和编码 - ？
庾淑瑞芝： A出现的概率是1/2,B出现的概率是1/18,C出现的概率是5/18,D出现的概率是3/18. 编码步骤: 1.初始化,根据符号概率的大小按由大到小顺序对符号进行排序. 2.把概率最小的两个符号组成一个节点. 3.重复步骤2,得到得到另外的节点,形成...

栾川县18390865802： 设字符集D={A,B,C,D,E},各字符使用频率W={10,2,5,6,4},画出对字符进行哈夫曼编码时所对应的哈夫曼树,并给出各字符的编码.是不是只有一种可能 - ？
庾淑瑞芝：[答案] 频率是W={10,2,5,6,4},你可以根据这个算出每个符号的使用概率.Huffman编码的基本思想就是:对于使用频率比较高的符号用较短的码字去编码,对于使用频率比较低的符号用较长的码字去编码,这样使得编码效率很高,即所编的...

栾川县18390865802： 给定有18个字符组成的文本(电文):A A D A T A R A E F R T A A F T E R,画出哈夫曼树 - ？
庾淑瑞芝： 先计算各个字符出现的个数作为权值:A 7 D 1 T 3 R3 E 2 F 2 然后选择两个最小权值的点构造新树,然后新树的根的权值(左右子树权值之和)到原序列中,重复上述过程只剩下一颗树为止.18/ \A7 11/ \5 6/ \ / \F2 T3 R3 3/ \D1 E2 默认左子树为0 右子树为1,上述哈夫曼编码是 A:0 F:100 T:101 R:110 D:1110 E:1111

栾川县18390865802： 我急需知道当输入任意的字符串时,系统自动给出每个字符的哈夫曼编码和对应的哈夫曼树C++程序,谢谢!) - ？
庾淑瑞芝： # include<stdio.h>#include<stdlib.h>#define MAXLEN 100 typedef struct Huffmantree { char ch; /*键值*/ int weight,mark; /*weight为权值,mark为标志域*/ struct Huffmantree *parent,*lchild,*rchild,*next; }Hftree,*linktree;/*整理输入的字符串,合并...

栾川县18390865802： 已知a,b,c,d,e,f字符的使用频率分别为{45,13,12,16,9,5},构造哈夫曼树并给出字符的哈弗曼编码 - ？
庾淑瑞芝： a:110b:1111c:01d:10e:1110f:00自推哈弗曼树吧

栾川县18390865802： 急求关于生成哈夫曼树的程序代码~谢谢啦! - ？
庾淑瑞芝： #include<iostream> using namespace std; typedef struct { int weight; int parent; int lchild; int rchild; }HTreeNode,*HTree; void createHTree(HTree *t ,int * w, int n ){ void select(HTree t, int i, int *s1, int *s2); *t = new HTreeNode[2*n-1]; for(int i=0;i<n;i++...