数据结构间的纵横联系(一)

详细内容

摘 要 本文详细阐述了数据结构间的纵横联系，所谓“横向联系”是对各种数据结构研究都从逻辑结构、存储结构、操作运算三方面出发的模式思想，所谓“纵向联系”是以简单数据结构类型为基础来实现对较复杂数据结构类型的研究。 关键词 逻辑结构 存储结构 操作运算 横向联系 纵向联系
1 引言 数据结构作为计算机核心学科，其主要研究内容：逻辑结构，物理存储结构，操作（或算法）[1]。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。 根据数据元素之间不同特性，把数据结构划分四种基本结构：（1）集合，（2）线型结构，（3）树型结构，（4）图状结构或网状结构。针对每种数据结构均从逻辑结构、存储结构和操作运算等方面进行研究，是贯穿数据结构研究始终的 “红线”，也是数据结构研究的共同切入点，称之为数据结构的“横向联系”。从集合、线型结构等基本数据结构入手，以实现树形结构、图或网状结构等较复杂结构研究，实现数据元素间的关系从简单到复杂探讨，称之为“纵向联系”。2 逻辑结构、存储结构、操作运算的思想模式――数据结构间的横向联系 逻辑结构的定义、存储结构的实现、操作运算的实现是对数据结构研究的基本思想，一种数据结构的研究首先对这三方面内容有一个清晰的探讨。 集合数据结构与数学中集合概念是一致的，其逻辑结构元素间只是同属关系。存储结构实现只是在计算机内存储，它的操作就是一些交、差、并、补等。 线型结构是N个数据元素的有限序列，至于每一个数据元素的具体的含义在不同的情况下各不相同，其长度可根据需要增长或缩短，其逻辑结构就是它的数据元素间的线形关系，即一个对一个，一个元素最多有一个前驱，最多有一个后继。它的存储结构的实现一般有顺序存储和链式存储两种方法。顺序表是指用一组地址连续的存储单元依次存储线性结构中的数据元素，这是一种随机存取的存储结构；链式存储是数据元素之间的逻辑关系由结点中的指针来表示并且每一个结点有且只有一个指针域。线性结构的操作中，最基本的操作是在线性结构中插入、删除数据元素。存储结构为顺序存储有线性顺序表、数组、串等。存储结构为链式存储结构时有链表等。根据线性表的操作的不同便产生了两种重要的数据结构即栈和队列，这两种数据结构是线性结构的典型例子[2]。 树型结构是一种重要的非线性结构，其中的树和二叉树最为常用。直观看来，树是以分支关系定义的层次结构，其逻辑结构是一对多的关系，而在二叉树中是一个根结点对应左右两个孩子的层次关系。存储结构的实现当采取顺序存储时用一组地址连续的存储单元依上而下、自左向右存储树中的结点元素。在链式存储结构中可采用二叉链表表示法即链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟结点，树形结构的最基本的操作是遍历，其它复杂的操作大部分就是遍历操作的衍生与扩展。在树型结构中最有特色的一种数据结构就是二叉树，其独特的逻辑结构是每个结点至多有二棵子树并且还有左右之分，这就决定着它独特的链式存储结构，每个数据元素有且只有两个指针分别指向该结点的左右孩子。二叉树的最基本的操作是遍历二叉树，对每个结点的访问是对其它复杂操作的基础，例如统计结点个数、统计叶子结点数、交换二叉树的左右孩子等一些复杂的操作运算均是遍历二叉树操作的扩展和衍生。基于二叉树的递归定义可得到遍历二叉树递归算法，前序遍历、中序遍历、后序遍历二叉树。 图状结构是一种较线型结构和树更复杂的数据结构，图的逻辑结构是多对多的关系即在图形结构中结点之间的关系是任意的。因此在存储结构中无法以数据元素在存储区中的物理位置来表示数据元素间的关系。即图没有顺序映象但可以借助数组的数据类型表示元素之间的关系，用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系信息[3]。另一方面图的存储结构也可由多重链表实现，即一个由一个数据域和多个指针域组成的结点来表示图中的一个顶点，其中数据域存储该顶点的信息，指针域存储指向邻接点的指针，但由于图中各个结点的度各不相同，结点的指针域设定不易确定，则图的链式存储结构可用邻接多重表表示法，对图中每个顶点建立一个单链表，第一个单链表的结点表示依附于顶点V的边，每个结点由三个域组成其中邻接点域指示顶点V的邻接点在图中的位置，链域指示下一条边或弧的结点，数据域存储和边或弧相关的信息，如权值等。每个链表附有一个表头结点。在表头结点中除了设有链域指向链表中第一个结点外还设有存储顶点的名或其它有关信息的数据域，这样实现了图的链式存储。遍历是最基本的操作也是最重要的操作运算，它是求解图的连通性、拓扑排序和求关键路径的基础，然而图的遍历比树的遍历复杂的多，因为图的任一顶点都有可能和其余的顶点相邻接。所以在访问某个顶点之后可能沿着某条路径搜索之后又回到该顶点上。因此要设有一个辅助数组V[0..n-1]，它的初始值置为假，一旦访问顶点Vi，便置V[i]为真，这样避免了同一个顶点被访问多次，对图的遍历有深度优先搜索和广度优先搜索。图的深度优先搜索遍历类似树的先根遍历，是树的先根遍历的推广。广度优先搜索类似树的按层次遍历的过程。图状结构中复杂的操作大部分都是以图的遍历为基础。 因此无论对于线型结构、树性结构、网状或图，它们都遵循着逻辑结构的定义、存储结构的实现、操作运算方法的实现模式来实现每种数据结构的类型。在数据结构研究中对每种数据结构的研究只有对它的这三个方面内容的研究，才能对它进行探索、掌握、改进。这是数据结构研究中的基本思想。在数据结构研究中当前面向各专门领域特殊问题的多维数据结构和从抽象数据类型的观点来讨论数据结构，都不能背离这个思想。3 由栈和队列实现树、图的遍历――纵向联系 遍历操作对树、图结构是很基础、很重要的运算 ，它是实现一个数据结构的核心部分，虽然根据树、图的递归定义能设计出树、图的遍历的递归算法，但从线型结构到树、图的发展也是数据结构从简单到复杂的逐步发展过程。线型结构中栈和队列是两个非常重要的数据结构，对于树、图的遍历可用栈和队列来实现。对树、图复杂的数据结构，可通过栈和队列的操作来实现复杂数据结构的操作，体现了数据结构间的“纵向联系”。 用栈实现二叉树的前序遍历算法： Status preorder (bitree t ) { P=t; Initstack(s); Push(s,p); While(!stackempty (s)){ pop(s,p) while(p){ visit(p); push(s,p→rchild); p=p- →lchild; } } } 用栈实现二叉树的中序遍历算法： Status inorder (bitree t ) {p=t;Initstack(s);Push(s,p);P=P→lchild; while(!stackempty){