当前位置： 首页 > news >正文

《数据结构（C语言版）第二版》第五章-树和二叉树（5.7 哈夫曼树及其应用）

news 来源：原创 2024/9/20 11:53:53

5.7 哈夫曼树及其应用

5.7.2 哈夫曼树的构造算法

c语言哈夫曼树及其编码 —— 十八岁没有梦想

#include <stdio.h>
#include <stdlib.h>typedef struct
{int weight;int parent;int lchild;int rchild;
}HTNode, * HuffmanTree;void CreateHuffmanTree(HuffmanTree& HT, int n);
void Select(HTNode* s, int n, int& s1, int& s2);
void OrderHuffmanTree(HuffmanTree& HT, int n);int main()
{HuffmanTree HT = NULL;CreateHuffmanTree(HT, 8);OrderHuffmanTree(HT, 8);return 0;
}void CreateHuffmanTree(HuffmanTree& HT, int n)
{if (n < 1){return;}//n = 1 时，只有一个结点，其权重为输入值，其双亲结点、左孩子、右孩子的结点下标均不存在（设为0）.且n = 1时，程序无法生成其最优前缀编码（实际中用最短的0或1均可）。int i = 0;int m = 2 * n - 1;int s1 = 0;int s2 = 0;HT = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1));//HT指向了一个一维数组的基地址，数组中的元素类型是HTNode,数组大小为m+1//等价于HTNode HT[m+1]//不说明数组大小时，为HTNode* HT，HuffmanTree HTfor (i = 1; i <= m; ++i){HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;}for (i = 1; i <= n; i++){printf("请输入第%d个叶子结点的权值：", i);scanf_s("%d", &HT[i].weight);}/*－－－－－－－－－－－初始化工作结束，下面开始创建哈夫曼树－－－－－－－－－－*/for (i = n + 1; i <= m; i++){//选择Select(HT, i - 1, s1, s2);//删除HT[s1].parent = i;HT[s2].parent = i;//合并HT[i].weight = HT[s1].weight + HT[s2].weight;HT[i].lchild = s1;HT[i].rchild = s2;}
}//在大小为n的一维整数型数组s中，找到最小的两个整数，并将其坐标存储在变量s1和s2中,下标从1开始
void Select(HTNode* s, int n, int& s1, int& s2)
{int m = 0;  //最小的值，下标为s1int p = 0;  //第二小的值，下标为s2int r = 1;int t = 1;//找到第一个双亲不为0的s[r]while (s[r].parent != 0){r++;}//找到第二个双亲不为0的s[t]t = r + 1;while (s[t].parent != 0){t++;}//比较s[r]和s[t]if (s[r].weight <= s[t].weight){m = s[r].weight;p = s[t].weight;s1 = r;s2 = t;}else{m = s[t].weight;p = s[r].weight;s1 = t;s2 = r;}for (int k = 3; k <= n; k++){if (s[k].parent == 0 && s[k].weight < m){p = m;s2 = s1;m = s[k].weight;s1 = k;}else if (s[k].parent == 0 && s[k].weight > m && s[k].weight < p){p = s[k].weight;s2 = k;}else{;}}//将下标小的作为新结点的左孩子，将下标大的作为新结点的右孩子int temp = 0;if (s1 > s2){temp = s1;s1 = s2;s2 = temp;}printf("\ns1 = %d, s2 = %d", s1, s2);
}
//遍历哈夫曼树（即遍历其HT数组各个结点元素的信息）
void OrderHuffmanTree(HuffmanTree& HT, int n)
{int k = 0;if (HT){for (k = 1; k <= (2 * n - 1); k++){printf("\n\nHT[%d].weight = %d, HT[%d].parent = %d, HT[%d].lchild = %d, HT[%d].rchild = %d ", k, HT[k].weight, k, HT[k].parent, k, HT[k].lchild, k, HT[k].rchild);}}
}

在这里插入图片描述
在这里插入图片描述

5.7.3 哈夫曼编码

用C语言实现哈夫曼编码 ——— 爱编程的小木可

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct
{int weight;int parent;int lchild;int rchild;
}HTNode, * HuffmanTree;typedef char** HuffmanCode;void CreateHuffmanTree(HuffmanTree& HT, int n);
void Select(HTNode* s, int n, int& s1, int& s2);
void OrderHuffmanTree(HuffmanTree& HT, int n);
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n);int main()
{HuffmanTree HT = NULL;HuffmanCode HC = NULL;int i = 0;char* p = NULL;CreateHuffmanTree(HT, 8);OrderHuffmanTree(HT, 8);CreatHuffmanCode(HT, HC,8);printf("\n\n各权重对应的编码为：");for (i = 1; i <= 8; i++){printf("\n%d：", HT[i].weight);for (p = HC[i]; *p != '\0'; p++){printf("%c ", *p);}}return 0;
}void CreateHuffmanTree(HuffmanTree& HT, int n)
{if (n <= 1){return;}int i = 0;int m = 2 * n - 1;int s1 = 0;int s2 = 0;HT = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1));//HT指向了一个一维数组的基地址，数组中的元素类型是HTNode,数组大小为m+1//等价于HTNode HT[m+1]//不说明数组大小时，为HTNode* HT，HuffmanTree HTfor (i = 1; i <= m; ++i){HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;}for (i = 1; i <= n; i++){printf("请输入第%d个叶子结点的权值：", i);scanf_s("%d", &HT[i].weight);}/*－－－－－－－－－－－初始化工作结束，下面开始创建哈夫曼树－－－－－－－－－－*/for (i = n + 1; i <= m; i++){//选择Select(HT, i - 1, s1, s2);//删除HT[s1].parent = i;HT[s2].parent = i;//合并HT[i].weight = HT[s1].weight + HT[s2].weight;HT[i].lchild = s1;HT[i].rchild = s2;}
}//在大小为n的一维整数型数组s中，找到最小的两个整数，并将其坐标存储在变量s1和s2中,下标从1开始
void Select(HTNode* s, int n, int& s1, int& s2)
{int m = 0;  //最小的值，下标为s1int p = 0;  //第二小的值，下标为s2int r = 1;int t = 1;//找到第一个双亲不为0的s[r]while (s[r].parent != 0){r++;}//找到第二个双亲不为0的s[t]t = r + 1;while (s[t].parent != 0){t++;}//比较s[r]和s[t]if (s[r].weight <= s[t].weight){m = s[r].weight;p = s[t].weight;s1 = r;s2 = t;}else{m = s[t].weight;p = s[r].weight;s1 = t;s2 = r;}for (int k = 3; k <= n; k++){if (s[k].parent == 0 && s[k].weight < m){p = m;s2 = s1;m = s[k].weight;s1 = k;}else if (s[k].parent == 0 && s[k].weight > m && s[k].weight < p){p = s[k].weight;s2 = k;}else{;}}//将下标小的作为新结点的左孩子，将下标大的作为新结点的右孩子int temp = 0;if (s1 > s2){temp = s1;s1 = s2;s2 = temp;}printf("\ns1 = %d, s2 = %d", s1, s2);
}//遍历哈夫曼树（即遍历其HT数组各个结点元素的信息）
void OrderHuffmanTree(HuffmanTree& HT, int n)
{int k = 0;if (HT){for (k = 1; k <= (2 * n - 1); k++){printf("\n\nHT[%d].weight = %d, HT[%d].parent = %d, HT[%d].lchild = %d, HT[%d].rchild = %d ", k, HT[k].weight, k, HT[k].parent, k, HT[k].lchild, k, HT[k].rchild);}}
}//算法5.11 根据哈夫曼树求哈夫曼编码
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{int i = 0;int start = 0;int c = 0;int f = 0;HC = (HuffmanCode)malloc(sizeof(char*) * (n + 1));char* cd = (char*)malloc(sizeof(char) * (n));cd[n - 1] = '\0';for (i = 1; i <= n; ++i){start = n - 1;c = i;  //结点cf = HT[i].parent;  //f为结点c的双亲while (f != 0)  //根结点与叶子结点及其它内部结点的区别{--start;if (HT[f].lchild == c){cd[start] = '0';}else  //HT[f].rchild == c{cd[start] = '1';}c = f;f = HT[f].parent;}HC[i] = (char*)malloc(sizeof(char) * (n - start));strcpy_s(HC[i], n - start, &cd[start]);
/* strcpy_s（*a，strlen(b)+1，*b）将指针b开始指向的内容（包括空终止符'\0'）复制到a指针		第一个参数：目标字符串指针 ；第二个参数：要复制的字符串长度，可使用strlen()函数直接求出。切记在使用strlen()求出字符串长度时，因为不包括终止符'\0'，因此需要+1；第三个参数：待复制的字符串指针。   */
//由复制的长度n - start，这里复制的编码不包括终止符'\0'，若要包括，长度再加一即可}free(cd);
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

哈夫曼译码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAXSIZE 100typedef struct
{int weight;int parent;int lchild;int rchild;
}HTNode, * HuffmanTree;typedef char** HuffmanCode;void CreateHuffmanTree(HuffmanTree& HT, int n);
void Select(HTNode* s, int n, int& s1, int& s2);
void OrderHuffmanTree(HuffmanTree HT, int n);
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n);
void Decode(HuffmanTree HT,int n, char* s);
int getline(char s[], int limit);int main()
{HuffmanTree HT = NULL;HuffmanCode HC = NULL;int i = 0;char* p = NULL;char s[MAXSIZE];int length = 0;int num = 1;char choice = '\0';CreateHuffmanTree(HT, 8);OrderHuffmanTree(HT, 8);CreateHuffmanCode(HT, HC, 8);printf("\n\n各权值对应的编码是：");for (i = 1;i <= 8; i++){printf("\n%d : ", HT[i].weight);for (p = HC[i]; *p != '\0'; p++){printf("%c", *p);}}getchar();  //此处有一个回车需要回收while (1){printf("\n请输入第%d个哈夫曼编码：", num);length = getline(s, MAXSIZE);printf("该编码对应的权值是：");Decode(HT, 8, s);printf("\n是否继续？（y/n）");scanf_s(" %c", &choice);getchar();num++;if (choice != 'y' && choice != 'Y'){break;}}return 0;
}void CreateHuffmanTree(HuffmanTree& HT, int n)
{if (n < 1){return;}int i = 0;int m = 2 * n - 1;int s1 = 0;int s2 = 0;HT = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1));for (i = 1; i <= m; i++){HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;}for (i = 1; i <= n; i++){printf("请输入第%d个权值：", i);scanf_s("%d", &HT[i].weight);}for (i = n+ 1; i <= m; i++){//选择Select(HT, i - 1, s1, s2);//删除HT[s1].parent = i;HT[s2].parent = i;//合并HT[i].weight = HT[s1].weight + HT[s2].weight;HT[i].lchild = s1;HT[i].rchild = s2;}
}void Select(HuffmanTree HT, int n, int& s1, int& s2)
{int m = 0; //最小值，下标是s1int p = 0; //第二小值，下标是s2int t = 1;int r = 1;int k = 1;while (HT[t].parent != 0){t++;}r = t + 1;while (HT[r].parent != 0){r++;}if (HT[t].weight <= HT[r].weight){m = HT[t].weight;s1 = t;p = HT[r].weight;s2 = r;}else{m = HT[r].weight;s1 = r;p = HT[t].weight;s2 = t;}for (k = r+1; k <= n; k++){if (HT[k].parent == 0 && HT[k].weight < m){p = m;s2 = s1;m = HT[k].weight;s1 = k;}else if(HT[k].parent == 0 && HT[k].weight > m && HT[k].weight < p){p = HT[k].weight;s2 = k;}else{;}}if (s1 > s2){int temp = s1;s1 = s2;s2 = temp;}}void OrderHuffmanTree(HuffmanTree HT,int n)
{if (HT){for (int i = 1; i <= 2*n-1; i++){printf("HT[%d].weight = %d, HT[%d].parent = %d, HT[%d].lchild = %d, HT[%d].rchild = %d\n",i,HT[i].weight,i,HT[i].parent,i,HT[i].lchild,i,HT[i].rchild);}}
}void CreateHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{int i = 0;int start = 0;int c = 0;int f = 0;HC = (HuffmanCode)malloc(sizeof(char*) * (n + 1));char* cd = (char*)malloc(sizeof(char) * n);cd[n - 1] = '\0';for (i = 1; i <= n; i++){start = n - 1;c = i;f = HT[i].parent;while (f != 0){--start;if (HT[f].lchild == c){cd[start] = '0';}if (HT[f].rchild == c){cd[start] = '1';}c = f;f = HT[c].parent;}HC[i] = (char*)malloc(sizeof(char) * (n - start));strcpy_s(HC[i], n - start, &cd[start]);}free(cd);
}//译码
void Decode(HuffmanTree HT, int n,char *s)
{int m = 2 * n - 1;char *p = s;int c = m; //从根节点开始往叶子结点走for (p = s; *p != '\0'; p++){//printf("\np = %c", *p);if (*p == '0'){c = HT[c].lchild;//printf("\nHT[c].weight = %d", HT[c].weight);}else if (*p == '1'){c = HT[c].rchild;//printf("\nHT[c].weight = %d", HT[c].weight);}else{;}}if (HT[c].lchild == 0 && HT[c].rchild == 0){printf("%d", HT[c].weight);}else{printf("输入的编码有误。\n");}
}int getline(char s[], int limit)
{int i = 0;int c = 0;for (i = 0; i < limit-1 && (c = getchar()) != EOF && c != '\n'; i++){s[i] = c;}s[i] = '\0';return i;
}

在这里插入图片描述
在这里插入图片描述

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 【AI学习】[2024北京智源大会]具身智能：具身智能关键技术研究：操纵、决策、导航
  • kafka 3.x 配置kerbos
  • 赋能未来园区：TSINGSEE视频AI智能管理平台如何引领园区管理智慧化转型
  • java selenium 设置代理，允许在其他环境中使用不同的IP访问
  • 分类预测 | Matlab实现PSO-XGBoost粒子群算法优化XGBoost的多特征分类预测
  • C# 方法的定义
  • JavaScript -- 总结 9 （小白）
  • k8s使用kustomize来部署应用
  • 排序算法1：堆排序，直接插入排序与希尔排序
  • System Verilog--$scanf应用举例
  • 学习日志8.7--防火墙安全策略
  • Hadoop单机及集群部署
  • html--前端
  • 前端构建工具|vite快速入门
  • DVWA（SQL注入）medium、high
  • (三)从jvm层面了解线程的启动和停止
  • 08.Android之View事件问题
  • Android交互
  • bootstrap创建登录注册页面
  • C++回声服务器_9-epoll边缘触发模式版本服务器
  • CentOS 7 防火墙操作
  • iOS仿今日头条、壁纸应用、筛选分类、三方微博、颜色填充等源码
  • leetcode-27. Remove Element
  • Mysql5.6主从复制
  • node学习系列之简单文件上传
  • Python 使用 Tornado 框架实现 WebHook 自动部署 Git 项目
  • python3 使用 asyncio 代替线程
  • vue从创建到完整的饿了么（18）购物车详细信息的展示与删除
  • 百度小程序遇到的问题
  • 规范化安全开发 KOA 手脚架
  • 互联网大裁员：Java程序员失工作，焉知不能进ali？
  • 记一次删除Git记录中的大文件的过程
  • 深度学习入门：10门免费线上课程推荐
  • 原生JS动态加载JS、CSS文件及代码脚本
  • 分布式关系型数据库服务 DRDS 支持显示的 Prepare 及逻辑库锁功能等多项能力 ...
  • 曾刷新两项世界纪录，腾讯优图人脸检测算法 DSFD 正式开源 ...
  • #HarmonyOS:软件安装window和mac预览Hello World
  • （2）空速传感器
  • (二) 初入MySQL 【数据库管理】
  • （亲测）设​置​m​y​e​c​l​i​p​s​e​打​开​默​认​工​作​空​间...
  • (文章复现)基于主从博弈的售电商多元零售套餐设计与多级市场购电策略
  • （详细文档！）javaswing图书管理系统+mysql数据库
  • （一）使用IDEA创建Maven项目和Maven使用入门（配图详解）
  • (转)Android学习系列(31)--App自动化之使用Ant编译项目多渠道打包
  • （转）JAVA中的堆栈
  • (转载)在C#用WM_COPYDATA消息来实现两个进程之间传递数据
  • .NET 3.0 Framework已经被添加到WindowUpdate
  • .Net 6.0--通用帮助类--FileHelper
  • .net wcf memory gates checking failed
  • .net 开发怎么实现前后端分离_前后端分离：分离式开发和一体式发布
  • /bin、/sbin、/usr/bin、/usr/sbin
  • @serverendpoint注解_SpringBoot 使用WebSocket打造在线聊天室（基于注解）
  • @Transient注解
  • [AX]AX2012开发新特性-禁止表或者表字段
  • [C/C++]_[初级]_[关于编译时出现有符号-无符号不匹配的警告-sizeof使用注意事项]