已知权值集合为{5,7,2,3,6,9},要求给出哈夫曼树,并计算带权路径长度WPL,写出c++算法

时间: 2023-08-19 16:17:07 浏览: 248
首先,哈夫曼树的构建需要用到最小堆,因此我们需要先实现最小堆。 ```c++ #include <iostream> #include <vector> using namespace std; template<class T> class MinHeap { private: vector<T> heap; void shift_up(int idx) { if (idx == 0) return; int parent = (idx - 1) / 2; if (heap[parent] > heap[idx]) { swap(heap[parent], heap[idx]); shift_up(parent); } } void shift_down(int idx) { int left = idx * 2 + 1; int right = idx * 2 + 2; int smallest = idx; if (left < heap.size() && heap[left] < heap[smallest]) { smallest = left; } if (right < heap.size() && heap[right] < heap[smallest]) { smallest = right; } if (smallest != idx) { swap(heap[idx], heap[smallest]); shift_down(smallest); } } public: void push(T val) { heap.push_back(val); shift_up(heap.size() - 1); } void pop() { if (heap.empty()) return; heap[0] = heap.back(); heap.pop_back(); shift_down(0); } T top() { return heap.front(); } bool empty() { return heap.empty(); } }; ``` 接下来,我们可以使用最小堆来构建哈夫曼树。对于给定的权值集合,我们可以将它们放入最小堆中,并不断地取出最小的两个权值进行合并,直到堆中只剩下一个节点为止。 ```c++ #include <iostream> #include <vector> using namespace std; template<class T> class TreeNode { public: T val; TreeNode<T> *left; TreeNode<T> *right; TreeNode(T val) : val(val), left(nullptr), right(nullptr) {} }; template<class T> TreeNode<T> *build_huffman_tree(vector<T> weights) { MinHeap<TreeNode<T> *> heap; for (auto weight : weights) { heap.push(new TreeNode<T>(weight)); } while (!heap.empty()) { TreeNode<T> *left = heap.top(); heap.pop(); if (heap.empty()) { return left; } TreeNode<T> *right = heap.top(); heap.pop(); TreeNode<T> *parent = new TreeNode<T>(left->val + right->val); parent->left = left; parent->right = right; heap.push(parent); } return nullptr; } ``` 最后,我们可以计算哈夫曼树的带权路径长度,即将每个叶子节点的权值乘以到根节点的距离,再将所有叶子节点的带权路径长度相加得到的值。可以使用递归来实现。 ```c++ template<class T> int calc_wpl(TreeNode<T> *root, int depth = 0) { if (!root->left && !root->right) { return root->val * depth; } return calc_wpl(root->left, depth + 1) + calc_wpl(root->right, depth + 1); } ``` 完整的c++代码如下:
阅读全文

相关推荐

doc
1. 对一个算法的评价,不包括如下( )方面的内容。 A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 2. 在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 对线性表,在下列哪种情况下应当采用链表表示?( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 采用开放定址法处理散列表的冲突时,其平均查找长度( )。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同 D.高于二分查找 6. 若需要利用形参直接访问实参时,应将形参变量说明为( )参数。 A.值 B.函数 C.指针 D.引用 7. 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的( )。 A.行号 B.列号 C.元素值 D.非零元素个数 8. 快速排序在最坏情况下的时间复杂度为( )。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 9. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 10. 栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 11. 用链接方式存储的队列,在进行插入运算时( ). A. 仅修改头指针   B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 12. 以下数据结构中哪一个是非线性结构?( ) A. 队列    B. 栈 C. 线性表    D. 二叉树 13. 树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 14. 二叉树的第k层的结点数最多为( ). A.2k-1 B.2K+1 C.2K-1    D. 2k+1 15. 若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为( ) A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3 16. 对n个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O(1)   B. O(n)   C. O(1og2n) D. O(n2) 17. 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K %9作为散列函数,则散列地址为1的元素有( )个, A.1 B.2 C.3 D.4 18. 设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 19.设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为( ) A.front=front+1 B.front=(front+1)%(m-1) C.front=(front-1)%m D.front=(front+1)%m 20.如下陈述中正确的是( ) A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中元素只能是字母 D.空串就是空白串 21.设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行( )趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8 22.设用链表作为栈的存储结构则退栈操作( )。 (A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈不作任何判别 23.下列四种排序中( )的空间复杂度最大。 (A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆 24.数据的最小单位是( )。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 25.设一组初始记录关键字序列为(50,40,95,20,15,70,60,45),则以增量d=4的一趟希尔排序结束后前4条记录关键字为( )。 (A) 40,50,20,95 (B) 15,40,60,20 (C) 15,20,40,45 (D) 45,40,15,20 26.设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为( )。 (A) 15,25,35,50,20,40,80,85,36,70 (B) 15,25,35,50,80,20,85,40,70,36 (C) 15,25,35,50,80,85,20,36,40,70 (D) 15,25,35,50,80,20,36,40,70,85 27. 设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路径长度之和为( )。 (A) 20 (B) 30 (C) 40 (D) 45 28.下面程序的时间复杂为( )。 for(i=1,s=0; i<=n; i++) { t=1; for(j=1;jnext=top; (D) top=top->next; 33. 字符串的长度是指( )。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C) 串中所含字符的个数 (D) 串中不同数字的个数 34. 队列是一种( )的线性表。 (A) 先进先出 (B) 先进后出 (C) 只能插入 (D) 只能删除 35.设散列表中有m个存储单元,散列函数H(key)= key % p,则p最好选择( )。 (A) 小于等于m的最大奇数 (B) 小于等于m的最大素数 (C) 小于等于m的最大偶数 (D) 小于等于m的最大合数 36.如下代码段输出的结果是( )。 String s1 = "abc"; String s2 = new String(s1); System.out.println(s1 == s2 + ","); System.out.println(s1.equals(s2)); A.true,true B.false,false C.true,false D.false ,true 37.二叉树有( )种不同的基本形态。 A.3 B.4 C.5 D.6 38.设一组初始记录关键字序列为(Q,H,C,Y,P,A,M,S,R,D,F,X),则按字母升序的第一趟冒泡排序结束后的结果是( )。 (A) F,H,C,D,P,A,M,Q,R,S,Y,X (B) P,A,C,S,Q,D,F,X,R,H,M,Y (C) A,D,C,R,F,Q,M,S,Y,P,H,X (D) H,C,Q,P,A,M,S,R,D,F,X,Y 39.设顺序循环队列Q[0:M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为(C )。 (A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M 40.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为( )。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 41.设某完全无向图中有n个顶点,则该完全无向图中有( )条边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 42.设某棵二叉树中有2000个结点,则该二叉树的最小高度为( )。 (A) 9 (B) 10 (C) 11 (D) 12 43.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为( A )。 (A) 10,15,14,18,20,36,40,21 (B) 10,15,14,18,20,40,36,21 (C) 10,15,14,20,18,40,36,2l (D) 15,10,14,18,20,36,40,21 44.设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8 45.设有n个关键字具有相同的Hash函数值,则用线性探测法把这n个关键字映射到Hash表中需要做( )次线性探测。 A.2 B.n(n+1) C.n(n+1)/2 D.n(n-1)/2 46.设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字90需要比较的关键字个数为( )。 A.1 B.2 C.3 D.4 47.设二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条件是( )。 A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子 48.设有n个待排序的记录关键字,则在堆排序中需要()个辅助记录单元。 (A) 1 (B) n (C) nlog2n (D) n2 49.下面关于线性表的叙述错误的是( )。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 50.将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为( )。 (A) 100 (B) 40 (C) 55 (D) 80 51数据结构是指数据及其相互之间的______________。当结点之间存在M对N(M:N)的联系时,称这种结构为_____________________。 52.一组初始记录关键字序列为(Q,H,C,Y,P,A,M,S,R,D,F,X),则按字母升序的第一趟冒泡排序结束后的结果是 。 53.队列的插入操作是在队列的___尾______进行,删除操作是在队列的____首______进行。54.根据搜索方法的不同,图的遍历有 和 两种。 55.堆栈的操作特点是 。 56. 若对一棵完全二叉树从0开始进行结点的编号,并按此编号把它顺序存储到一维数组A中,即编号为0的结点存储到A[0]中。其余类推,则A[ i ]元素的左孩子元素为________,右孩子元素为_______________,双亲元素为____________。 57. 快速排序算法的平均时间复杂度为____________,直接插入排序算法的平均时间复杂度为___________。 58.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为_________,在表尾插入元素的时间复杂度为____________。 59.一棵高度为5的二叉树中最少含有______个结点,最多含有_____个结点。 11.对于给定的若干个元素,可以构造出的逻辑结构有 结构, 结构和 结构三种。 60.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式(3+4X)-2Y/3对应的后缀算式为_______________________________。 61.设完全二叉树的顺序存储结构中存储数据ABCDE,要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。 62.设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。 63.设一组初始记录关键字序列为(19,21,16,5,18,23),要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。 64..线性表的存储结构有哪两种,各有何特点? 65.在顺序循环队列中,什么是假溢出?请指出解决假溢出的常见方法。 66.阅读下面的算法: LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L;L=L->next;p=L; S1: while(p->next) p=p->next; S2: p->next=q;q->next=NULL; } return L; } 语句S1和语句组S2的功能是什么? 67.已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示 (1)画出该图的图形; (2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历,写出相应的遍历序列。 68.已知关键字序列为{8,17,26,32,40,72,87,99},采用折半查找算法,给定值为70,35时分别与哪些元素比较?画出相应的二叉判定树 69. 设散列表的长度为8,散列函数H(k)=k mod 7,初始记录关键字序列为(25,31,8,27,13,68),要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 70.对于KMP算法,模式串中每个字符的最大真子串构成一个数组,定义为模式串的next[j]函数。next[j]函数定义如下: Max{k|0<k<j且“t0t1…tk-1”=“tj-ktj-k+1…tj-1”} 当此集合非空时 next[j]= 0 其他情况 -1 当j=0 计算t=“abcabaa”的next[j],要求写出具体的推算步骤。

最新推荐

recommend-type

江西师范大学科学技术学院在四川2020-2024各专业最低录取分数及位次表.pdf

那些年,与你同分同位次的同学都去了哪里?全国各大学在四川2020-2024年各专业最低录取分数及录取位次数据,高考志愿必备参考数据
recommend-type

麒麟win10双系统重新安装win10后麒麟启动菜单看不到解决方法

麒麟win10双系统重新安装win10后麒麟启动菜单看不到解决方法
recommend-type

多邻国Duolingo v6.0.3 高级版.apk

多邻国Duolingo v6.0.3 高级版.apk
recommend-type

QT网络编程: 实现TCP通讯设置(客户端)

QT网络编程: 实现TCP通讯设置(客户端)
recommend-type

前后端全部开源微信小程序商城(Java + uniapp) 快速搭建一个属于自己的微信小程序商城

减少重复造轮子,开源微信小程序商城(前后端开源:uniapp+Java)。快速搭建一个属于自己的微信小程序商城。
recommend-type

SSM动力电池数据管理系统源码及数据库详解

资源摘要信息:"SSM动力电池数据管理系统(源码+数据库)301559" 该动力电池数据管理系统是一个完整的项目,基于Java的SSM(Spring, SpringMVC, Mybatis)框架开发,集成了前端技术Vue.js,并使用Redis作为数据缓存,适用于电动汽车电池状态的在线监控和管理。 1. 系统架构设计: - **Spring框架**:作为整个系统的依赖注入容器,负责管理整个系统的对象生命周期和业务逻辑的组织。 - **SpringMVC框架**:处理前端发送的HTTP请求,并将请求分发到对应的处理器进行处理,同时也负责返回响应到前端。 - **Mybatis框架**:用于数据持久化操作,主要负责与数据库的交互,包括数据的CRUD(创建、读取、更新、删除)操作。 2. 数据库管理: - 系统中包含数据库设计,用于存储动力电池的数据,这些数据可以包括电池的电压、电流、温度、充放电状态等。 - 提供了动力电池数据格式的设置功能,可以灵活定义电池数据存储的格式,满足不同数据采集系统的要求。 3. 数据操作: - **数据批量导入**:为了高效处理大量电池数据,系统支持批量导入功能,可以将数据以文件形式上传至服务器,然后由系统自动解析并存储到数据库中。 - **数据查询**:实现了对动力电池数据的查询功能,可以根据不同的条件和时间段对电池数据进行检索,以图表和报表的形式展示。 - **数据报警**:系统能够根据预设的报警规则,对特定的电池数据异常状态进行监控,并及时发出报警信息。 4. 技术栈和工具: - **Java**:使用Java作为后端开发语言,具有良好的跨平台性和强大的生态支持。 - **Vue.js**:作为前端框架,用于构建用户界面,通过与后端进行数据交互,实现动态网页的渲染和用户交互逻辑。 - **Redis**:作为内存中的数据结构存储系统,可以作为数据库、缓存和消息中间件,用于减轻数据库压力和提高系统响应速度。 - **Idea**:指的可能是IntelliJ IDEA,作为Java开发的主要集成开发环境(IDE),提供了代码自动完成、重构、代码质量检查等功能。 5. 文件名称解释: - **CS741960_***:这是压缩包子文件的名称,根据命名规则,它可能是某个版本的代码快照或者备份,具体的时间戳表明了文件创建的日期和时间。 这个项目为动力电池的数据管理提供了一个高效、可靠和可视化的平台,能够帮助相关企业或个人更好地监控和管理电动汽车电池的状态,及时发现并处理潜在的问题,以保障电池的安全运行和延长其使用寿命。
recommend-type

管理建模和仿真的文件

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

MapReduce分区机制揭秘:作业效率提升的关键所在

![MapReduce分区机制揭秘:作业效率提升的关键所在](http://www.uml.org.cn/bigdata/images/20180511413.png) # 1. MapReduce分区机制概述 MapReduce是大数据处理领域的一个核心概念,而分区机制作为其关键组成部分,对于数据处理效率和质量起着决定性作用。在本章中,我们将深入探讨MapReduce分区机制的工作原理以及它在数据处理流程中的基础作用,为后续章节中对分区策略分类、负载均衡、以及分区故障排查等内容的讨论打下坚实的基础。 MapReduce的分区操作是将Map任务的输出结果根据一定规则分发给不同的Reduce
recommend-type

在电子商务平台上,如何通过CRM系统优化客户信息管理和行为分析?请结合DELL的CRM策略给出建议。

构建电商平台的CRM系统是一项复杂的任务,需要综合考虑客户信息管理、行为分析以及与客户的多渠道互动。DELL公司的CRM策略提供了一个绝佳的案例,通过它我们可以得到构建电商平台CRM系统的几点启示。 参考资源链接:[提升电商客户体验:DELL案例下的CRM策略](https://wenku.csdn.net/doc/55o3g08ifj?spm=1055.2569.3001.10343) 首先,CRM系统的核心在于以客户为中心,这意味着所有的功能和服务都应该围绕如何提升客户体验来设计。DELL通过其直接销售模式和个性化服务成功地与客户建立起了长期的稳定关系,这提示我们在设计CRM系统时要重
recommend-type

R语言桑基图绘制与SCI图输入文件代码分析

资源摘要信息:"桑基图_R语言绘制SCI图的输入文件及代码" 知识点: 1.桑基图概念及其应用 桑基图(Sankey Diagram)是一种特定类型的流程图,以直观的方式展示流经系统的能量、物料或成本等的数量。其特点是通过流量的宽度来表示数量大小,非常适合用于展示在不同步骤或阶段中数据量的变化。桑基图常用于能源转换、工业生产过程分析、金融资金流向、交通物流等领域。 2.R语言简介 R语言是一种用于统计分析、图形表示和报告的语言和环境。它特别适合于数据挖掘和数据分析,具有丰富的统计函数库和图形包,可以用于创建高质量的图表和复杂的数据模型。R语言在学术界和工业界都得到了广泛的应用,尤其是在生物信息学、金融分析、医学统计等领域。 3.绘制桑基图在R语言中的实现 在R语言中,可以利用一些特定的包(package)来绘制桑基图。比较流行的包有“ggplot2”结合“ggalluvial”,以及“plotly”。这些包提供了创建桑基图的函数和接口,用户可以通过编程的方式绘制出美观实用的桑基图。 4.输入文件在绘制桑基图中的作用 在使用R语言绘制桑基图时,通常需要准备输入文件。输入文件主要包含了桑基图所需的数据,如流量的起点、终点以及流量的大小等信息。这些数据必须以一定的结构组织起来,例如表格形式。R语言可以读取包括CSV、Excel、数据库等不同格式的数据文件,然后将这些数据加载到R环境中,为桑基图的绘制提供数据支持。 5.压缩文件的处理及文件名称解析 在本资源中,给定的压缩文件名称为"27桑基图",暗示了该压缩包中包含了与桑基图相关的R语言输入文件及代码。此压缩文件可能包含了以下几个关键部分: a. 示例数据文件:可能是一个或多个CSV或Excel文件,包含了桑基图需要展示的数据。 b. R脚本文件:包含了一系列用R语言编写的代码,用于读取输入文件中的数据,并使用特定的包和函数绘制桑基图。 c. 说明文档:可能是一个Markdown或PDF文件,描述了如何使用这些输入文件和代码,以及如何操作R语言来生成桑基图。 6.如何在R语言中使用桑基图包 在R环境中,用户需要先安装和加载相应的包,然后编写脚本来定义桑基图的数据结构和视觉样式。脚本中会包括数据的读取、处理,以及使用包中的绘图函数来生成桑基图。通常涉及到的操作有:设定数据框(data frame)、映射变量、调整颜色和宽度参数等。 7.利用R语言绘制桑基图的实例 假设有一个数据文件记录了从不同能源转换到不同产品的能量流动,用户可以使用R语言的绘图包来展示这一流动过程。首先,将数据读入R,然后使用特定函数将数据映射到桑基图中,通过调整参数来优化图表的美观度和可读性,最终生成展示能源流动情况的桑基图。 总结:在本资源中,我们获得了关于如何在R语言中绘制桑基图的知识,包括了桑基图的概念、R语言的基础、如何准备和处理输入文件,以及通过R脚本绘制桑基图的方法。这些内容对于数据分析师和数据科学家来说是非常有价值的技能,尤其在需要可视化复杂数据流动和转换过程的场合。