#include<iostream.h>奇伟鞋油
#include<malloc.h>
#include<string.h>
#include<iomanip.h>
#define Max 32767 //int 型最大可取值
typedef struct Node{
int weight;
int parent,Lchild,Rchild;
}HTNode;
typedef char *HuffmanCode;
void select(int w[],int n,int &xb1,int &xb2){ //select(w,i-1,xb1,xb2);
int min1,min2; //min1最小，min2次小
min1=w[1];xb1=1;
min2=w[2];xb2=2;
if(min1>min2){
min1=w[2];xb1=2;
min2=w[1];xb2=1; //安排第一和第二个数的显示顺序
}
for(int i=3;i<=n;i++){//n=7 遍历>2的数组元素
if(w[i]<min1){
min2=min1;xb2=xb1; //第一次遍历，下标为6和7的3，2显示，其中2为最小，3为次小，故先显示xb1 2--7 //然后是xb2 3--6
min1=w[i]; xb1=i;
}
劳动部else if(w[i]<min2){
min2=w[i];
xb2=i; //安排次小的在前
}
}
cout<<"权值 下标"<<endl;
cout<<setw(4)<<w[xb1]<<setw(4)<<xb1<<endl; //输出被选节点的下标和权值 cout<<setw(4)<<w[xb2]<<setw(4)<<xb2<<endl;
cout<<"--------------"<<endl;
}
void createHTree(HTNode ht[],HuffmanCode hc[],int w[],int n){
int start;
int m=2*n-1;
for(int i=1;i<=n;i++){
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].Rchild=0;//初始化原有数据成员，都赋值为0
ht[i].Lchild=0;
}
初步询价
for(i=n+1;i<=m;i++){
ht[i].weight=0;
ht[i].parent=0;呜莎测试
ht[i].Rchild=0;
ht[i].Lchild=0;//初始化权值相加的成员
}
int xb1,xb2;
cout<<"依次被选中的节点值"<<endl;
for(i=n+1;i<=m;i++){
select(w,i-1,xb1,xb2);//（数据成员，遍历参数，下标1，下标2）
ht[xb1].parent=i; //第一次遍历双亲为8 ht[xb2].parent=i;
ht[i].Lchild=xb1; //一道初始化此双亲的孩子节点
ht[i].Rchild=xb2; //要保证下标小的作左孩子，还需加一句判断语句
w[i]=w[xb1]+w[xb2]; //双亲=左右孩子节点权值相加
ht[i].weight=w[i];
if(xb1>xb2){//保证 下标小 的做左孩子
ht[i].Lchild=xb2;
ht[i].Rchild=xb1;
}
w[xb1]=Max;
w[xb2]=Max; //修改选过的节点的权值，避免下次再被选中
}
/
/输出所有节点的下标、权值、双亲、左孩子、右孩子的下标
cout<<endl<<endl<<endl<<"生成的Huffman树，顺序存储结构（双亲表示法）："<<endl<<endl<<"下标、权值、双亲、左孩子、右孩子"<<endl;
for(i=1;i<=13;i++)
cout<<setw(2)<<i<<": "<<setw(4)<<ht[i].weight<<" "<<setw(4)<<ht[i].parent<<" "<<setw(4)<<ht[i].Lchild<<" "<<setw(4)<<ht[i].Rchild<<endl;
char *cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0'; //这里限制哈夫曼编码写入到cd[5]就结束了
for(i=1;i<=n;i++){
start=n-1;
for(int c=i,p=ht[i].parent;p!=0;c=p,p=ht[p].parent)
if(ht[p].Lchild==c) //左孩子下标是否为数据成员下标1，2，3，4，5，6，7
cd[--start]='0'; //i=1时，编码cd[6]='0'，然
后分别为i=2时 cd[5]='0'.........
else cd[--start]='1';
hc[i]=(char *)malloc(sizeof(char));//hc[i]只是一个指针，指针指向的空间还没有分配，所以此时用strcpy向str1所指向的内存
//中拷贝内容将出错。利用malloc动态分配指向的内存（在堆中）
strcpy(hc[i],&cd[start]);
}
free(cd);
沈阳大学学报
}
void main(){
int w[14]={0,40,30,16,5,4,3,2};
int n=7;
int m=2*n-1;
微型齿轮HTNode ht[14];//哈夫曼树成员数组 从1---13； 0 下标不用。用于双亲表示法存储Huffman树
HuffmanCode hc[8];//7个叶子节点也就是w[14]里面的，从1-7； 0下标不用 其中HuffmanCode被自定义为char型指针数据类型
createHTree(ht,hc,w,n);
cout<<endl<<endl<<"各叶子节点的编码如下："<<endl;
for(int i=1;i<=n;i++){
cout<<i<<" :"<<hc[i]<<endl;
}
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议