第一章数据结构与算法1.1算法算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等于计算机方法,程序的编制不可能优于算法的设计。算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括:(1)可行性;(2)确定性,算法中每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许有多义性;(3)有穷性,算法必须能在有限的时间内做完,取能在执行有限个步骤后终止,包括合理的执行时间的含义;(4)拥有足够的情报。算法的基本要素:一是对数据对象[1]的运算和操作;二是算法的控制结构[2]。指令系统:一个计算机系统能执行的所有指令的集合。基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输[3]。算法的控制结构:列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度:算法时间复杂和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2数据结构的基本概念数据结构研究的三个方面:(1)数据集合中和数元素之间所固有的逻辑关系,即数据的逻辑结构;(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;数据的特点:有一定的结构,有型与值之分,如整型、实型、字符型等。而数据的值给出了符合定型的值,如整型值15。数据库:是数据的集合,具有统一的结构形式并存放于统一的存储介质内,是多种应用数据的集成,并可被各个应用程序共享。数据库存放数据是按数据所提供的数据模式存放的,具有集成与共享的特点。数据库管理系统:一种系统软件,负责数据库中的数据组织[4]、数据操纵、数据维护、控制及保护和数据服务[5]等,是数据库的核心。数据库管理系统功能:(1)数据模式定义:即为数据库构建其数据框架;(2)数据存取的物理构建:为数据模式的物理存取与构建提供有效的存取方法[6]与手段;(3)数据操纵:为用户使用数据库的数据提供方便,如查询、插入、修改、删除等以及简单的算术运算及统计;(4)数据的完整性、安生性定义与检查;(5)数据库的并发控制[7]与故障恢复;(6)数据的服务:如拷贝、转存、重组、性能监测、分析等。为完成以上六个功能,数据库管理系统提供以下的数据语言:(1)数据定义语言:负责数据的模式定义与数据的物理存取构建;(2)数据操纵语言[8]:负责数据的操纵,如查询与增、删、改等;(3)数据控制语言:负责数据完整性[9]、安全性的定义与检查以及并发控制、故障恢复等。数据语言按其使用方式具有两种结构形式:交互式命令(又称自含型或自主型语言)宿主型语言(一般可嵌入某些宿主语言[10]中)。数据库管理员:对数据库进行规划、设计、维护、监视等的专业管理人员。数据库系统:由数据库(数据)、数据库管理系统(软件)、数据库管理员(人员)、硬件平台(硬件)、软件平台(软件)五个部分构成的运行实体。数据库应用系统:由数据库系统、应用软件及应用界面三者组成。文件系统[11]阶段:提供了简单的数据共享与数据管理能力,但是它无法提供完整的、统一的、管理和数据共享的能力。层次数据库与网状数据库系统阶段 :为统一与共享数据提供了有力支撑。关系数据库系统阶段数据库系统的基本特点:数据的集成性 、数据的高共享性与低冗余性 、数据独立性(物理独立性与逻辑独立性)、数据统一管理与控制。数据库系统的三级模式:(1)概念模式[12]:数据库系统中全局数据逻辑结构的描述,全体用户公共数据视图;(2)外模式[13]:也称子模式与用户模式。是用户的数据视图,也就是用户所见到的数据模式;(3)内模式[14]:又称物理模式,它给出了数据库物理存储结构与物理存取方法。数据库系统的两级映射:(1)概念模式到内模式的映射;(2)外模式到概念模式的映射。4.2 数据模型数据模型的概念:是数据特征的抽象,从抽象层次上描述了系统的静态特征、动态行为和约束条件,为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。E-R模型的基本概念(1)实体:现实世界中的事物;(2)属性:事物的特性;(3)联系:现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。E-R模型三个基本概念之间的联接关系:实体是概念世界中的基本单位,属性有属性域,每个实体可取属性域内的值。一个实体的所有属性值叫元组[15]。E-R模型的图示法:(1)实体集表示法[16]; (2)属性表法; (3)联系表示法。层次模型的基本结构是树形结构,具有以下特点:(1)每棵树有且仅有一个无双亲结点[17],称为根;(2)树中除根外所有结点有且仅有一个双亲。从图论上看,网状模型是一个不加任何条件限制的无向图[18]。关系模型采用二维表来表示,简称表,由表框架及表的元组组成。一个二维表就是一个关系。在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键,则称该属性集为A的外键或外码。关系中的数据约束:(1)实体完整性[19]约束:约束关系的主键中属性值不能为空值[20];(2)参照完全性约束:是关系之间的基本约束;(3)用户定义的完整性约束[21]:它反映了具体应用中数据的语义[22]要求。4.3关系代数[23]关系数据库系统的特点之一是它建立在数据理论的基础之上,有很多数据理论可以表示关系模型的数据操作,其中最为著名的是关系代数与关系演算[24]。关系模型的基本运算:(1)插入 (2)删除 (3)修改 (4)查询(包括投影、选择、笛卡尔积运算)4.4 数据库设计[25]与管理数据库设计是数据应用的核心。数据库设计的两种方法:(1)面向数据:以信息需求为主,兼顾处理需求;(2)面向过程:以处理需求为主,兼顾信息需求。数据库的生命周期:需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段[26]、运行阶段、进一步修改阶段。需求分析常用结构析方法和面向对象的方法。结构化分析(简称SA)方法用自顶向下[27]、逐层分解的方式分析系统。用数据流图[28]表达数据和处理过程的关系。对数据库设计来讲,数据字典是进行详细的数据收集和数据分析所获得的主要结果。数据字典是各类数据描述的集合,包括5个部分:数据项[29]、数据结构、数据流(可以是数据项,也可以是数据结构)、数据存储、处理过程。数据库概念设计的目的是分析数据内在语义关系。设计的方法有两种(1)集中式模式设计法(适用于小型或并不复杂的单位或部门);(2)视图集成设计法。设计方法:E-R模型与视图集成。视图设计一般有三种设计次序:自顶向下、由底向上、由内向外。视图集成的几种冲突:命名冲突、概念冲突、域冲突、约束冲突。关系视图设计:关系视图的设计又称外模式设计。关系视图的主要作用:(1)提供数据逻辑独立性;(2)能适应用户对数据的不同需求;(3)有一定数据保密功能。数据库的物理设计主要目标是对数据内部物理结构作调整并选择合理的存取路径,以提高数据库访问速度有效利用存储空间。一般RDBMS中留给用户参与物理设计的内容大致有索引设计、集成簇设计和分区设计。数据库管理的内容:(1)数据库的建立;(2)数据库的调整;(3)数据库的重组;(4)数据库安全[30]性与完整性控制[31];(5)数据库的故障恢复;(6)数据库监控(3)对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含:(1)表示数据元素的信息;(2)表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。线性结构[32]条件:(1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。非线性结构[33]:不满足线性结构条件的数据结构。1.3线性表[34]及其顺序存储[35]结构线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。非空线性表的结构特征:(1)且只有一个根结点a ,它无前件;(2)有且只有一个终端点a ,它无后件;(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。线性表的顺序储结构具有以下两个基本特点:(1)线性表中所有元素的所占的存储空间是连续的;(2)线性表中各数元素在存储空间中是按逻辑顺序依次存放的。