|
|
发表于 2020-11-1 19:05:40
|
显示全部楼层
没有看你的错误，提供个完整的仅供参考
- #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
置顶卡
千斤顶
显身卡
楼主