《哈夫曼树实验报告》由会员分享，可在线阅读，更多相关《哈夫曼树实验报告（14页珍藏版）》请在金锄头文库上搜索。
1、中南大学数据结构课程实验实验报告题 目 hafuman编码 学生姓名 柯鑫鑫 学生学号 3901130604 专业班级 1306 需求分析设字符集为26个英文字母，其出现频度如下表所示。以二叉链表作存储结构，编写程序，实现如下的功能：1、根据所提供的字母数据建立一个Huffman树；2、根据生成的Huffman树的结构，显示输出所有字母的Huffman编码。3、（选作内容）根据产生的Huffman编码，实现Huffman编/译码器。概要设计要结构体存放每个节点的信息，要数组存放字母频率表的信息，节点与节点之间用二叉链表连接。结构体的结构如下struct Nodechar date;int we
2、ight;Node *parent;Node *lchild;Node *rchild;date表示存放的字母，weight表示权重。把叶子节点方在前面。叶子节点与总节点的关系为 总结点=叶子节点*2-1；（注：可以把常量定义成#define NUM 94 /字符数#define TNUM 187 /#define LTH 20 /编码最大长度好处如下便于程序的升级有利于直观的理解，而不只是数字）初始化各个节点如下for (int i = 0; idate = charsi;nodei-parent = NULL;nodei-weight = weighti;nodei-lchild = NU
3、LL;nodei-rchild = NULL;for (int i = NUM; iparent = NULL;nodei-weight = -1;nodei-lchild = NULL;nodei-rchild = NULL;详细设计找出没有父节点的最小的两个节点for (int i = NUM; i TNUM; i+)int one = 10000;int two = 10000;int a = 0;int b = 0;int j = 0;for (; j parent = NULL)if (nodej-weight weight;a = j;else if (nodej-weighton
4、e&nodej-weight weight;b = j;nodej-lchild = nodea;nodej-rchild = nodeb;nodea-parent = nodej;nodeb-parent = nodej;nodej-weight = nodea-weight + nodeb-weight;定义数组来存储哈夫曼编码并初始化char HTNUMLTH;for (int i = 0; i LTH; i+)for (int j = 0; j NUM; j+)HTji = 7;二叉链表从下往上走，如果是左孩子哈夫曼编码为0，如果是右孩子哈夫曼编码为1；数组从最右往前走；for (in
5、t i = 0; i parent != NULL)Node *temp = m-parent;if (m = temp-lchild)HTij = 0;if (m = temp-rchild) HTij = 1;m = m-parent;j-;输出哈夫曼编码表string sNUM;for (int i = 0; iNUM; i+)for (int j = 0; jLTH; j+)if (HTij != 7)si.append(1, HTij);for (int i = 0; i NUM; i+)cout date si endl;system(pause);哈夫曼编码/编码string c
6、ode;for (int i = 0; i inputt.size(); i+)if (inputt.at(i) - a + 1 = -64)code.append(s0);else if (97 = inputt.at(i) & inputt.at(i) = 122)code.append(sinputt.at(i) - a + 1);else if (65 = inputt.at(i) & inputt.at(i) = 90)code.append(s26 + inputt.at(i) - 65 + 1);else if (48 = inputt.at(i) & inputt.at(i)
7、= 57)code.append(s53 + inputt.at(i) - 0);else if (33 = inputt.at(i) & inputt.at(i) = 47)code.append(s63 + inputt.at(i) - !);else if (58 = inputt.at(i) & inputt.at(i) = 64)code.append(s78 + inputt.at(i) - :);else if (91 = inputt.at(i) & inputt.at(i) = 96)code.append(s85 + inputt.at(i) - );else if (12
8、3 = inputt.at(i) & inputt.at(i) = 125)code.append(s91+inputt.at(i)-);cout code endl;ofstream output;output.open(code.txt);output code;output.close();此处的编码为文件读入哈夫曼的译码string yima;Node* head = nodeTNUM - 1;for (int i = 0; i rchild != NULL)head = head-rchild;if (code.at(i) = 0&head-lchild != NULL)head =
9、 head-lchild;if (head-lchild = NULL)yima.append(1, head-date);head = nodeTNUM - 1;cout the word is: yima endl;system(pause);return 0;实验截图说明如果是文本输入的话要注意附录：完整代码简单键盘输入#include#includeusing namespace std;#define NUM 27 /字母数#define TNUM 53 /#define LTH 15 /编码最大长度struct Nodechar date;int weight;Node *pare
10、nt;Node *lchild;Node *rchild;int main()char chars = , 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 ;int weight = 183, 64, 13, 22, 32, 103, 21, 15, 47, 57, 1, 5, 32, 20, 57, 63, 15, 1, 48, 51, 80, 23, 8, 18, 1, 16, 1 ;Node *nodeTNUM;for (int i = 0; i TNUM; i+)nodei = n
11、ew Node;for (int i = 0; idate = charsi;nodei-parent = NULL;nodei-weight = weighti;nodei-lchild = NULL;nodei-rchild = NULL;for (int i = NUM; iparent = NULL;nodei-weight = -1;nodei-lchild = NULL;nodei-rchild = NULL;for (int i = NUM; i TNUM; i+)int one = 10000;int two = 10000;int a = 0;int b = 0;int j = 0;for (; j parent = NULL)if (nodej-weight = one)two = one;b = a;
