编写一个C语言函数createHTree,根据每个字符的出现次数(字符出现次数存放在全局数组Ccount中,Ccount[i]表示ASCII码值为i的字符出现次数),按照Huffman树生成规则,生成一棵Huffman树。1.依据数组Ccount中出现次数不为0的项,构造出树林F={T0,T1,...,Tm},初始时Ti(0<=i<=m)为只有一个根结构的树,且根结点(叶结点)的权值为相应字符的出现次数的二叉树(每棵树结点的类型为struct tnode,其成员c为字符,weight为树节点权值); 2.对树林F中每棵树按照其根节点的权值由小到大进行排序(若权值weight相同,字符c小的排在前面),得到一个有序树林F; 3.构造Huffman树。

时间: 2023-06-24 08:08:08 浏览: 55
以下是createHTree函数的实现: ```c #include <stdio.h> #include <stdlib.h> struct tnode { // 树节点类型 char c; int weight; struct tnode *left, *right; }; int Ccount[256]; // 记录每个字符出现的次数 // 比较函数,用于qsort排序 int cmp(const void *a, const void *b) { struct tnode *ta = *(struct tnode **)a; struct tnode *tb = *(struct tnode **)b; if (ta->weight != tb->weight) { return ta->weight - tb->weight; } else { return ta->c - tb->c; } } // 创建Huffman树 struct tnode *createHTree() { // 构造树林F struct tnode *F[256]; int i, m = 0; for (i = 0; i < 256; i++) { if (Ccount[i] != 0) { F[m] = (struct tnode *)malloc(sizeof(struct tnode)); F[m]->c = i; F[m]->weight = Ccount[i]; F[m]->left = F[m]->right = NULL; m++; } } // 对树林F中每棵树按照其根节点的权值进行排序 qsort(F, m, sizeof(struct tnode *), cmp); // 构造Huffman树 while (m > 1) { // 取出权值最小的两棵树合并 struct tnode *t1 = F[0], *t2 = F[1]; struct tnode *t = (struct tnode *)malloc(sizeof(struct tnode)); t->c = '\0'; t->weight = t1->weight + t2->weight; t->left = t1; t->right = t2; // 从树林F中删除这两棵树,将合并后的树插入树林F int j; for (j = 2; j < m; j++) { F[j - 2] = F[j]; } F[m - 2] = t; m--; // 对树林F中每棵树按照其根节点的权值进行排序 qsort(F, m, sizeof(struct tnode *), cmp); } return F[0]; } ``` 该函数首先根据全局数组`Ccount`中出现次数不为0的项,构造出树林F,然后对树林F中每棵树按照其根节点的权值进行排序。接着,循环取出权值最小的两棵树合并,将合并后的树插入树林F中,并且对树林F中每棵树按照其根节点的权值进行排序。当树林F中只剩下一棵树时,该树即为生成的Huffman树,函数返回该树的根节点指针。

相关推荐

最新推荐

recommend-type

Python优秀项目 基于Flask+MySQL实现的玩具电子商务网站源码+部署文档+数据资料.zip

CSDN IT狂飙上传的代码均可运行,功能ok的情况下才上传的,直接替换数据即可使用,小白也能轻松上手 【资源说明】 Python优秀项目 基于Flask+MySQL实现的玩具电子商务网站源码+部署文档+数据资料.zip 1、代码压缩包内容 代码的项目文件 部署文档文件 2、代码运行版本 python3.7或者3.7以上的版本;若运行有误,根据提示GPT修改;若不会,私信博主(问题描述要详细) 3、运行操作步骤 步骤一:将代码的项目目录使用IDEA打开(IDEA要配置好python环境) 步骤二:根据部署文档或运行提示安装项目所需的库 步骤三:IDEA点击运行,等待程序服务启动完成 4、python资讯 如需要其他python项目的定制服务,可后台私信博主(注明你的项目需求) 4.1 python或人工智能项目辅导 4.2 python或人工智能程序定制 4.3 python科研合作 Django、Flask、Pytorch、Scrapy、PyQt、爬虫、可视化、大数据、推荐系统、人工智能、大模型
recommend-type

人脸识别例子,利用python调用opencv库

人脸识别例子
recommend-type

densenet模型-基于深度学习对手势方向识别-不含数据集图片-含逐行注释和说明文档.zip

densenet模型_基于深度学习对手势方向识别-不含数据集图片-含逐行注释和说明文档 本代码是基于python pytorch环境安装的。 下载本代码后,有个环境安装的requirement.txt文本 如果有环境安装不会的,可自行网上搜索如何安装python和pytorch,这些环境安装都是有很多教程的,简单的 环境需要自行安装,推荐安装anaconda然后再里面推荐安装python3.7或3.8的版本,pytorch推荐安装1.7.1或1.8.1版本 首先是代码的整体介绍 总共是3个py文件,十分的简便 且代码里面的每一行都是含有中文注释的,小白也能看懂代码 然后是关于数据集的介绍。 本代码是不含数据集图片的,下载本代码后需要自行搜集图片放到对应的文件夹下即可 在数据集文件夹下是我们的各个类别,这个类别不是固定的,可自行创建文件夹增加分类数据集 需要我们往每个文件夹下搜集来图片放到对应文件夹下,每个对应的文件夹里面也有一张提示图,提示图片放的位置 然后我们需要将搜集来的图片,直接放到对应的文件夹下,就可以对代码进行训练了。 运行01生成txt.py,是将数据
recommend-type

数据仓库实例【41页】.ppt

数据仓库实例【41页】
recommend-type

自回归模型,线性回归预测

线性回归预测 在多元线性回归模型中,我们通过对多个预测变量(predictor)的线性组合预测了目标变量(variable of interest)。在自回归模型中,我们则是基于目标变量历史数据的组合对目标变量进行预测。自回归一词中的自字即表明其是对变量自身进行的回归。
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

深入了解MATLAB开根号的最新研究和应用:获取开根号领域的最新动态

![matlab开根号](https://www.mathworks.com/discovery/image-segmentation/_jcr_content/mainParsys3/discoverysubsection_1185333930/mainParsys3/image_copy.adapt.full.medium.jpg/1712813808277.jpg) # 1. MATLAB开根号的理论基础 开根号运算在数学和科学计算中无处不在。在MATLAB中,开根号可以通过多种函数实现,包括`sqrt()`和`nthroot()`。`sqrt()`函数用于计算正实数的平方根,而`nt
recommend-type

react的函数组件的使用

React 的函数组件是一种简单的组件类型,用于定义无状态或者只读组件。 它们通常接受一个 props 对象作为参数并返回一个 React 元素。 函数组件的优点是代码简洁、易于测试和重用,并且它们使 React 应用程序的性能更加出色。 您可以使用函数组件来呈现简单的 UI 组件,例如按钮、菜单、标签或其他部件。 您还可以将它们与 React 中的其他组件类型(如类组件或 Hooks)结合使用,以实现更复杂的 UI 交互和功能。
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。