哈夫曼树实验报告

中南大学

《数据结构》课程实验

实验报告

题 目 hafuman编码 学生姓名 柯鑫鑫 学生学号 3901130604 专业班级 1306

需求分析

设字符集为26个英文字母，其出现频度如下表所示。以二叉链表作存储结构，编写程序，实现如下的功能：

1、根据所提供的字母数据建立一个Huffman树；

2、根据生成的Huffman树的结构，显示输出所有字母的Huffman编码。 3、（选作内容）根据产生的Huffman编码，实现Huffman编/译码器。

概要设计

要结构体存放每个节点的信息，要数组存放字母频率表的信息，节点与节点之间用二叉链表连接。结构体的结构如下 struct Node{ char 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 = chars[i]; node[i]->parent = NULL; node[i]->weight = weight[i]; node[i]->lchild = NULL; node[i]->rchild = NULL; } for (int i = NUM; iparent = NULL; node[i]->weight = -1; node[i]->lchild = NULL; node[i]->rchild = NULL; }

详细设计

找出没有父节点的最小的两个节点 for (int i = NUM; i parent == NULL){ if (node[j]->weight <= one){ two = one; b = a; one = node[j]->weight; a = j; } else if (node[j]->weight>one&&node[j]->weight <= two){ two = node[j]->weight; b = j; } } } node[j]->lchild = node[a]; node[j]->rchild = node[b]; node[a]->parent = node[j]; node[b]->parent = node[j]; node[j]->weight = node[a]->weight + node[b]->weight; }

定义数组来存储哈夫曼编码并初始化 char HT[NUM][LTH]; for (int i = 0; i < LTH; i++){ for (int j = 0; j

二叉链表从下往上走，如果是左孩子哈夫曼编码为0， 如果是右孩子哈夫曼编码为1； 数组从最右往前走；

for (int i = 0; i < NUM; i++){ int j = LTH - 1;

Node *m = node[i]; while (m->parent != NULL){ Node *temp = m->parent; if (m == temp->lchild){ HT[i][j] = '0'; } if (m == temp->rchild) { HT[i][j] = '1'; } m = m->parent; j--; } }

输出哈夫曼编码表 string s[NUM]; for (int i = 0; idate << \ \ } system(\哈夫曼编码 //编码 string code; for (int i = 0; i

else if (58 <= inputt.at(i) && inputt.at(i) <= 64) code.append(s[78 + inputt.at(i) - ':']); else if (91 <= inputt.at(i) && inputt.at(i) <= 96) code.append(s[85 + inputt.at(i) - '[']); else if (123 <= inputt.at(i) && inputt.at(i) <= 125) code.append(s[91+inputt.at(i)-'{']); } cout << code << endl; ofstream output; output.open(\ output << code; output.close();

此处的编码为文件读入 哈夫曼的译码 string yima; Node* head = node[TNUM - 1]; for (int i = 0; i < code.size(); i++){ if (code.at(i) == '1'&&head->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 = node[TNUM - 1]; } } cout << \ system(\ return 0;

实验截图