数据结构间纵横联系探究论文

数据结构间纵横联系探究论文1引言数据结构作为计算机核心学科，其主要研究内容：逻辑结构，物理存储结构，操作（或算法）[1]。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。逻辑结构的定义、存储结构的实现、操作运算的实现是对数据结构研究的基本思想，一种数据结构的研究首先对这三方面内容有一个清晰的探讨。集合数据结构与数学中集合概念是一致的，其逻辑结构元素间只是同属关系。存储结构实现只是在计算机内存储，它的操作就是一些交、差、并、补等。线型结构是N个数据元素的有限序列，至于每一个数据元素的具体的含义在不同的情况下各不相同，其长度可根据需要增长或缩短，其逻辑结构就是它的数据元素间的线形关系，即一个对一个，一个元素最多有一个前驱，最多有一个后继。它的存储结构的实现一般有顺序存储和链式存储两种方法。顺序表是指用一组地址连续的存储单元依次存储线性结构中的数据元素，这是一种随机存取的存储结构；链式存储是数据元素之间的逻辑关系由结点中的指针来表示并且每一个结点有且只有一个指针域。线性结构的操作中，最基本的操作是在线性结构中插入、删除数据元素。存储结构为顺序存储有线性顺序表、数组、串等。存储结构为链式存储结构时有链表等。根据线性表的操作的不同便产生了两种重要的数据结构即栈和队列，这两种数据结构是线性结构的典型例子[2]。树型结构是一种重要的非线性结构，其中的树和二叉树最为常用。直观看来，树是以分支关系定义的层次结构，其逻辑结构是一对多的关系，而在二叉树中是一个根结点对应左右两个孩子的层次关系。存储结构的实现当采取顺序存储时用一组地址连续的存储单元依上而下、自左向右存储树中的结点元素。在链式存储结构中可采用二叉链表表示法即链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟结点，树形结构的最基本的操作是遍历，其它复杂的操作大部分就是遍历操作的衍生与扩展。在树型结构中最有特色的一种数据结构就是二叉树，其独特的逻辑结构是每个结点至多有二棵子树并且还有左右之分，这就决定着它独特的链式存储结构，每个数据元素有且只有两个指针分别指向该结点的左右孩子。二叉树的最基本的操作是遍历二叉树，对每个结点的访问是对其它复杂操作的基础，例如统计结点个数、统计叶子结点数、交换二叉树的左右孩子等一些复杂的操作运算均是遍历二叉树操作的扩展和衍生。基于二叉树的递归定义可得到遍历二叉树递归算法，前序遍历、中序遍历、后序遍历二叉树。图状结构是一种较线型结构和树更复杂的数据结构，图的逻辑结构是多对多的关系即在图形结构中结点之间的关系是任意的。因此在存储结构中无法以数据元素在存储区中的物理位置来表示数据元素间的关系。即图没有顺序映象但可以借助数组的数据类型表示元素之间的关系，用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系信息[3]。另一方面图的存储结构也可由多重链表实现，即一个由一个数据域和多个指针域组成的结点来表示图中的一个顶点，其中数据域存储该顶点的信息，指针域存储指向邻接点的指针，但由于图中各个结点的度各不相同，结点的指针域设定不易确定，则图的链式存储结构可用邻接多重表表示法，对图中每个顶点建立一个单链表，第一个单链表的结点表示依附于顶点V的边，每个结点由三个域组成其中邻接点域指示顶点V的邻接点在图中的位置，链域指示下一条边或弧的结点，数据域存储和边或弧相关的信息，如权值等。每个链表附有一个表头结点。在表头结点中除了设有链域指向链表中第一个结点外还设有存储顶点的名或其它有关信息的数据域，这样实现了图的链式存储。遍历是最基本的操作也是最重要的操作运算，它是求解图的连通性、拓扑排序和求关键路径的基础，然而图的遍历比树的遍历复杂的多，因为图的任一顶点都有可能和其余的顶点相邻接。所以在访问某个顶点之后可能沿着某条路径搜索之后又回到该顶点上。因此要设有一个辅助数组V[0..n-1]，它的初始值置为假，一旦访问顶点Vi，便置V[i]为真，这样避免了同一个顶点被访问多次，对图的遍历有深度优先搜索和广度优先搜索。图的深度优先搜索遍历类似树的先根遍历，是树的先根遍历的推广。广度优先搜索类似树的按层次遍历的过程。图状结构中复杂的操作大部分都是以图的遍历为基础。因此无论对于线型结构、树性结构、网状或图，它们都遵循着逻辑结构的定义、存储结构的实现、操作运算方法的实现模式来实现每种数据结构的类型。在数据结构研究中对每种数据结构的研究只有对它的这三个方面内容的研究，才能对它进行探索、掌握、改进。这是数据结构研究中的基本思想。在数据结构研究中当前面向各专门领域特殊问题的多维数据结构和从抽象数据类型的观点来讨论数据结构，都不能背离这个思想。用栈实现二叉树的前序遍历算法：Statupreorder(bitreet){P=t;Inittack();Puh(,p);].北京：科学出版社.2002年[2]严蔚敏.数据结构(C语言版)[M].北京：清华大学出版社.1997年[4]蓝雯飞.数据结构的面向对象描述方法研究[J].计算机工程与应用，2006;42(26)：79-80[5]刘毅.关于Treap数据结构问题的研究[J].计算机应用与软件,2005;22(8):36-38[6]胡泽明,岳瑞生,王志刚.嵌入式GIS线要素无缝拼接的数据结及实现算法[J].测绘科学,2006;31(5):102-10