网站提交做外链有什么作用,免费广告推广,公司为什么要网站备案,网红助手24小时自助下单app目录 1.哈夫曼树是什么#xff1f; 2.哈夫曼编码是什么#xff1f; 3.哈夫曼编码的应用 4.包含头文件 5.结点设计 6.接口函数定义 7.接口函数实现 8.哈夫曼编码测试案列 哈夫曼树是什么#xff1f; 哈夫曼树#xff08;Huffman Tree#xff09;是一种特殊的二叉树#xf…目录 1.哈夫曼树是什么 2.哈夫曼编码是什么 3.哈夫曼编码的应用 4.包含头文件 5.结点设计 6.接口函数定义 7.接口函数实现 8.哈夫曼编码测试案列 哈夫曼树是什么 哈夫曼树Huffman Tree是一种特殊的二叉树由David A. Huffman在1952年发明的用于数据压缩领域。哈夫曼树是一种最优的二叉树因为它具有最小的加权路径长度。这里的“最优”是指在给定的一组权重通常是字符出现频率下哈夫曼树的加权路径长度即树中所有叶节点的权重乘以其到根节点的距离是最小的以下是哈夫曼树的特点 1.完全二叉树除了最后一层外每一层都是满的 2.加权路径长度最小所有叶节点的权重乘以其到根节点的距离之和是最小的 3.每个节点都有权重叶节点代表单个字符非叶节点代表字符的集合 哈夫曼编码是什么 哈夫曼编码是一种使用哈夫曼树进行编码的方法。它将每个字符映射为一个唯一的二进制串这些二进制串的长度不同且是根据字符出现频率来确定的。频率越高的字符其编码越短频率越低的字符其编码越长。这种编码方式可以有效地减少数据的存储空间或传输时间。实现哈夫曼编码的步骤如下 1.统计字符频率首先统计数据集中每个字符出现的频率 2.构建哈夫曼树 1.将每个字符及其频率作为叶子节点放入优先队列通常是最小堆 2.从队列中取出两个权重最小的节点创建一个新的内部节点其权重为这两个节点权重之和 3.将新节点重新加入队列。重复上述步骤直到队列中只剩下一个节点这个节点就是哈夫曼树的根节点 3.生成编码从根节点开始向左子树走标记为0向右子树走标记为1直到到达叶节点此时叶节点对应的字符的路径标记就是其哈夫曼编码 哈夫曼编码的应用 哈夫曼编码是一种非常实用的编码技术它通过利用数据的内在特性来优化存储和传输效率 1.数据压缩用于无损数据压缩特别是在文本压缩中非常有效。 2.文件压缩如ZIP文件格式就使用了哈夫曼编码。 3.通信协议在某些通信协议中用于减少传输数据的大小。 包含头文件
#includestdio.h
#includestdlib.h
#includestring.h 结点设计
#define Initsize 100
typedef int Elemtype;
int Node[Initsize][2]; //定义二维数组Node存储输入的字符和字符所含的权值
int NodeValue[Initsize]; //定义一维数组NodeValue存储经排序过的字符的权值
int Hand 0; //定义整形变量Hand作为数组NodeValue的头指针
int CodeHead 0; //定义int类型变量CodeHead作为指针数组Code的头指针typedef struct HTree {Elemtype value; //存储结点权值Elemtype Lvalue, Rvalue; //存储孩子标识struct HTree* lchild; //存储左孩子树struct HTree* rchild; //存储右孩子树
}HTree,*HfmTree;HfmTree Head; //定义全局变量Head作为哈夫曼树的根节点指针
HfmTree Code[Initsize]; //定义HTree类型的指针数组Code存储结点的地址 接口函数定义
void InitHTree(HfmTree A); //用于初始化哈夫曼树
void InsertNode(int A); //用于输入字符和其权值
void SortNodeV(int A); //用于对输入的权值进行排序
void InitLHfm(HfmTree A); //用于哈夫曼树的左子树进行初始化并赋值
void InitRHfm(HfmTree A); //用于哈夫曼树的右子树进行初始化并赋值
void InsertHTree(HfmTree A,int B); //用于创建哈夫曼树
void PostOrder(HfmTree A); //用于对哈夫曼树进行后序遍历
void InputBTree(HfmTree A); //用于对哈夫曼树的结点权值输出
void SeekHTreeL(HfmTree A, int B); //用于单独寻找哈夫曼树的左子树的字符及权值
void SeekHTreeR(HfmTree A, int B); //用于寻找哈夫曼树的右子树的字符及权值
void InputHfmCode(HfmTree A,int B); //用于输出哈夫曼编码
void InitRootHfm(HfmTree A,HfmTree B,HfmTree C); //用于对哈夫曼树的根结点进行初始化并赋值 接口函数实现
void InputHfmCode(HfmTree A,int B) { //用于输出哈夫曼编码int i,j;while (A ! NULL) { //对哈夫曼树的左子树进行进栈操作Code[CodeHead] A;A A-lchild;CodeHead;}printf(\n);SeekHTreeL(A, B); //使用函数SeekHtreeL对其哈夫曼树进行寻找左子树的字符及权值for (i 1; i CodeHead; i) {printf(%d, Code[i]-Lvalue); //对栈里结点所含的Lvalue进行输出(从根结点开始输出其含有的LvaLue)}CodeHead--; //出栈操作while (CodeHead ! 0) { //判断栈是否为空printf(\n);SeekHTreeR(A, B); //使用函数SeekHTreeR对其哈夫曼树进行寻找右子树的字符及权值for (i 0; i CodeHead - 1; i) { //对栈里结点所含的Lvalue进行输出(从根结点开始输出其含有的LvaLue)if (i CodeHead - 1) { //若为栈尾结点则输出其右子树printf(%d, Code[i]-Rvalue); break;}printf(%d, Code[i]-Lvalue);}CodeHead--; //出栈操作}
}void SeekHTreeR(HfmTree A, int B) { //用于寻找哈夫曼树的右子树的字符及权值int i,j;for (i CodeHead - 1; i 0; i){ //遍历栈if (i CodeHead-1) { //判断是否为栈的倒数第二个结点(跟定义的结点的有关)for (j 0; j B; j) { //遍历存储字符及权值的数组寻找对应的字符和权值if (Node[j][1] Code[i]-rchild-value) {Node[j][1] -1; //未防止字符不一样但权值相同的出现造成输出哈夫曼编码错误printf(%c的哈夫曼编码为, Node[j][0]);break; }}}break; }
}void SeekHTreeL(HfmTree A, int B){ //用于单独寻找哈夫曼树的左子树的字符及权值int i,j;for (i 0; i CodeHead; i) { //遍历栈if (i CodeHead - 1) { //判断是否为栈的倒数第二个结点(跟定义的结点的有关)for (j 0; j B; j) { //遍历存储字符及权值的数组寻找对应的字符和权值if (Node[j][1] Code[i]-value) { Node[j][1] -1; //未防止字符不一样但权值相同的出现造成输出哈夫曼编码错误printf(%c的哈夫曼编码为, Node[j][0]);break;}}}}
}void InputBTree(HfmTree A) { //用于对哈夫曼树的结点权值输出 printf(%d , A-value);
}void PostOrder(HfmTree A) { //用于对哈夫曼树进行后序遍历 if (A ! NULL) {PostOrder(A-lchild); PostOrder(A-rchild); InputBTree(A); }
}void InsertHTree(HfmTree A,int B) {//用于创建哈夫曼树if(HandB-1){ //判断是否已将所有字符及权值进行构建对应的哈夫曼树的结点if (A NULL) { HfmTree Q (HTree*)malloc(sizeof(HTree)); HfmTree W (HTree*)malloc(sizeof(HTree)); InitLHfm(Q); //使用函数InitLHfm对其左子树初始化Hand;InitRHfm(W); //使用函数InitRHfm对其右子树初始化InitRootHfm(A, Q, W); //使用函数InitRootHfm对其根结点初始化Head A; //更新哈夫曼树的头指针的指向InsertHTree(A, B); }else {HfmTree Q (HTree*)malloc(sizeof(HTree)); HfmTree W (HTree*)malloc(sizeof(HTree)); Hand;InitRHfm(Q); //使用函数InitRHfm对其右子树初始化InitRootHfm(W, A, Q); //使用函数InitRootHfm对其根结点初始化Head W;InsertHTree(W, B);}}
}void InitRootHfm(HfmTree A, HfmTree B, HfmTree C) {//用于对哈夫曼树的根结点进行初始化并赋值A (HTree*)malloc(sizeof(HTree));A-value B-value C-value; //根结点的权值为两个子结点的权值之和A-Lvalue 1; //添加左子树标识A-Rvalue 0;A-lchild B; //添加根结点指向的左子树A-rchild C; //添加根结点指向的右子树printf(新建的根结点的权值数据为%d\n, A-value);
}void InitRHfm(HfmTree A) { //用于哈夫曼树的右子树进行初始化并赋值A-value NodeValue[Hand]; //对结点所含的权值进行更新A-Lvalue 0;A-Rvalue 1; //添加右子树标识A-lchild NULL; A-rchild NULL;printf(新建的右孩子的权值数据为%d\n, A-value);
}void InitLHfm(HfmTree A) { //用于哈夫曼树的左子树进行初始化并赋值A-value NodeValue[Hand]; //对结点所含的权值进行更新A-Lvalue 1; //添加左子树标识A-Rvalue 0;A-lchild NULL;A-rchild NULL;printf(新建的左孩子的权值数据为%d\n, A-value);
}void SortNodeV(int A) { //用于对输入的权值进行排序int i, j, Q;for (i 0; i A - 1; i) { //冒泡排序for (j 0; j A - 1 - i; j)if (NodeValue[j] NodeValue[j 1]) {Q NodeValue[j];NodeValue[j] NodeValue[j 1];NodeValue[j 1] Q;}}
}void InsertNode(int A) { //用于输入字符和其权值int i, j;char Q;for (i 0; i A; i) {j 0;printf(请输入结点的字符);getchar(); //清除缓冲区防止赋值脏数据Qgetchar();Node[i][j] (int) Q;j;printf(请输入结点的权值);scanf_s(%d, Node[i][j]);NodeValue[i] Node[i][j];}
}void InitHTree(HfmTree A) { //用于初始化哈夫曼树A NULL;printf(初始化哈夫曼树成功\n);
} 哈夫曼编码测试案列
void main() {int NodeSize,i;HfmTree X;InitHTree(X);printf(请问需要输入多少个字符);scanf_s(%d, NodeSize);InsertNode(NodeSize);SortNodeV(NodeSize);InsertHTree(X, NodeSize);printf(创建哈夫曼树成功\n);printf(后序遍历的哈夫曼树为);PostOrder(Head);printf(\n);InputHfmCode(Head,NodeSize);
}
