地理信息系统原理方法和应用-邬伦等编著.pdf

没有 百度文库财富值 请到文库帮手网 w w w.365x u e y u a n.c o m 免费帮下载 百度文库积分 资料 人用计算机的时代。目前，计算机技术正在继续向巨型、微型、网络和人工智能等几个方向发展：1）为满足尖端科学研究的需要，还必须发展高速、大存贮容量和强功能的巨型机；2）计算机另一个发展方向是要研制价格低廉、使用灵活方便的微型机，以适应各种应 用领域。3）计算机网络是计算机的又一发展方向，计算机网络提高了计算机系统资源，特别是 信息资源的综合利用，把分布在许多地区的计算机系统，特别是分布在各地的信息资源联结 在一起，组成一个规模更大、功能更强、可靠性更高的信息综合处理系统。4）美国、日本等国正在研制第五代“智能”计算机，它不是注重数学运算，而是注重 于逻辑推理或模拟人的“智能”。图 A1-1：计算工具的发展概况 12 计算机的基本组成 按照诺伊曼理论建立起来的当代计算机，应当具有输入/输出功能、存储记忆功能、计 算功能、判断功能和自我管理功能。从功能模拟的角度，Ne u m a n n 计算机通常由与上述功能 对应的功能部件组成，这些部件主要包括输入/输出设备、存储器和中央处理单元（CPU,Ce n t r a l Pr o c e s s i n g Un i t）。它们之间的关系如图 A1-2 所示。图 A1-2：计算机组成框图 1）输入/输出（I/O）设备 输入输出设备是接收外部信息（如输入原始数据和程序）或用来向外部输出信息（如计 算结果）的功能部件，包括打印机、显示器、键盘、磁带机、扫描仪、鼠标器、光笔、触摸 屏、条形码阅读器等。2）中央处理单元（CPU,Ce n t r a l Pr o c e s s i n g Un i t）CPU 是计算机的核心，它主要由运算部件、控制器、寄存器组所组成：（2l）控制器 控制器的主要功能是按时钟提供的统一节拍，把程序中每一条指令所含的各基本操作进 行时序分配，并发出相应的控制信号，驱动各部件按照节拍有秩序地完成程序规定的操作内 容。（22）运算部件（ALU）运算部件是直接进行数据变换与运算的部件。运算部件主要由逻辑电路构成的加法器组 成。加法与逻辑运算是运算器最基本的操作，由它们可以进一步实现四则运算（加、减、乘、除）和逻辑操作（逻辑运算、条件运算等）。（23）寄存器组 运算部件进行计算需要输入两个操作数，并产生两个输出：结果和运算特征。运算特征 也称运算状态，如操作结果是否为零、是正还是负、有无进位、操作是加还是减等等，取得 这些操作特征的目的是为了决定下一步的操作。3）存储器 存储器是计算机的记忆装置，用以保存程序、原始数据以及中间结果。目前，计算机基 本上采用线性地址存取方式。每一个地址对应一个存储单元，存储单元可以按位（b i t）或 按字节（8b i t）、字（16b i t）、半字（8b i t）、双字（32b i t）等编址。在按字节编址的情况 下，每个存储单元存储一个字节（1By t e）信息。存储器中存储单元的数量称为该存储器的容量，它是评价计算机功能的重要指标之一。存储器容量愈大，所能存储的信息就越多，可处理的问题的复杂度就越高。容量、价格、存 取速度是评价计算机存储器的三大指标。但三者之间又互相制约：容量大，存取速度就要低；采用存取速度高的元件，成本就高；成本高，就不允许做得容量太大。为此，通常采用分级 存储方式来解决这三者之间的矛盾。最基本的分级存储结构是两级存储，即把存储器分为主（内）存储器与辅助（外）存储器两级。主存储器采用半导体存储器，辅助存储器采用磁介 质存储器。磁盘就是广泛使用的一种辅助存储器。为了进一步提高计算机的性能，在主存和 CPU 之间又增加一级比主存速度更高的高速缓冲存储器 Ca c h e，形成三级存储体系。13 存储系统 早期的诺伊曼计算机是以运算器为中心的，系统内各部件间的信息传送都要经过运算 器。随着计算机应用的深入和外部设备的发展，内存与外存等外部设备之间的信息交换日益 频繁，为适应这一情况，形成以存储器为中心的系统结构，主存同外部设备之间的信息交换 不再通过运算器。共享主存的多处理机的出现，更加强了存储p a g e 1器作为计算机系统的中心地位。这时，存储器除了要向一台或多台高速运行的 CPU 提供所需的指令和数据外，还要同并行工 作的外存及其它外设和终端等设备交换信息。存储系统的特性，已经成为影响整个系统最大 吞吐量的决定性因素。广义地讲，在一定条件下，物质性质的改变，就是对过程条件的记忆，如果这些物理性 质可检测并且与其相应过程条件之间有确定的一一对应关系，则可用做记忆元件。基于二进 制逻辑的电子计算机所要求的记忆元件应当有两个明确定义的物理状态，以分别表示两个逻 辑值，并且这两个状态可以被检测并转换成电信号。信息的存取速度取决于测量与改变元件 的记忆状态所需的时间，能满足这一要求的物质有机械的、磁的、电子的、光学的、化学的 和生物的等等。131 主存储器组成 目前，主存储器中所使用的记忆元件是电子的，即半导体的，包括：1）半导体 RAM（Ra n d o m Ac c e s s Me m o r y）记忆元件 随机存取存储器 RAM 要求能随机地对存储器中的任何单元进行存取，且与存取的时间和 该单元的物理位置无关。具体地说，它要求元件有如下记忆特性。l 有两种稳定状态；l 在外部信号的激励下，两种稳定状态能进行无限次相互转换；l 在外部信号激励下，能读出两种稳定状态；l 可靠地存储。2）半导体 ROM（Re a d On l y Me m o r y）记忆元件 ROM 是一种在机器运行过程中只能读出、不能写入信息的无源存储器，是一种非易失性 器件。它所存储的信息是用特殊方式写入的，主要用于存储器经常要用的一些固定信息。3）闪速存储器（Fl a s h m e m o r y）132 辅助存储器 辅助存储器是主存储器的后援存储设备，用以存放当前暂时不用的程序或数据。对辅助 存储器的基本要求是：容量大、成本低、可以脱机保存信息。目前主要有磁读写、光读写两 类，如磁盘、磁带、光盘、光磁盘等。1）软盘存储器 软盘存储器由软磁盘、软盘驱动器、软盘适配器三部分组成。它们是目前个人计算机中 应用最为广泛的一种辅助存储器。2）硬磁盘存储器 硬磁盘的盘片以铝合金为基体，因而“硬”，但存储原理与软磁盘相同，相对软盘，硬 盘存储器存储容量更大，访问速度更快。3）磁带存储器 磁带存储器是最早应用的磁表面存储器，其特点是存储容量大、价格便宜。4）光盘存储器 由于多媒体的发展，这促使了光盘技术的迅速发展。光盘存储器是把激光束聚焦成 l u m 左右的微小光点，使之能量高度集中，在记录介质上产生物理或化学变化而存储信息的。读 出时，激光束在介质上扫描，根据反射光的变化判断记录的数据。光盘存储技术记录密度高，存储容量大；可长期（60 年100 年）保存信息；成本低廉，易于大量复制；存储密度高，体积小，能自由更换盘片；是很好的大容量存储技术。但是光 盘的数据存取速率比磁盘低，目前一般为 50150MB/S，因此还不能完全取代磁盘。5）磁盘阵列 RAID RAID（Re d u n d a n t Ar r a ys o f In e x p e n s i v e Di s k）是并行处理技术在磁盘系统中的应用。它把多台小型的磁盘存储器（或光盘存储器）按一定的条件组织成同步化的阵列，利用类似 于存储器中的多体交叉技术，将数据展开存储在多台磁盘上，提高了数据传输的带宽，并用 冗余技术提高了系统的可靠性。14 输入/输出系统 输入/输出系统是计算机主机与外界交换信息时需要的硬、软件设备的总称，简称外设 系统。一般说来，外设系统的硬件由以下几个方面组成，这里主要介绍外部设备。1）外部设备：围绕主机而设置的各种信息媒体转换和传递的设备。2）设备控制器与接口：控制主机与外部设备之间的信息格式、交换过程、外部设备运 行状态的硬、软件，也称设备适配器，它与外部设备的特性有关。3）I/O 总线；主机与外部设备之间的信息传送通路。141 外部设备及其分类 “外部设备”也称为外围设备。它们是指计算机系统中，除主机以外，直接或间接与计 算机交换信息、改变信息媒体或载体形式的装置。从使用的角度，外部设备大致可以分为如 下三类。1）人机交互设备 人一机交互设备，就是用户和计算机间交流信息的设备，其功能是把用户可以识别的信 息媒体，转换成计算机可以识别的信息，如键盘、图形扫描仪、摄像机、语言识别器等；或 者把计算机处理的结果信息，转换为用户可以识别的信息媒体，如打印机、显示器、绘图仪、语音合成器p a g e 2等。2）机机通信设备 机机通信设备就是一台计算机与其他计算机或别的系统之间通信的设备，如两台相 同型号或不同型号之间的计算机利用电话线路进行通信时，所需的调制解调器（MODEM）以 及用计算机进行实时控制时的数/模（D/A，Ana l o g/Di g i t a l）模/数（A/D）转换设备等。3）计算机信息的驻在设备 计算机信息的驻在设备，即计算机的外存储设备，如磁盘、光盘、磁带等。这些已在前 面介绍过了。本节主要偏重于介绍人机交互设备。142 字符输入/输出设备 1）键盘 字符输入设备的实质是将要输入的字符转换成相应的 0、1 码。目前，键盘是最重要的 字符输入设备，键盘的基本组成元件是按键开关，它的种类很多，一般可分为触点式和无触 点式两大类。2）打印设备 打印设备是一种硬拷贝设备，它的作用是将输出信息打印在纸上，产生永久性记录。打 印设备种类繁多，有多种分类方法。按印字原理分类，可以分为：l 击打式：打印过程打印头要撞击纸。击打式打印机又分为活字式打印和点阵式打印；l 非击打式：采用电、磁、光、喷墨等物理、化学方法印刷字符，打印过程纸不被撞 击。如激光印字机（其技术来自复印机）、喷墨印字机等。按工作方式可以分为：l 串行打印机：逐字打印；l 行式打印机：一次输出一行。143 图形/图像设备 1）绘图仪 绘图仪与图形显示器相似而又不同，不同处在于它是输出永久性图形的设备，而图形显 示器是输出过程图形的设备，并且它们的结构元件不同；相似之处在于，它们形成图形的原 理相似，即按形成图形的元素，绘图仪也可以分为向量绘图仪和点阵绘图仪两类。（1）向量绘图仪 向量绘图仪，又称笔绘图仪，构成向量图形的基本元素是直线段。（2）点阵绘图仪 点阵绘图仪又称无笔绘图仪，组成点阵图形的基本元素是点，或称象素。属于点阵绘图 机的有静电绘图仪、喷墨绘图仪、热敏绘图仪和激光绘图仪等。2）摄象机和扫描仪（l）摄象机 摄象机是最直接的图像输入设备，它能把所摄图像经数字量化后变成数字图像存人磁 带、磁盘或光盘，以备放映。（2）扫描仪 扫描仪是能够全面而快速输入数据、文字和图形以及图像的输入设备。扫描仪从结构原 理上可分为两大类，一类是 CCD 作为光敏元件，另一类是以光导纤维作为光的传导元件。在 地理信息系统数据录入中，通过扫描仪得到图像数据，然后进行跟踪矢量化，是快速获取数 据的重要手段。144 定位及拾取设备 定位/拾取设备通过指点来读取（位于屏幕或图表、图形上的）坐标，以画出或修改图 形。按所拾取的坐标分为两类：拾取绝对坐标，如光笔和数字化仪；拾取相对坐标，如鼠标 器、跟踪球、操纵杆等。1）光笔 光笔是一种输入设备，用来检测信号，因为外形像支笔，所以叫光笔。其前端装有光敏 器件，后端用导线接到计算机上。当光敏端的笔尖接触屏幕时，产生的光电信号向计算机发 出中断脉冲信号，此瞬间显示存储器的地址就是光笔所指位置，计算机按操作人员的命令作 出响应或画图、编辑和修改。2）触摸屏 触模屏是一种能对物体的接触或靠近产生反应的定位设备。根据采用技术之不同，触摸 屏分为五类：电阻式、电容式、表面超声波式、扫描红外线式和压感式。3）数字化仪 在大量 GIS 应用中，一个至关重要的任务就是要把若干图形输入计算机中去。计算机不 能直接识别这些图形，必须数字化即将其坐标输入到计算机。专门实现这一功能的计算机外 部设备叫数字化仪。即所谓数字化仪是指专门用来读取图形信息的计算机输入装置。数字化仪设备比较简单，一般由两部分组成，第一部分是感应板部分（又叫画图板 Dr a w i n g Bo a r d，但叫感应板比较确切），第二部分是点设备（Po i n t i n g d e v i c e s）又叫传送 器或者游标。对于立式的数字化仪还有一个底座，是为了架感应板用的。数字化仪是计算机图形系统的输入设备。当画笔接触到其图形板上的某一位置时，会将 画笔位置的坐标转换为二进制的数字量，输入计算机，随着画笔的运动，可以把一个图形输 入到计算机中。数字化仪的种类较多，按测量坐标的原理，大体上可分为机电式、超声波式、磁致伸缩 式和电磁感应式四种，其中电磁感应式是目前最常见的数字化仪。4）鼠标器、跟踪球和操纵杆 鼠标器、跟踪球（也称轨迹球）和操纵杆，是与屏幕相配合拾取光标的相位坐标的输入 设备。145 虚拟现实设备p a g e 3 一个虚拟现实系统，可以分解为三个独立的、但又相互联系的感觉引导子系统，即视觉 子系统、听觉子系统和触觉动觉子系统。这三个子系统由虚拟环境产生器进行控制、协调，如图 A1-3 所示。命令 听觉子系统 虚 拟 数据 环 头及眼跟踪 境 视觉子系统 产 图形、图象 生 器 手跟踪 触觉/动觉子系统 数据 图 A1-3：VR 系统一般组成 1）虚拟环境产生器 虚拟环境产生器实质上是一个包括虚拟世界数据库的高性能计算机系统。该数据库包含 了虚拟环境中对象的描述以及对象的运动、行为及碰撞作用等性质的描述。虚拟环境产生器 的另一作用是生产图像。这些图像的生成必须在最短的时间延迟内考虑参与者头部的位置和 方向。虚拟环境产生器内的任何通信延迟都必将表现为视觉的滞后。如果这种滞后可以感知，在某种条件下就会使参与者产生晕眩的感觉。2）触觉/动觉子系统 为了增强虚拟环境中身临其境的感觉，必须给参与者提供一些诸如触觉等方面的生理反 馈，触觉反馈是指 VR 系统必须提供所能接触到的物体的触觉刺激，如物体表面纹理或甚至 包括触摸的感觉等。参与者感觉到物体的表面纹理等时，同时也感觉到运动阻力。当然，毫 无疑问 VR 系统中的触觉/动觉反馈是很难实现的。一旦实现，将极大地增强虚拟存在的感受。目前触觉/动觉系统中一个重要的部分是手跟踪和手势跟踪。它的一个已经实用化的设备是 数据手套（Da t a Gl o v e），如图 A1-4 所示。图 A1-4：数据手套 数据手套的机理主要依靠纤细的光导纤维和光线的直线传播特性。它选用非常适合于屈 伸的材料制成。对每一个指头都有一根光纤从手腕出发，经指尖绕回再到手腕处的光纤；一 端装有光信号源（LED），另一端装有测量光通量的光传感器件。在指关节处光纤表面切 有微小的豁口，当手指弯曲时豁口裂开有光通量漏掉。当人带上手套后手指伸直时，由于光 线的直线传播几乎能获得 100的输出光量，一旦手指弯曲则光量随弯曲程度而衰减。这种 光量的变化，在控制器里由模/数变换器（A/D）转换成数字量，向主计算机传送，并进行计 算、解释。目前，数据手套暂时只能输入手势语言信息，当人情不自禁地去“触摸”或抓放一个物 体时，数据手套便可以把这些手势信息转入（反馈）到虚拟环境产生器中。当然，为了反映 手在“抓摸”时的用力情况，还应有压力反馈，这个问题目前正在解决。3）视觉子系统 视觉是人类用以接收信息的主要器官。目前，VR 技术中最重要的一项技术是大视场双 眼体视显示技术。人类的视觉，是一个具有双眼坐标定位功能自然序列：人的两只眼睛同时看到周围世界 的同一个窗口，但由于两眼位置上的差别，在视网膜上各自生成略有差别的图像，这两 个图像通过大脑，被综合成一个含有景物深度的立体图像。VR 体视显示技术用以下两种方 案解决这一问题：一种是用两套主机分别计算并驱动对应左右眼的两个显示器；另一种是用 一套主机分时地为左右两眼产生相应的图像。图 A1-5：一种头盔式显示器及其分解图 目前，VR 显示装置的主流是头盔式显示器。图 A1-5 为头盔式显示器原理的分解图。当 然，最重要的还是要能在显示屏上产生清晰、逼真的图像。4）听觉子系统 通常听觉系统也安装在头盔显示器上。听觉子系统主要由声音合成、3D 声音定域和语 音识别组成，以给虚拟环境中的用户一个真实的声音环境。（l）声音合成 尽管听觉系统以比视觉系统低得多的频带宽度工作，但人的听觉系统很善于在众多的声 音中挑取特定的声音，作为对视觉摄取信息的补充。因此，在 VR 系统中加入声音合成装置 是十分必要的。当视觉系统处理某一事件时，听觉系统同时在后台工作。（2）3D 声音定域 为造成逼真的声音环境，就要使参与者能通过两耳因位置不同，所接受的声波的时差等，分辨出声源与自己的相对位置；即使参与者在头部运动时，也能感觉这种声音保持在原处不 变。为了达到这种效果，声音定域系统必须考虑参与者两个“耳廓”的高频滤波特性。参与 者头部的方向对于正确地空间化声音信号是很重要的。因此，虚拟环境产生器要为声音定域 装置提供头部的位置和方向信号。（3）语音识别 语音识别在输入数据大量时，是非常有效的。146 调制解调器 目前使用的计算机一般都是数字计算机，即在计算机中处理的是数字信号，而普通电话 线上传输的是音频信号。用普通电话线传输数字信号的效率是很低的。为了能用普通电话线 进行计算机通信，应当把要发送的数字信号先调制（Mo d u l a t e）成音频信号，送到目的地后 再解调（De m o d u l a t e）成数字信号。完成这一功能的设备称p a g e 4为调制解调器 MODEM。由于一台 计算机既要接收信号，又要发送信号，所以调制解调器既有调制功能，又有解调功能。调制 解调器是拨号接入方式下的关键设备。一些新的输入输出设备：随着计算机技术的发展，出现了一些新的、更加方便的输入输出设备，下面是其中的简 单介绍：源数据自动化设备：包括条形码阅读机，磁性墨水字符阅读机（用于支票上的数字）。语音录入：也称为“语音识别”，允许用户通过讲话向系统发出指令。数码相机：可以直接得到数字图像，并由软件进行进一步的处理。15 计算机系统性能 全面衡量一台计算机的性能要考虑多种指标，并且对不同的用途所侧重的方面不同。下 面从普遍应用的角度，介绍主要的几种性能指标。1）CPU 字长 CPU 字长是指 CPU 一次所能处理的位数。CPU 字长越长，表明 CPU 所能处理的数据的精 度越高，并且影响处理的速度。因为短字长的 CPU 对较大的数据要通过两次甚至多次运算 实现。目前微型计算机的字长从 8 位、16 位、32 位，到 64 位等。当然 CPU 字长越长，价格 就越高。为了适应不同的需要，并协调精度与成本，人们还设计了可变字长计算，如半字长、全字长、双字长等。2）主频率 CPU 工作的节拍是由主时钟控制的。主时钟不断地产生固定频率的时钟脉冲，时钟脉冲 的频率就是 CPU 的主频率。主频率越高，CPU 的工作节拍越快。这是影响机器运算速度的重 要参数。3）主存容量 主存用以直接与 CPU 交换信息。主存容量大，处理问题的能力就强。同时由于它与外存 之间的信息交换次数少，解题时间效率高。计算机的最大主存容量由 CPU 的地址总线的根数 决定。地址总线为 16 条时，CPU 的最大寻址范围为 64K；地址总线为 20 条时，CPU 的最大 寻址范围为 1M。目前，微机地址总线为 32 条，最大寻址空间为 4G。4）软、硬件配置及性能价格比 软、硬件配置包括外部设备的配备情况，指令系统以及操作系统功能的强弱、界面是否 友好，有无其它支持软件和应用软件等。性能价格比是人们对经济效益的选择，这个值越大 越好。5）RASIS 特性 可靠性（Re l i a b i l i t y）、可用性（Av a i l a b i l i t y）、可维护性（Se r v i c e b i l i ty）、完整 性（In t e g r a l i t y）和安全性（Se c u r i t y）统称 RASIS。它们是衡量一个现代化的计算机系 统性能的五大功能特性。6）兼容性 所谓兼容性（Co m p a t i b i l i t y），是指系统间所含的某些“东西”具有并存性，即意味着 两个系统之间存在着一定程度的通用性，它使机器能承前启后、便于推广。2数据库系统基础 目前，数据库管理系统（DBMS,Da t a Ba s e Ma n a g e m e n t Sy s t e m）正日益进入最终用户的 日常应用，人们每天都在日常生活中用到数据库，如使用信用卡购物、订票、书目查询等等，在使用过程中，用户不需要了解数据的具体存取和管理方式，正是数据管理系统提供了这些 功能。21 数据库的基本概念 定义数据库管理系统之前，必须首先定义这种系统的基本成分数据库，一个数据库 有四个主要成分：数据、（Re l a t i o n s h i p）约束 联系、（Co n s t r a i nt）和模式（Sc h e m a）（图 A1-6）。数据是所存储的逻辑实体在计算机中的二进制表示；联系表示数据项之间的某种对应；约束 是定义正确数据状态的断言；一种模式描述数据库中数据的组织和联系。数据项 联系 数据库 约束 模式 图 A1-6：数据库组成 模式为数据库管理系统各个组成部分的使用和应用的安全定义数据库的各种视图。模式 将数据存储的物理外表与逻辑表示分开（见图 A1-7）。内部模式定义数据在物理数据存储区 中如何组织以及放在何处。概念模式模型按照适当的数据库数据模型（如关系模型或对象模 型）定义所存储数据的结构。外部模式为特定用户们定义数据库的一个或多个视图。外部模式 1 外部模式 1 外部模式 n 内部模式 内部模式p a g e 5 物理数据库 图 A1-7：数据库模式的概念 数据库管理系统为访问数据库提供服务，同时维护存储数据所要求的正确性和一致性。在数据库管理系统中，运行的工作单元是事务（Tr a n s a c t i o n）单元，在此之上定义了一 致性和正确性。事务应该支持 ACID 属性。ACID 属性包括：事务运行的原子性（At o m i c）、一致性（Co n s i s t e n t）、独立性（Is o l a t i o n）和事务执行的持久性（Du r a b i l i t y）。1）原子性确保事务被当成一个不可分割（Al l o r No t h i n g，要么全做，要么根本不做）的操作单元处理。2）事务操作的一致性确保数据库从原来的一致性状态正确转移到一个新的一致性状态，此处的一致性由数据库中数据项上的谓词定义。3）事务的独立属性定义了允许它们可见什么。一个被孤立的事务只“看到”数据库的 一个视图，就好像事务是单独在数据库上执行一样。4）持久性属性确保一旦提交了一个事务，其结果就持久存在且不能从数据库中消除。2.2 数据库的数据模型 按照描述数据与数据间关系的方法不同，数据库常用的数据模型有层次模型、网状模型 和关系模型。221 层次模型 层次模型是一种基本层次联系的集合，它实际上是一种有根定向的有序树，如图 A1-8 所示。层次模型的基本结构是树结构根、枝、叶结构，数据存放的基本单位是片断（即 层），片断是内在有逻辑联系的一组数据，总的来说，层次模型按照树形结构以片断为单位 存放数据。层次模型比较容易实现，但是查找比较麻烦，数据的冗余度也比较大。道路 R2 时令路 R8 公路 R9 R3 R4 大车路 R10 R11 单 轨 铁 路 R5 铁路 R12 窄 轨 铁 路 R6 乡村路 R13 R7 小路 R14 双 轨 铁 路 2 层 公 路 简 易 公 路 建 筑 中 公 路 建 筑 中 铁 路 3 层 图 A1-8：数据库层次模型 222 网状模型 所谓网状模型是指一个连通的基本层次联系的集合，如图 A1-9 所示。复杂的网总可以 分解成若干个基本结构，即分解成系。系有系主（只有一个）和系属（可以有多个），系主 和系属之间有关系，而且关系是双向的。R1 工人数 R2 农民数 R3 干部数 R4 知识分子 R6 有职业人口数 R7 流动人口数 R9 总人口数 R11 人口 图 A1-9：网状模型示例 网状模型存放的基本单位是记录，也就是按记录存放，查询时，从系（系主和系属）查 起。网状模型查找时间较省，数据和冗余度比层次模型小，但比关系模型要大。R8 居住人口数 R10 人口密度 无职业人口数 R5 223 关系模型 关系模型是目前最为流行的数据模型，它是由许多二维关系表组成的集合。例如表 1 就是一张关系表，R是关系名，Ai 是属性名，关系和属性（R,A1,A2An）组成了数据表的模，一 式(Sc h e m a)；Vi j 叫做分量，表中的一列是一个属性，相当于一个数据项（或数据元素）行叫做个元组（Tu p l e），相当于一条记录。关系模型中所有数据都按表格存放，有关系的数据放在一张表上，表与表之间有连接。表 A1-1：关系表 R Aj An A2 A1 Vl j Vl n V11 V12 Vi 2 Vi l Vi j Vi n Vm j Vm n 关系模型的特点是每一个分p a g e 6量必须是不可分割的数（数据元素），也就是不允许表中还 有表。另外表和表之间的联系要用关系表示，而不是用其它表示。关系模型查找很方便，数据冗余度小，但关系联结时效率较低。关系表的操作可以分为以下四种：1）通用的集合操作，如并、交、差运算等；2）去除关系表的某些部分的操作，包括选择(Se l e c t i o n)和投影(Pr o j e c t i o n)，前者去除某 些元组，后者则用于除去某些属性；3）两个关系表的合并，包括“笛卡尔积”以及各种方式的连接运算；4）更名操作，即对关系表属性名称的修改，它不改变元组，但是改变了关系表的模式。下面以常见的学生管理例子说明这些操作：学生关系表 R1 Vm 1 Vm 2 姓名 Ca r o l a Ma x w e l l Ch u r c h i l l 姓名 Jo h ns o n Ma x w e l l Ba r b a r a Wi l l i a m s 年龄 20 21 18 年龄 17 21 24 20 性别 女 男 男 性别 男 男 女 女 学生关系表 R2 学生成绩表 R3 姓名 语文 数学 Jo h n s o n A A Ma x w e l l B A Ba r b a r a A A Wi l li a m s A C Ca r o l a C C Ch u r c h i l l C B 对 R1 和 R2 进行求交集运算的结果（R4）姓名 Ma x w e l l 年龄 21 性别 男 对 R1 和 R2 进行求并集运算的结果（R5）姓名 Jo h n s o n Ma x w e l l Ba r b a r a Wi l l i a m s Ca r o l a Ch u r c h i l l 姓名 Jo h n s o n Ma x w e l l Ba r b a r a Wi l l i a m s Ca r o l a Ch u rc h i l l 年龄 17 21 24 20 20 18 年龄 17 21 24 20 20 18 性别 男 男 女 女 女 男 性别 男 男 女 女 女 男 语文 A B A A C C 数学 A A A C C B 对 R5 和 R3 根据“姓名”进行连接操作结果（R6）对 R6 选择“性别=“男”，并且对姓名、语文、数学成绩进行投影的结果（R7）”姓名 语文 数学 Jo h n s o n A A Ma x w e l l B A Ch u r c h i l l C B 关 系 数 据 库 的 查 询 和 修 改 操 作 是 通 过 SQL(结 构 化 查 询 语 言，St r u c t u r e d Qu e r y La n g u a g e)，SQL 的基础是关系代数，同时也包括了其它的一些操作，如求和、汇总、数据 更新等等，下面是一个 SQL 查询的例子：对于关系：省份（省会，人口，产值，面积）SQL 语句：Se l e c t *Fr o m 省份 Wh e r e 人口60,000,000 a n d 面积160,000 用于查询得到人口大于 6 千万并且面积小于 16 万平方公里的省份。224 面向对象数据库模型 网络和层次以及关系模型都适合那些结构简单以及访问有规律的数据。这些模型的最佳 应用领域有个人记录管理，清单控制，终端用户销售，商业记录等，所有这些应用领域都只 有相当简单的数据结构、联系以及数据使用模式。但是，当试图把这三种模型应用于更高级 的领域时，数据不能用类似于记录这样的简单结构来表示了，访问和操作方法也不再简单。这些应用领域需要更复杂的抽象数据类型，如图形，声音，图标，包，清单，队列，以及地 图，这些数据类型都各自定义了独特的操作方法例如，一个地图对象可以定义为经度、纬度、地点的时间维；以等高线来定义地形；用图标表示主要的嵌入对象，而他们本身也可 能是对象。除了这些定义之外，在地图的各区域可能还含有隐藏的数据。我们可以表示人口 密度、动物密度、植物、水源、建筑物及其类别（例如，单个住宅楼，高楼，工业建筑，居 民楼）、污染情况以及其他信息，所有这些都是从应用领域典型使用中派生出来的抽象数据 类型（图 A1-10）。图 A1-10：地图抽象数据类型 面向对象数据库的引入就是为了满足一再出现的复杂信息的共享。在复杂数据进入数据 库以后，数据库提供了存贮信息的统一视图，与具体存贮结构无关。把物理数据结构与逻辑 数据结构分开，同时控制数据的共享及保持数据的正确性、完整性和一致性，大大方便了应 用程序的开发和维护，减少生命周期内的各种费用。通过一组优化的程序来管理数据，使得 整体效果更优，性能更稳定。2.3 数据库管理系统 数据库管理系统（DBMS）是为数据库访问提供服务的软件，同时维护所有数据必需的 特性。数据库管理系统为支持应用程序访问和操作数据库数据提供下列服务：1）事务处理 事务将使数据库从一个一致状态转移到另一个一致状态。数据库操作被分成两大类：数 据访问操作和事务操作。有三种特定的事务操作：启动（St a r t）指示将开始一个新事务，提 交（Co m m i t）指示事务已正常终止且其作用结果将持久存在，以及放弃（Ab o r t）指示事务 被异常终止，其所有结果将被放弃。事务通常需要具p a g e 7有前面提到过的 ACID 属性。2）并发控制 并发控制是一种数据库管理活动，它协调数据库操作进程的并发操作和对共享数据的访 问，并且解决它们之间可能发生的潜在冲突。并发控制机制的目标是允许并发维护共享数据 的一致性，数据库系统中的并发单元是事务。3）恢复 数据库中恢复的目标是确保异常终止或出错的事务不会对数据库或其他事务产生不利 影响。异常终止的事务有两种影响；对数据的影响和对其他事务的影响。恢复可使得数据库 在事务异常终止后返回某个一致状态。4）安全 安全是保护数据免受非授权的泄露、更改或破坏。每个用户和应用程序都有特定的数据 访问特权。这些特权可以由外部模式定义，即根据各个用户被允许访问和/或修改的数据，给予它们不同的数据视图。安全系统提供一些方法，来决定每个用户或应用程序可访问什么 视图。通过授权和身份鉴别过程，安全还具有限制初始访问数据库的功能。这些过程中最常 用的是注册名和口令保护服务。5）语言接口 DBMS 提供对用于定义和操作数据的语言的支持。概念模式是用数据定义语言（Da t a De f i n i t i o n La n g u a g e，DDL）说明的。这种数据库语言部件是用来描述数据、数据间联系和 对数据和联系的约束的表示法。DDL 首先用在数据库设计时，以后修改模式时还会用到 DDL。数据操纵语言（Da t a Ma n i p u l a t i o n La n g u a g e，DML）用于表达数据库上的操作。DML 有时也称为查询语言。DBMS 提供 DML，以便用户和应用程序编写者访问数据库中数据，而不必知道数据库如何存储数据或把数据存在何处。6)容错性 不管发生什么故障仍能继续提供可靠 DBMS 服务的能力称为容错性。一个出错的数据 库部件将使与其交互的其他部件产生故障。典型的数据库故障包括违反约束和事务超时错 误。如上所述，恢复与容错性密切相关，因为恢复是一种机制，它能容许发生使事务异常终 上的差错。7)数据目录 数据目录（有时称为数据字典）是一个系统数据库，它含有主数据库中数据的描述（有 时被称为元数据，Me t a d a t a）。它包含有关数据、联系、约束的信息，以及将这些特征组织 到一个统一数据库中的所有模式的信息。通过查询目录可获得有关主要数据库结构的信息，因而目录被看成一个数据库。8）存储管理 DBMS 提供数据持久存储的管理机制。内部模式定义数据应该如何用存储管理机制存 储。为了访问物理存储，存储管理系统与操作系统间有接口。3数据结构和算法 3.1 数据结构的概念 311 数据结构一个例子 从提出一个实际问题到计算机解出答案需要经过下列步骤：首先从实际问题抽象出一个 数学模型，然后设计一个解此数学模型的算法，最后编出程序、进行测试、调整直至得到最 终解答。寻求数学模型的实质是分析问题，从中提取操作的对象以及这些操作对象之间含有 的关系，然后用数学语言加以描述。例如，在分析了一个物理现象或化学现象变化的规律之 后可以得到一组代数方程或微分方程。然而，更多的问题无法用数学方程加以描述。下面用 一个例子来说明数据结构。多叉路口交通灯的管理问题。通常，在十字交叉的路口只要设红绿两色的交通灯便可保 持正常的交通秩序，而在多叉路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞而又 达到最大的流通呢？假设有如图 A1-11（a）所示的五叉路，其中 C 和 E 为单行道，在路口 有 13 条可行的通路，其中有的可以同时通行，如 AB、和 EC，而有的不可同时通行，如 EB 和 AD，那末，在路口应如何设置交通灯进行管理？这个问题可以转换成一个图的染 色问题。假设在图上以一个圆圈表示一条通路，在不能同时通行的两个圆圈之间画一连线，对图中的圆圈上色，要求同一连线上的两个圆圈不同色且颜色种类最少。图 A1-11（b）是 与图 A1-11（a）相应的图，图中 13 个圆圈表示 13 条通路，圆中的号码分别表示四种颜色 的交通灯。图 11:五叉路口交通管理意图（a）三叉路口（b）表示通路的图 由以上例子可见，描述这样一类问题的数学模型不再是数值方程，而是诸如表、树和图 等的非数值性的数据结构。因此，简单说来，数据结构就是一门研究非数值性程序设计中计 算机操作的对象以及它们之间的关系和运算等的学科。312 基本术语 下面是数据结构中常用到的名词和术语的含义：1）数据（Da t a）数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号 的集合。它是计算机程序加工的“原料”。例如，一个利用数值分析的方法解代数方程的程p a g e 8 序处理的对象只是整数和实数，而一个编译程序或文字处理程序的对象是字符串。因此，对 计算机而言，数据的含义极为广泛，如图形、声音等都属于数据的范畴。2）数据元素（Da t a El e m e n t）是数据的基本单位，即数据这个集合中的一个个体（客体）。有时一个数据元素可由若 干个数据项（d a t a i t e m）组成，数据项是数据的最小单位。3）数据对象（Da t a Ob j e c t）是具有相同特性的数据元素的集合，是数据的一个子集。例如，整数的数据对象是集合 N，-2，-1，0，1，2，字母字符的数据对象是集合 CA，B，Z。4）数据结构（Da t a St r u c t u r e）简单说来，数