Allocating Storage for Extendible Arrays
Allocating Storage for Extendible Arrays
复制标题
为可扩展阵列分配存储
DOI：
10.1145/321850.321861
复制
发表时间：
1974
期刊：
影响因子：
--
通讯作者：
A. Rosenberg
中科院分区：
文献类型：
--
作者：
A. Rosenberg
数组是最好理解和最广泛使用的数据结构之一。然而，即使是现在，也没有令人满意的技术来处理涉及可扩展阵列的算法（其中，例如，可以动态地附加行和/或列）。在本文中，可扩展阵列的存储分配的问题进行审查，在作者的早期工作的数据图和寻址方案。一个正式的模拟断言，数组扩展的简单性排除简单的遍历（沿沿着行/列）证明。两种策略，用于构建阵列的可扩展实现制定，并建立这种实现的某些固有的局限性。
Arrays are among the best understood and most widely used data structures. Yet even now, there are no satisfactory techniques for handling algorithms involving extendible arrays (where, e.g., rows and/or columns can be appended dynamically). In this paper, the problem of allocating storage for extendible arrays is examined in the light of the author's earlier work on data graphs and addressing schemes. A formal analog of the assertion that simplicity of array extension precludes simplicity of traversal (marching along rows/columns) is proved. Two strategies for constructing extendible realizations of arrays are formulated, and certain inherent limitations of such realizations are established.