做网站好不好,深圳趣网站建设,下载一个百度时事新闻,公司简介模板免费如何写实验九 哈夫曼编码
一、【实验目的】
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
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;
} 参考资料
