计算机辅助工程基础

第二章计算机辅助工程基础

■数据结构和算法

■计算机图形学

■工程数据库

■软件工程

■新技术趋势

>

2.1数据结构和算法

y

交叉口信号相位的设置问题

信号相位是指在一个交叉口某个方向的交通流（或几个交通流的组合）

同时得到的通行权及被分配得到这些通行权的时间带。

在多叉路口需设几个相位才能既使车辆相互之间不冲突而又达到最大的

流通呢？

假设有如图所示的五叉路，其中C和E为

单行道，在路口有13条可行的通路，其

中有的可以同时通行而不发生冲突，如

A-B和E—C,而有的在同时通行时一

定会冲突，如E-B和A—D,那末，在

该交叉口应如何设置相位？这个问题可

以转换成一个图的染色问题。

A

交叉口信号相位的设置问题

——图的染色问题

.♦在图上以一个圆圈表示一条通路,在不能同时通行的两个圆圈之

间画一连线，对图中的圆圈上色，要求同一连线上的两个圆圈不同

色且颜色种类最少；

♦一种解决方案，图中13个圆圈表示13条通路，四种颜色分别表示

A

基本概念

数据结构是相互之间存在一种或多种特定关系的数据元

素的集合。在任何问题中，数据元素都不是孤立存在的,

而是在它们之间存在着某种关系，这种数据元素相互之

间的关系称为结构。

数据结构就是一门研究非数值性程序设计中计算机操作

的对象以及它们之间的关系和运算等的学科

基本概念

■数据:对客观事物的符号表示，在计算机科学中是指所

有能输入到计算机中并被计算机程序处理的符号的总称

■数据元素:数据的基本单位，在计算机程序中通常作为

一个整体进行考虑和处理

■数据对象:性质相同的数据元素的集合，是数据的一个

子集

■数据结构:相互之间存在一种或多种特定关系的数据元

素的集合

四类基本结构

■集合数据元素1数据元素2

-线性结构数据元素1数据元素2

■

■树形结构数据元素2

数据元素1

数据元素3

■网状结构数据元素2

数据元素1

数据元素3

线性表

线性表是最常用且最简单的一种数据结构，它是属同一数

据对象的〃个数据元素的有限序列

■若将线性表记为，称与］是由的

直接前趋元素，火［震％的苴于芟盾Z度尤第

■线性表中元素的个数〃（心=0）定义为线性表的长度，片0时

称为空表。

■在非空表中的每个数据元素都有一个确定的位置，比如《

是第Z•个数据元素，称Z•为生在线性表中的位序

线性表1—顺序表

顺序表以一组地址连续的存储单元依次存储线性表的

数据元素，由此在逻辑上相邻的两个元素在物理位置上

也是相邻的。只要给定了存储线性表的起始位置，表中

任一数据元素都可以随机存取，因此顺序表是一种随机

存取的存储结构。顺序表通常用数组类型来实现.

12...n-1n

ai的地址计算函数为：

addr(aj=addr(aT)+(i-1)*d

线性表2—链表

■链表使用一组任意的存储单元存储线性表的数据元素（这

组存储单元可以是连续的，也可以是不连续的，即逻辑上

相邻的两个元素在物理位置不一定相邻）。

■数据元素生的存储映象（称为结点）包括两个域：①存储

数据元素信息的数据域；②存储直接后继位置信息的指针

域，〃个结点链接成一个链表。链表在高级程序语言中可用

指针来实现

线性表2—链表

数据指针数据指针数据指针

删除元素

添加元素

数据指针

栈

■栈是限定在表尾进行插入或删除操作的特殊线性表。先

进后出的线性表.

■%为栈底元素，%为栈顶元素。

■栈中元素按％,…,玛的次序进栈，出栈的第一个元素

应为栈顶元素心。

栈

基本运算有：

■建立一个栈

■检查栈中剩余容量

■从栈顶推入一个元素

■从栈顶取出一个元素

-删除一个栈

应用举例：常用软件中的撤销9与恢复Q操作

队列

■队列是一种先进先出的线性表。

■它只允许在表的一端进行插入，而在表的另一端进行

删除。在队列中，允许插入的一端叫做队尾，允许删除

的一端则称为队首。

■假设队列为Q=

■则称为为队首元素，4为队尾元素。

■队中元素按％,出，…，程的次序进入

■退出队列也只能按这个次序依次进行。

队列

基本运算有：

-建立一个队列

■检查队列状态

■从队尾插入一个元素

■从队首删除一个元素

-删除一个队列

应用举例：生活中的排队

例一交叉口仿真系统控制结构

■当采用仿真方法分析一系列交叉口所发生的交通状态时,

需要采用分时处理技术分别逐个改变每一个交叉口的状

态，同时系统整体环境也在发生着一些具有时间先后次

序的情况。

系统环境信息管道

控制结构

□

9交叉口信息管道

3交叉口4交叉口5

树

■结点A为树的根，根的每个分

支称为子树，子树也是一棵树

■结点子树的根为结点的孩子，

如B、C、D为结点A的孩子，

而A为B、C、D的双亲

■同一个双亲的孩子之间为兄

弟关系，如B、C、D

■没有孩子的结点为树的叶子，

H、F、G、D为树的叶子

树的基本运算

-初始化一棵树

■得到树的根

-得到一个结点的双亲

■得到一个结点的兄弟

■得到一个结点的孩子

■插入子树

-删除子树

■遍历树

■清空树

特殊的树

■二叉树

■二叉搜索树

■哈夫曼树用于具有层次结构的数

■B树据的组织、搜索和比较

■AVL树

■红-黑树

各种特定的树结构被广泛应用于交通

CAE软件中，它们可以加快查找的速度

和分析处理的效率。

二叉树

二叉树在树结构的应用中起着非常重要的作用

■对二叉树的许多操作算法简单；

-而任何树都可以与二叉树相互转换，解决了树的存储结构及其运

算中存在的复杂性。

定义：二叉树是由n(n>=0)个结点的有限集合构成，此集

合或者为空集，或者由一个根结点及两棵互不相交的左

右子树组成，并且左右子树都是二叉树。

这也是一个定义。二叉树可以是空集合，根可以有

空的左子树或空的右子树。

二叉树结点的子树要区分左子树和右子树即使只有一

棵子树也要进行区分，说明它是左子树，还是右子树。

这是二叉树与树的最主要的差别。

二叉树的5种形式

⑹

根和空的左

空二叉树

右子树

(c)

根和左子树根和右子树根和左右子树

遍历二叉树

在二叉树的一些应用中，常常要求在树中查找具有某种特征的结

点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二

叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使

得每一个结点均被访问一次，而且仅被访问一次。

遍历对线性结构是容易解决的，而二叉树是非线性的，因而

需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队

列上，从而便于遍历。

（根结点）

一（右子树）

由二叉树的递归定义，二叉树的

三个基本组成单元是：根结点、

（左子树）

左子树和右子树。

假如以L、D、R分别表示遍历左子树、遍历根结点和遍历

右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、

RLD六种遍历方案。若规定先左后右，则只有前三种情况，分

别规定为：

DLR——先（根）序遍历，

LDR——中（根）序遍历，

LRD——后（根）序遍历。

先序遍历二叉树

先序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。

124537

中序遍历二叉树

中序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则

(1)中序遍历左子树；

(2)访问根结点；

(3)中序遍历右子树。

425137

后序遍历二叉树

后序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。

452731

4例题

例如图(1)所示的二叉树表达式

(a+b*(c-d)-e/f)

按先序遍历：-+a*b-cd/ef

按中序遍历：a+b*c-d-e/f

按后序遍历：abcd-*+ef/-

冽题

已知一棵二叉树的前序遍历的结果是ABECDFGHU,中序遍

历的结果是EBCDAFHIGJ,试画出这棵二叉树。

当前序序列为ABECDFGH口，中序序列为EBCDAFHIGJ时,

逐步形成二叉树的过程如下图所示：

树的路径长度(PL)

PL是指从根到其它各结点的路径长度(分支数)

之和。

(a)PL=13(b)PL=15

完全二叉树各结点的路径长度分别是数列

0,1,122,2,2,3,3,3,3,3,3,3,3,4,4,4,…其路径长度为前n项之和,

具有最小值：户乙=三口。名2。一+1）」

z=o

霍夫曼树

具有最小WPL的扩充二叉树叫霍夫曼树

n—i

亚包=>^乜

7=0

(a)WPL=36(b)WPL=46(c)WPL=35(霍夫曼树)

霍夫曼树的构造方法

将n个权值视为具有n棵扩充二叉树的森林F,然后重复以

下步骤，直到F中只有一棵树为止：

①在F中选根的权值最小的两棵作为左右子树构造一棵新

的二叉树，其根的权为左右子树根的权值之和。

②在F中删除那两棵树，并把新的二叉树加入。

J霍夫曼树的构造方法

⑦，②，⑤，④⑦，⑤,

(b)

霍夫曼编码——霍夫曼树应用事例

1、最小冗余编码问题

☆设用0,I码来对一串字符信息进行等长编码：

T——00,A——01,D——10,S——11

☆对于信息串“ATTSTATADT”所得至U的编码为

01,00,00,11,00,01,00,01,10,00共20位编码

☆字母集合｛T,A,D,S｝出现的频度W=｛5,3,1,1),

若采用不等长编码表示

T——0,A——10,D——110,S——111所得到的

编码是10,0,0,111,0,10,0,10,110,0共17位，这是最小冗

余编码。

霍夫曼编码——霍夫曼树应用事例

☆以字符的频度为权构造霍夫曼树

☆左分支表示0,右分支表示1

☆从根到各外结点路径上经由的数

字序列构成各字符的编码

一^霍夫曼编码—霍夫曼树应用事例

3、霍夫曼树编码的优越性

☆是最小冗余码

☆非前缀码——码Ci不是码Q的前缀

☆译码简单唯一——不断从根开始沿霍夫曼编码树查找。

10001110100101100译码得到的只能是报文串：|

ATTSTATADT

习题

■给定权值集合｛15,03,14,02,06,09,16,17),构

造相应的霍夫曼树，并计算它的带权外部路径长度。

■假定用于通信的电文仅由8个字母cl,c2,c3,c4,c5,

c6,c7,c8组成，各字母在电文中出现的频率分别为5,

25,3,6,10,11,36,4o试为这8个字母设计不等长

Huffman编码，并给出该电文的总码数。

05

0203

(VI)

0203

此树的带权路径长度WPL229

y答_

已知字母集{cl,c2,c3,c4,c5,c6,c7,c8},频率<5,25,3,6,

10,11,36,4},则Huffman编码为:

clc2c3c4c5c6c7c8

01101000000111001010110001

00

电文总码数为01

4*5+2*25+4*3+4*6+3*10961

0

+3*11+2*36+4*4=2570

17,2156

00

C2

70

00

C

345

C3C8C4

例：路网规划

在路网规划过程中，需在现状路网的基础上不断改造、完善，由近及远

地提出各个规划特征年的路网规划方案；类似这种由单个初始路网经过多个

阶段的演变而衍生成的一系列有着直接或间接派生关系的路网方案可称之为

动态路网。在动态路网中，不同路网方案的数据存在大量的重复部分。

传统的交通分析软件，对动态路网大多是按多个独立路网建立和分析的。

不但造成数据冗余过大，更致命的是掩盖了路网动态演变的过程。基于树结

构的方案树可有效描述动态路网的动态性，揭示路网方案之间的联系。

-方案树的每个结点代表一个路网方案;

■根结点即为初始路网；

■连接结点的边代表方案间的直接派生关系；

■双亲结点即为基础方案，孩子结点即为派生方案，兄弟结点代表了不同

的比选方案；

-树的高度代表动态路网的层次数，一个层次代表动态路网的一个演变阶

段。

图一有向图

■有向图G=(N,4)由节点集N和弧集/构成。N中的每个元素z•称为节点

(或顶点)。4中的每个元素。可由N中的有序节点对«,/)表示，称为从2

到J的弧(或边)

■对于弧&/),z.和/称为。的端点，其中，.称为起点，/称为终点，并称/邻

才妾至加

■对于弧(V)，称(zj)关联于环明称«,/)为泊勺出弧、)的入弧

-一个节点的出弧的数目称为该节点的出度，入孤的数目称为该节点的

入度，出度与入度之和称为该节点的度

■起点和终点均相同的2条及2条以上的弧称为多重弧，起点和终点为同

一节点的弧称为环。一个无环、无多重弧的有向图称为简单有向图，一

个无环、但允许有多重弧的有向图称为多重有向图。没有任何弧与之关

联的节点称为孤立点

图一有向图

节点集N={1,2,3},弧集4={(1,2),

(1,3),(2,1),(2,3),(3,2)}

节点1是弧(1,2)的起点，节点2是该

弧的终点，节点2邻接到节点1

弧(1,2)关联于节点1和2,弧(1,2)为

节点1的出弧、节点2的入弧

节点1的出度为2,入度为1,度为3

■无向图的定义类似于有向图，根本的区别在于无向图中组

成弧的节点对是无序的，即连接节点环9的弧既可以记成

(4)，也可记成(//)。有向图的相关概念都可自然地推广到

无向图上来，但在涉及方向性的概念时会有一些微小的差异,

比如无向图的一条弧的端点不再有起点和终点之分。

■有向网络就是赋予节点和弧一定数值、权重的有向图，也

就是赋权有向图；对应地，无向网络就是赋权无向图。网络

和图的区别在于：它不仅代表着一种数学形式，而且具有物

理结构。但是，由于图都是可以赋权的，因此在一般场合下,

对图和网络的概念都不加细分，两者可以通用。

有向图的表示法一关联矩阵

有向图G=（N,4）的关联矩阵B是一个〃XM的矩阵（〃为节点数目，加为弧

数目），每行对应于一个节点，每列对应于一条弧。若节点，是弧。的起

点，则关联矩阵中对应的元素为1；若，是。的终点，则对应的元素为T；

若，.与。不关联，则对应的元素为0。对于简单图，关联矩阵每列只含有两

个非零元（一个1,一个-1）。在关联矩阵中，每行元素1的个数正好是

对应节点的出度，每行元素-1的个数正好是对应顶点的入度。

(1,2)(1,3)(2,1)(2,3)(3,2)

1「11—1001

1

2T011T

30—10—11

有向图的表示法一邻接矩阵

有向图G=(N,⑷的邻接矩阵C是一个“X〃的矩阵，每行、每列均对应一个

节点；如果两节点之间有一条弧，则邻接矩阵中对应的元素为1;否则

为零。每行元素之和正好是对应节点的出度，每列元素之和正好是对应

节点的入度。

123

1「0111

2j101[

3010

有向图的表示法一邻接表

有向图的邻接表就是所有节点的邻接节点集的列表。邻接表可以用多种

数据结构加以实现，通常采用数组加链表的混合形式。在这样的邻接表

中，节点存储在数组中，对每个节点用一个单向链表列出该节点的所有

邻接节点，链表中每个单元实际对应于一条弧（该弧的起点取决于链表

头，终点取决于该单元存储的节点）。

A

2332

有向图的表示法一方法比较

有向图的关联矩阵和邻接矩阵的表示法非常简单、直接。但

是，在关联矩阵的所有〃X加个元素中，只有2加个为非零元；

在邻接矩阵的所有层个元素中，只有加个为非零元，它们属

于稀疏矩阵。对于比较稀疏的网络（比如交通网络，节点的

平均出度在3左右），这两种表示法会浪费大量的存储空间。

而邻接表的存储效率最高，只需要什加个存储单位，尤其适

合于稀疏网络。

其他的有向图表示法包括：星形表、双向邻接表、邻接多重

表等，可参考相关文献。

土最短路径

求最短路径的Dijkstra算法

■设有向图出(V,E),其中，V={0,1,2」……，n),

cost是表不G的邻接矩阵，cost[i][jj表不有向边〈i,j＞的

权。若不存在有向边＜i,j＞,则cost的权为无穷大。

-设S是一个集合，其中的每个元素表示一个顶点，从源点

到这些顶点的最短距离已经求出。设顶点1为源点，集合

初态s={0}。

■数组dist记录从源点到其他各项点当前的最短距离，其初

值为dist[i]=cost[0]ji],i=l,2,・・・,no

■从s之外的顶点集合V-S中选出一个顶点w,使dist[w]的值

最小。于是从源点到达w只通过s中的顶点，把w加入集合s

中，调整dist中从源点至(JV-S中每个顶点v的距离：

dist[v]=min{dist[v]，dist(w)+cost[w][v]}

最短路径

.重复上述过程，直到S中包含V中其余各项点的最短路径。

-最终结果是：S记录了存在丛鹿更胪算照件单熟空鲁获

数组dist记录了从源点到V中到其余各项点N间的最短路径.

Example

45

50

201015

50

15

3

Answer

sdist

Answer(Con1)

-最后的输出结果如下:

■—3-235

■20

■3-215

■"3-230

■5-210

■6-2oo

算法及其复杂度分析

(1)有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步

之后结束，且每一步都可在有穷时间内完成。

(2)确定性：算法中每一条指令必须有确切的含义,读者理解时不会产

生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于

相同的输入只能得出相同的输出。

(3)可行性：一个算法是可行的,即算法中描述的操作都是可以通过已

经实现的基本运算执行有限次来实现的。

(4)输入：一个算法有零个或多个的输入,这些输入取自于某个特定的

对象的集合。

(5)输出：一个算法有一个或多个的输出。这些输出是同输入有着某些

特定关系的量。

4算法及其复杂度分析_

Fs常设计一个“好”的算法应考虑达到以下目标：

-(1)正确性：算法应当满足具体问题的需求。通常一个大型问题的需求，要

以特定的规格说明方式给出，而一个不那么严格的问题至少应当包括对于输

入、输出和加工处理等明确的无歧义性的描述。设计或选择的算法应当能正

确地反映这种需求。

-(2)可读性：算法主要是为了人的阅读与交流,其次才是机器执行。可读性

好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和

修改。

-(3)健壮性：当输入数据非法时,算法也能适当地作出反应或进行处理，而

不会产生莫明其妙的输出结果。

-(4)效率与低存储量需求：通俗地说,效率指的是算法执行时间。存储量需

求指算法执行过程中所需要的最大存储空间。一个好算法要有高的执行效率

和低的存储量需求。

4算法及其复杂度分析_

Fs常设计一个“好”的算法应考虑达到以下目标：

-(1)正确性：算法应当满足具体问题的需求。通常一个大型问题的需求，要

以特定的规格说明方式给出，而一个不那么严格的问题至少应当包括对于输

入、输出和加工处理等明确的无歧义性的描述。设计或选择的算法应当能正

确地反映这种需求。

-(2)可读性：算法主要是为了人的阅读与交流,其次才是机器执行。可读性

好有助于人对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和

修改。

-(3)健壮性：当输入数据非法时,算法也能适当地作出反应或进行处理，而

不会产生莫明其妙的输出结果。

-(4)效率与低存储量需求：通俗地说,效率指的是算法执行时间。存储量需

求指算法执行过程中所需要的最大存储空间。一个好算法要有高的执行效率

和低的存储量需求。

2・2计算机图形学

概念

计算机图形学主要研究用计算机及其图形

设备来输入、表示、变换、运算和输出图

形的原理、算法及系统。

图形主要分为两类，一类是基于线条信息

表示的，如工程图、等高线地图、曲面的

线框图等，另一类是明暗图，也就是通常

所说的真实感图形。

概念

计算机图形学主要研究用计算机及其图形

设备来输入、表示、变换、运算和输出图

形的原理、算法及系统。

图形主要分为两类，一类是基于线条信息

表示的，如工程图、等高线地图、曲面的

线框图等，另一类是明暗图，也就是通常

所说的真实感图形。

图形生成和变换:曲线绘年

规则曲线的绘制

最小二乘法拟合

三次样条曲线

贝齐尔(Bezier)

曲线B样条曲线

图形生成和变换：曲面绘

双线性曲面

直纹曲面

回转曲面

孔思(coons)曲面

图形生成和变换:男

平面裁剪（线段裁剪、曲线裁剪和多边形裁

剪）——分区编码剪裁

三维裁剪

图形生成和变换：二维几何

变换、三维几何变换等・・・・・・

例

100110001010

000100000010

010101000110

---------------------------------------------------------

2・3工程数据库

数据库系统基础

数据库是通用化的相关数据的集合，它不仅包

括数据本身，而且包括关于数据之间的联系。

因此，一个数据库有四个主要成分：数据、联

系、约束和模式。数据是所存储的逻辑实体在

计算机中的二进制表示；联系表示数据项之间

的某种对应；约束是定义正确数据状态的断言;

一种模式描述数据库中数据的组织和联系。

数据

联系

数据库

约束

模式

数据库系统基础

模式为数据库管理系统各个组成部分的使用和应

用的安全定义数据库的各种视图。模式将数据存

储的物理外表与逻辑表示分开。内部模式定义数

据在物理数据存储区中如何组织以及放在何处。

概念模式按照适当的数据库数据模型（如关系模

型或对象模型）定义所存储数据的结构。外部模

式为特定用户们定义数据库的一个或多个视图。

外部模式1外部模式1外部模式n

物理数据库

数据库的数据模型一层次模型

层次模型是一种基本层次联系的集合，它实际上是一种有

根定向的有序树。层次模型的基本结构是树结构——根、

枝、叶结构，数据存放的基本单位是片断（即层），片断

是内在有逻辑联系的一组数据，总的来说，层次模型按照

树形结构以片断为单位存放数据。层次模型比较容易实现,

但是查找比较麻烦，数据的冗余度也比较大。

2层

层

数据库的数据模型一网状模型

所谓网状模型是指一个连通的基本层次联系的集合。复杂

的网总可以分解成若干个基本结构，即分解成系。系有系

主（只有一个）和系属（可以有多个），系主和系属之间

有关系，而且关系是双向的。

网状模型存放的基本单位是记录，也就是按记录存放，查

询时，从系（系主和系属）查起。网状模型查找时间较省,

数据和冗余度比层次模型小，但比关系模型要大。

RiR2R3R4

数据库的数据模型一关系模型

关系模型是目前最为流行的数据模型，它是由许

多二维关系表组成的集合。下表就是一张关系表,

R是关系名，Aj是属性名，关系和属性

(R,A],A2…4)组成了数据表的模式；Vjj叫做分

量，表中的一列是一个属性，相当于一个数据项,

一行叫做一个元组，相当于一条记录。

u•S£§

<>>>**>

•:::

»一・中

<r

•:•:

1峪

<>>>,>>

A—>

（中国地图，面积，周长，名称）

ESMOND

54.447168.4888黑龙江省

4129.113129.933内蒙古自治区

175.59184.9053新强维吾尔自治区

21.314541.1859吉林省

15.602838.3792辽宁省

41.507776.7812的省

1.733218.49791北京巾

15.961124.7842山西省

1.213677.26263天津市

20.393638.5711陕西省

5.2717718.5204宁夏回族自治区

71.36359.5622青海省

15.388140.9005山东省

114.33176.6291西藏目治区

16.13530.9113河南省

9.7358727.8925江苏省

13.365129.4915安徽省

关系表的操作可以分为以下四种：

■通用的集合操作，如并、交、差运算等；

■去除关系表的某些部分的操作，包括选择和投影，前者

去除某些元组，后者则用于除去某些属性；

■两个关系表的合并，包括“笛卡尔积”以及各种方式的

连接运算；

■更名操作，即对关系表属性名称的修改，它不改变元组,

但是改变了关系表的模式。

这些操作以及相关的都是通过结构化查询语言SQL完成的

Query1浏览窗口-In]x|

.数据库的数据模型—面向对象模型

网络和层次以及关系模型都适合那些结构简单以及访问有

规律的数据。

面向对象数据库的引入就是为了满足一再出现的复杂信息

的共享。在复杂数据进入数据库以后，数据库提供了存贮

信息的统一视图，与具体存贮结构无关。把物理数据结构

与逻辑数据结构分开，同时控制数据的共享及保持数据的

正确性、完整性和一致性，大大方便了应用程序的开发和

维护，减少生命周期内的各种费用。通过一组优化的程序

来管理数据，使得整体效果更优，性能更稳定。

.数据库管理系统

品据库管理系统是为数据库访问提供服务的软件,同时维

护所有数据必需的特性。数据库管理系统提供下列服务：

1）事务处理

有三种特定的事务操作：启动指示将开始一个新事务，提

交指示事务已正常终止且其作用结果将持久存在，以及放

弃指示事务被异常终止，其所有结果将被放弃。

2）并发控制

并发控制是一种数据库管理活动，它协调数据库操作进程

的并发操作和对共享数据的访问，并且解决它们之间可能

发生的潜在冲突。

数据库管理系统

3）恢复

数据库中恢复的目标是确保异常终止或出错的事务不会对

数据库或其它事务产生不利影响。恢复可使得数据库在事

务异常终止后返回某个一致状态。

4）安全

安全是保护数据免受非授权的泄露、更改或破坏。每个用

户和应用程序都有特定的数据访问特权。这些过程中最常

用的是注册名和口令保护服务。

数据库管理系统

5）语言接口

提供对用于定义和操作数据的语言的支持。数据定义语言

用于描述数据、数据间联系和对数据和联系的约束的表示

法；数据操纵语言用于表达数据库上的操作。

6）容错性

不管发生什么故障仍能继续提供可靠服务的能力称为容错

性。恢复与容错性密切相关。

.数据库管理系统

7）数据目录

也称数据字典，是一个系统数据库，含有主数据库中数据

的描述。

8）存储管理

提供数据持久存储的管理机制。

2.4软件工程基础

软件与软件危机

您什么是软件软件=程序？

@什么是软件危机

软件危机首次爆发于二十世纪六十年代。

在大型程序设计中，人们发现投入大量的

人力、物力、时间开发出的软件，其成本、

效率、质量等方面却处于失控状态，尤其

软件维护异常困难。程序的修改扩充往往

需要大量重复性投入。

软件与软件危机

软件危机产生的原因主要有三个:

口软件开发者不熟悉用户问题的领域，或没有理解用户

需求，软件产品与要求不一致。

口软件是一种逻辑产品而非物理产品，软件的开发过程

本质上是人的思考过程。

口人的智力在面对越来越复杂的问题时，处理问题的效

率会越来越低。

软件工程

软件危机的出现迫使人们重新认识软

件和软件开发过程。

大型软件开发也应该借鉴建筑、机械

等行业的发展过程，由“手工方式”

向“工程化”方向发展。1968年在北

大西洋公约组织(NATO)的年会上首次

提出软件工程的概念，此后又逐步提

出软件生命期的概念。

0软件工程

O软件工程的提出和软件的定义

软件是程序、方法、规则、相关文档以及在计算机上运行

所必需的数据的集合。而软件工程是开发、运行、维护软件

的系统方法。

O软件生命期

软件生命期指从开始研制到废弃不用的整个期间，可划分

为五个阶段：需求分析、设计、编程、测试和运行维护。

O软件的质量标准

F确性肄壮忤可维护忤

可用性可重用性效率等

y软件工程

正确性

软件的正确性指的是软件系统在正

常条件下能够正确工作，完成规定功能。

这是软件的首要指标。

例如，要求设计程序，输入一批数据,

计算它们的累加和。在这里，正确性就

是正确能正确计算累加和。

、■软件工程

~r^

健壮性

软件的健壮性指的是在意外情况下(如输入数据不合理或

某些硬件故障)，软件系统仍能适当地工作，并对意外情况

进行适当处理，而不致于导致错误结果甚至系统的瘫痪或死

机。

例如，要求设计程序，根据输入的三边a、b、c的长度判别

三角形类型。现有如下设计思想：若a、b、c中只有两个量相

等，则为等腰三角形，若三个量均相等，则为等边三角形，

否则为一般三角形。如果输入为(-2,-2,-2)时，程序输

出为：等边三角形。这个结果显然是错误的。这是由于程序

对不合理数据不能进行适当处理，我们就说这个程序的健壮

性不好。

软件工程

可维护性

软件的维护包括发现并改正软件的错误，以

及由于软件运行环境发生变化或软件功能扩充

而对软件进行的改动。

软件的可维护性指的是软件容易维护的程度。

一般地说，软件的可读性好，容易理解，维护

起来也就比较容易。因此可读性是可维护性的

基础。

软件工程框架

软件工程的目标可以概括为“生产具有正确性、可用性

以及开销合宜的产品”，其活动包括需求、设计、实现、

确认以及支持等活动，围绕工程设计、支持以及管理，

有以下的四条基本原则：①选取适宜的开发模型；②采

用合适的设计方法；③提供高质量的工程支持；④重视

开发过程的管理。

'I软件工程框架

*软件工程活动一需求分析

需求分析阶段处于软件开发的前期，其基本活动是准确

定义未来系统的目标，确定为了满足用户的需求必须做

什么。需求分析又划分为两个阶段，即需求获取和需求

规约，前者是用自然语言清楚地描述用户的要求，而需

求规约的目的是消除获取需求的二义性和不一致性。

建立需求面临着以下三个方面的困难：①问题空间的理

解；②人与人之间的通信；③需求的不断变化。面向对

象的分析方法被认为是解决上述困难较好的技术。

*软件工程活动-系统设计

需求分析阶段的主要任务是确定系统“做什么”，而设

计阶段则要解决“怎么做”的问题。

通常设计阶段又划分为总体设计和详细设计，总体设计

确定系统的总体结构框架；而详细设计要具体地描述如

何具体地实现系统，通常可以依据详细设计的结果进行

编码。详细设计包括：详细的算法；数据表示和数据结

构；实施的功能和使用数据之间的关系。

软件工程活动一实现阶段

在软件实现阶段，要将设计的结果变换成程序设计语言

编写的程序。在实现阶段，首先要确定程序设计语言，

其影响因素包括：开发人员对语言的熟悉程度，语言的

可移植性，编译程序的效率，编译工具的支持等等。目

前，C++语言是普遍被采用的构造系统软件的编程语言,

而Java则更多地应用于编写网络程序。

无论采用哪一种编程语言，都要求编写高质量的源程序

代码。

.软件工程活动一确认活动

系统完成后的软件测试是主要的确认活动。软件测试是

指按照特定规程，发现软件错误的过程。软件测试的技

术大体上可以分为两类，即白盒测试技术和黑盒测试技

术，前者依据的是程序逻辑结构，后者依据的是软件行

为描述。根据测试的步骤，测试活动又可以划分为单元

测试，集成测试，确认测试和系统测试。

软件工程活动一软件维护

当软件开发完成并交付用户使用后，就进入运行/维护阶

段，在运行/维护阶段仍需要对软件进行修改，称为软件

维护。

软件维护活动可以分为以下几类：①正性维护；②适应

性维护；③完善性维护；④预防性维护。

软件工程活动一软件维护

当软件开发完成并交付用户使用后，就进入运行/维护阶

段，在运行/维护阶段仍需要对软件进行修改，称为软件

维护。

软件维护活动可以分为以下几类：①正性维护；②适应

性维护；③完善性维护；④预防性维护。

软件开发过程模型

软件开发模型是软件开发全部过程、活动和任务的结构框架。软件

开发模型能够清晰、直观的表达软件开发过程，明确规定要完成的

主要活动和任务，可以作为软件项目工作的基础。

主要模型有：

■瀑布模型一将各项活动规定为依照固定顺序连接的若干阶段工作,

形如瀑布流水

■演化模型一当开发人员将核心需求实现后，用户提出反馈意见，

以支持系统的最终设计和实现

-螺旋模型一在瀑布模型以及演化模型的基础上，加入风险分析所

建立的模型

-喷泉模型一体现了软件开发过程中所固有的迭代和无间隙的特征

面向过程的程序开发方法

传统的程序设计方法可以归结为“程序=算法+数据结

构”，将程序定义为处理数据的一系列过程。这种设计

方法的着眼点是面向过程的，特点是数据与程序分离，

即数据与数据处理分离。

结构化程序设计的基本思想是采用自顶向下、逐步细化

的设计方法和单人单出的控制结构。

程序

模块1模块2模块3

1.22.12.2

1.3.11.3.21.3.33.1.13.1.2

举一个简单的例子，要求读入一组整数，统计其中

正整数和负整数的个数。

该任务的模块结构及细化过程如下：

1.读入数据

一正整数个数为0；负整数个数0

—取第一个整数

2.统计正数、负数

的个数；—重复j2.1如数大于0,正整数个数加1

至统/2.2如数小于0,负整数个数加1

3.输出结果

I2.3:取下一个整数

这种设计方法的优缺点在于：

♦结构化程序设计可以把一个较为复杂的程序设

计任务分解为许多易于控制和处理的子任务，

分块解决，具有很大优点。

♦但它把数据和处理数据的过程分离开来，当数

据结构改变时，所有相关的处理数据过程都要

进行相应的修改，程序的可重用性较差，对大

型程序设计很难适应。

.面向对象的程序开发方法

-面向过程程序设计缺点的根源在于数据与数据处理分

离。

面向对象程序设计模拟自然界认识和处理事物的方法,

将数据和对数据的操作方法放在一起，形成一个相对独

立的整体——对象(object),同类对象还可抽象出共

性，形成类(class)o一个类中的数据通常只能通过

本类提供的方法进行处理，这些方法成为该类与外部的

接口。对象之间通过消息(message)进行通讯。

念

寸1t

表针

旋钮

其他机械机构

调节旋钮

基本辍念

-1

是一个抽象的概念，用来描述某一类对象所共

有的、本质的属性和行为。

类的一个具体实现，称为实例

描述这类对象共有的、本质的属性和行为

具体到一只圆形的或方形的闹钟

闹钟共有的属性（表针、旋钮、内部结构）

和行为（调节旋钮）

［寒有槐念

I

消息

我们把对象之间产生相互作用所传递的信息称做消息。

计算机世

界

对象

类

对象、实体与类

“面向对象”殁本开或清点

对象是一个封装体，在其中封装了该

对象的属性和操作。通过限制对属性和操

作的访问权限，可以将属性“隐藏”在对

动

机

读

象内部，对外提供一定的接口，在对象之调

作

表

械

外只能通过接口对对象进行操作。节

盘

旋

零

钮

件

对象的独立性

数据的可靠性

独立模块

“面向对象”残才开发特支

健宗鸟源金

面向对象程序设计提供了类似的机制:汽车

当定义了一个类后，又需定义

一个新类，这个新类与原来的类客车货车

相比，只是增加或修改了部分属

性和操作，这时可以用原来的类

派生出新类，新类中只需描述自小轿车大客车

己所特有的属性和操作。

新类称为子类或派生类，原来的类称为基类。派生可以一直

进行下去，形成一个派生树。

“面向对象”桂格外或清克

多态性指，同一个消息被不同对象接收时,

产生不同结果，即实现同一接口，不同方法。

计算大学生高数、英语、计算机、线

平均成绩性代数

“面向对象”强本开或清点

继承和多态性组合，可以生成很多相

似但又独一无二的对象。继承性使得这

些对象可以共享许多相似特性，而多态

又使同一个操作对不同对象产生不同表

现形式。这样不仅提高了程序设计的灵

活性，而且减轻了分别设计的负担。

I.面向对象的程序开发过程

面向对象软件开发的根本合理性在于它符

合客观世界的组成方式和大脑的思维方式。

在大型程序开发过程中，编码只是其中很

小一部分，应当采用工程化的方法，并将面

向对象的思想贯穿于软件开发全过程，这就

是面向对象的软件工程。

面相对象的软件工程同样遵循分层抽象、

逐步细化的原则。软件开发过程包括以下五

个阶段：分析、设计、编程、测试和维护

面向对象的程序开发过程一1

面向对象的分析：从问题的陈述开始，逐步建立起客观

事物的模型，分析模型中的对象，使得对象的描述与客

观事物相一致。相同特性的对象为一类，一般类和特殊

类之间有继承关系。

面向对象的设计：主要是把在面向对象分析阶段建立的

模型，用面向对象的方法产生一个具体实现。包括：把

面向对象的分析模型直接到面向对象的设计作为面向对

象设计的一部分；针对具体实现中的人机界面、数据存

储、任务管理等因素补充一些与实现有关的部分。

面向对象的程序开发过程一2

面向对象的编程：编程是面向对象的软件开发最终落实

的重要阶段。它主要是要用面向对象的语言实现面向对

象设计方案中的每个成员。

面向对象的调试：调试的任务是发现软件中的错误。以

对象的类作为一个基本测试单位，查错范围是类定义之

内的属性和服务以及接口所涉及的部分。这样可以更准

确地发现错误，提高测试效率。

面向对象的维护：软件作为一件产品，无论经过多么严

格的测试，总还会存在一些错误。所以，软件的维护是

不能省略和停止的。

2.5新技术趋势

人工智能

■专家系统是人工智能研究中的一个重要方面。

专家系统与CAD技术的结合，形成设计型的专

家系统，又称为智能化CAD。

■在交通CAE领域中，人工智能和专家系统的应

用已成为研究的热点，但要真正能投入实际应

用，尚有很多工作要做。国内曾对公路选线专

家系统以及用专家系统的方法改进道路CAD系

统方面做过探索性研究。

数据挖掘

个于专家系统工具过分依赖用户或专家人工

地将知识输入知识库中，而且分析结果往往

带有偏差和错误，再加上耗时、费用高，故

不可行。

■产生了一个新的研究方向

■基于数据库的知识发现(KnowledgeDiscovery

inDatabase),以及相应的数据挖梅(Data

Mining)理论和技术的研究

数据挖掘工具

数据矿山信息金块

in州』帆Utubtss

1988199019952004

ExpertSystemsExpertSystems

数据挖掘是多学科的产物

、KDD已经成为人工智能研究热点

■目前，关于KDD的研究工作已经被众多

领域所关注，如过程控制、信息管理、

商业、医疗、金融等领域。

■作为大规模数据库中先进的数据分析工

具，KDD的研究已经成为数据库及人工

智能领域研究的一个热点。

数据挖掘算法

•支持向量机

•决策树学习

•Bayes分类

•聚类

•主分量分析方法

•人工神经网络

•EM算法

•模糊逻辑

•智能优化

机器学习

-人工智能目前的研究热点是机器学习。机器学习是一

种使获取知识自动化的计算方法的学习。机器学习在

人工智能的研究中具有十分重要的地位。其应用已遍

及人工智能的各个分支，如专家系统、自动推理、自

然语言理解、模式识别、计算机视觉、智能机器人等

领域。

-机器学习方法

■特征选择

■分类方法

■决策树

■人工神经网络与遗传算法

■支持向量机

■图论与聚类方法

网格技术

■网格(Grid)概念源于电力公用网，其基本思想是

使用户在应用网格技术时，就像日常生活从电

力网中获取电能那样，可以方便地获取网络上

高性能的计算能力。根据Foster和Kesselman

的定义，网格是构筑在互联网上的一组新兴技

术，它将高速互联网、计算机、大型数据库、

传感器、远程设备等融为一体，为科技人员和

普通老百姓提供更多的资源、功能和服务。

网格的概念

网格计算

■网格计算(Gridcomputing)是利用互联网

技术，把分散在不同地理位置的计算机

组成一台虚拟超级计算机。

IBM的网格远景：现在的计算机

Storage

___Applications

未来：因特网是计算机！

TheInternetasaComputingPlatform

Data

n--------

・优势：计算能力强，费用低

在实质上来说“网格计算”是一种分布式应用,

网