程序调试中的树形结构演变可视化模型

树形结构作为一种非线性数据结构,在程序执行过程中的演变过程较为抽象,尤其是在对其进行加工型操作时,容易发生内存泄漏。针对编程初学者难以掌握树形结构的逻辑演变过程,以及在程序中发生内存泄漏错误时调试较为困难的问题,文中提出了一种对程序调试过程中树形结构的演变过程进行可视化呈现的处理模型TEVM(Tree Evaluation Visualization Model)。针对单个可视化程序在调试步骤前和调试步骤后的两个树形结构,设计了一种将树形结构转换为线性表示的结构对比算法,得出了它们的包括泄漏树在内的结构差异;同时设计了一种树形结构布局方法,并计算它们的布局差异。根据结构差异和布局差异生成可视化演变序列,调用绘图引擎对该序列进行解析和执行,从而完成对树形结构及其演变过程的动态、平滑和直观的可视化呈现,帮助编程初学者快速理解树形结构相关程序的执行过程,提升调试效率。将TEVM模型集成于一个面向编程实训教学的集成开发环境原型Web AnyviewC中,取得了较好的应用效果。     

图式程序内部表示的设计与实现

文中通过分析图式语言及其图式程序的特征和它们内部表示的特殊要求，提出了一种特殊的树结构来体现和管理图式程序的层次结构，采用结构树与正文相结合的方法来解决图式程序内部表示由于频繁的插入，移动，定位等操作所为的一系列问题，同时给出这种方法具体的方法和实现。     

Realization of a Binary Clocked Linear Tree and Its Use for Processing Texts in Natural Languages

An implementation and the functioning of a synchronized binary linear tree are described. A structure of the so-called time line is proposed; the structure is used at the discourse level to process semantic connections between elements of various sentences. The structure of a system that processes texts in natural languages is considered. It is assumed that a semiotic feedback can lead to an internal monologue and self-consciousness. Based on the synchronized linear tree, a realization of semiotic feedback is described. It is shown that a model of the above-mentioned internal monologue can be used to synthesize phrases in natural languages.     

面向媒体处理器可重定目标编译器的代码生成

在可重定目标编译器的设计与实现中,RTL中间表示具有内部的树结构表示形式和外部的正文表示形式的特性,使RTL适合作为可重定目标编译器中的中间表示。利用RTL的这种双重特性,提出适用于可重定目标编译器的代码生成技术,通过树模式匹配的方法建立中间表示与机器描述中指令模板的映射关系,实现汇编代码的输出。通过MD32Builder集成环境的构建,证明该技术简单易行。     

基于图割和显著性的图像结构表示方法研究*

通过分析现有基于内容的图像结构表示方法,存在鲁棒性不强和结构多样性易增加分类的复杂性并降低分类正确率的问题,研究了基于图割的二叉树和基于显著性的多叉树图像结构表示方法,并与基于区域相似性的二叉树和改进深度的多叉树表示进行比较。实验表明,基于图割和显著性的表示方法能有效提高结构树的语义性和分类性能。     

Structure-Preserving Hierarchical Decompositions

A hierarchy tree of a graph G is a rooted tree whose leaves are the vertices of G; the internal nodes are usually called clusters. Hierarchy trees are well suited for representing hierarchical decompositions of graphs. In this paper we introduce the notion of P-validity of hierarchy trees with respect to a given graph property P. This notion reflects the similarity between any high-level representation of G obtained from the hierarchy tree and the topological structure of G. Maintaining the properties of a graph at any level of abstraction is especially relevant in graph drawing applications. We present a structural characterization of P-valid hierarchy trees when the clustered graph is a tree and property P is the acyclicity. Besides being interesting in its own right, our structure theorem can be used in the design of a polynomial time algorithm for recognizing P-valid hierarchy trees.     

组密钥管理中的d叉树数据结构设计

d叉树数据结构与算法在互联网多播安全的层次化组密钥管理的实现中是极其重要的。我们设计了适用于层次化组密钥管理的d叉树数据结构表示与算法，并给出了相应的存储结构中随机定位所需要的数学性质。     

基于面向对象XML数据的索引机制

XML正在迅速成为Internet上信息表示和数据交换的重要标准.而面向对象的特征具有很强的建模能力,将面向对象的概念引入到XML可以提高XML模式语言的建模能力.而现有的索引模式都不支持面向对象XML数据的查询,由此提出了一种基于面向对象XML数据的OOCtree（Object-Oriented compact tree）索引模式,它是一棵包含组级和元素级的两级双向树.组级提供简洁的结构概要和继承信息,可以在查询早期阶段裁剪大量的搜索空间;元素级提供详细的孩子父亲连接关系,可以快速地访问某元素的父亲,极大地提高了查询处理效率.     

The polaris internal representation

The Polaris Program Manipulation System is a production quality tool for source-to-source transformations and complex analysis of Fortran code. In this paper, we describe the motivations for and the implementation of Polaris' internal representation (IR). The IR is composed of a basic abstract syntax tree on top of which exist many layers of functionality. This functionality allows complex operations on the data structure. Further, the IR is designed to enforce the consistency of the internal structure in terms of both the correctness of the data structures and the correctness of the Fortran code being manipulated. In addition, operations on the IR result in the automatic updating of affected data structures such as flow information. We describe low the system's philosophies developed from its predecessor, the Delta prototyping system, and how they were implemented in Polaris' IR. We also provide a number of examples of using the Polaris system. The research described was supported by Army contract DABT63-92-C-0033. This work is not necessarily representative of the positions or policies of the Army or the Government.     

国标BASIC语言实现中的集成化编程支持环境

本文介绍了在国家“七五”科技攻关项目“国标BASIC语言的实现”中所设计实现的一个集成化编程支持环境。它以语法树作为环境内部的唯一存贮形式,使环境中各部分共享这一统一的内部表示。本文介绍了该环境的结构、功能特点及实现,着重介绍了语法制导的编辑器以及程序的正文表示形式和语法树表示形式之间的相互转换,同时阐述了该环境对自顶向下逐步求精的程序设计方法学的支持。     

一种新的高级综合的设计表示模型

高级综合技术的研究在当前倍受关注。高级综合的第一步是将以算法形式给出的数字系统的行为描述转化为综合设计的内部表示，而后其它子任务在此基础上进行。本文提出了一种新的基于Ｐｅｔｒｉ网的高级综合的设计表示模型，它不但表表示出给定的设计的最大并行性，而且能够表示出高级综合过程中的不同阶段的设计，从而在高级综合的各个阶段都可采用这同一个模型。该模型可自动生成且容易理解，特别适合于表示并行（或并发）度大的设计     

Classification of melanoma using tree structured wavelet transforms

This paper presents a wavelet transform based tree structure model developed and evaluated for the classification of skin lesion images into melanoma and dysplastic nevus. The tree structure model utilizes a semantic representation of the spatial-frequency information contained in the skin lesion images including textural information. Results show that the presented method is effective in discriminating melanoma from dysplastic nevus. The results are also compared with those obtained using another method of developing tree structures utilizing the maximum channel energy criteria with a fixed energy ratio threshold.     

Efficiently building a parse tree from a regular expression

We show in this paper that parsing with regular expressions instead of context-free grammars, when it is possible, is desirable. We present efficient algorithms for performing different tasks that concern parsing: producing the external representation and the internal representation of parse trees; producing all possible parse trees or a single one. Each of our algorithms to produce a parse tree from an input string has an optimal time complexity, linear with the length of the string. Moreover, ambiguous regular expressions can be used. Received: 21 October 1997 / 30 May 2000     

A Markov chain model for dynamic binary search tree behaviour

We present a Markov chain model for the analysis of the behaviour of binary search trees (BSTs) under the dynamic conditions of insertions and deletions. The model is based on a data structure called a lineage tree, which provides a compact representation of different BST structures while still retaining enough information to model the effect of insertions and deletions and to compute average path length and tree height. Different lineages in the lineage tree correspond to states in the Markov chain. Transition probabilities are based on the number of BST structures corresponding to each lineage. The model is based on a similar lineage tree model developed for B-trees. The BST model is not intended for practical computations, but rather as a demonstration of the generalizability of the lineage tree approach for modeling data structures such as B-trees, B*-trees, B⁺-trees, BSTs, etc.     

基于Lobe表示的树木快速3D建模

提出了一种基于Lobe表示的树木三维建模方法,该方法的核心思想在于树冠形状取决于外形轮廓,而其内部的枝叶结构具有相似性,可以从有限的模板库通过纹理合成的方法近似生成.该方法可以描述成两大部分:1)编码.将给定树木表示成骨架和Lobe的形式;2)解码.根据Lobe形状,基于已有的枝叶模板生成Lobe内部三维结构.这种基于Lobe的轻量级树木表示方法在很大程度上提高了大规模树木三维模型存储和传输的效率,非常适用于网络环境下大规模城市场景的交互式应用.     

State-space approach to nonlinear predictive generalised minimum variance control

A nonlinear predictive generalised minimum variance control algorithm is introduced for the control of nonlinear discrete-time multivariable systems. The plant model is represented by the combination of a very general nonlinear operator and also a linear subsystem which can be open-loop unstable and is represented in state-space model form. The multi-step predictive control cost index to be minimised involves both weighted error and control signal costing terms. The solution for the control law is derived in the time domain using a general operator representation of the process. The controller includes an internal model of the nonlinear process, but because of the assumed structure of the system, the state observer is only required to be linear. In the asymptotic case, where the plant is linear, the controller reduces to a state-space version of the well-known GPC controller.     

旅行商问题中巡回路径的数据结构

旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序,并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序,但是最坏情况下完成逆序操作需要Ω（n）时间,不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O（logn）,适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O（n^0.5）,适用于大规模的旅行商问题。     

Efficient memory representation of XML document trees

Implementations that load XML documents and give access to them via, e.g., the DOM, suffer from huge memory demands: the space needed to load an XML document is usually many times larger than the size of the document. A considerable amount of memory is needed to store the tree structure of the XML document. In this paper, a technique is presented that allows to represent the tree structure of an XML document in an efficient way. The representation exploits the high regularity in XML documents by compressing their tree structure; the latter means to detect and remove repetitions of tree patterns. Formally, context-free tree grammars that generate only a single tree are used for tree compression. The functionality of basic tree operations, like traversal along edges, is preserved under this compressed representation. This allows to directly execute queries (and in particular, bulk operations) without prior decompression. The complexity of certain computational problems like validation against XML types or testing equality is investigated for compressed input trees.