利用哈弗曼树编码原理，对字符进行编码（C++,C语言都可）
题目：输入任意字符串，str]=("a”，“b”，“c”，"d”，"e”，"f”，”g”，“h”；每种字符出现频率fnum，=0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.13，根据出现频率，利用哈夫曼编码原理，对每个字符进行(0.1)编码，并输出每种字符编码。
运行结果及代码如下：
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define MAXLEN 30
#define MAXLEAF 130
#define MAXWEIGHT 1
//结点
struct HuffmanNode
{
char node; //结点字符
double weight; //结点权值
int parent; //父结点
int lchild; //左子节点
int rchild; //右子节点
int no; //节点编号
};
//每个结点的编码
struct HuffmanCode
{
int bit[MAXLEN]; //存储哈夫曼编码
int length; //每个结点编码的长度
};
bool cmp1(HuffmanNode a, HuffmanNode b)
{
return a.weight < b.weight;
}
bool cmp2(HuffmanNode a, HuffmanNode b)
{
return a.no < b.no;
}
HuffmanNode HNode[2 * MAXLEAF - 1];
HuffmanCode HCode[MAXLEAF];
//构造哈夫曼树
void CreateHafman(char buf[], double w[], int n)
{
//初始化结点
for (int i = 0; i < 2 * n - 1; i++)
{
HNode[i].weight = MAXWEIGHT;
HNode[i].parent = -1;
HNode[i].lchild = -1;
HNode[i].rchild = -1;
HNode[i].no = 2 * n;
}
for (int i = 0; i < n; i++)
{
HNode[i].node = buf[i];
HNode[i].weight = w[i];
HNode[i].no = i;
}
for (int i = 0; i < n - 1; i++)
{
int min1 = 0, min2 = 1;
sort(HNode, HNode + n + i, cmp1);
for (int j = 0; j < n + i; j++)
{
if (HNode[min1].parent != -1)
{
min1++;
min2 = min1 + 1;
continue;
}
if (HNode[min2].parent != -1)
min2++;
}
HNode[n + i].lchild = HNode[min1].no;
HNode[n + i].rchild = HNode[min2].no;
HNode[n + i].weight = HNode[min1].weight + HNode[min2].weight;
HNode[n + i].no = n + i;
HNode[min1].parent = HNode[n + i].no;
HNode[min2].parent = HNode[n + i].no;
}
//cout << "哈夫曼树构建成功！" << endl;
}
//获取每个字符的哈夫曼编码
void Getcode(int n)
{
int offset = 2 * n - 1, p, j;
HuffmanCode hc;
sort(HNode, HNode + offset, cmp2);
for (int i = 0; i < n; i++)
{
hc.length = 0;
j = i;
p = HNode[j].parent;
while (p != -1)
{
if (HNode[p].lchild == HNode[j].no)
hc.bit[hc.length] = 0;
else
hc.bit[hc.length] = 1;
hc.length++;
j = HNode[p].no;
p = HNode[j].parent;
}
for (int k = 0; k < hc.length; k++)
HCode[i].bit[k] = hc.bit[hc.length - k - 1];
HCode[i].length = hc.length;
}
}
//显示哈夫曼编码
void showHafman(int n)
{
//输出哈夫曼编码
for (int i = 0; i < n; i++)
{
if (HNode[i].node == '\n')
cout << "\\n" << ": Huffman code is: ";
else if (HNode[i].node == '\r')
cout << "\\r" << ": Huffman code is: ";
else if (HNode[i].node == '\t')
cout << "\\t" << ": Huffman code is: ";
else
cout << HNode[i].node << ": Huffman code is: ";
for (int j = 0; j < HCode[i].length; j++)
cout << HCode[i].bit[j];
cout << endl;
}
}
int main()
{
int n = 8;
char buf[MAXLEAF]={'a','b','c','d','e','f','g','h'};
double w[MAXLEAF]={0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.13};
CreateHafman(buf, w, n); //创建哈夫曼树
Getcode(n);//获取每个字符的编码
showHafman(n);
return 0;
}
#include<bits/stdc++.h>
#include<string.h>
#define OK 1
#define ERROR 0
typedef int Status;
using namespace std;
//#include"header.h"
typedef char **CTree;
typedef struct Huffman {
float2
weight;
int lchild,rchild,parent;
}Huffman,*HTree;
//构造哈夫曼树
//重载复制函数(将s2的从第n个字符开始复制到s1中去)
void strcpy(char *s1,char *s2,int n){
int len2=strlen(s2);
for(int i=0;i<=len2;i++){
s1[i]=s2[i+n];
}
}
//在HT中选择最小的结点
void select(HTree &HT,int n,int &s1,int &s2){
int m1=32767,m2=32767;
s1=0;s2=0;
for(int k=1;k<=n;k++){
if((HT[k].parent==0)&&(HT[k].weight<m1)){
m2=m1;
s2=s1;
m1=HT[k].weight;
s1=k;
}else if((HT[k].parent==0)&&(HT[k].weight<m2)){
m2=HT[k].weight;
s2=k;
}
}
}
//构造哈夫曼编码
void createHuffmanCode(HTree HT,CTree &CT,int n){
CT=new char*[n+1];//应是char*，不是*char,因为声明指针类型的时候就是char*
char *temp=new char[n];//临时数组
int s,tp,tc;
temp[n-1]='\0';
for(int i=1;i<=n;i++){
tp=HT[i].parent;
tc=i;
s=n-1;
while(tp){
if(HT[tp].lchild==tc)
temp[--s]='0';
else
temp[--s]='1';
tc=tp;
tp=HT[tp].parent;
}
CT[i]=new char[n-s];
strcpy(CT[i],temp,s);
}
delete temp;
}
Status createHuffmanTree(HTree &HT,int n,char *&str){
int num,i;
int s1,s2;
if(n<=1)
return ERROR;
num=2*n-1;
HT=new Huffman[num+1];//0号单元未用
str=new char[num+1];//同样0号单元未用
for(i=1;i<=num;i++){
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
cout<<"输入结点（字符）和结点的权值（频率）：\n";
for(i=1;i<=n;i++){
getchar();
scanf("%c%f",&str[i],&HT[i].weight) ;
}
cout<<"------------HT的初态-------------\n";
cout<<"结点i\tweight\tparent\tlchild\trchild\n";
for(i=1;i<=num;i++){
cout<<i<<"\t";
if(i<=n)
cout<<HT[i].weight<<"\t";
else
cout<<0<<"\t";
cout<<0<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<endl;
}
//----开始创建
for(i=n+1;i<=num;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].weight=HT[s1].weight+HT[s2].weight;
}
cout<<"------------HT的终态-------------\n";
cout<<"结点i\tweight\tparent\tlchild\trchild\n";
for(i=1;i<=num;i++)
cout<<i<<"\t"<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<endl;
return OK;
}
int main(){
HTree HT;
CTree CT;
int num;
char *str=NULL;
cout<<"输入结点的个数：";
cin>>num;
createHuffmanTree(HT,num,str);
createHuffmanCode(HT,CT,num);
cout<<"每个结点的哈夫曼编码：\n";
for(int i=1;i<=num;i++)
cout<<str[i]<<"："<<CT[i]<<endl;
system("pause");
return 0;
}
仅供参考：
#include <iostream>
#include <string>
using namespace std;
struct huffTree {
int parent;
int lchild;
int rchild;
int weight;
string flag;
};
struct Lowest_node {
char ch;
int ch_num;
};
void coding(int length,huffTree *tree,int n,int &a,int &b) {
int i;
int r,s;
r=s=length;
for (i=0;i<n;i++) {
if (tree[i].weight<r
&& tree[i].parent==-1) {
r=tree[i].weight;
a=i;
}
}
for (i=0;i<n;i++) {
if (tree[i].weight<s
&& i!=a
&& tree[i].parent==-1) {
s=tree[i].weight;
b=i;
}
}
}
void frequency(string str) {
int i,j;
int length=str.length();
Lowest_node *node=new Lowest_node[length];
for (i=0;i<length;i++) node[i].ch_num=0;
int char_type_num=0;
for (i=0;i<length;i++) {
for (j=0;j<char_type_num;j++)
if (str[i]==node[j].ch
|| ('a'<=node[j].ch && node[j].ch<='z'
&& str[i]+32==node[j].ch))
break;//
if (j<char_type_num) node[j].ch_num++;
else {
if ('A'<=str[i] && str[i] <= 'Z') node[j].ch=str[i]+32;
else node[j].ch=str[i];
node[j].ch_num++;
char_type_num++;
}
}
for (i=0;i<char_type_num;i++) {
for (j=i;j<char_type_num;j++) {
if (node[j].ch_num<node[j+1].ch_num) {
int temp;
char ch_temp;
temp=node[j].ch_num;
ch_temp=node[j].ch;
node[j].ch_num=node[j+1].ch_num;
node[j].ch=node[j+1].ch;
node[j+1].ch_num=temp;
node[j+1].ch=ch_temp;
}
}
}
for (i=0;i<char_type_num;i++)
cout<<"字符"<<node[i].ch<<"出现了"<<node[i].ch_num<<"次"<<endl;
huffTree *huff=new huffTree[2*char_type_num-1];
huffTree temp;
string *code=new string[2*char_type_num-1];
for (i=0;i<2*char_type_num-1;i++) {
huff[i].lchild=-1;
huff[i].parent=-1;
huff[i].rchild=-1;
huff[i].flag=-1;
}
for (j=0;j<char_type_num;j++) huff[j].weight=node[j].ch_num;
int min1,min2;
for (int k=char_type_num;k<2*char_type_num-1;k++) {
coding(length,huff,k,min1,min2);
huff[min1].parent=k;
huff[min2].parent=k;
huff[min1].flag="0";
huff[min2].flag="1";
huff[k].lchild=min1;
huff[k].rchild=min2;
huff[k].weight=huff[min1].weight+huff[min2].weight;
}
for (i=0;i<char_type_num;i++) {
temp=huff[i];
while (1) {
code[i]=temp.flag+code[i];
temp=huff[temp.parent];
if (temp.parent==-1) break;//
}
}
cout<<"字符串的每个字符huffman编码为："<<endl;
for (i=0;i<char_type_num;i++) cout<<node[i].ch<<" "<<code[i]<<endl;
cout<<"整个字符串的huffman编码为："<<endl;
for (i=0;i<length;i++) { //S?
for (j=0;j<char_type_num;j++) {
if (str[i]==node[j].ch)
cout<<code[j];
}
}
delete[] node;
node=NULL;
delete[] huff;
huff=NULL;
delete[] code;
code=NULL;
}
int main() {
int length=0;
string str;
cout<<"请输入一个字符串：";
cin>>str;
frequency(str);
return 0;
}
//请输入一个字符串：2333abcde
//字符3出现了3次
//字符2出现了1次
//字符a出现了1次
//字符b出现了1次
//字符c出现了1次
//字符d出现了1次
//字符e出现了1次
//字符串的每个字符huffman编码为：
//3 11
//2 000
//a 001
//b 010
//c 011
//d 100
//e 101
//整个字符串的huffman编码为：
//000111111001010011100101