#include<iostream>
#include <stdio.h>
#include <string>
#include "44.h"
#define MAX 1000
using namespace std;
typedef struct
{
char bits[50];
int start;
}huffmancode;
int main()
{
huffmannode ht[100]; /* 定义储存权值的空间 */
huffmancode cd[100];
char string[100]; /* 定义数组存储空间 */
char hcd[100];
int i,j,x,y,s1,s2,m1,m2,n,c,f,k;
cout<<"请输入长度 n= "; /* 输入字符的个数 */
cin>>n;
cout<<"==============================="<<endl;
for(i=0;i<n;i++)
{
getchar(); /* 获得输入的字符 */
cout<<"输入字符: ";
cin>>ht[i].parent; /* 输入字符函数 */
cout<<"输入权值: ";
cin>>ht[i].weight;
}
cout<<"============================="<<endl;
for(i=0;i<2*n-1;i++)
{
ht[i].parent=ht[i].lchild=ht[i].rchild=-1; /* 初始化父结点，左右子结点 */
}
for (i=n;i<2*n-1;i++)
{
s1=s2=0; /* 初始化变量 */
m1=m2=MAX;
for (j=0;j<i;j++)
{
if (ht[j].weight<m1 &&ht[j].parent==-1) /* 寻找无父结点的最小值 */
{
m2=m1;
s2=s1;
m1=ht[j].weight;
s1=j; /* 寻找当前最小值 */
}
else if(ht[j].weight<m2 &&ht[j].parent==-1) /* 寻找无父结点的次小值 */
{
m2=ht[j].weight;
s2=j;
} /* 寻找次小值 */
}
ht[s1].parent=i; /* s1的父结点为i */
ht[s2].parent=i;
ht[i].weight=m1+m2; /* 最小值的权值相加为i的权值 */
ht[i].lchild=s1; /* i的左子为s1 */
ht[i].rchild=s2; /* i的右子为s2 */
}
for(i=0;i<n;i++)
{
cd[i].start=n;
x=i;
y=ht[x].parent; /* 记录父结点 */
while (y!=-1)
{
if (ht[y].lchild==x)
cd[i].bits[cd[i].start]='0'; /* 给字符赋0值 */
else
cd[i].bits[cd[i].start]='1'; /* 给字符赋1值 */
cd[i].start--;
x=y;
y=ht[y].parent;
}
}
cout<<"字符"<<"->"<<"权值："<<endl;
for (i=0;i<n;i++)
{
cout<<ht[i].parent; /* 输出字符 */
for(j=cd[i].start;j<=n;j++)
{
cout<<cd[i].bits[j]; /* 输出字符的01代码 */
}
cout<<endl;
}
cout<<"============================="<<endl;
cout<<"请输入信息: "<<endl;
cin>>string; /* 输入字符串 */
for(i=0;string[i]!='\0';i++)
{
for(c=0;c<=n;c++)
if(string[i]==ht[c].parent) /* 寻找与输入字符相匹配的字母 */
{
for(j=cd[c].start;j<=n;j++)
cout<<cd[c].bits[j]; /* 输出字母代码 */
break;
}
}
cout<<"============================="<<endl;
cout<<"请输入密文：";
cin>>hcd; /* 输入0、1代码 */
f=2*n-2;
for(i=0;hcd[i]!='\0';i++)
{
if(hcd[i]=='0') /* 判断输入为0，寻找左子 */
f=ht[f].lchild;
else if(hcd[i]=='1')
f=ht[f].rchild; /* 判断输入为1，寻找右子 */
if(f<n)
{
cout<<ht[f].parent; /* 输出字符串 */
f=2*n-2;
}
}
cout<<endl;
return 0;
}
头文件
#include
using namespace std;
typedef struct huffmannode
{
char parent;
struct huffmannode* lchild;
struct huffmannode* rchild;
int weight;
int n;
int value;
}node, *huffmantree;
huffmantree Create(huffmantree T)
{
char v;
v=getchar();
if(v==0)
T=NULL;
else
{
T = (node*) malloc(sizeof(node));
if(!T)
exit(0);
T->parent = v;
T->lchild = Create(T->lchild);
T->rchild = Create(T->rchild);
}
return T;
}
void preOrder(huffmantree T)
{
if(T)
{
cout<parent;
preOrder(T->lchild);
preOrder(T->rchild);
}
}
