一、题目
在一个加密应用中，要处理的信息来自下面的字符集，各个字符的相关使用频度如下：
| 字符 | 空格 | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 频度 | 180 | 64 | 13 | 23 | 32 | 103 | 22 | 15 | 47 | 57 | 1 | 5 | 31 | 20 | 55 | 63 | 15 | 1 | 48 | 56 | 80 | 25 | 7 | 18 | 2 | 16 | 1 |
现请编写程序你实现如下功能：
(1) 运行时，由用户输入来初始化字符集大小和相应用字符。
(2) 输入一个要加密的字符串，将其加密。
(3) 输出解密字符串。
二、功能
参见题目。
三、要求1. 独立完成，设计算法并编写代码，调试通过。
2. 写设计说明书。
内容：题目、功能、要求、分析、代码，收获和体会及不足等。
3. 以个人独立完成。每一个选择一个题目。选题方式是：自己学号整除5所得的余数是几就做几号题。如学号为12做2号题，学号为5的做0号题。
4. 时间：从第13周开始收集资料，进行准备。具体设计时间在16-17周（等实验室安排）。在设计周周五检查（在机房子单独接受老师检查并提问），次周周五前提交设计说明书（实习报告）。
5. 实习单独计算成绩，学分1分，成绩好坏和考试没关系。
四、分析
根据题目需要实现的功能，对其进行分析可以得出本字符串加密应用中应该包含如下的模块：
字符集模块：功能为创建一个字符集合，其中包含需要被编码和加密的各个字符、字符的频度和字符的编码。由于字符集一经初始化，其数据元素就不会进行更改且题目已告知字符集的大小。因此选用顺序表作为其逻辑结构，数组作为其存储结构。
哈夫曼编码模块：根据字符集中字符的频度对每个字符进行编码，编码值回代字符集模块中的编码表。利用哈夫曼编码实现，因此选用二叉树作为其逻辑结构，静态链表作为其存储结构。
加密模块：利用字符集中的编码表对输入的需要加密的字符串进行哈夫曼编码，提高空间利用率。然后，对已编码处理后的字符串进行加密。加密的方式为用10个质数与密码做取余运算，编码后的字符串中从第0位开始，每个余数个位置与原值取反。直到10个余数全部利用完毕。
解密模块：首先根据密码，作出与加密相反的步骤解出相应的明文。然后再反哈夫曼编码解出原字符串。
五、代码
1.头文件部分
CharSet.h
#ifndef CharSet_H
#define CharSet_H
#include <string>
using namespace std;
const int MaxSize = 30; //字符集最多有30个元素，26个大写字母加空格，余量可扩充其他符号struct Character //用结构体存储字符的信息
{char symbol; //字符本身int frequency; //字符的频度string code; //字符的编码
};class CharSet
{
public:CharSet(); //让用户初始化字符集void PrintSet();int GetLen();Character* GetCh();
private:Character ch[MaxSize];int length;
};
#endifCoding.h
#ifndef Coding_H
#define Coding_H
#include "CharSet.h"
struct element
{int weight;int lchild, rchild, parent;
};
void BuildTree(element[], Character*, int); //构造哈夫曼树函数原型
void Select(element[], int&, int&, int); //哈夫曼树选择函数原型
void Coding(element[], Character*, int); //哈夫曼树编码函数原型
#endifDecrypt.h
#ifndef Decrypt_H
#define Decrypy_H
#include <string>
#include "CharSet.h"
void Decrypt(Character*, int); //解密解码模块原型
void Decryptor(string&, unsigned int); //解密器函数原型
#endifEncrypt.h
#ifndef Encrypt_H
#define Encrypt_H
#include <string>
#include "CharSet.h"
void Encrypt(string, Character*, int); //编码加密模块原型
string& replace_all(string&, const string&, const string&); //替换子串函数原型
void Encryptor(string, unsigned int); //加密器函数原型
#endif2.源码部分
CharSet.cpp
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
#include "CharSet.h"CharSet::CharSet()
{int n;cout << "请输入字符集大小：";cin >> n;cin.ignore();if (n > MaxSize || n < 1)throw"字符集大小超过范围！";for (int i = 0; i < n; i++){cout << "请输入字符集中的第" << i+1 << "个字符" << endl;ch[i].symbol = cin.get();cin.ignore();cout << "请输入其频度" << endl;cin >> ch[i].frequency;cin.ignore();ch[i].code = "-1";}length = n;
}void CharSet::PrintSet()
{cout << "字符" << setw(5) << "频度" << setw(8) << "编码" << endl;for (int i = 0; i < length; i++){cout << setw(2) << ch[i].symbol << setw(6) << ch[i].frequency;if (ch[i].code == "-1")cout << setw(10) << "未编码" << endl;elsecout << setw(11) << ch[i].code << endl;}
}int CharSet::GetLen()
{return length;
}Character* CharSet::GetCh()
{return ch;
}Coding.cpp
#include <string>
using namespace std;
#include "Coding.h"void BuildTree(element huffTree[], Character w[], int n)
{int i, k, i1 = 0, i2 = 0;for (i = 0; i < 2 * n - 1; i++) //初始化，所有结点均没有双亲和孩子{huffTree[i].parent = -1;huffTree[i].lchild = -1;huffTree[i].rchild = -1;}for (i = 0; i < n; i++) //构造n棵只含有根结点的二叉树huffTree[i].weight = w[i].frequency;for (k = n; k < 2 * n - 1; k++) //n-1次合并{Select(huffTree, i1, i2, k); //查找权值最小的两个根结点，下标为i1和i2huffTree[i1].parent = k; //将i1和i2合并，且i1和i2的双亲是khuffTree[i2].parent = k;huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;huffTree[k].lchild = i1;huffTree[k].rchild = i2;}
}
void Select(element huffTree[], int &i1, int &i2, int k)
{i1 = 0;i2 = 0;while (i1 < k){if (huffTree[i1].parent == -1)break;elsei1++;}for (int i = i1 + 1; i < k; i++){if (huffTree[i].parent == -1)if (huffTree[i].weight < huffTree[i1].weight)i1 = i;}huffTree[i1].parent = i1;while (i2 < k){if (huffTree[i2].parent == -1)break;elsei2++;}for (int i = i2 + 1; i < k; i++){if (huffTree[i].parent == -1)if (huffTree[i].weight < huffTree[i2].weight)i2 = i;}
}
void Coding(element huffTree[], Character c[], int n)
{int p, q;for (int i = 0; i < n; i++){string code = "";p = i;while (huffTree[p].parent != -1){q = huffTree[p].parent;if (huffTree[q].lchild == p){code = code + "0";}else{code = code + "1";}p = huffTree[p].parent;}reverse(code.begin(), code.end());c[i].code = code;}
}Decrypt.cpp
#include <iostream>
using namespace std;
#include "Decrypt.h"
void Decrypt(Character c[], int n)
{string str,dstr="",temp="";unsigned int password;cout << "请输入需要解密的字符串:";cin >> str;cout << "请输入6位密码:";cin >> password;Decryptor(str, password);for (int i = 0; i < str.length(); i++){temp = temp + str[i];for (int j = 0; j < n; j++){if (temp==c[j].code){dstr = dstr + c[j].symbol;temp = "";}}}cout << "解码后的字符串为：" << endl;cout << dstr << endl;
}void Decryptor(string& estr, unsigned int p)
{int pt[10], l;int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; //定义质数组for (int i = 0; i < 10; i++){pt[i] = (p%prime[i]) + 1; //定义加密因子}l = estr.length();for (int i = 9; i > -1; i--){for (int j = 0; j < l; j = j + pt[i]){if (estr[j] == '0'){estr[j] = '1';}else{estr[j] = '0';}}}cout << "解密后的字符串为：" << endl;cout << estr << endl;
}
Encrypt.cpp
#include <iostream>
using namespace std;
#include "Encrypt.h"void Encrypt(string str,Character c[],int n)
{string estr,s[MaxSize]; //存放加密后的字符串unsigned int password; //存放用户输入的密码estr = str;for (int i = 0; i < n; i++){s[i].insert(s[i].begin(), c[i].symbol);estr = replace_all(estr, s[i], c[i].code); //在字符串中，将字符集中有的字符替换为编码}cout << "编码后的字符串为：" << endl;cout << estr << endl;cout << "请输入6位加密字符串的密码：" << endl;cin >> password;Encryptor(estr, password);
}string& replace_all(string& str, const string& old_value, const string& new_value) //字符串替换模块，将某些子串替换为其他字符串
{while (true){string::size_type pos(0);if ((pos = str.find(old_value)) != string::npos)str.replace(pos, old_value.length(), new_value);else break;}return str;
}void Encryptor(string estr, unsigned int p)
{int pt[10],l;int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; //定义质数组for (int i = 0; i < 10; i++){pt[i] = (p%prime[i])+1; //定义加密因子}l = estr.length();for (int i = 0; i < 10; i++){for (int j = 0; j < l; j = j + pt[i]){if (estr[j] == '0'){estr[j] = '1';}else{estr[j] = '0';}}}cout << "加密后的字符串为：" << endl;cout << estr << endl;
}main.cpp
#include <iostream>
#include <Windows.h>
using namespace std;
#include "CharSet.h"
#include "Coding.h"
#include "Decrypt.h"
#include "Encrypt.h"int main()
{string str;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED);cout << "***********功能一：初始化字符集**********" << endl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_GREEN | FOREGROUND_BLUE);cout << "----------步骤一：输入字符和频度---------" << endl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);CharSet mychar;mychar.PrintSet();system("pause");cout << endl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_GREEN | FOREGROUND_BLUE);cout << "----------步骤二：对字符进行编码---------" << endl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);element huffTree[2 * MaxSize];BuildTree(huffTree,mychar.GetCh(),mychar.GetLen());Coding(huffTree, mychar.GetCh(), mychar.GetLen());mychar.PrintSet();system("pause");cout << endl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED);cout << "************功能二：加密字符串***********" << endl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);cout << "请输入需要加密的字符串：";getline(cin, str);Encrypt(str, mychar.GetCh(), mychar.GetLen());system("pause");cout << endl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED);cout << "************功能三：解密字符串***********" << endl;SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);Decrypt(mychar.GetCh(), mychar.GetLen());system("pause");return 0;
}以上源码在 Microsoft Visual C++ 2013中编译通过
六、收获
收获都是些对字符串的处理，包括对以下难点的处理。难点一：字符集构造函数对于单个空格字符读取到字符集中，会受到回车的干扰。
难点二：将字符集中的频度信息传入编码模块。
难点三：在编码模块中不断选出最小的两个叶子结点。
难点四：对每个字符进行哈夫曼编码。
难点五：对已编码好的字符串进行加密的加密方法和相应的解密方法。
难点六：将哈夫曼编码串还原为原输入的字符串。
七、体会多使用库函数能减少编码量。着眼于问题的重点，不要受困于旁枝末节。对同一个问题可能会有多种解决的算法。首先利用自己能编写出来的算法，然后随着自己对问题和算法理解的加深，不断对算法进行优化。很多时候错误出在一些不起眼的判断条件上，然不是大框架的问题。查找错误要沿着从小到大的方向。
八、不足
本程序结构尚未足够精简和清晰，各个函数间互相调用、参数传递较为混乱。未能完全符合面向对象的编程思想。
本程序对题目的针对性较强，未能做到经少量修改就能对其他字符串或文件中的字符串进行加密。
九、验证
