哈夫曼树实验报告.docx

中南大学数据结构课程实验实验报告题 目 hafuman编码 学生姓名 柯鑫鑫 学生学号 3901130604 专业班级 1306 需求分析设字符集为26个英文字母，其出现频度如下表所示。以二叉链表作存储结构，编写程序，实现如下的功能：1、根据所提供的字母数据建立一个Huffman树；2、根据生成的Huffman树的结构，显示输出所有字母的Huffman编码。3、（选作内容）根据产生的Huffman编码，实现Huffman编/译码器。概要设计要结构体存放每个节点的信息，要数组存放字母频率表的信息，节点与节点之间用二叉链表连接。结构体的结构如下struct Nodechar date;int weight;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 = 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 weight;a = j;else if (nodej-weightone&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 (int 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 code;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) = 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 (123 = 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 = 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 *parent;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 = new 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 weight;a = j;else if (nodej-weightone&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;for (int 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;/编码string code;string input;cout input;for (int i = 0; i input.size(); i+)code.append(sinput.at(i) - a + 1);cout codeendl;/译码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 = head-lchild;if (head-lchild = NULL)yima.append(1, head-date);head = nodeTNUM-1;cout the word is: yimaendl;system(pause);return 0;全ascall码文本输入代码#include#include#includeusing namespace std;#define NUM 94 /字符数#define TNUM 187 /#define LTH 20 /编码最大长度struct Nodechar date;int weight;Node *parent;Node *lchild;Node *rchild;int main()ifstream inputm;inputm.open(wenben.txt);string inputt;char c1000000;if (inputm.fail()cout File does not exist endl;cout exit program endl;return 0;while (!inputm.eof()inputm.getline(c, 1000000, );inputm.close();inputt = c;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, 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, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, !, , #, $, %, &, , (, ), *, +, , -, ., /, :, ;, , ?, , , , , , _, , , |, ;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 ,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55;Node *nodeTNUM;for (int i = 0; i TNUM; i+)nodei = new 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 weight;a = j;else if (nodej-weightone&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;for (int 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 code;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) = 57)code.append(s53 + inputt.at(i) -