本篇博客主要是为大连海事大学数据结构实验附加题2提供一个解题思路。

一、实验要求

哈夫曼编码与译码器
① 问题描述：给定n个字符的全值数组w，根据哈夫曼编码与译码规则，实现一个哈夫曼编/译码系统（利用实验指导书上的27个字符的数据进行实验）。
② 利用顺序表存储Huffman树，编码结果的存储方式采用书上的结构。
③ Huffman树的构造约定如下：
 根的权值较小的子树作为左子树，当权值相等时，先生成的作为左子树；
 按照结点的产生次序选择权值较小的两棵子树构造Huffman树；
 从叶子到根逆向求每个字符的Huffman编码，不采用递归方法；
 从根结点开始实现译码，要求被译码的字符数大于20个字符。
④ 采用文件方式存储n个权值和待翻译的二进制代码，其余的数据或结构均不采用文件存储。

二、实验可运行代码

#include<stdio.h>
#include<fstream>
#include<stdlib.h>
#include<string.h>
#pragma warning(disable : 4996)
#define MAX 1000
typedef struct
{char code;//字符int weight;//权值int parent, lchild, rchild;//双亲，左右孩子
}HTNode, * HuffmanTree;
//挑选权值最小的结点
void Select(HuffmanTree HT, int i, int& s1, int& s2)
{int k;int weight1 = MAX;int weight2 = MAX;for (k = 1; k <= i; k++){if (HT[k].parent == 0 && weight1 > HT[k].weight){weight1 = HT[k].weight;s1 = k;}}for (k = 1; k <= i; k++){if (HT[k].parent == 0 && weight2 > HT[k].weight&& k != s1){weight2 = HT[k].weight;s2 = k;}}
}
//哈夫曼树结构打印
void OutPut(HuffmanTree HT, int n)
{int i;printf("哈夫曼树：\n");printf("序号\t字符\t权值\t父\t左\t右\n");for (i = 1; i <= n; i++){printf("%d\t%c\t%d\t%d\t%d\t%d\n", i, HT[i].code, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);}
}
//创建Huffman树
void CreateHuffmanTree(HuffmanTree& HT, int n)
{int i;int s1 = 0, s2 = 0;//结点序号返回值int m = 2 * n - 1;FILE* fp;fp = fopen("Huffman1.txt", "r");if (!fp){printf("文件打开失败！！！\n");exit(0);}if (m < 2){printf("不合法！！\n");exit(1);}HT = new HTNode[m + 1];//初始化for (i = 1; i < m+1; i++){HT[i].code = '*';HT[i].lchild = 0;HT[i].parent = 0;HT[i].rchild = 0;HT[i].weight = 0;}//文件读入int j = 1;while (fgetc(fp)!=EOF){fscanf(fp, "%c%d", &HT[j].code, &HT[j].weight);j++;}fclose(fp);for (i = n + 1; i <= m; i++){Select(HT, i - 1, s1, s2);HT[s1].parent = i;HT[s2].parent = i;HT[i].lchild = s1;HT[i].rchild = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;}
}
//编码
void EnCoding(HuffmanTree HT, int n, int Coding[60][15])
{int i, k;HTNode FT, CT;for (i = 1; i <= n; i++){int j = 1;int t = i;CT = HT[i];FT = HT[CT.parent];while (FT.parent != 0){if (FT.lchild == t){Coding[i][j] = 0;j++;}if (FT.rchild == t){Coding[i][j] = 1;j++;}t = CT.parent;CT = FT;FT = HT[CT.parent];}if (FT.lchild == t){Coding[i][j] = 0;j++;}if (FT.rchild == t){Coding[i][j] = 1;j++;}Coding[i][0] = j;//存放数组长度}printf("字符编码：\n");for (i = 1; i <= n; i++){printf("%c:", HT[i].code);for (k = Coding[i][0] - 1; k > 0; k--){printf("%d", Coding[i][k]);}printf("  ");}printf("\n");
}
//解码
void DECODE(HuffmanTree HT, int d,int password[500])
{int i=0;//i用于循环，j用于表示指针位置HTNode  D;D = HT[53];while(i<d){if (D.lchild != 0 && password[i] == 0){D = HT[D.lchild];i++;}if (D.lchild != 0 && password[i] == 1){D = HT[D.rchild];i++;}if(D.lchild==0&&D.rchild==0){printf("%c", D.code);D = HT[53];}}printf("\n");
}
int main()
{int i, k, t=0, id,d=0;int p = 0;char code[255];HuffmanTree HT;int n = 27;int m = 2 * n - 1;int Coding[60][15];CreateHuffmanTree(HT, n);OutPut(HT, m);EnCoding(HT, n, Coding);while (1){printf("请选择功能：\n");printf("1.字符串编码\n");printf("2.密码译码\n");printf("0.退出\n");printf("请输入功能编号：");scanf("%d", &id);getchar();switch (id){case 0:exit(0);case 1:printf("请输入明文（字符串）：\n");gets_s(code);//可以接受输入空格printf("密文如下：\n");i = 0;while(code[i]!=NULL){for (k = 1; k <= n; k++){if (code[i] == HT[k].code){t = k;break;}}for (k = Coding[t][0] - 1; k > 0; k--){printf("%d", Coding[t][k]);}i++;}printf("\n");break;case 2:int password[500];d = 0;printf("请输入密文（数字与数字之间用空格隔开,最后一位数字之后不用空格，加上#）：\n");while (1){scanf("%d", &password[d++]);if (getchar() == '#')break;}p = 0;printf("明文如下：\n");DECODE(HT,d, password);break;default:printf("请输入正确的功能编号！！！\n");}}return 0;
}

三、权值文件

四、实验结果示例

哈夫曼树状态表如下：

编码解码示例如下：

仅供参考！