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

摘要本文详细阐述了数据结构间的纵横联系，所谓“横向联系”是对各种数据结构研究都从逻辑结构、存储结构、操作运算三方面出发的模式思想，所谓“纵向联系”是以简单数据结构类型为基础来实现对较复杂数据结构类型的研究。

关键词逻辑结构存储结构操作运算横向联系纵向联系

1引言

数据结构作为计算机核心学科，其主要研究内容：逻辑结构，物理存储结构，操作（或算法）[1]。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

根据数据元素之间不同特性，把数据结构划分四种基本结构：（1）集合，（2）线型结构，（3）树型结构，（4）图状结构或网状结构。针对每种数据结构均从逻辑结构、存储结构和操作运算等方面进行研究，是贯穿数据结构研究始终的“红线”，也是数据结构研究的共同切入点，称之为数据结构的“横向联系”。从集合、线型结构等基本数据结构入手，以实现树形结构、图或网状结构等较复杂结构研究，实现数据元素间的关系从简单到复杂探讨，称之为“纵向联系”。

2逻辑结构、存储结构、操作运算的思想模式——数据结构间的横向联系

逻辑结构的定义、存储结构的实现、操作运算的实现是对数据结构研究的基本思想，一种数据结构的研究首先对这三方面内容有一个清晰的探讨。

集合数据结构与数学中集合概念是一致的，其逻辑结构元素间只是同属关系。存储结构实现只是在计算机内存储，它的操作就是一些交、差、并、补等。

线型结构是N个数据元素的有限序列，至于每一个数据元素的具体的含义在不同的情况下各不相同，其长度可根据需要增长或缩短，其逻辑结构就是它的数据元素间的线形关系，即一个对一个，一个元素最多有一个前驱，最多有一个后继。它的存储结构的实现一般有顺序存储和链式存储两种方法。顺序表是指用一组地址连续的存储单元依次存储线性结构中的数据元素，这是一种随机存取的存储结构；链式存储是数据元素之间的逻辑关系由结点中的指针来表示并且每一个结点有且只有一个指针域。线性结构的操作中，最基本的操作是在线性结构中插入、删除数据元素。存储结构为顺序存储有线性顺序表、数组、串等。存储结构为链式存储结构时有链表等。根据线性表的操作的不同便产生了两种重要的数据结构即栈和队列，这两种数据结构是线性结构的典型例子[2]。

树型结构是一种重要的非线性结构，其中的树和二叉树最为常用。直观看来，树是以分支关系定义的层次结构，其逻辑结构是一对多的关系，而在二叉树中是一个根结点对应左右两个孩子的层次关系。存储结构的实现当采取顺序存储时用一组地址连续的存储单元依上而下、自左向右存储树中的结点元素。在链式存储结构中可采用二叉链表表示法即链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟结点，树形结构的最基本的操作是遍历，其它复杂的操作大部分就是遍历操作的衍生与扩展。在树型结构中最有特色的一种数据结构就是二叉树，其独特的逻辑结构是每个结点至多有二棵子树并且还有左右之分，这就决定着它独特的链式存储结构，每个数据元素有且只有两个指针分别指向该结点的左右孩子。二叉树的最基本的操作是遍历二叉树，对每个结点的访问是对其它复杂操作的基础，例如统计结点个数、统计叶子结点数、交换二叉树的左右孩子等一些复杂的操作运算均是遍历二叉树操作的扩展和衍生。基于二叉树的递归定义可得到遍历二叉树递归算法，前序遍历、中序遍历、后序遍历二叉树。

图状结构是一种较线型结构和树更复杂的数据结构，图的逻辑结构是多对多的关系即在图形结构中结点之间的关系是任意的。因此在存储结构中无法以数据元素在存储区中的物理位置来表示数据元素间的关系。即图没有顺序映象但可以借助数组的数据类型表示元素之间的关系，用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系信息[3]。另一方面图的存储结构也可由多重链表实现，即一个由一个数据域和多个指针域组成的结点来表示图中的一个顶点，其中数据域存储该顶点的信息，指针域存储指向邻接点的指针，但由于图中各个结点的度各不相同，结点的指针域设定不易确定，则图的链式存储结构可用邻接多重表表示法，对图中每个顶点建立一个单链表，第一个单链表的结点表示依附于顶点V的边，每个结点由三个域组成其中邻接点域指示顶点V的邻接点在图中的位置，链域指示下一条边或弧的结点，数据域存储和边或弧相关的信息，如权值等。每个链表附有一个表头结点。在表头结点中除了设有链域指向链表中第一个结点外还设有存储顶点的名或其它有关信息的数据域，这样实现了图的链式存储。遍历是最基本的操作也是最重要的操作运算，它是求解图的连通性、拓扑排序和求关键路径的基础，然而图的遍历比树的遍历复杂的多，因为图的任一顶点都有可能和其余的顶点相邻接。所以在访问某个顶点之后可能沿着某条路径搜索之后又回到该顶点上。因此要设有一个辅助数组V[0..n-1]，它的初始值置为假，一旦访问顶点Vi，便置V[i]为真，这样避免了同一个顶点被访问多次，对图的遍历有深度优先搜索和广度优先搜索。图的深度优先搜索遍历类似树的先根遍历，是树的先根遍历的推广。广度优先搜索类似树的按层次遍历的过程。图状结构中复杂的操作大部分都是以图的遍历为基础。

因此无论对于线型结构、树性结构、网状或图，它们都遵循着逻辑结构的定义、存储结构的实现、操作运算方法的实现模式来实现每种数据结构的类型。在数据结构研究中对每种数据结构的研究只有对它的这三个方面内容的研究，才能对它进行探索、掌握、改进。这是数据结构研究中的基本思想。在数据结构研究中当前面向各专门领域特殊问题的多维数据结构和从抽象数据类型的观点来讨论数据结构，都不能背离这个思想。

3由栈和队列实现树、图的遍历——纵向联系

遍历操作对树、图结构是很基础、很重要的运算，它是实现一个数据结构的核心部分，虽然根据树、图的递归定义能设计出树、图的遍历的递归算法，但从线型结构到树、图的发展也是数据结构从简单到复杂的逐步发展过程。线型结构中栈和队列是两个非常重要的数据结构，对于树、图的遍历可用栈和队列来实现。对树、图复杂的数据结构，可通过栈和队列的操作来实现复杂数据结构的操作，体现了数据结构间的“纵向联系”。

用栈实现二叉树的前序遍历算法：

Statuspreorder(bitreet)

{P=t;

Initstack(s);

Push(s,p);

While(!stackempty(s)){

pop(s,p)

while(p){

visit(p);

push(s,prchild);

p=p-lchild;}

}}

用栈实现二叉树的中序遍历算法：

Statusinorder(bitreet)

{p=t;

Initstack(s);

Push(s,p);

P=Plchild;

while(!stackempty){

while(p){

push(s,p);

p=p-lchild;}

pop(s,p);

visist(p);

p=prchild;}}

用栈来实现二叉树的后序遍历算法：

Statuspostorder(bitreet){

P=t;

inistack(s);

While(p||!stackempty(s)){

If(p){

push(s,p);

P=plchild;}

ElseIf(!stackempty(s)){

pre=null;

Gettop(s,p);

While(prchild==pre){pop(s,p);

Visit(p);

Pre=p;

Gettop(s,p);}

P=prchild;}

}}}

用队列实现二叉树层次遍历算法：

VoidLayers(bitreet){

if(t){

p=t;

Initqueue(q);

Enqueue(q,t);

while(!empty(q)){

p=Dlqueue(q);

visit(p);

if(Plchild)Enqueue(q,plchild);

if(prchild)Enqueue(q,prchild);}

}

用队列实现图的广度优先搜索算法：

VoidBfs(Graphg,intv){

Visit(v);

Visited[v]=true;

Enqueue(q,v);

While(!emptyqueue(q)){

Dlqueue(g,vex);

For(w=firstadjvex(g,vex),w,w=nextadjvex(g,vex,w)){

If(!visited[w]){visit(w);

Visited[w]=true;

Enqueue(q,w);}}

}}

VoidDfs(Graphg,intv){

Visit(v);

Visited[v]=true;

Push(s,v);

While(!emptystack(s)){V=gettop(s);

For(w=fistadjvex(g,v);w&&!visited[w];w=nextadjvex(g,v,w))

If(!w)pop(s)

Else{visit(w);

Visited[w]=true;

Push(s,w);}}

因为二叉树、图的其它的操作大部分是对遍历基本操作的拓展或综合应用，灵活运用栈和队列可实现，并且算法描述比较直观。线性结构是数据结构学科的基础，树、图的发展在线性结构的基础上而发展，因树、图发展促进着线性结构中和一些算法的完善和改进，线型结构、树型结构、图状结构是紧密相联的。

4抽象数据类型的研究

数据结构间纵横联系明显且紧密。运用与把握这种“纵横联系”，对从抽象数据类型的角度来进行数据结构的学习与研究有着重要的借鉴意义。

抽象数据类型（ADT）的研究越来越被人所重视[4-8]，它可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算(过程或函数)。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。它仍遵循逻辑结构、存储结构、操作运算的数据结构基本思想，所有的抽象数据类型都可有简单的分类策略获得，这个策略就是抽象数据类型对象像什么和对它们做些什么。逻辑结构定义、存储结构表示、操作的实现在抽象类型中它们被称为数据类型说明、抽象数据类型的表示和抽象数据类型的实现[3]。抽象数据类型具体的表示和实现依赖所采用的语言,用户可以用某高级语言的固有数据类型和自定义类型并借助于过程和函数来表示和实现抽象数据类型。

5结论

逻辑结构、存储结构、操作运算等核心方面是贯穿数据结构研究与发展的一条基本线，也是数据结构研究中所看到数据结构间的“横向联系”。应用基本数据结来实现复杂数据结构的方法与途径，这是对数据元素之间关系从简单到复杂的探讨，即为“纵向联系”。数据结构联系是对数据结构的整体把握，体现在这种“横向联系”和“纵向联系”之中。灵活运用与把握这种数据结构间的关系，对抽象数据结构类型的研究有重要的借鉴意义，同时对数据结构的实际教学过程有着一定的指导意义。

参考文献

[1]陆松年.数据结构教程[M].北京：科学出版社.2002年

[2]严蔚敏.数据结构(C语言版)[M].北京：清华大学出版社.1997年

[3]帅训波.数据结构间普遍整体联系[D].曲阜：曲阜师范大学计算机科学学院.2003年

[4]蓝雯飞.数据结构的面向对象描述方法研究[J].计算机工程与应用，2006;42(26)：79-80

[5]刘毅.关于Treap数据结构问题的研究[J].计算机应用与软件,2005;22(8):36-38

[6]胡泽明,岳瑞生,王志刚.嵌入式GIS线要素无缝拼接的数据结及实现算法[J].测绘科学,2006;31(5):102-103

[7]戴坚锋,邵雷兵.一种新型的可扩展分布式数据结构[J].计算机应用研究,2005;22(8):170-171

[8]李先国,梁涌.一种高效的适用于字词检索的数据结构[J].微电子学与计算机,2006;23(12):157-160