网站开发项目文档,南山做网站公司,2022年注册公司流程,沈阳工程最新动态实验九 哈夫曼编码
一、【实验目的】
1、理解哈夫曼树的基本概念 2、掌握哈夫曼树的构造及数据结构设计 3、掌握哈夫曼编码问题设计和实现
二、【实验内容】
1、假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成#xff0c;它们在电文中出现的概率分别为{ 0.…实验九 哈夫曼编码
一、【实验目的】
1、理解哈夫曼树的基本概念 2、掌握哈夫曼树的构造及数据结构设计 3、掌握哈夫曼编码问题设计和实现
二、【实验内容】
1、假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 }试为这8个字母设计哈夫曼编码。 提示:包含两个过程: 1构建哈夫曼树 2输出编码。
三、【实验源代码】 优先队列版
#include iostream
#include queue
#include map
using namespace std;// 定义结点结构体
struct Node
{Node *l; // 左孩子结点Node *r; // 右孩子结点int w; // 结点权值char letter; // 字符// 结点构造函数Node(Node* _l, Node* _r, int _w, char _letter){l _l;r _r;w _w;letter _letter;}// 重载小于运算符bool operator (const Node cmp) const {return w cmp.w;}
};priority_queueNode heap; // 定义优先队列用于构建哈夫曼树的堆
mapchar, string hafCode; // 存储哈夫曼编码的映射表// 构建哈夫曼树
Node* build()
{while (heap.size() 1){// 从堆中取出两个权值最小的结点合并为一个新的父结点Node* x new Node(heap.top().l, heap.top().r, heap.top().w, heap.top().letter);heap.pop();Node* y new Node(heap.top().l, heap.top().r, heap.top().w, heap.top().letter);heap.pop();Node* node new Node(x, y, x-w y-w, !); // 父结点的字符设为!heap.push(*node); // 将新父结点加入堆中}return new Node(heap.top().l, heap.top().r, heap.top().w, heap.top().letter); // 返回哈夫曼树的根结点
}// 递归遍历哈夫曼树生成哈夫曼编码
void dfs(Node* n, string m)
{if (n-letter ! !){hafCode.insert(make_pair(n-letter, m)); // 将字符和其对应的哈夫曼编码插入映射表}if (n-l ! NULL)dfs(n-l, m 0); // 左孩子结点编码为m 0if (n-r ! NULL)dfs(n-r, m 1); // 右孩子结点编码为m 1
}// 输出字符的哈夫曼编码
void printHafCode()
{for (char i a; i h; i)cout 字母 i 的哈夫曼码值是: hafCode[i] endl;
}int main()
{// 将初始字符权值放入优先队列中heap.push(Node(NULL, NULL, 7, a));heap.push(Node(NULL, NULL, 19,b));heap.push(Node(NULL, NULL, 2, c));heap.push(Node(NULL, NULL, 6, d));heap.push(Node(NULL, NULL, 32,e));heap.push(Node(NULL, NULL, 3, f));heap.push(Node(NULL, NULL, 21,g));heap.push(Node(NULL, NULL, 10,h));Node *root build(); // 构建哈夫曼树dfs(root, ); // 生成哈夫曼编码printHafCode(); // 输出哈夫曼编码return 0;
}能跑就行
#include iostream
using namespace std;
#include cstdio
#include cstring
typedef struct node { //哈夫曼树中单个节点的信息int parent; //父节点char letter; //字母int lchild;int rchild;double weight; //权值
}*HuffmanTree;
void Select(HuffmanTree tree, int n, int s1, int s2) { //找到权值最小的两个值的下标其中s1的权值小于s2的权值int min 0;for (int i 1; i n; i) {if (tree[i].parent 0) {min i;break;}}for (int i min 1; i n; i) {if (tree[i].parent 0 tree[i].weight tree[min].weight)min i;}s1 min; //找到第一个最小值并赋给s1for (int i 1; i n; i) {if (tree[i].parent 0 i ! s1) {min i;break;}}for (int i min 1; i n; i) {if (tree[i].parent 0 i ! s1 tree[i].weight tree[min].weight)min i;}s2 min; //找到第二个最小值并赋给s2
}
void CreateHuff(HuffmanTree tree, char* letters, double* weights, int n) {int m 2 * n - 1; //若给定n个数要求构建哈夫曼树则构建出来的哈夫曼树的结点总数为2n-1tree (HuffmanTree)calloc(m 1, sizeof(node)); //开辟空间顺序储存Huffman树用calloc开辟的空间初始化的值为0NULL符合Huffman树初始化条件parent、weight、lchild、rchild等初始化应为0由于tree[0]不存数据因为任何节点的父节点若为0会与节点初始化0值相混淆故不存数据则要开辟2n-11个空间额外开辟一个空间for (int i 1; i n; i) { //给节点赋字母及其对应的权值tree[i].weight weights[i - 1];tree[i].letter letters[i];}for (int i n 1; i m; i) {int s1 0, s2 0;Select(tree, i - 1, s1, s2); //每次循环选择权值最小的s1和s2,生成它们的父结点tree[i].weight tree[s1].weight tree[s2].weight; //新创建的节点i 的权重是s1和s2的权重之和tree[i].lchild s1; //新创建的节点i 的左孩子是s1tree[i].rchild s2; //新创建的节点i 的右孩子是s2tree[s1].parent i; //s1的父亲是新创建的节点itree[s2].parent i; //s2的父亲是新创建的节点i}
}
void HuffmanCoding(HuffmanTree tree, char** HuffCode, int n) {HuffCode (char**)malloc(sizeof(char*) * (n 1)); //运用char型二级指针可理解成包含多个char*地址的数组开n1个空间因为下标为0的空间不用char* tempcode (char*)malloc(sizeof(char) * n);tempcode[n - 1] \0;for (int i 1; i n; i) {int start n - 1;int doing i; //doing为正在编码的数据节点int parent tree[doing].parent; //找到该节点的父结点while (parent) { //直到父结点为0(NULL)即父结点为根结点时停止if (tree[parent].lchild doing) //如果该结点是其父结点的左孩子则编码为0否则为1tempcode[--start] 0;elsetempcode[--start] 1;doing parent; //继续往上进行编码parent tree[parent].parent;}HuffCode[i] (char*)malloc(sizeof(char) * (n - start)); //开辟用于存储编码的内存空间strcpy(HuffCode[i], tempcode[start]); //将编码拷贝到字符指针数组中的相应位置}free(tempcode); //释放辅助空间
}
int main() {int n 8;char letters[9] { ,a, b, c, d, e, f, g, h};double weights[9] {0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10};HuffmanTree tree;CreateHuff(tree, letters, weights, n); //构建哈夫曼树char** HuffCode;HuffmanCoding(tree, HuffCode, n);for (int i 1; i n; i)printf(字母 %c 的哈夫曼编码值是: %s\n, tree[i].letter, HuffCode[i]);return 0;
} 参考资料
