Shigure_Q 2016-12-03 12:31 采纳率: 50%
浏览 4109
已结题

c++实现哈夫曼编码和译码系统

在数据通讯中,经常要将传送的文字转换为二进制字符0和1组成的二进制串,称这个过程为编码。与子相对的是解码或是译码,就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。
要求: 设计一个菜单可以循环显示
B——建树:读入字符集和各字符频度,建立哈夫曼树。
T——遍历:先序和中序遍历二叉树。
E——生成编码:产生每个字符的哈夫曼编码。
C——编码:输入由字符集中字符组成的任意字符串,利用已经生成的哈夫曼编码进行编码,显示编码结果。
D——译码:利用已建成的哈夫曼树进行译码。
X——退出。
我的代码如下:
#include

#include

using namespace std;

string s1[10000];
string s[10000];

//结点类型

struct element {

double weight; //字符出现的概率为实数

char ch;

int lchild, rchild, parent;

};

//在HuffTer中找权值最小的两个结点i1和i2

void Select(element huffTree[], int *a, int *b, int n) {

int i;

double weight = 0;

for(i = 0; i < n; i++) {

if(huffTree[i].parent != - 1) //如果有父结点的,不进行判断

continue;

else {

if(weight == 0) {

weight = huffTree[i].weight;

*a = i;

}

else {

if(huffTree[i].weight < weight) {

weight = huffTree[i].weight;

*a = i;

}

}

}

}

weight = 0;

for(i = 0; i < n; i++) {

if(huffTree[i].parent != -1 || (i == *a))

continue;

else {

if(weight == 0) {

weight = huffTree[i].weight;

*b = i;

}

else {

if(huffTree[i].weight < weight) {

weight = huffTree[i].weight;

*b = i;

}

}

}

}

int temp;

if(huffTree[*a].lchild < huffTree[*b].lchild) { //避免根结点的左右子树混淆

temp = *a;

*a = *b;

*b = temp;

}

}

//建立霍夫曼树

void HuffmanTree(element huffTree[], int w[], char ch[], int n) {

for(int i = 0; i < 2 * n - 1;i++) {//霍夫曼树共有2*n - 1个结点

huffTree[i].parent = -1; //双亲结点

huffTree[i].lchild = -1; //左孩子结点

huffTree[i].rchild = -1; //右孩子结点

}

for(int i = 0; i < n; i++) { //构造n棵只含有根结点的二叉树

huffTree[i].weight = w[i]; //给哈夫曼树赋权值

huffTree[i].ch = ch[i]; //需要编码的字符

}

for(int k = n; k < 2 * n - 1; k++) {//n-1次合并

int i1 = 0;

int i2 = 0;

Select(huffTree, &i1, &i2, k); //在HuffTer中找权值最小的两个结点i1和i2

huffTree[i1].parent = k; //将i1和i2合并,则i1和i2的双亲是k

huffTree[i2].parent = k;

huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;

huffTree[k].lchild = i1;

huffTree[k].rchild = i2;
huffTree[k].ch = NULL;
}

}

//霍夫曼编码

void HuffmanCode(element hTree[], int n) {

int i, j, k;
for(i = 0; i < n; i++) { //在数组HuffTree中前n个元素是叶子结点,需要编码

s[i] = ""; //编码s初始化为空串

j = i; //暂存i,不破坏循环变量

while(hTree[j].parent != -1) {//结点j存在双亲

k = hTree[j].parent;

if(j == hTree[k].lchild) {//结点j是其双亲的左孩子

s[i] = s[i] + "0";

}

else { //结点j是其双亲的右孩子
s[i] = s[i] + "1";

}

j = hTree[j].parent; //将结点j的双亲赋给j

}

cout << "字符" << hTree[i].ch << "的编码:" << endl;

for(int p = s[i].size() - 1; p >= 0; p--) { //将s作为结点i的编码逆序输出
s1[i] += s[i].at(p);

}

cout << s1[i] << endl;

}

}

int main() {
char mark;
while(cin >> mark) {
if(mark == 'B') {
int n;
cout << "请输入字符个数:" << endl;
cin >> n;
char c[n];
int w[n];
element huffTree[2 * n];
cout << "请输入字符以及对应权值:" << endl;
for(int i = 0; i < n; i++) {
cin >> c[i] >> w[i];
}
HuffmanTree(huffTree, w, c, n); // 构造霍夫曼树
while(cin >> mark) {
if(mark == 'E') {
HuffmanCode(huffTree, n); //生成编码
}
if(mark == 'C') { //对输入字符串进行编码
string temp;
cout << "请输入编码字符串:" << endl;
cin >> temp;
cout << "该串霍夫曼编码为:" << endl;
for(int i = 0; i < temp.size(); i++) {
for(int j = 0; j < n; j++) {
if(temp.at(i) == c[j]) {
cout << s1[j];
}
}
}
cout << endl;
}
if(mark == 'D') {
string temp1;
cout << "请输入译码字符串:" << endl;
cin >> temp1;
cout << "该串译码为:" << endl;
string temp2 = "";
string :: iterator it = temp1.begin();
temp2 += *it;
for(;;) {
for(int i = 0; i < n; i++) {
if(temp2 == s1[i]) {
cout << c[i];
temp2 = "";
break;
}
}
it++;
if(it == temp1.end()) {
break;
}
else {
temp2 += *it;
}
}
cout << endl;
}
if(mark == 'X') {
break;
}
}
break;
}
else {
cout << "请先建树" << endl;
}
}

return 0;  

}

想请教下如何遍历?

  • 写回答

2条回答 默认 最新

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题