排序算法与全排列生成算法研究

引入排序计算树和排列枚举树的概念,研究某些排序算法和全排列生成算法之间的关系,由插入排序算法直接导出了一个全排列生成算法,也由一个全排列生成算法导出了一个排序算法.     

变换存储结构的一种高效排序算法

给出变换存储结构的一种高效排序算法 ,该算法的时间复杂度为 O(n) ,且与待排序数据的分布无关 .给出了该排序算法的描述 ,并在时间复杂度和空间复杂度两方面与其他排序算法作了比较     

一种改进的基于区间树的等值线提取算法

从DEM中提取等值线是计算机制图和地理信息系统的基本功能之一。本文提出一种基于区间树索引的等值线提取算法。借鉴在平衡二又排序树中插入元素的算法来建立区间讨结点;在查找等值线经过的网格时,仅对搜索路径上区间树结点的网格队列排序,避免对区间树全部结点的网格队列排序。实验表明,此算法较以往算法在时间上具有优势。     

在二叉查找树上删除结点的算法与实现

本文首先介绍了在二叉查找树上删除结点的典型算法,然后将其与2004年上半年全国计算机软件考试软件设计师级下午试题五中所采用的算法作了分析与比较,并对考生答题中出现的问题进行了讨论.     

一种新的删除AVL树的结点的算法

所有传统的删除AVL树的结点的算法的主要思想都是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除AVL树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与目前通常采用的Foster的算法相比,新算法不涉及辅助栈的使用。设n是AVL树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的算法相同。实验结果表明新算法的平均执行时间比Foster的算法的短。新算法的空间复杂性是O(1),比Foster的算法的低。     

一种新的删除红黑树的结点的算法

提出一种新的删除红黑树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。证明新算法是正确的。设n是红黑树的内部结点的个数。执行新算法时进行O（1）次旋转。新算法的时间复杂性是O（log2n）。实验结果表明新算法的平均执行时间比Tarjan的算法和Guibas-Sedgewick算法的短。新算法的空间复杂性是O（1）。     

一种新的三叉哈夫曼树生成算法

文中在实现哈夫曼编码的二叉哈夫曼树以及已有的三叉哈夫曼树生成算法的基础上,提出了一种新的三叉哈夫曼树生成算法．通过比较带权路经长度证明了本算法的优越性。     

二叉排序树查找算法性能分析

查找是计算机中经常要用到的操作。二叉排序树排序树查找属于动态查找类,二叉排序树查找算法与建立算法密切相关。给出了一种计算二叉排序树平均查找长度的算法,希望能对查找算法的研究起到一点作用。     

基于有向弧的多边形拓扑关系生成算法

本文提出了一种基于结点弧段邻接关系自动生成多边形拓扑关系的算法,对每个结点的关联弧段按方位角排序并对这种排序进行了补充定义,对弧段的方向也作了相关规定。以此为基础,本算法避免了多边形内角的重复计算和反复搜索,提高了建立多边形拓扑关系的效率。最后,对该算法进行了分析和实例计算。     

LZW码的改进算法

分析了LZW码算法存在的不足,介绍了解决这种不足的具体办法。简单介绍了定长编码和哈夫曼编码,详细说明了将一般文件转换为文本文件的具体过程。用实例说明了LZW码的改进算法的具体实现过程,并通过对文件的压缩结果进行比较,说明了该算法的可行性。     

一种新的并行归并排序算法

文章提出了一种新的并行归并排序算法。算法充分利用并行系统中各个处理机中数据排序后序列长度相等的特点,计算出归并段对中的一个元素和最后一个元素的位置,然后再从相应的位置进行归并排序。该算法可使排序后的数据分布完全达到平衡,具有较高的负载平衡性、可扩展性和排序稳定性。文章最后给出了基于PC集群的实验结果,并把该结果与PSRS算法作了比较。     

基于凸包求解的简单多边形方向判断新算法

Graham ScanA求解简单多边形凸包算法简洁高效,但是对于未确定方向的简单多边形,该算法需设定一个方向求解其凸包。提出一种新的算法,该算法通过利用凸包求解的Graham ScanA算法来判断简单多边形的方向。算法取得了较好的实用效果。     

任意三维物体FDTD共形网格生成算法

时域有限差分法(FDTD)是计算电磁学广泛使用的方法之一.作为一种数值方法,首先要对目标模型进行网格离散.它直接影响到计算的精确性与复杂性.为了避免采用Yee氏单元对复杂模型建模所产生的阶梯误差,实现了一种任意复杂形状三维物体FDTD共形网格自动生成算法.对于由AutoCAD等建模软件生成的目标模型(三角形和四边形构成),应用计算机图形学方法求出网格线与模型的交点,在三个网格面分别生成共肜网格.数值结果证实了共形网格生成方法的正确性和在提高FDTD方法计算精度方面的有效性.     

虚拟场景的压缩算法与实时传输

提出了一种基于空间坐标的图形压缩、解压缩算法。它根据点或数值的空间坐标分布特点,充分考虑到虚拟场景在网络传输下对实时性的需求,把顺序传送的数值坐标通过类似于“时频变换”的转化后加以传输,实现客户端图形逐位细化的实时传输目的。     

Topology Abstraction of Surface Models for Three-Dimensional Grid Generation

Surface grid generation and the subsequent volume grid generation is the key to unstructured grid-based computational simulation. The baseline entities of the surface models under consideration for use with the proposed surface grid generator are curves and surfaces. There is a necessity to establish a topology relation between the curves and surfaces, prior to a surface gridding process. The present paper addresses issues related to this topology abstraction. Effort has also been made to generally discuss how to bridge the gap between CAD modelling and surface gridding. The proposed procedures have been incorporated into an Interactive Geometry Utility Environment (IGUE). The IGUE is a sub-environment of a Parallel Simulation User Environment (PSUE), which has been developed for unstructured grid-based computational simulation. Arbitrary computer application software can be integrated into the environment to provide a multi-disciplinary engineering analysis capability within one unified computational framework. Examples of computational applications have been included in the present paper, to demonstrate the use of the PSUE and geometry preparation procedure with an emphasis of topology abstraction.     

A New Paradigm for Geometric Processing

A new paradigm for geometric processing is proposed. The paradigm can be featured by the four key phrases: (1) Totally Four Dimensional Homogeneous Processing, (2) 4 × 4 Matrix Method and 4 × 4 Determinant Method, (3) Integer Arithmetic with Adaptive Data-Length Control Technique, (4) Systematic Paradigm Structures Based on the Duality.     

求结点可同名的森林所有子树的算法

讨论了求结点可同名的森林的所有子树的算法,并将其应用于化学领域:如何将许多具有某种共同属性的物质的分子结构图形分解成子分子结构,进一步地试图找出存在于大多数具有该属性的物质中的子分子结构,并讨论这样的子分子结构导致物质具有该共同属性的可能性。     

一种新的基于中心线的双线巷道自动生成算法

针对目前双线巷道自动生成算法存在的问题,提出了一种新的基于中心线的双线巷道自动生成算法。该算法实现原理:由巷道中心线分别向两侧偏移巷道宽度的1/2距离,生成不等宽的双线巷道,双线首尾相接再生成多边形区域;任取两条巷道,求一条巷道的多边形区域与另一条巷道的双线的交点,并判断相邻两交点之间的双线是否在多边形区域内,若在多边形区域内,且一条巷道在另一条巷道的上方或相互贯通,则裁剪掉这部分双线巷道;遍历所有巷道使两两之间都经过这种方法处理,最终生成相互贯通或交叉的双线巷道图。     

生成M序列的一种新的算法

该文基于反馈多项式产生序列的原理,提出了一种通过构造n级(n<32)M序列反馈多项式从而生成M序列的高效生成算法,并在此算法基础上提出一类新的序列(M-1序列)。由此算法产生的反馈多项式十分简单,易于用硬件实现。此算法方案可以作为设计序列密码的密钥发生器的基础,亦可以用于通信、编码等领域,具有一定的实用性。     

分“档”快速排序算法研究

文章在文献［１］的基础上,提出了一种由分“档”、整体置换和局部快速排序所组成的新排序算法——分“档”快速排序法。算法分析和实验结果都表明：在待排序数据均匀分布或正态分布的情况下,分“档”快速排序算法的时间复杂度可以达到Ｏ（ｎ）,而附加存储空间开销却仅仅为［（ｎ＋１）／２］,同时排序速度明显优于Ｑｕｉｃｋ Ｓｏｒｔ［２］、快速分组排序［５］、分“档”统计插入排序［１］和 Ｐｒｏｐｏｒｔｉｏｎ 　Ｓｐｌｉｔ Ｓｏｒｔ［４］等算法。