《第2章计算机辅助系统开发基础知识.doc》由会员分享，可在线阅读，更多相关《第2章计算机辅助系统开发基础知识.doc（11页珍藏版）》请在金锄头文库上搜索。
1、DBFQ第2章 计算机辅助系统开发基础知识2.1 数据结构对于软件开发来说，数据结构具有重要的意义，所谓程序可以看作是数据结构+算法。借助数据结构可以采用相对规范的方法将编程对象加以表述。例如，当我们需要在程序中记录一组等高线数据，并要求表达它们之间的相邻关系（这往往是为了在相邻登高线之间建立三角形数字地面模型），可能就需要借助于树型数据结构了：这时我们利用等高线包围的区域相互包含与否的关系，建立树结构。在图21中，等高线A包围的区域直接包含了等高线B、D所包围的区域，B包围的区域包A AC D BDBE E C（a）（b）图21 利用树来表示等高线之间的关系含了C所包围区域，D所包围区域包含
2、了E所包围区域。为此建立如图21（b）所示的数据结构。这样，只要在父节点与子节点，以及同级子节点之间进一步判别等高线是否相邻，除此之外的情况是属于绝对不会相邻的。2.1.1栈图2-2栈结构示意栈就像在一个只打开一端的乒乓球筒中放入乒乓球一样（参见图22），先放入的球需要后取出，具有元素的先进后出特性，我们往往利用这一特性实现编程过程中的某些目的。例如，在机场场道设计CAD系统的平面布局设计工作中，由于工作带有试探性质，希望必要时能够放弃一些刚刚完成的操作，以退回原来的某种状态重新开始。这时我们可以将所进行的设计工作（例如增加了一条滑行道）按照完成的先后顺序逐步加入一个信息栈中，当需要退回原来的
3、某一状态时，从栈的顶端逐步取出修改变化情况的信息，一步一步加以恢复。首先恢复的是最后进行的工作，直到达到希望退回的状态为止。当然这种情况下如果栈中已存满了元素，我们需要在栈的另一端打开取出一些元素加以放弃，以腾出一些栈空间，这是一种特殊的取出操作。清楚了栈的基本工作原理，还需要定义栈的基本数据操作，这样就便于我们确定栈的基本函数。在栈上定义的基本运算一般有：* 在内存空间建立一个栈；* 检查栈中剩余的容量；* 从栈的顶端推入一个元素；* 从栈的顶端取出一个元素；* 删除一个栈。除了这些基本运算之外，我们往往需要定义一些辅助运算，以帮助完成一些复杂的操作：* 查看栈中最上面一个元素的内容（并不从
4、栈中取出）；* 从栈的底端删除一个元素。2.1.2队列图2-3队列结构示意队列的工作方式与栈不同，它像一个两端打开的乒乓球筒（参见图23），所有的乒乓球只能从指定的一端放入，而拿出乒乓球则必须在另一端进行，具有先进先出的特性。利用这种特性，我们可以建立一些特殊的数据模型来描述程序所要实现的解决某些问题的过程。例如，当我们采用仿真方法分析一系列交叉口所发生的交通状态时，需要采用分时处理技术分别逐个改变每一个交叉口的状态，同时系统整体环境也在发生着一些具有时间先后次序的情况。这时，我们可以采用如图24所示的结构建立计算机处理模型。在该模型中，具有两个层次的队列（我们可以把它们看作是一种信息管道），
5、在上面的层次（称之为环境层次）上，系统环境队列描述存储环境情况的变化事件；在下面层次（称之为交叉口层次）中，每一个交叉口对应于一个信息队列，其中的元素代表外界的一个影响事件。环境层次与交叉口层次之间的控制机构判定某种环境变化事件将对哪些交叉口产生影响，从而将影响事件元素送入相应的交叉口信息管道之中。计算过程中，计算机将逐个扫描各交叉口并根据从相应信息队列中取出的情况进行必要的处理。系统环境信息管道 控制结构交叉口信息管道交叉口4交叉口3交叉口2交叉口1交叉口5图24 交叉口仿真系统控制机构为具体说明队列的实现方法，在此列举一个程序示例，这是采用C语言编写的程序，如果采用C+可以编写的更加合理，
6、但我们的目的是说明具体算法，采用C语言程序将有助于更多的读者理解。在这一程序中，采用一个队列信息描述头部记录有关的信息，其中包括指向指向记录队列内容内存块起始位置的指针start，指示当前队列头部（出口）位置的参数head，指示当前队列尾部位置的参数tail，记录队列容量的参数size，记录队列每个元素占用内存大小的参数objsize，记录队列中已有元素个数的参数nob。队列中元素存储在建立队列时所申请的内存空间，在这一内存空间上，利用head、tail两个位置参数构成了一个环形内存空间（参见图25）。建议读者阅读一下程序清单中EnterQueue()和GetElementQueue()两个函
7、数。物理存储终点物理存储起点队列头（出口）位置队列尾（入口）位置图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为队列元素个数，obj
8、size为单个元素占用的字节数*/intDelQueue( QUEUE *qp );/*删除整个队列，其中qp为需要删除的队列指针*/intEnterQueue( char * obj, QUEUE * qp ); /*在队列中加入一新元素，obj为元素指针，qp为队列指针*/intGetElementQueue( char * obj, QUEUE * qp );/*从队列中取出一个新元素*/intSpAvailQueue( QUEUE *qp );/*获取队列中剩余的元素容量*/*扩展功能服务函数*/intSpUsedQueue( QUEUE * qp );/*获取对列中已使用掉的元素容量
9、*/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, i
10、nt 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 );intE
11、nterQueue( 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-nob
12、j 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
13、-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 )ret
