《智能家居产品 从设计到运营》——1.7 【本章小结】

第1章 利用树型数据关系的解题策略 树是一个具有层次结构的集合,一种限制前件数且没有回路的连通图.在现实生活和程序设计的竞赛试题中,许多问题的数据关系呈树型结构,因此有关树的概念.原理.操作方法和一些由树的数据结构支持的算法,一直受到编程者的重视,被广泛应用于解题过程.在本章里,我们将介绍利用树型数据关系解题的七种策略: 1) 利用划分树求解整数区间内第k大值. 2) 利用最小生成树及其扩展形式(最优比率生成树.最小k度生成树.次小生成树)计算有权连通无向图中边权和满足限制条件的最优生成树. 3

1.7 本章小结 树是一个具有层次结构的集合,一种没有回路的连通图,在程序设计竞赛中,许多试题的数据关系呈现树型结构.为了拓宽读者对树的认识.拓展树的应用范围.掌握更多利用树型结构解题的处理方法,我们在本章中介绍了以往竞赛曾涉及的一些前沿知识: 1) 探讨了如何利用划分树求解整数区间内第k大的值:即先离线构建出整个查询区间的划分树,然后在划分树中查找某子区间中第k大值.这个算法保证能在O(logn)的时间复杂度内快速求出问题解. 2) 通过分析一些蕴涵最小生成树性质的试题,给出了应用最小生成树原

前言 策略即计策和谋略,指一种总体的行为方针和行事方法,即一种可以实现目标的方案集合,而非纠缠于细枝末节的雕虫小技.程序设计的解题策略指的是编程解题过程中所采取的一种基本方法,是对解题方法的综合性.智能性和个性化的认识.尤其是当面对非标准.非模式化的问题时,就更需要发挥创造性思维,求索应对策略和解题艺术.正如古人所言"术谋之人以思谟为度,故能成策畧之奇,而不识遵法之良". 对于程序设计竞赛选手的培养,教师应注重在两个方面系统地训练选手:①程序设计竞赛的知识体系:②程序设计的解题策略.

本章小结 嵌入式 Linux C 语言应用程序设计(修订版)本 章 小 结 熟练使用开发工具是进行嵌入式Linux C语言开发的第一步.本章详细介绍了嵌入式Linux C语言开发常见的编辑器vi.编译器GCC.调试器GDB.工程管理器make和综合编辑器Emacs. 对于这些工具的使用方法,读者一定要通过实际动手操作来熟练掌握.本章在每个工具的讲解中都有一个完整的实例,希望读者能够完整操作这些实例. 动 手 练 练 1．在vi中编辑如下代码(命名为test.c),并自行编写Makefile运行该

本章小结 本 章 小 结 本章首先从现代计算机发展的角度介绍了嵌入式系统发展的历史,读者可以清楚地了解到嵌入式系统和通用计算机这两大分支的区别. 接下来,本章介绍了嵌入式系统的定义.特点,嵌入式系统的硬件架构和常见的嵌入式操作系统.在这里,读者要着重掌握嵌入式系统与通用计算机在各个方面的区别,掌握嵌入式系统的特征. 接下来,本章介绍了ARM处理器系列.ARM处理器的工作状态.存储格式.处理器模式以及S3C2410处理器的基本功能.ARM处理器是非常成功的一类微处理器,关于这部分的内容读者简单了解

1.2 利用最小生成树及其扩展形式解题 设G=(V,E,ω)是连通的有权无向图(节点集为V,边集为E,边权集为ω),连通图G中包含所有节点,且只有V-1条边的连通子图即为G的生成树.边权值和最小的生成树称为最小生成树.在现实生活中,最小生成树的原理和算法有着广泛的应用.程序设计竞赛中与最小生成树有关的试题一般有两类: 1) 构建最小生成树. 2) 应用最小生成树原理优化算法. 本节除了深入研讨最小生成树的性质和求解方法外,还给出了三种特殊类型生成树: 1) 最优比率生成树. 2) 最小k度限制生

1.4 利用改进型的二叉查找树优化动态集合的操作 我们知道,二叉查找树(binary search tree)能够支持多种动态集合操作,因此在程序设计竞赛中,二叉查找树起着非常重要的作用,它可以用来表示有序集合.建立索引或优先队列等.作用于二叉查找树上的基本操作时间是与树的高度成正比的:对于一棵含n个节点的二叉查找树,如果呈完全二叉树结构,则这些操作的最坏情况运行时间为O(log2n):但如果呈线性链结构,则这些操作的最坏情况运行时间退化为O(n).针对二叉查找树这种不平衡.不稳定的弊病,人们做

1.3 利用线段树解决区间计算问题 在现实生活中,我们经常遇到与区间有关的问题,例如,记录一个区间的最值(最大或最小值)和总量,并在区间的插入.删除.修改中维护这些最值和总量:再如,统计若干矩形并的面积.线段树拥有良好的树形二分特征,我们可以从其定义和结构中发现,在线段树的基础上完成这些问题的计算操作,是十分简捷和高效的.1.3.1 线段树的基本概念 一棵二叉树,记为T(a,b),参数a.b表示该节点表示区间［a,b］.区间的长度b-a记为L.递归定义T［a,b］: 若区间长度L>1:区间［a,

1.6 利用左偏树实现优先队列的合并 优先队列在程序设计竞赛中十分常见,在统计问题.最值问题.模拟问题和贪心问题等类型的题目中,优先队列都有着广泛的应用.二叉堆是一种常用的优先队列,它编程简单.效率高,但如果问题需要对两个优先队列进行合并,二叉堆的效率就无法令人满意了.为了解决这个问题,我们引入了左偏树.1.6.1 左偏树的定义和性质在介绍左偏树之前,我们先来回顾一下优先队列和可并堆的概念.优先队列(priority queue):一种抽象数据类型(ADT).它是一种容器,里面有一些元素,这些元

1.5 利用动态树维护森林的连通性 本节将介绍一种特殊的数据结构--动态树(dynamic tree).在正式介绍动态树之前,我们先来分析一个带有普遍性的问题.1.5.1 动态树的问题背景 给出一棵共有n(n≤10000)个节点的树,每条边都有一个权值,要求维护一个数据结构,支持如下操作: 操作1--修改某条边的权值. 操作2--询问某两个节点之间唯一通路上的最大边权. 其中操作的总次数为q. 对于操作2,我们很容易想到一种算法:先求出被询问的两节点的最近公共祖先,然后分别求出这两个节点至最近公