#include
#include
#include
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
using namespace std;
typedef struct{
int bit[100];
int start;
}Code;
typedef struct node{
char data;
int weight;
int parent;
int lchild;
int rchild;
bool tag;
}Node;
int HuffmanTree(Node node[MAXNODE], int a[128])
{
int i, j, m1, m2, x1, x2;
int n = 0;
for (i = 0; i < 128; i++)
{
if (a[i])
{
node[n].weight = a[i];
node[n].parent = -1;
node[n].lchild = -1;
node[n].rchild = -1;
node[n].data = (char)i;
n++;
}
}
for (i = n ; i < 2*n; i++)
{
node[n].weight = 0;
node[n].parent = -1;
node[n].lchild = -1;
node[n].rchild = -1;
}
/*循环构建霍夫曼树*/
for (i = 0; i <n-1; i++)
{
m1 = m2 = MAXVALUE;
/* m1、m2中存放两个无父结点且结点权值最小的两个结点 /
x1 = x2 = 0;
/ 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
for (j = 0; j < n + i; j++)
{
if (node[j].parent == -1 && node[j].weight<m1)
{
m2 = m1;
x2 = x1;
m1 = node[j].weight;
x1 = j;
}
else if (node[j].weight < m2 && node[j].parent == -1)
{
m2 = node[j].weight;
x2 = j;
}
}
/* 设置找到的两个子结点 x1、x2 的父结点信息 */
node[x1].parent = n + i;
node[x2].parent = n + i;
node[n + i].weight = node[x1].weight + node[x2].weight;
node[n + i].lchild = x1;
node[n + i].rchild = x2;
}
return n;
}
int main()
{
Node node[MAXNODE];
Code code[MAXLEAF], cd;
char s[500];
int i, j, c, p,n;
int a[128] = { 0 };
cout << "Please input your string:"< cin >> s;
for (i = 0; s[i]; i++)
a[s[i]]++;
for (j = 0; j < 128; j++)
{
if (a[j])
{
cout << (char)j << ":" << a[j] << endl;
}
}
n=HuffmanTree(node, a);
cout << n;
for (i = 0; i < n; i++)
{
cd.start = n-1;
c = i;
p = node[c].parent;
while (p != -1)
{
if (node[p].lchild == c)
cd.bit[cd.start] = 0;
else
{
cd.bit[cd.start] = 1;
}
cd.start--;
c = p;
p = node[c].parent;
}//end while
for (j = cd.start + 1; j < n; j++)
{
code[i].bit[j] = cd.bit[j];
}
code[i].start = cd.start;
}//end for
/* 输出已保存好的所有存在编码的哈夫曼编码 */
cout << "编码:" << endl;
for (i = 0; i < n; i++)
{
cout << node[i].data<< " :";
for (j = code[i].start + 1; j < n; j++)
{
cout << code[i].bit[j];
}
cout << endl;
}
system("pause");
}
你的方法定义是不是不对?调用方法之后node里面的内容有带回到主函数吗?可以断点看下返回之后node的内容。