A constructive approach to the design of algorithms and their data structures
A constructive approach to the design of algorithms and their data structures
复制标题
算法及其数据结构设计的建设性方法
DOI：
10.1145/182.358444
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
Frank Wm. Tompa
中科院分区：
文献类型：
--
作者：
G. Gonnet;Frank Wm. Tompa
Gaston Gonnet 目前的研究兴趣是数据结构、算法分析和符号计算。 Frank Tompa 目前的研究重点是将数据结构设计原理应用于可视图文系统。加拿大委员会拨款 A3353 和 A9292。允许免费复制本材料的全部或部分内容，前提是这些副本不是为了直接商业利益而制作或分发、ACM 版权声明和出版物的标题及其日期，并注明复制已获得计算机器协会的许可。以其他方式复制或重新发布需要付费和/或特定许可。 1. 简介 最近对数据结构的大部分研究都针对（抽象）数据类型的与表示无关的描述 [6] 或独立实现的描述（例如，[13]）。不幸的是，还没有齐心协力来描述使用通用框架的实现。因此，除了少数情况（例如，[2,4,5]）之外，很难理解不同表示和算法之间的相似性，也很难深入了解适合特定处理要求的修改表示的设计。在本文中，我们提出了一个用于描述数据结构实现的框架。目标是能够指定（静态）表示结构本身以及用于操纵它们的算法。我们并不声称拥有通用的规范语言，更不用说拥有独特或最佳的表示方法。相反，我们希望提出一种规范框架，它可以：
Gaston Gonnet's current research interests are in data structures, analyses of algorithms and symbolic computation. Frank Tompa's current research focus is on applying the principles of data structure design to videotex systems. Council of Canada under grants A3353 and A9292. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 1. INTRODUCTION Much of the recent research into data structures has been directed at representation-independent descriptions of (abstract) data types [6] or at descriptions of isolated implementations (e.g., [13]). Unfortunately, there has not been a concerted effort to describe implementations using a common framework. As a result, except in a few instances (e.g., [2, 4, 5]), it has been difficult to appreciate the similarities among distinct representations and algorithms and to obtain insight into the design of modified representations that suit particular processing requirements. In this paper, we present a framework for describing data structure implementations. The goal is to be able to specify both the (static) representational structures themselves and the algorithms that are used to manipulate them. We do not claim to possess a universal specification language, much less a unique or optimal presentation method. Rather, we wish to present one specification framework that can: