题目:输入任意字符串,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)编码,并输出每种字符编码。画出解题的程序流程图(传统流程图或N-S流程图均可)程序如下
#include
#include
#include
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;
}
流程图总览:
visio画图试试?