21 数据结构.doc

11第2章 计算机辅助系统开发基础知识第2章 计算机辅助系统开发基础知识2.1 数据结构对于软件开发来说，数据结构具有重要的意义，所谓程序可以看作是数据结构+算法。借助数据结构可以采用相对规范的方法将编程对象加以表述。例如，当我们需要在程序中记录一组等高线数据，并要求表达它们之间的相邻关系（这往往是为了在相邻登高线之间建立三角形数字地面模型），可能就需要借助于树型数据结构了：这时我们利用等高线包围的区域相互包含与否的关系，建立树结构。在图21中，等高线A包围的区域直接包含了等高线B、D所包围的区域，B包围的区域包A AC D BDBE E C（a）（b）图21 利用树来表示等高线之间的关系含了C所包围区域，D所包围区域包含了E所包围区域。为此建立如图21（b）所示的数据结构。这样，只要在父节点与子节点，以及同级子节点之间进一步判别等高线是否相邻，除此之外的情况是属于绝对不会相邻的。2.1.1栈图2-2栈结构示意栈就像在一个只打开一端的乒乓球筒中放入乒乓球一样（参见图22），先放入的球需要后取出，具有元素的先进后出特性，我们往往利用这一特性实现编程过程中的某些目的。例如，在机场场道设计CAD系统的平面布局设计工作中，由于工作带有试探性质，希望必要时能够放弃一些刚刚完成的操作，以退回原来的某种状态重新开始。这时我们可以将所进行的设计工作（例如增加了一条滑行道）按照完成的先后顺序逐步加入一个信息栈中，当需要退回原来的某一状态时，从栈的顶端逐步取出修改变化情况的信息，一步一步加以恢复。首先恢复的是最后进行的工作，直到达到希望退回的状态为止。当然这种情况下如果栈中已存满了元素，我们需要在栈的另一端打开取出一些元素加以放弃，以腾出一些栈空间，这是一种特殊的取出操作。清楚了栈的基本工作原理，还需要定义栈的基本数据操作，这样就便于我们确定栈的基本函数。在栈上定义的基本运算一般有：l 在内存空间建立一个栈；l 检查栈中剩余的容量；l 从栈的顶端推入一个元素；l 从栈的顶端取出一个元素；l 删除一个栈。除了这些基本运算之外，我们往往需要定义一些辅助运算，以帮助完成一些复杂的操作：l 查看栈中最上面一个元素的内容（并不从栈中取出）；l 从栈的底端删除一个元素。2.1.2队列图2-3队列结构示意队列的工作方式与栈不同，它像一个两端打开的乒乓球筒（参见图23），所有的乒乓球只能从指定的一端放入，而拿出乒乓球则必须在另一端进行，具有先进先出的特性。利用这种特性，我们可以建立一些特殊的数据模型来描述程序所要实现的解决某些问题的过程。例如，当我们采用仿真方法分析一系列交叉口所发生的交通状态时，需要采用分时处理技术分别逐个改变每一个交叉口的状态，同时系统整体环境也在发生着一些具有时间先后次序的情况。这时，我们可以采用如图24所示的结构建立计算机处理模型。在该模型中，具有两个层次的队列（我们可以把它们看作是一种信息管道），在上面的层次（称之为环境层次）上，系统环境队列描述存储环境情况的变化事件；在下面层次（称之为交叉口层次）中，每一个交叉口对应于一个信息队列，其中的元素代表外界的一个影响事件。环境层次与交叉口层次之间的控制机构判定某种环境变化事件将对哪些交叉口产生影响，从而将影响事件元素送入相应的交叉口信息管道之中。计算过程中，计算机将逐个扫描各交叉口并根据从相应信息队列中取出的情况进行必要的处理。系统环境信息管道 控制结构交叉口信息管道交叉口4交叉口3交叉口2交叉口1交叉口5图24 交叉口仿真系统控制机构为具体说明队列的实现方法，在此列举一个程序示例，这是采用C语言编写的程序，如果采用C+可以编写的更加合理，但我们的目的是说明具体算法，采用C语言程序将有助于更多的读者理解。在这一程序中，采用一个队列信息描述头部记录有关的信息，其中包括指向指向记录队列内容内存块起始位置的指针start，指示当前队列头部（出口）位置的参数head，指示当前队列尾部位置的参数tail，记录队列容量的参数size，记录队列每个元素占用内存大小的参数objsize，记录队列中已有元素个数的参数nob。队列中元素存储在建立队列时所申请的内存空间，在这一内存空间上，利用head、tail两个位置参数构成了一个环形内存空间（参见图25）。建议读者阅读一下程序清单中EnterQueue()和GetElementQueue()两个函数。物理存储终点物理存储起点队列头（出口）位置队列尾（入口）位置图25环形存储空间队列结构示意【清单21】通用型队列模块的Include文件/*-*QUEUE.H *-*/#defineQUEUE_NAME_LEN32typedef struct char *start;inthead;inttail;intsize;intnobj;intobjsize;charname QUEUE_NAME_LEN + 1 ; QUEUE;/*基本功能服务函数*/QUEUE * MakeQueue( int qsize, int objsize );/*建立队列并返回其指针，qsize为队列元素个数，objsize为单个元素占用的字节数*/intDelQueue( QUEUE *qp );/*删除整个队列，其中qp为需要删除的队列指针*/intEnterQueue( char * obj, QUEUE * qp ); /*在队列中加入一新元素，obj为元素指针，qp为队列指针*/intGetElementQueue( char * obj, QUEUE * qp );/*从队列中取出一个新元素*/intSpAvailQueue( QUEUE *qp );/*获取队列中剩余的元素容量*/*扩展功能服务函数*/intSpUsedQueue( QUEUE * qp );/*获取对列中已使用掉的元素容量*/char * ShowNextQueue( QUEUE * qp );/*显示队列中下一个预备出列元素的内容*/intEnterHeadQueue( char * obj, QUEUE * qp );/*从队列的出口端压入一个元素*/intDeleteTailQueue( char * obj, QUEUE * qp );/*从队列的入口删除一个元素*/【清单22】通用型队列模块的源程序/*-*QUEUE.C Yang Dongyuan 1990.11 *-*/#include #include #include queue.hQUEUE * MakeQueue( int qsize, int objsize )QUEUE * qp;if( !( qp = ( QUEUE * )malloc( sizeof( QUEUE ) + qsize * objsize ) )return( NULL );qp-start = ( char * )( qp + 1 );qp-size = qsize;qp-objsize = objsize;qp-head = 0;qp-tail = 0;qp-nobj = 0;return( qp );intDelQueue( QUEUE *qp )if( qp-nobj )return( 0 );free( qp );return( 1 );intEnterQueue( char * obj, QUEUE * qp )int i;char * bp;if( qp-nobj = qp-size )return( 0 );qp-nobj +;bp = qp-start + ( qp-objsize * qp-tail );for( i = qp-objsize; - i = 0; *bp+ = *obj + );if( + qp-tail = qp-size )qp-tail = 0;return( 1 );intDeleteTailQueue( char * obj, QUEUE * qp )inti;char* bp;if( qp-nobj nobj -;if( - qp-tail tail = qp-size - 1;bp = qp-start + ( qp-objsize * qp-tail );for( i = qp-objsize; - i = 0; *obj+ = *bp + );return( 1 );intEnterHeadQueue( char * obj, QUEUE * qp )short i;char * bp;if( qp-nobj = qp-size )return( 0 );qp-nobj +;if( - qp-head head = qp-size - 1;bp = qp-start + ( qp-objsize * qp-head );for( i = qp-objsize; - i = 0; *bp+ = *obj + );return( 1 );intGetElementQueue( char * obj, QUEUE * qp )short i;char *bp;if( qp-nobj nobj -;bp = qp-start + ( qp-objsize * qp-head );for( i = qp-objsize; -i = 0; *obj + = *bp + );if( + qp-head = qp-size )qp-head = 0;return( 1 );char * ShowNextQueue( QUEUE * qp )return( qp-start + ( qp-head * qp-objsize ) );intSpUsedQueue( QUEUE * qp )return ( qp-nobj );shortSpAvailQueue( QUEUE *qp )return( qp-size - qp-nobj );2.1.3链表链表提供了一种动态的数据结构，这种数据结构非常便于处理如下的问题：一组逻辑上成线性结构的元素组，在程序运行的过程需要不断进行元素的删除或插入工作。例如，道路路线CAD系统中横断面设计程序中遇到的一个问题是，如果考虑平面线形的修改，将会造成某一段路线横断面数量的增减变化，如采用连续方式存储横断面数据（例如采用数组），则每次变化都需要大量移动数据才能完成，这时我们需要一种在逻辑上是线性连续，但在物理上却允许是非线性的方法，以避免由于个别元素的增减造成大量数据移动的情况。最简单的链接表是单向链表，它的每一个元素都有一个指向其后面元素位置的指针，其结构如图26(a)所示。在这一结构中，如果需要删除一个元素，只要将它前面元素的指针修改，直接指向被删除元素后面的元素既可。而插入一个元素亦可通过插入位置前后元素的指针修改来实现。 数据 指针数据 指针数据 指针(a)单向链表结构示意数据 指针数据 指针数据 指针(b)单向链表删除元素数据 指针数据 指针数据 指针数据 指针(c)单向链表增添元素图26单向链表结构及操作示意图2.1.4 B树对于一维升序或降序数据序列（假设其个数为N）来说，可以采用两分检索的方法来迅速地找到需要插入或删除元素的位置。但是当采用顺序存储的方式时，为插入一个元素，需要将其以下的数据均进行后移；为删除一个元素，需要将以下的数据进行前移。为避免大量的数据移动，提高插入和删除的工作效率，研究者提出了多种解决方法，B树就是其中较好的一种方案。B树是由一系列节点（有的资料中称之为页）所构成，它的每一个节点均由2m个数据域和2m+1个指针域所构成，每个节点的数据从左向右成升序排列。一般情况下，B树的每个节点中的数据域不一定存放满数据，但基本上每个节点存放的数据数大于m个。图22显示了一棵m=2的B树结构。 0.25 0.40 0.72 A 0.27 0.31 0.12 0.15 0.20 0.22 0.75 0.80 0.95 0.51 0.60 EBDC图27 B树示例B树中父节点与子节点中的数据之间具有如下关系：父节点中每一数据域中存放的数据，均大于该数据域左侧指针指向的子节点中的所有数据，也小于该数据域右侧指针指向子节点中的所有数据。以图22所示的B树来看，节点A中的数据0.25，其左侧的指针指向节点B，B中的数据均小于0.25，其右侧的指针指向C，C中的数据也均大于0.25。为建立一棵B树，需要将一个一个的数据插入其中。在此，我们讨论有关在B树中插入数据的问题。当需要在上面所示的B树中插入一个数据，例如是0.65，首先需要查询其应插入的位置。首先将根节点的数据与带插入数据向比较，其结果发现应插入在0.40与0.72之间。而后，根据这两个数据之间的指针所值的位置，查到所指向的子节点D。比较之后确认应插入在数据0.60之后，当检查0.60右侧的指针后发现该指针为空，由此确认应插入在节点D中数据0.60之右侧，恰巧在这个位置是空的，因此插入数据0.65后即完成了所需的插入工作。这是存在的另一种可能性，是在0.60右侧有另外的数据，但节点D中还有空间允许填入新的数据，这是需要将0.60后面的数据进行右移，空出位置来插入0.65这一数据。当查询到插入位置，却发现该节点已填满数据时，我们需要进行节点的分割。仍以上述B树为例，设需要插入的数据是0.10。采用相同的方法，确认需要插入的位置在节点B的数据0.12的左侧，但由于节点B已填入了四个数据，必须建立新的节点存放数据。为此，我们将原节点中存放的数据和待插入的数据一起，找寻其中间数据，根据中间数据将这2m+1个数据分为两部分：小于中间数据的m个数据存入新的节点B1，大于中间数据的m个数据存入节点B2中，将中间数据存入节点B的父节点A中，同时对中间数据两侧的指针加以处理，使其指向节点B1和B2。当出现父节点同样数据存满的情况时，采用类似的方法将父节点进行相应的分割。对于上述插入结果，可以参见图23所示的情况。 0.15 0.25 0.40 0.72 A 0.10 0.12 B1 0.20 0.22 B2图28 在B树中插入新的数据示例不断插入新的数据，我们能够建立完整的B树。对于B树来说，其深度不会超过logmN，在查找的过程中最不利的情况下其数据比较运算的次数不会超过m logmN次。2.1.5 位图如果我们面临这样一个问题：需要建立一个集合，集合中可能的成员包括26各英文字母。这时采用位图描述集合是一个非常有效的方法：该位图中包括26个bit，每一个与一个字母相对应，检查某一字母是否在集合之中，只要查看对应该字母的位是0还是1即可。位图的逻辑结构非常简单，为线性连续空间，在此主要结合程序编制介绍其实现方法。在本书的后面，我们还可以看到将位图应用到大型二值矩阵中的做法（在第章等高线图绘制中）。位图模块程序是道路交通基本函数库中的一部分，其任务是为位图操作提供基本支持。实际上该函数库已是较老的版本，现在使用的是C+类库的版本，为了让读者易于理解采用技术难度小一些的方式介绍，目前我们的重点并不在程序结构而在于实现方法。【清单23】位图模块的Include文件/*-*BITMAP.H *-*/typedef charBITMAP;BITMAP *MakeBitmap( unsigned size );/根据给定的长度size建立一个位图。intSetBit( unsigned c, char * map, unsigned val );/设置第c个bit的数值。intTestBit( unsigned c, char * map );/获取第c个bit的数值。该程序是一个采用C语言编写的程序，三个对外服务函数的功能如上所述，具体程序结构如清单24所示。【清单24】位图模块源程序清单/*-*BITMAP.C *-*/#define DEBUG#include#include#includebitmap.hBITMAP *MakeBitmap( unsigned size )unsigned*map, numbyte;numbyte = ( size 3 ) + ( ( size * 0x07) ? 1 : 0 );if( map = ( unsi