哈夫曼树的建立
哈夫曼树的建立
[ 标签：哈夫曼,建立 ]
数据结构课程设计题目 - -~
哈夫曼树的建立
任务：建立最优二叉树函数
要求：可以建立函数输入二叉树，并输出其哈夫曼树
2010、加油 回答:3 人气:10 解决时间:2010-02-04 18:25
满意答案
好评率：0%
给你个大概的代码，把显示跟调用那里改改
#include
#include
#include
#include
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild,ch;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表 int m,s1,s2;
HuffmanTree HT;
void Select(int n){ //选择两个权值最小的结点
int i,j;
for(i=1;i
if(!HT[i].parent){
s1 = i;break;
}
}
for(j=i+1;j
if(!HT[j].parent){
s2 = j;break;
}
}
for(i=1;i
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i)){ s1=i;
}
}
for(j=1;j
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j)){ s2=j;
}
}
}
void HuffmanCoding(HuffmanCode HC[], int *w, int n) {
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;
int start;
if (n
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用 for (i=1; i
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].ch=0;
}
for (i=n+1; i
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].ch=0;
}
for (j=1,i=n+1; i
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点， // 其序号分别为s1和s2
Select(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;
HT[i].ch=j;
}
//-----从叶子到根逆向求每个字符的哈夫曼编码
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i
start=n-1;
HT[i].ch=i;
for(unsigned int 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]);
}
free(cd);
}
void PTree(int n){//打印树的结构
int r=2*n-1;
printf("树的结构为（0表示无孩子）：\n");
for(;r>0;r--){
cout"
}
}
void trans(){//译码
int i=m;
char a;
printf("输入0/1进行译码，输入'!'进行编码");
cin>>a;
while(a=='0'||a=='1'){
if(a=='0')i=HT[i].lchild;
else if(a=='1') i=HT[i].rchild;
if(HT[i].lchild==0){
cout
i=m;
}
else if(a=='!') return;//当接收到的输入为"!"时返回主函数进行编码 cin>>a;
}
}
void main() {
HuffmanTree HT;
HuffmanCode *HC;
int *w,n,i,j;
char b,c;
puts("输入结点数：");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值\n",n);
for(i=0;i
scanf("%d",&w[i]);
}
HuffmanCoding(HC,w,n);
puts("\n各结点的哈夫曼编码为：");
for(i=1;i
c=(char)i+64;
cout
}
PTree(n);
printf("\n各结点的哈夫曼译码为：\n");
trans();
cout
cin>>b;
j=(int)(b-64);
while(j){
cout
cin>>b;
j=(int)(b-64);
}
cout
system("pause");
哈夫曼树的建立及应用
[ 标签：,, ]
1、 给定权值5，29，7，8，14，23，3，11，建立哈夫曼树，
输出哈夫曼编码。
2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二
进制编码，输出它的哈夫曼译码。
用C++解决!!网友们帮帮忙!!
卟 卟 回答:1 人气:71 解决时间:2008-05-13 18:01
网友完善的答案
好评率：0% 查看完善答案历史>>
#include
#include
const int n=8;
const int m=2*n-1;
struct tree
{
float weight;
int parent;
int lch,rch;
};
struct codetype
{
int bits[n+1];
int start;
char ch;
};
tree hftree[m+1];
struct codetype code[n+1];
void creathuffmantree()
{
int i,j,p1,p2;
float s1,s2;
for(i=1;i
{
hftree[i].parent=0;
hftree[i].lch=0;
hftree[i].rch=0;
hftree[i].weight=0;
}
cout
for(i=1;i
cin>>hftree[i].weight;
for(i=n+1;i
{
p1=p2=0;
s1=s2=32767;
for(j=1;j
if(hftree[j].parent==0)
if(hftree[j].weight
{
s2=s1;
s1=hftree[j].weight;
p2=p1;
p1=j;
}
else
if(hftree[j].weight
{
s2=hftree[j].weight;p2=j;
}
hftree[p1].parent=i;
hftree[p2].parent=i;
hftree[i].lch=p1;
hftree[i].rch=p2;
hftree[i].weight=hftree[p1].weight+hftree[p2].weight;
}
}
void huffcode()
{
codetype cd;
int c,p;
for(int i=1;i
{
cd.start=n+1;
cd.ch=96+i;
c=i;
p=hftree[i].parent;
while(p!=0)
{
cd.start--;
if(hftree[p].lch==c)cd.bits[cd.start]=0;
else cd.bits[cd.start]=1;
c=p;
p=hftree[p].parent;
}
code[i]=cd;
}
for(i=1;i
{
cout
for(int j=code[i].start;j
cout
cout
}
}
void trancode()
{
int i=m;char b;
cout
cin>>b;
while((b=='0')||(b=='1'))
{
if(b=='0')i=hftree[i].lch;
else i=hftree[i].rch;
if(hftree[i].lch==0)
{
cout
i=m;
}
cin>>b;
}
}
void main()
{
creathuffmantree();
huffcode();
trancode();
}
评价答案
好:0
一般:0
不好:0
原创:0
非原创:0
回答采纳率:25.0% 2010-05-13 10:53
好评率：0%
给你个我写的哈夫曼函数：
void HuffmanTree(HuffmanTree &HT, int * w, int n)
{
//w 存放n 个字符的权值（均>0），构造赫夫曼树HT
if (n
m=2* n-1;
HT=(HuffmanTree)malloc(m+1) * sizeof(HTNode); //分配存储空间 //用给定的n个权值，构造n棵只有一个根结点的二叉树
for (p=1, i=1, j=0; i
HT[p]={ w[j], 0, 0, 0}; //HT[0]未用
//按构造哈夫曼树的步骤2、3、4，建哈夫曼树
for (; 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]存放新子树的根结点， HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight; }
}
哈夫曼树编程问题
30
[ 标签：, ]
要求建立哈夫曼树，并实现编码功能和译码功能和打印功能 我写了一些但是有问题希望高手改一下程序如下#include "stdio.h"
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 10
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
char yuanma;
}HNodeType;
void HaffmanTree(HNodeType HuffNode[])
{
int i,j,m1,m2,x1,x2;
printf("输入叶结点个数：");
scanf("%d",&n);
for(i=0;i
{
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
printf("输入n个原码：");
for(i=0;i
scanf("%c",&HuffNode[i].yuanma);
printf("输入对应n个叶结点的权值：");
for(i=0;i
{
scanf("%d",&HuffNode[i].weight);
printf("%d",HuffNode[i].weight);
}
for(i=0;i
{
m1=MAXVALUE;
m2=MAXVALUE;
x1=x2=0;
for(j=0;j
{
if(HuffNode[j].weight
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].weight
m2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
}
typedef struct
{
int bit[MAXBIT];
int start;
}HCodeType;
void HaffmanBem(HCodeType HuffmanCode[])
{
HNodeType HuffNode[MAXNODE];
HCodeType HuffCode[MAXLEAF],cd;
int i,j,c,p;
HaffmanTree(HuffNode);
for(i=0;i
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HuffNode[c].parent;
}
for(j=cd.start+1;j
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
for(i=0;i
{
for(j=HuffCode[j].start+1;j
printf("%1d",HuffCode[i].bit[j]);
printf("\n");
}
int r=0,q=0,a[100],b[100];
p=0,c=0;
printf("输入需要翻译的编码：");
while(scanf("%d",a[r++])!=0);
while(p
{
for(i=0;i
{
p=c;
for(j=HuffCode[i].start+1;j
{
if(HuffCode[i].bit[j]==a[p])
p++;
else break;
}
if(j==n)
{
c=p;
b[q]=i;
q++;
break;
}
}
}
printf("译码是：");
for(int z=0;z
printf("%d",HuffNode[b[z]].yuanma);
}
void main()
{
HCodeType HuffCode[MAXLEAF];
HaffmanBem(HuffCode);
} 小鹿 回答:2 人气:17 解决时间:2009-12-07 00:04
满意答案
好评率：100%
#include "stdio.h"
#define MAXVALUE 10000 //定义最大权值
#define MAXLEAF 30 //定义哈夫曼树中叶结点个数
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 10
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
char yuanma;
}HNodeType;
int n;
void HaffmanTree(HNodeType HuffNode[])//哈夫曼树的构造算法
{
int i,j,m1,m2,x1,x2;
printf("输入叶结点个数(大于0小于30)：");
scanf("%d",&n); //输入叶结点的个数
for(i=0;i
{
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
printf("\n\n");
printf("输入%d个权值及对应的原码：",n);
for(i=0;i
{
scanf("%d",&HuffNode[i].weight);
scanf("%c",&HuffNode[i].yuanma);
}
for(i=0;i
{
m1=MAXVALUE;
m2=MAXVALUE;
x1=x2=0;
for(j=0;j
{
if(HuffNode[j].weight
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].weight
{
m2=HuffNode[j].weight;
x2=j;
}
} //将找出的两棵子树合并为一棵子树
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
}
typedef struct
{
int bit[MAXBIT];
int start;
}HCodeType;
void HaffmanBem(HCodeType HuffmanCode[])
{ //生成哈夫曼编码
HNodeType HuffNode[MAXNODE];
HCodeType HuffCode[MAXLEAF],cd;
int i,j,c,p;
HaffmanTree(HuffNode); //建立哈夫曼树
for(i=0;i
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1) // 有叶结点向上直到树根
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
if(HuffNode[p].rchild==c)
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HuffNode[c].parent;
}
for(j=cd.start+1;j
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}printf("\n\n\n");
printf("字符 对应的编码\n");
for(i=0;i
{ printf(" %c ",HuffNode[i].yuanma) ;
for(j=HuffCode[i].start+1;j
printf(" %d",HuffCode[i].bit[j]);
printf("\n");
}
printf("\n\n\n");
int r=0,q=0,a[100],b[100],flag=1,y=1;
p=0,c=0;
printf("输入需要翻译的编码(输入2结束)：");
for(r=0;r
{
scanf("%d",&a[r]);
if(a[r]==2)
break;
}
while(flag)
{
for(i=0;i
{
p=c;
for(j=HuffCode[i].start+1;j
{
if(HuffCode[i].bit[j]==a[p])
p++;
else break;
}
if(j==n)
{
c=p;
b[q]=i;
q++;
break;
}
}
if(c
flag=1;
else
flag=0;
if(i==n)
{
y=0;
printf("\n\n\n输入的编码有误!!!!");
flag=0;
}
}
printf("\n\n\n");
if(y==1)
{
printf("译码是：");
for(int z=0;z
printf("%c ",HuffNode[b[z]].yuanma);
printf("\n\n\n");
}
}
void main()
{
printf(" \1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\1\n \n 欢迎来到哈夫曼编译码系统\n \n");
HCodeType HuffCode[MAXLEAF];
HaffmanBem(HuffCode);
}
评价答案
好:5
一般:0
不好:0
原创:5
非原创:0
匿名 2009-12-06 23:59 小鹿的感言：
Thank you!!!! 我有更好的回答 收藏
转载到QQ空间
相关内容
∙
∙
∙
∙
∙
∙
∙ ∙ ∙
∙ •1个回答 •编程关于哈夫曼树的建立和编码器的实现？1个回答 •3个回答 •1个回答 •哈夫曼树编程1个回答 哈夫曼树算法
其他答案
看别人的程序还不如自己写一个，每个人都有这样的体会，尤其较长的程序代码。 我这有一个你可以借鉴一下：
#include"stdlib.h"
#include
#include
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
{
if(HT[i].m_weight
if(HT[i].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
{
(*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
m=2*n-1;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;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
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; }
for(i=n+1;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
{
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
for(i=0;i
{
char c; int wei;
cin>>c>>wei;
//保存到结构中
w[i].elem=c;
w[i].m_weight=wei;
}
cout
//编码
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(&HT,&HC,w,n);
//编码输出
cout
cout
for(i=1;i
cout
程序执行结果：
哈夫曼树问题
20
[ 标签：哈夫曼 ]
在字符集｛A,B,C,D,E,F｝中，各字符出现的次数为W=｛2，3，6，10，14，15｝问题一：构造哈夫曼树设计出各字符对应的哈夫曼码，并求出其带权路径长度。 问题二：按上面的字符编码将“[***********]1”序列，翻译成字符序列！！！
有没有高手详细点帮忙解决一下啊！！万分感谢啊！！ ☆疯兔☆ 回答:1 人气:15 解决时间:2009-03-05 15:26
满意答案
好评率：0%
1.带权路径长度WPL=2*4+3*4+6*3+10*2+14*2+15*2=116
A:0000
B:0001
C:001
D:01
E:10
F:11
2.EFDABFC
构造的树如下
答案补充
构造哈夫曼树的基本思想:
1.将N个权值分别是W1,W2...WN的结点按权值递增排列,将每个权值看作一棵二叉树,构成N棵二叉树的森林F={T1,T2,...,TN}
2.在森林F中选取两棵结点权值最小的二叉树,作为左右子树构造一棵新的二叉树,并使得新二叉树根结点的权值为基左右子树上根结点的权值之和
3.在森林F中,删除这两棵树,同时将新得到的二叉树代替这两棵树加入森林F中.
4.对新的森林重复步骤2和3,直到森林只剩下一棵树为止,这棵树就是所要的哈夫曼树.
答案补充
编码规则:用二叉树的叶子结点表示字符,对二叉树中每个分支的左右分支分别用0和1进行编码,从树的根结点到叶子结点,沿途上所有的0和1组成的编码序列作为此叶子结点所代表字符的二进制编码.
译码规则:从树的根结点出发,按二进制位串中的0和1确定是进行左分支还是右分支,到达叶子结点时,译出此叶子结点对应的字符.若电文还没结束,则回到根结点继续进行译码
.
你是 要代码 还是要 解题方法？
提问人的追问 2010-01-24 14:26
解题方法，代码都要，谢谢 - -
回答人的补充 2010-01-24 14:39
哈夫曼树是根据每个叶子节点的权值
每次都取权值最小的两个结点取出组成2叉树
然后将取出的两个结点的权值之和放回原结点权值之中作为一个新的叶子节点权值
然后依次类推 知道所有叶子节点都在一棵二叉树中为止
举例：
2、5、10、23、26、30这几个
1、取 最小的2，5
2、将2、5 的总权值 放回原叶子节点中
也就是说 新的 权值列表为 7、10、23、26、30
3、重复取最小的两个 也就是7、10
将7+10=17放回原列表中
重复至只剩下最后两个权值为止
96
40 56
17 【23】 【26】 【30】
7 【10】
【2】 【5】
带【】为叶子节点
回答人的补充 2010-01-24 15:32
---------------------------------------------------96
----------------------------40
----------------------------------------56
-----------------17 -----------------【23】----------- 【26】 -----------
【30】
--------7 ---------------【10】
【2】-- 【5】
带【】为叶子节点
□Fate_R 回答采纳率:7.7% 2010-01-24 14:24
//本程序根据26个英文字母出现的频度，得到了它们的一种哈夫曼编码方案 //by jirgal 2005.4.18 #include #include #define NUM 26 //字母数 #define TNUM 51 // #define LTH 15 //编码最大长度 class Node { public: char data; int weight; int parent; int lchild; int rchild; }; void main() { char
ch[NUM]={'a','b','c','d','e','f','g','h','i','j','k','l',
'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};//26个字母 int weit[NUM]={856,139,279,378,1304,289,199,528,627,13,42,
339,249,707,797,199,12,677,607,1045,249,92,149,17,199,8};//出现频率 Node nodes[TNUM]; //用对象数组存储哈夫曼树 int i,j,one,two,a,b; int hc[NUM][LTH]; //用于存储编码 int m,n; //初始化数组 for(i=0;i
nodes[i].lchild=-1; nodes[i].rchild=-1; } //建立哈夫曼树
for(i=NUM;i
for(j=0;j
if(nodes[j].weight>two&&nodes[j].weight
nodes[i].rchild=b; nodes[i].weight=nodes[a].weight+nodes[b].weight; } //初始化hc for(i=0;i
for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent)
{ if(nodes[n].lchild==m) { hc[i][j]=0; } else { hc[i][j]=1; } j--; } } //输出 nodes cout
cout
cout
cout
哈夫曼树及哈夫曼编码的C程序实现(数据结构题)
20
[ 标签：哈夫曼,编码,程序 ]
问题描述〕输入一个有n个叶结点的权值构造一棵哈夫曼树；
（例如：n＝8，权值为 5 29 7 8 14 23 3 11）
根据哈夫曼树构造哈夫曼编码，用指向字符串的指针数组来存放，从叶子到树根逆向求每个结点的哈夫曼编码
去年做的课程设计，有什么不合要求的自己改改
#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
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; for(j = 1;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
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用 for (i=1; i
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼树的构造过程如下所示：");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i
printf("\n%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
// 在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("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j
printf("\n%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
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",n);
for(i = 0;i
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各结点的哈夫曼编码:");
for(i = 1;i
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}
评价答案
好:0
一般:0
不好:1
原创:0
非原创:0
樹欲靜風不止 2008-12-17 15:16
满意答案
好评率：0%
#include
#include
#define MAXINF 10000
struct htnode
{
int ww;
int parent,llink,rlink;
};
struct httree
{
int m;
int root;
struct htnode *ht;
};
typedef struct httree *phttree;
phttree huffman(int m,int *w)
{
phttree pht;
int i,j,x1,x2,m1,m2;
pht=(phttree)malloc(sizeof(struct httree));
pht->ht=(struct htnode*)malloc(sizeof(struct htnode)*(2*m-1)); for(i=0;i
{
pht->ht[i].llink=-1;
pht->ht[i].rlink=-1;
pht->ht[i].parent=-1;
if(i
pht->ht[i].ww=w[i];
else
pht->ht[i].ww=-1;
}
for(i=0;i
{
m1=MAXINF;m2=MAXINF;
x1=-1;x2=-1;
for(j=0;j
if(pht->ht[j].wwht[j].parent==-1)
{
m2=m1;x2=x1;m1=pht->ht[j].ww;x1=j;
}
else if(pht->ht[j].wwht[j].parent==-1) {
m2=pht->ht[j].ww;x2=j;
}
pht->ht[x1].parent=m+i;pht->ht[x2].parent=m+i; pht->ht[m+i].ww=m1+m2;pht->ht[m+i].llink=x1; pht->ht[m+i].rlink=x2;
}
pht->root=2*m-2;
return pht;
}
int main()
{
int i,m,*a;
phttree kun;
printf("输入权值个数：");
scanf("%d",&m);
printf("输入权值：\n");
for(i=0;i
scanf("%d",&a[i]);
kun=huffman(m,a);
for(i=0;i
{
printf("%d%5d%5d",i,kun->ht[i].ww,kun->ht[i].parent); printf("%5d%5d\n",kun->ht[i].llink,kun->ht[i].rlink); }
system("pause");
return 0;
}
今年才开课，前不久写的，呵呵
评价答案
好:0
一般:0
不好:0
原创:0
非原创:0
寂寞的风 回答采纳率:25.0% 2008-12-17 16:41 我有更好的回答 收藏
转载到QQ空间
相关内容
∙
∙
∙
∙
∙
∙
∙ ∙
∙ •数据结构的问题,求一个构造哈夫曼树的算法4个回答 •1个回答 •1个回答 •1个回答 •2个回答 哈夫曼树算法
其他答案
#include "string.h"
#include "stdio.h"
#define MAXVALUE 1000 /*定义最大权值*/
#define MAXLEAF 30 /*定义哈夫曼树叶结点个数*/
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 30 /*定义哈夫曼编码的最大长度*/
typedef struct
{ int bit[MAXBIT];
int start;
} HCODETYPE;
typedef struct
{ int weight;
int parent;
int lchild;
int rchild;
} HNODETYPE;
char *getcode1(char *s1,char *s2,char *s3) /*首先去掉电文中的空格*/ { char temp[128]="",*p,*q;
p=s1;
while ((q=strstr(p,s2))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2); }
strcat(temp,p);
strcpy(s1,temp);
return s1;
}
/*再去掉重复出现的字符（即压缩电文），提取哈夫曼树叶结点*/ char * getcode (char *s1)
{ char s2[26],s5[26];
char temp[200]="",*p,*q,*r,*s3="";
int m,e,n=0;
m=strlen(s1);
while(m>0)
{ p=s1;
s2[0]=s1[0];
s2[1]='\0';
r=s2;
e=0;
while((q=strstr(p,r))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2);
e++; }
m-=e;
strcat(temp,p);
strcpy(s1,temp);
s5[n]=s2[0];
n++;
strcpy(temp,"");
}
s5[n]='\0';
strcpy(s1,s5);
printf(" 压缩后的电文（即叶结点）: %s\n",s1);
return s1;
}
HNODETYPE huffmantree(char *s2,char s3[])
{ HNODETYPE huffnode[MAXNODE];
HCODETYPE huffcode[MAXLEAF],cd;
int sum,i,j,n1,n2,x1,x2,p,k,c;
char s1[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m', 'n','o','p','q','r','s','t','u','v','w','x','y','z'};
char s5[MAXLEAF];
int ww[26]={0},n=0;
strcpy( s5,s2);
sum=strlen(s2);
for(i=0;i
for(j=0;j
if(s2[j]==s1[i]) ww[i]++;
n=strlen(s3);
for (i=0;i
{ huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1; }
for(i=0;i
for(j=0;j
if (s3[i]==s1[j]) huffnode[i].weight=ww[j];
for (i=0;i
{ n1=n2=MAXVALUE;
x1=x2=0;
for(j=0;j
{ if (huffnode[j].parent==-1 && huffnode[j].weight
{ n2=n1;
x2=x1;
n1=huffnode[j].weight;
x1=j; }
else
if (huffnode[j].parent==-1 && huffnode[j].weight
{ n2=huffnode[j].weight; x2=j;}
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight; huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for(i=0;i
{ cd.start=n-1;
c=i;
p=huffnode[c].parent;
while (p!=-1)
{ if (huffnode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
for (j=cd.start+1;j
huffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
printf(" 各叶结点对应哈夫曼编码 : ");/*输出每个叶结点的哈夫曼编码*/ for(i=0;i
{ for(j=huffcode[i].start+1;j
printf("%d",huffcode[i].bit[j]);
printf(" ");}
printf("\n 电文的全部哈夫曼编码 : ");/*输出电文的全部哈夫曼编码*/ for(k=0;k
for(i=0;i
if(s2[k]==s3[i])
{ for(j=huffcode[i].start+1;j
printf("%d",huffcode[i].bit[j]);
printf(" "); }
printf("\n");
}
main()
{
char s1[MAXLEAF],s2[MAXLEAF];
printf("\n 请输入电文 : ");
gets(s1);
strcpy(s2,getcode1(s1," ",""));
huffmantree(s1,getcode(s2));
谁能帮我写个完整的哈夫曼编码系统，用c语言
匿名 回答:1 人气:68 解决时间:2008-02-24 19:40
满意答案
好评率：0%
#include "string.h"
#include "stdio.h"
#define MAXVALUE 1000 /*定义最大权值*/
#define MAXLEAF 30 /*定义哈夫曼树叶结点个数*/
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 30 /*定义哈夫曼编码的最大长度*/
typedef struct
{ int bit[MAXBIT];
int start;
} HCODETYPE;
typedef struct
{ int weight;
int parent;
int lchild;
int rchild;
} HNODETYPE;
char *getcode1(char *s1,char *s2,char *s3) /*首先去掉电文中的空格*/ { char temp[128]="",*p,*q;
p=s1;
while ((q=strstr(p,s2))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2); }
strcat(temp,p);
strcpy(s1,temp);
return s1;
}
/*再去掉重复出现的字符（即压缩电文），提取哈夫曼树叶结点*/ char * getcode (char *s1)
{ char s2[26],s5[26];
char temp[200]="",*p,*q,*r,*s3="";
int m,e,n=0;
m=strlen(s1);
while(m>0)
{ p=s1;
s2[0]=s1[0];
s2[1]='\0';
r=s2;
e=0;
while((q=strstr(p,r))!=NULL)
{ *q='\0';
strcat(temp,p);
strcat(temp,s3);
p=q+strlen(s2);
e++; }
m-=e;
strcat(temp,p);
strcpy(s1,temp);
s5[n]=s2[0];
n++;
strcpy(temp,"");
}
s5[n]='\0';
strcpy(s1,s5);
printf(" 压缩后的电文（即叶结点）: %s\n",s1);
return s1;
}
HNODETYPE huffmantree(char *s2,char s3[])
{ HNODETYPE huffnode[MAXNODE];
HCODETYPE huffcode[MAXLEAF],cd;
int sum,i,j,n1,n2,x1,x2,p,k,c;
char
s1[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m',
'n','o','p','q','r','s','t','u','v','w','x','y','z'};
char s5[MAXLEAF];
int ww[26]={0},n=0;
strcpy( s5,s2);
sum=strlen(s2);
for(i=0;i
for(j=0;j
if(s2[j]==s1[i]) ww[i]++;
n=strlen(s3);
for (i=0;i
{ huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1; }
for(i=0;i
for(j=0;j
if (s3[i]==s1[j]) huffnode[i].weight=ww[j];
for (i=0;i
{ n1=n2=MAXVALUE;
x1=x2=0;
for(j=0;j
{ if (huffnode[j].parent==-1 && huffnode[j].weight
x2=x1;
n1=huffnode[j].weight;
x1=j; }
else
if (huffnode[j].parent==-1 && huffnode[j].weight
}
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight; huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for(i=0;i
{ cd.start=n-1;
c=i;
p=huffnode[c].parent;
while (p!=-1)
{ if (huffnode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
for (j=cd.start+1;j
huffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
printf(" 各叶结点对应哈夫曼编码 : ");/*输出每个叶结点的哈夫曼编码*/
for(i=0;i
{ for(j=huffcode[i].start+1;j
printf("%d",huffcode[i].bit[j]);
printf(" ");}
printf("\n 电文的全部哈夫曼编码 : ");/*输出电文的全部哈夫曼编码*/
for(k=0;k
for(i=0;i
if(s2[k]==s3[i])
{ for(j=huffcode[i].start+1;j
printf("%d",huffcode[i].bit[j]);
printf(" "); }
printf("\n");
}
main()
{
char s1[MAXLEAF],s2[MAXLEAF];
printf("\n 请输入电文 : ");
gets(s1);
strcpy(s2,getcode1(s1," ",""));
huffmantree(s1,getcode(s2)); }