没有看你的错误，提供个完整的仅供参考#include<iostream>
#include<string>
#include<limits.h>
using namespace std;
struct HNode //树结点（静态三叉链表）
{
char name; //结点内容
int weight; //结点权重
int parent; //双亲数组下标
int LChild; //左孩子数组下标
int RChild; //右孩子数组下标
};
struct HCode //编码表中的每个元素
{
char data; //字符内容
string code; //对应编码
};
static int a[128] = { 0 }; //权值数组
static char name[128] = ""; //字符内容
static int n = 0; //字符种类数
class Huffman
{
private:
HNode* HTree = NULL; //哈夫曼树
HCode* HCodeTable = NULL; //存储编码表
int N=0; //叶子数量
void code(int i, string newcode); //递归函数，对第i个结点编码
public:
void CreateHTree(int a[], int n, char *name); //创建哈夫曼树
void CreateCodeTable(); //创建编码表
void Encode(char* d,string &s); //编码
void Decode(char* s,char *d); //解码
void PrintHCodeTable(); //打印编码表
void PrintHTree(); //打印哈夫曼树
void printHfmTree(int root, int height, ostream& out);//直观打印
void Analyze(string s,char *d); //分析压缩效果
~Huffman(); //析构
};
//a[]为每种字符的权值，n为字符种类，name[]为各个字符的内容
void Huffman::CreateHTree(int a[], int n, char *name)
{
N = n; //叶子数
HCodeTable = new HCode[N];
HTree = new HNode[2 * N - 1]; //初始化树的每个结点
for (int i = 0; i < N; i++)
{
HTree[i].name = name[i];
HTree[i].weight = a[i];
HTree[i].LChild = HTree[i].RChild = HTree[i].parent = -1;
HCodeTable[i].data = name[i];
}
int x=0, y=0; //开始建哈夫曼树
for (int i = n; i < 2 * N - 1; i++) //N个叶子，2*N-1个结点
{
int min1 = INT_MAX;//最小值，INT_MAX在<limits.h>中定义的
int min2 = INT_MAX;//次小值
for(int j = 0; j < i;j++)
{
if (HTree[j].parent == -1)
{
if (HTree[j].weight < min1)
{
min2 = min1;
min1 = HTree[j].weight;
y = x;
x = j;
}
else if ((HTree[j].weight >= min1) && (HTree[j].weight < min2))
{
min2 = HTree[j].weight;
y = j;
}
else { ; }
}
}
HTree[x].parent = HTree[y].parent = i; //父结点下标（实际意义：三结点相连）
HTree[i].weight = HTree[x].weight + HTree[y].weight;
HTree[i].LChild = x;
HTree[i].RChild = y;
HTree[i].parent = -1; //待定，默认-1
}
}
//递归函数，对第i个结点编码
void Huffman::code(int i, string newcode)
{
if (HTree[i].LChild == -1) //左子树空
{
HCodeTable[i].code = newcode;
return;
}
code(HTree[i].LChild, newcode + "0");
code(HTree[i].RChild, newcode + "1");
}
//生成编码表
void Huffman::CreateCodeTable()
{
code(2 * N - 2, "");
}
//打印编码表
void Huffman::PrintHCodeTable()
{
cout << "\t\t\t\t所建字符编码表如下：" << endl;
cout << "\t\t\t\t--------------------------" << endl;
cout << "\t\t\t\t字符内容\t" << "对应编码\t" << endl;
for (int i = 0; i < N; i++)
{
cout <<"\t\t\t\t"<< HCodeTable[i].data << "\t\t" << HCodeTable[i].code << endl;
}
cout << "\t\t\t\t--------------------------" << endl;
}
//析构
Huffman::~Huffman()
{
delete[]HTree;
delete[]HCodeTable;
}
static string coded_string = ""; //用于存储对象字符串的编码串
static char text_out[] = ""; //存储解码结果
//编码 d为字符串，s为编码后的编码串
void Huffman::Encode(char* d,string &s)
{
int k = 0;
while (d[k] != '\0')
{
for (int i = 0; i < N; i++)
{
if (HCodeTable[i].data == d[k])
{
s = s + HCodeTable[i].code;
break;
}
}
k++;
}
cout << "\t\t\t\t编码结果如下： "<< endl;
cout <<"\t\t\t\t"<< s << endl;
}
// 解码 s为编码串，d为解码后的字符串
void Huffman::Decode(char* s,char* d)
{
while (*s != '\0')
{
int parent = 2 * N - 2; //根节点在HTree中的下标（共2*N-1个结点）
while (HTree[parent].LChild != -1) //有左孩子，不是叶子结点
{
if (*s == '0')
parent = HTree[parent].LChild;//左拐
else
parent = HTree[parent].RChild;//右拐
s++;//后移一位
}//目的：找下标parent
*d = HCodeTable[parent].data;
d++;
}
}
//打印Huffman树
void Huffman::PrintHTree()
{
cout << "\t\t\t\t所建哈夫曼静态链表示如下：" << endl;
cout << "\t\t\t\t==============================================" << endl;
cout << "\t\t\t\t位置\t"<<"内容\t"<<"权值\t" << "双亲\t" << "左孩子\t" << "右孩子\t" << endl;
for (int i = 0; i < N * 2 - 1; i++)
{
cout <<"\t\t\t\t"<<i<<"\t"<<HTree[i].name<<"\t"<< HTree[i].weight << "\t" << HTree[i].parent << "\t" << HTree[i].LChild << "\t" << HTree[i].RChild<< endl;
}
cout << "\t\t\t\t==============================================" << endl;
//可视化直观打印
cout << "\t\t\t\t该哈夫曼树打印如下（横向打印）：" << endl << endl;
printHfmTree(2 * N - 2, 0, cout);
}
//递归实现直观打印
void Huffman::printHfmTree(int root, int height, ostream& out)
{
char branches[] = { " /\\<" }; //树枝图形
if (root != -1)
{
//先打印当前结点的右子树，并且深度+1
printHfmTree(HTree[root].RChild, height + 1, out); //递归
for (int i = 0; i < height; i++) out << "\t";//根据深度，右移
out << HTree[root].weight;//输出权值
//叶结点，则再打印出相应的字符
if (HTree[root].LChild == -1 && HTree[root].RChild == -1)
out << "(" << HTree[root].name << ")";
//打印树枝
out << branches[((HTree[root].LChild != -1) << 1) | (HTree[root].RChild != -1)];
//换行，打印当前结点的左子树
out << endl;
printHfmTree(HTree[root].LChild, height + 1, out); //递归
}
}
//s为编码串，d为原字符串
void Huffman::Analyze(string s, char* d)
{
char* s1 = (char*)s.data();
double m = 0, n = 0;
while (*s1 != '\0') { m++; s1++; }
while (*d != '\0') { n++; d++; }
cout << "\t\t\t\t压缩比为:" << 100 * (m / 8.0) / n << "%" <<"\n"<< endl;
}
//测试函数
int main()
{
Huffman huffman1; //建树(默认构造)
cout << "请输入需要操作的字符串：" << endl;
char text[128];
cin.getline(text, 128, '\n');
text[strlen(text) + 1] = '\0';
int str_length = sizeof(text) / sizeof(text[0]);
char Character_range[] = "abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890 !"#$%&\'()*+,-./:;<=>?@[\]^_`{|}~";
//给定范围，支持所有可显示字符
for (int i = 0; i < str_length; i++) //遍历text
{
bool p = 0; //标记
for (int j = 0; j < n; j++)
{
if (text[i] == name[j])
{
a[j]++; p = 1;
break;
}
}
for (int j = 0; j < strlen(Character_range)+1 && p == 0; j++)
{
if (text[i] == Character_range[j])
{
name[n] = text[i];
a[n]++; n++;
break;
}
}
}
int length = 0; //记录长度
for (int i = 0; i < 128; i++)
{
length += a[i];
}
char* coded_str = (char*)coded_string.data(); //类型转换，为参数准备
cout << "\t\t\t\t\t 给定字符串统计结束，系统就绪！\n" << endl;
cout << "\t\t\t\t Welcome to the Huffman coding system! \n";
cout << "\t\t\t\t***************************************************\n";
cout << "\t\t\t\t * │1.打印Huffman树 2.打印编码表 │ *\n";
cout << "\t\t\t\t * │ │ *\n";
cout << "\t\t\t\t * │3.编码并打印 4.解码并打印 │ *\n";
cout << "\t\t\t\t * │ │ *\n";
cout << "\t\t\t\t * │5.计算压缩率 6.退出程序 │ *\n";
cout << "\t\t\t\t***************************************************\n";
cout << endl;
huffman1.CreateHTree(a, n, name);//建树
huffman1.CreateCodeTable(); //建表
int select;
do
{
cout << "\t\t\t\t请选择操作方式 (1~6):" << endl;
cin >> select;
if (select > 6)
cout << "错误操作，请重新输入！" << endl;
else
switch (select) {
case 1:
huffman1.PrintHTree();
break;
case 2:
huffman1.PrintHCodeTable();
break;
case 3:
huffman1.Encode(text,coded_string);
break;
case 4:
coded_str = (char*)coded_string.data(); //类型转换
huffman1.Decode(coded_str, text_out);
text_out[length - 2] = '\0';
cout << "\t\t\t\t解码后的字符串为：" << "\n"<<text_out << "\n"<<endl;
break;
case 5:
huffman1.Analyze(coded_string, text);
break;
case 6:
cout << "\t\t\t\t\tThank you for using!" << endl;
}
} while (select != 6);
}
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2020-11-1 18:32:27
置顶卡
千斤顶
显身卡
发表于 2020-11-1 19:05:40
楼主