【摘 要】
:
二叉树是计算机科学中最基本的也是最重要的树型数据结构。因此,二叉树枚举算法的研究无论在算法理论上还是在实际应用中都具有重要的意义。 树的枚举有两种含义,一种是计
论文部分内容阅读
二叉树是计算机科学中最基本的也是最重要的树型数据结构。因此,二叉树枚举算法的研究无论在算法理论上还是在实际应用中都具有重要的意义。 树的枚举有两种含义,一种是计数,即计算具有某种特性的树的总数目,Catalan数C_n是该领域著名的成果之一,它表示n个节点组成的二叉树的数目;另一种是生成,即一个一个地产生具有某种特性的所有树。 本文首先介绍了现有的四种基于编码的二叉树枚举生成算法。然后,以各个算法生成C_n个编码所需要的平均递归调用次数作为时间复杂度对比的尺度,对几个主要的编码生成算法进行了对比分析。 P序列编码生成算法是一种广义模式下的二叉树编码生成算法。本文对P序列编码的生成算法进行了研究。首先提出了一个枚举生成P序列编码的递归算法,实验数据表明:新算法通过减少递归调用的次数,使算法的效率比H.Ahrabian的算法提高了50%以上。基于上述对比结果,本文又提出了一个非递归算法,进一步提高了算法的效率,而且根据该非递归算法设计的二叉树枚举生成算法可以按照规范的局部顺序生成对应的二叉树。 堆是一种重要的二叉树,它被广泛应用于数据排序、最短路径、任务调度、最小生成树等与优先级队列相关的领域。所以,堆的枚举算法的研究对相关应用领域会有很大的帮助。 本文首先介绍了各种类型的堆结构及其发展,然后介绍了新近发现的最大值堆的一种性质,以及基于这一性质提出的一种最大值堆的生成算法。最后,对最大值堆的枚举计数进行了深入的研究。 首先,讨论了已有的两种堆的枚举计数算法,然后根据最大值堆的生成过程推导出了堆的枚举计数新公式。并且基于这一公式提出了一种新的最大值堆的枚举计数算法,该算法与同类算法相比具有以下优点: 1.其他的计数算法,“算法的时间复杂度不是n的多项式”;而新算法不需要递归就可以实现,算法的时间复杂度为O(n)。 2.新算法仅需要一个大小为n的一维数组,空间复杂度为O(n)。
其他文献
随着信息化的发展,人力资源管理已成为企业发展中举足轻重的原动力,人力资源管理已成为企业间竞争的主要支撑力。进行人力资源系统的开发,必然涉及到其中复杂的工作流程,保证用户数据的一致性与完整性。 本文主要讨论了分布式事务中,事务的常用概念以及事务流的处理。笔者在对事务的各方法和规范分析的基础上,对数据库端、数据存取层以及应用服务层各层次进行了针对事务处理的研究,并将其思想应用到实际开发的人力资源管理系
本文系统地分析了基于XML和Java技术的SOAP服务模型及其实现机制,针对目前Web服务实现的复杂性,提出了一种简单、轻快的基于Java的SOAP服务实现模型,这种模型能够实现快速部署We
视频会议系统最早是由贝尔实验室研制出来的。由于其主要是以模拟方式传送声音和图像,对信号的进一步处理非常困难。而且其性能、价格和会议成本都不具有良好的推广条件。在
设计模式是一种软件复用技术,是前人设计经验的总结,每一个具体模式都是经过验证行之有效的。J2EE 模式是 J2EE 平台与设计模式结合的产物,是模式在特定平台下的应用,它具有设计模式原有的优点,同时又比通用模式更加具体化。通过使用面向模式的分析与设计方法,并用 UML 类图来表示系统构造块,我们可以快速开发出一个可靠的大型软件系统。本文介绍了架构、框架、设计模式的概念以及它们之间的关系,利用面向模
由于布匹瑕疵的多样性和复杂性,使得当前已有的瑕疵检测系统效果不够理想。所以如何提高瑕疵检测和分类的准确性成为实时布匹瑕疵检测系统的关键所在。 在瑕疵的检测方面,
本文先介绍了防火墙、入侵检测、TCP/IP、网络数据报截获技术、Winsock编程、加密和认证以及网络攻击等一些相关知识;然后对系统总体设计以及核心模块作了详细的陈述;最后
本文主要研究3G的运营环境对网管系统的影响,在此基础上提出业务管理的功能,并且采用WBM技术设计并实现了数据呈现模块。 3G网管同样要遵循相应的国际规范。本文首先对目前
本文致力于对上下文相关中间件的研究,旨在为移动应用的开发提供一种支持上下文相关的软件架构。当前许多支持上下文相关的中间件系统都是把上下文相关的应用建立在移动终端可
实现医疗单位内部信息共享,进而为远程医学服务是医疗信息系统建设与应用的重要方面,而解决好医学影像信息数据量大与信息传输线路有限带宽的矛盾则是信息系统建设与应用成功
随着当代医疗的快速发展,人们对于无创诊疗的诉求越加迫切。呼吸诊疗作为中西医都提倡的一种诊疗方式,具有可靠性高、无创伤、无疼痛、操作简单的优点,具有较好的发展前景。但是