1、1.1算法 1、度词是指解题方案的准确而完整的描述。换句话说,算法是对特定问题求解步骤的一种描述。*:算法不等于程序,也不等于计算方法算法的基本特征(1)可行性。针对实际问题而设计的算法,执行后能 够得到满意的结果。(2)确定性。每一条指令的含义明确,无二义性。并 且在任何条件下,算法只有唯一的一条执行路径,即 相同的输入只能得出相同的输出。(3)有穷性。算法必须在有限的时间内完成。有两重 含义,一是算法中的操作步骤为有限个,二是每个步 骤都能在有限时间内完成。(4)拥有足够的情报。算法中各种运算总是要施加到 各个运算对象上,而这些运算对象又可能具有某种初 始状态,这就是算法执行的起点或依据。
2、因此,一个 算法执行的结果总是与输入的初始数据有关,不同的 输入将会有不同的结果输出。当输入不够或输入错误 时,算法将无法执行或执行有错。一般说来,当算法 拥有足够的情报时,此算法才是有效的;而当提供的 情报不够时,算法可能无效。3、算法复杂度主要包括时间复杂度和空间复杂度。(1)算法|时间复杂度|是指执行算法所需要的计算工作 量,可以用执行算法的过程中所需基本运算的执行次 数来度量。(2)算法|空间复杂阖是指执行这个算法所需要的内存 空间。1.2数据结构的基本概念1、|数据结构|是指相互有关联的数据元素的集合。2、数据结构主要包括:(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑
3、结构。数据的逻辑结构包含:1)表示数据元素的信息;2)表示各数据元素之间的前后件关系。图(多对多)(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。数据的存储结构有顺序、链式等。1)顺序存储。它是把逻辑上相邻的结点存储在物理位 置相邻的存储单元里,结点间的逻辑关系由存储单元 的邻接关系来体现。由此得到的存储表示称为顺序存 储结构。2)链式存储。它不要求逻辑上相邻的结点在物理位置 上亦相邻,结点间的逻辑关系是由附加的指针字段表 示的。由此得到的存储表示称为链式存储结构。*:数据的逻辑结构反映数据元素之间的逻辑关系,数 据的存储结构(也称数据的物理结构)是数据的逻辑 结构
4、在计算机存储空间中的存放形式。同一种逻辑结 构的数据可以采用不同的存储结构,但影响数据处理 效率。1.4栈和队列1、栈及其基本运算阀是限定在一端进行插入与删除运算的线性表。在栈中,允许插入与删除的一端称为栈顶,不允许插 入与删除的另一端称为栈底。栈顶元素总是最后被插 入的元素,栈底元素总是最先被插入的元素。即栈是 按照“先进后出”或“后进先出”的原则组织数据 的。2、队列及其基本运算画是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。尾指针(Rear)指向队 尾元素,头指针(front)指向排头元素的前一个位置(队头)。队列是“先进先出”或“后进后出”的线性表。1.6树与二叉
5、树1、树的基本概念网是一种简单的非线性结构。在树这种数据结构中,所有数据元素之间的关系具有明显的层次特性。在树结构中,每一个结点只有一个前件,称为固结点。没有前件的结点只有一个,称为树的根结点,简称树 的根。每一个结点可以有多个后件,称为该结点的国 Ho没有后件的结点称为|叶子结点。在树结构中,一个结点所拥有的后件的个数称为该圉 点的度|,所有结点中最大的度称为树的阂。树的最大 层次称为西深圃。2、二叉树及其基本性质(1)什么是二叉树二叉树|是一种很有用的非线性结构,它具有以下两个 特点:1)非空二叉树只有一个根结点;2)每一个结 点最多有两棵子树,且分别称为该结点的左子树与右 子树。*:根据
6、二叉树的概念可知,二叉树的度可以为0(叶 结点)、1(只有一棵毛照L品2(有2棵子树)。(2)二叉树的基本性质性质1在二叉树的第k层上,最多有 个结点。性质2深度为m的二2黄树最多有个 个结点。性质3在任意一棵二叉树盅虞蕉数为琥苗点后 叶子结点)总比度为2的结点多一个。性质4具有n 个结点的二叉树,其深度至少为,其中表示取 的整数部分。3、满二叉树与完全二叉树满二叉树:除最后一层外,每一层上的所有结点都有 两个子结点。完全二叉树:除最后一层外,每一层上的结点数均达 到最大值;在最后一层上只缺少右边的若干结点。*:根据完全二叉树的定义可得出:度为1的结点的个 数为0或1。下图a表示的是满二叉树,
7、下图b表示的是完全二叉 树:完全二叉树还具有如下两个特性:性质5具有n个结点的完全二叉树深度为log 2+1 性质6设完全二叉树共有n个结点,如果从根结点 开始,按层序(每一层从左到右)用自然数1,2,n给结点进行编号,则对于编号为k(k=l,2,,n)的结点有以下结论:若k=l,则该结点为根结点,它没有父结点;若kl,则该结点的父结点的编号为INT(k/2)o若2kWn,则编号为k的左子结点编号为2k;否则 该结点无左子结点(显然也没有右子结点)。若2k+lWn,则编号为k的右子结点编号为2k+l;否则该结点无右子结点。5、二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结 点。二叉树
8、的遍历可以分为以下三种:(1)前序遍历(DLR):若二叉树为空,则结束返回。否则:首先访问根结点,然后遍历左子树,最后遍历 右子树;并且,在遍历左右子树时,仍然先访问根结 点,然后遍历左子树,最后遍历右子树。(2)中序遍历(LDR):若二叉树为空,则结束返回。否则:首先遍历左子树,然后访问根结点,最后遍历 右子树;并且,在遍历左、右子树时,仍然先遍历左 子树,然后访问根结点,最后遍历右子树。(3)后序遍历(LRD):若二叉树为空,则结束返回。否则:首先遍历左子树,然后遍历右子树,最后访问 根结点,并且,在遍历左、右子树时,仍然先遍历左 子树,然后遍历右子树,最后访问根结点。1.7查找技术查找:
9、根据给定的某个值,在查找表中确定一个其关 键字等于给定值的数据元素。查找结果:(查找成功:找到;查找不成功:没找到。)平均查找长度:查找过程中关键字和给定值比较的平 均次数。1、顺序查找基本思想:从表中的第一个元素开始,将给定的值与 表中逐个元素的关键字进行比较,直到两者相符,查 到所要找的元素为止。否则就是表中没有要找的元素,查找不成功。在平均情况下,利用顺序查找法在线性表中查找一个 元素,大约要与线性表中一半的元素进行比较,最坏 情况下需要比较工次。顺序查找一个具有n个元素的线性表,其平均复杂度 为 0(n)oF列两种情况下只能采用顺序查找:1)如果线性表是无序表(即表中的元素是无序的),
10、则不管是顺序存储结构还是链式存储结构,都只能用 顺序查找。2)即使是有序线性表,如果采用链式存储结构,也只 能用顺序查找。2、二分法查找思想:先确定待查找记录所在的范围,然后逐步缩小 范围,直到找到或确认找不到该记录为止。前提:必须在具有顺序存储结构的有序表中进行。查找过程:1)若中间项(中间项mid二(n-1)/2,mid的值四舍五 入取整)的值等于x,则说明已查到;2)若x小于中间项的值,则在线性表的前半部分查找;3)若x大于中间项的值,则在线性表的后半部分查找。特点:比顺序查找方法效率高。最坏的情况下,需要 比较log2n次。*:二分法查找只适用于顺序存储的线性表,且表中元 素必须按关键
11、字有序(升序)排列。对于无序线性表 和线性表的链式存储结构只能用顺序查找。在长度为 n的有序线性表中进行二分法查找,其时间复杂度为0(log2n)o 1.8排序技术 排序是指将一个无序序列整理成按值非递减顺序排列 的有序序列,即是将无序的记录序列调整为有序记录 序列的一种操作。1、交换类排序法(方法:冒泡排序,快速排序)。2、插入类排序法(方法:简单插入排序,希尔排序)。3、选择类排序法(方法:简单选择排序,堆排序)。总结:各种排序法比较:第二章程序设计基础类别排序方法基本思想时间复杂度交换类冒泡排序相邻元素比较,不满足条件时交换n(n-l)/2快速排序选择基推元素,通过交换,划分成两个子序列
12、0(nlogjn)插入类简单插入排序待排序的元素看成为一个有序表和一个无序表,将无序表中元素插入到有序表中n(n-l)2希尔排序分割成若干个子序列分别进行直接插入排序。吐)邮类简单选择排序扫描整个线性表,从中选出最小的元素,将它交换到表的最前面堆排序选建堆,然后将堆顶元素与堆中最后一个元素交 换,再调整为堆O(nlogjn)2.1 程序设计风格程序设计的风格主要强调:“清晰第一,效率第二主要应注重和考虑下述一些因素:(1)源程序文档化。1)符号名的命名。符号名能反映它所代表的实际东西,应有一定的实际含义。2.2 结构化程序设计(面向过程的程序设计方法)1、结构化程序设计方法的主要原则可以概括为
13、:ms 向下,逐步求精,模块化,限制使用goto语句。(1)自顶向下。程序设计时,应先考虑总体,后考虑 细节;先考虑全局目标,后考虑局部目标。不要一开 始就过多追求众多的细节,先从最上层总目标开始设 计,逐步使问题具体化。(2)逐步求精。对复杂问题,应设计一些子目标作过 渡,逐步细化。(3)模块化。一个复杂问题,肯定是由若干稍简单的 问题构成。模块化是把程序要解决的总目标分解为分 目标,再进一步分解为具体的小目标,把每个小目标 称为一个模块。(4)限制使用goto语句。2、结构化程序的基本结构:顺序结构,选择结构,重 复结构。1)顺序结构。一种简单的程序设计,即按照程序语句 行的自然顺序,一条
14、语句一条语句地执行程序,它是 最基本、最常用的结构。2)选择结构。又称分支结构,包括简单选择和多分支 选择结构,可根据条件,判断应该选择哪一条分支来 执行相应的语句序列。3)重复结构。又称循环结构,可根据给定的条件,判 断是否需要重复执行某一相同的或类似的程序段。仅仅使用顺序、选择和循环三种基本控制结构就足以 表达各种其他形式结构,从而实现任何单入口/单出口 的程序。2.3 面向对象的程序设计客观世界中任何一个事物都可以被看成是一个对象,面向对象方法的本质就是主张从客观世界固有的事物 出发来构造系统,提倡人们在现实生活中常用的思维 来认识、理解和描述客观事物,强调最终建立的系统 能够映射问题域
15、。也就是说,系统中的对象及对象之 间的关系能够如实地反映问题域中固有的事物及其关 系。面向对象方法的主要优点:(1)与人类习惯的思维方 法一致;(2)稳定性好;(3)可重用性好;(4)易于 开发大型软件产品;(5)可维护性好。*:面向对象的程序设计主要考虑的是提高软件的可重 用性。刘国是面向对象方法中最基本的概念,可以用来表示 客观世界中的任何实体,对象是实体的抽象。面向对 象的程序设计方法中的对象是系统中用来描述客观事 物的一个实体,是构成系统的一个基本单位,由一组 表示其静态特征的属性和它可执行的一组操作组成。对象是属性和方法的封装体。回国即对象所包含的信息,它在设计对象时确定,一 般只能
16、通过执行对象的操作来改变。操同描述了对象执行的功能,操作也称为方法或服务。操作是对象的动态属性。*:一个对象由对象名、属性和操作三部分组成。对象的基本特点:标识惟一性,分类性,多态性,封 装性,模块独立性好。(1)标识惟一性。指对象是可区分的,并且由对象的 内在本质来区分,而不是通过描述来区分。(2)分类性。指可以将具有相同属性的操作的对象抽 象成类。(3)多态性。指同一个操作可以是不同对象的行为。(4)封装性。从外面看只能看到对象的外部特性,即 只需知道数据的取值范围和可以对该数据施加的操 作,根本无需知道数据的具体结构以及实现操作的算 法。对象的内部,即处理能力的实行和内部状态,对 外是不
17、可见的。从外面不能直接使用对象的处理能力,也不能直接修改其内部状态,对象的内部状态只能由 其自身改变。*:信息隐蔽是通过对象的封装性来实现的。(5)模块独立性好。对象是面向对象的软件的基本模 块,它是由数据及可以对这些数据施加的操作所组成 的统一体,而且对象是以数据为中心的,操作围绕对 其数据所需做的处理来设置,没有无关的操作。从模 块的独立性考虑,对象内部各种元素彼此结合得很紧 密,内聚性强。国是指具有共同属性、共同方法的对象的集合。所以 类是对象的抽象,对象是对应类的一个实例。逋是一个实例与另一个实例之间传递的信息。消息 的组成包括:(1)接收消息的对象的名称;(2)消息 标识符,也称消息
18、名;(3)零个或多个参数。*:在面向对象方法中,一个对象请求另一个对象为其 服务的方式是通过发送消息。S3是指能够直接获得已有的性质和特征,而不必重 复定义他们。继承分单继承和多重继承。单继承指一 个类只允许有一个父类,多重继承指一个类允许有多 个父类。*:类的继承性是类之间共享属性和操作的机制,它提 高了软件的可重用性。磊忸是指同样的消息被不同的对象接受时可导致完 全不同的行动的现象。第三章软件工程基础3.1软件工程基本概念|软件工程|是应用于计算机软件的定义、开发和维护的 一整套方法、工具、文档、实践标准和工序。软件工 程的目的就是要建造一个优良的软件系统,它所包含 的内容概括为以下两点:
19、1)软件开发技术,主要有软件开发方法学、软件工具、软件工程环境。2)软件工程管理,主要有软件管理、软件工程经济学。软件工程的主要思想是将工程化原则运用到软件开发 过程,它包括3个要素:方法、工具和过程。方法是 完成软件工程项目的技术手段;工具是支持软件的开 发、管理、文档生成;过程支持软件开发的各个环节 的控制、管理。软件工程过程是把输入转化为输出的一组彼此相关的 资源和活动。3、软件生命周期软件生命周期软件产品从提出、实现、使用维护到 停止使用退役的过程。软件生命周期分为软件定义、软件开发及软件运行维 护三个阶段:1)软件定义阶段:包括制定计划和需求分析。制定计划:确定总目标;可行性研究;探
20、讨解决方案;制定开发计划。需求分析:对待开发软件提出的需求进行分析并给出 详细的定义。2)软件开发阶段:软件设计:分为概要设计和详细设计两个部分。软件实现:把软件设计转换成计算机可以接受的程序代码。软件测试:在设计测试用例的基础上检验软件的各个 组成部分。3)软件运行维护阶段:软件投入运行,并在使用中不 断地维护,进行必要的扩充和删改。*:软件生命周期中所花费最多的阶段是软件运行维护 阶段。2、结构化分析方法结构化分析方法是结构化程序设计理论在软件需求分 析阶段的应用。结构化分析方法的实质:着眼于数据流,自顶向下,逐层分解,建立系统的处理流程,以数据流图和数据 字典为主要工具,建立系统的逻辑模
21、型。结构化分析的常用工具:1)数据流图(DFD);2)数 据字典(DD);3)判定树;4)判定表。数据流图|以图形的方式描绘数据在系统中流动和处理 的过程,它反映了系统必须完成的逻辑功能,是结构 化分析方法中用于表示系统逻辑模型的一种工具。加工 数据流 存储文件 源、潭上图是数据流图的基本图形元素:3、软件需求规格说明书(SRS)软件需求规格说丽利是需求分析阶段的最后成果,通 过建立完整的信息描述、详细的功能和行为描述、性 能需求和设计约束的说明、合适的验收标准,给出对 目标软件的各种需求。软件设计的基本原理包括:抽箜、模块化、信息隐蔽 和模块独立性。模块的耦合性和内聚性是衡量软件的模块独立性
22、的两 个定性指标。百困性:是一个模块内部各个元素间彼此结合的紧密 程度的度量。一个设计良好的软件系统应具有高内聚、低耦合的特 征。在结构化程序设计中,模块划分的原则是:模块内具 有高内聚度,模块间具有低耦合度。3.4软件测试1、软件测试定义:使用人工或自动手段来运行或测定 某个系统的过程,其目的在于检验它是否满足规定的 需求或是弄清预期结果与实际结果之间的差别。*:软件测试的目的:尽可能地多发现程序中的错误,不能也不可能证明程序没有错误。2、软件测试方法:静态测试和动态测试。静态测试|:包括代码检查、静态结构分析、代码质量 度量。不实际运行软件,主要通过人工进行。动态测试|:是基于计算机的测试
23、,主要包括白盒测试 方法和黑盒测试方法。(1)白盒测试白盒测试方法也称为结构测试或逻辑驱动测试。它是 根据软件产品的内部工作过程,检查内部成分,以确 认每种内部操作符合设计规格要求。(2)黑盒测试黑盒测试方法也称为功能测试或数据驱动测试。3、软件测试过程一般按4个步骤进行:单元测试、集 成测试、确认测试和系统测试。3.5程序的调试程序调试的任务是诊断和改正程序中的错误,主要在 开发阶段进行,调试程序应该由编制源程序的程序员 来完成。第四章数据库设计基础4.1 数据库系统的基本概念1、数据、数据库、数据管理系统(1)数据:实际上就是描述事物的符号记录。数据的特点:有一定的结构,有型与值之分。数据
24、的 型给出了数据表示的类型,如整型、实型、字符型等。而数据的值给出了符合给定型的值,如整型(INT)值 15o(2)|数据库(DB:是数据的集合,具有统一的结构 形式并存放于统一的存储介质内,是多种应用数据的 集成,并可被各个应用程序所共享。数据库存放数据是按数据所提供的数据模式存放的,具有集成与共享的特点,亦即是数据库集中了各种应 用的数据,进行统一的构造和存储,而使它们可被不 同应用程序所使用。(3)|数据库管理系统系BMS)|:一种系统软件,负责 数据库中的数据组织、数据操纵、数据维护、控制及 保护和数据服务等,是数据库的核心。数据库管理系统功能:1)数据模式定义。数据库管理系统负责为数
25、据库构建 模式,也就是为数据库构建其数据框架。2)数据存取的物理构建。数据库管理系统负责为数据 模式的物理存取与构建提供有效的存取方法与手段。3)数据操纵。数据库管理系统为用户使用数据库中的 数据提供方便,它一般提供如查询、插入、修改以及 删除数据的功能。此外,它自身还具有做简单的算术 运算及统计的能力,而且还可以与某些过程性语言结 合,使其具有强大的过程性操作能力。4)数据的完整性、安生性定义与检查。数据库中的数 据具有内在语义上的关联性与一致性,它们构成了数 据的完整性,数据的完整性是保证数据库中数据正确 的必要条件,因此必须经常检查以维护数据正确。数 据库中的数据具有共享性,而数据共享可
26、能会引发数 据的非法使用,因此必须要对数据正确使用做出必要 的规定,并在使用时做检查,这就是数据的安全性。数据完整性与安全性的维护是数据库系统的基本功 能。5)数据库的并发控制与故障恢复。数据库是一个集成、共享的数据集合体,它能为多个应用程序服务,所以 就存在着多个应用程序对数据库的并发操作。在并发 操作中如果不加控制和管理,多个应用程序间就会相 互干扰,从而对数据库中的数据造成破坏。因此,数 据库管理系统必须对多个应用程序的并发操作做必要 的控制以保证数据不受破坏,这就是数据库的并发控 制。数据库中的数据一旦遭到破坏,数据库管理系统 必须有能力及时进行恢复,这就是数据库的故障恢复。6)数据的
27、服务。数据库管理系统提供对数据库中数据 的多种服务功能,如数据拷贝、转存、重组、性能监 测、分析等。(4)|数据库管理员(DBA)|:对数据库进行规划、设 计、维护、监视等的专业管理人员。(5)|数据库系统 系威”:由数据库(数据)、数据 库管理系统(软件)、数据库管理员(人员)、硬件 平台(硬件)、软件平台(软件)五个部分构成的运 行实体。(6)数据库应用系统:由数据库系统、应用软件及应 用界面三者组成。*:数据库技术的根本目标是解决数据的共享问题。2、数据库系统的发展数据库管理发展至今已经历了三个阶段:人工管理阶 段、文件系统阶段和数据库系统阶段。下表是数据管理三个阶段的比较:人工管理 阶
28、段文件系统阶段数据库系统阶段背 景应用背 景科学计算科学计算、管 理大规模管理硬件背 景无直接存 取存储设备磁盘、磁鼓大容量磁备盘软件背 景没有操作 系统有义件系统有数据库管理系 统处理方 式批处理联机实时处 理、批处理联机实时处理、分布处理、批处 理特 点数据的 管理者用户(程序 员)文件系统数据库管理系统数据面 向的对 象某一应用 程序某一应用现实世界数据的无共享,冗共享性差,冗共享性高,冗余共享程 度余度极大余度大度小数据的 独立性不独立,完 全依赖于 程序独立性差具后图度的物理 独立性和一定的 逻辑独立性数据的 结构化无结构记录内有结构,整体无结 构整体结构化,用 数据模型描述数据控
29、制能力应用程序 自己控制应用程序自己 控制由数据库管理系 统提供数据安全 性、完整性、并 发控制和恢复能 力3、数据库系统的基本特点(1)数据的高集成性。(2)数据的高共享性与低冗余性。*:数据库系统可以减少数据冗余,但无法避免一切冗 余。(3)数据独立性:|数据独立性|是数据与程序间的互不 依赖性,即数据库中数据独立于应用程序而不依赖于 应用程序。也就是说,数据的逻辑结构、存储结构与 存取方式的改变不会影响应用程序。数据独立性一般分为物理独立性与逻辑独立性两级。1)I物理独立性卜物理独立性即是数据的物理结构(包 括存储结构,存取方式等)的改变,如存储设备的更 换、物理存储的更换、存取方式改变
30、等都不影响数据 库的逻辑结构,从而不致引起应用程序的变化。2)|逻辑独立性|:数据库总体逻辑结构的改变,如修改 数据模式、增加新的数据类型、改变数据间联系等,不需要相应修改应用程序,这就是数据的逻辑独立性。(4)数据统一管理与控制。数据统一管理与控制主要包含以下三个方面:1)数据的完整性检查:检查数据库中数据的正确性以 保证数据的正确。2)数据的安全性保护:检查数据库访问者以防止非法 访问。3)并发控制:控制多个应用的并发访问所产生的相互 干扰以保证其正确性。4、数据库系统的内部结构体系(1)数据库系统的三级模式:1)概念模式|:数据库系统中全局数据逻辑结构的描述,是全体用户(应用)公共数据视
31、图。2)怀时 也称子模式或用户模式,它是用户的数据 视图,也就是用户所见到的数据模式,它由概念模式 推导而出。3)|内模式|:又称物理模式,它给出了数据库物理存储 结构与物理存取方法。内模式的物理性主要体现在操 作系统及文件级上,它还未深入到设备级上(如磁盘 及磁盘操作)。内模式对一般用户是透明的,但它的 设计直接影响数据库的性能。(2)数据库系统的两级映射:1)概念模式/内模式的映射|:实现了概念模式到内模 式之间的相互转换。当数据库的存储结构发生变化时,通过修改相应的概念模式/内模式的映射,使得数据库 的逻辑模式不变,其外模式不变,应用程序不用修改,从而保证数据具有很高的物理独立性。2)收
32、卜模式/概念模式的映射|:实现了外模式到概念模 式之间的相互转换。当逻辑模式发生变化时,通过修 改相应的外模式/逻辑模式映射,使得用户所使用的那 部分外模式不变,从而应用程序不必修改,保证数据 具有较高的逻辑独立性。4.2数据模型1、数据模型(1)数据模型的概念:是数据特征的抽象,它从抽象 层次上描述了系统的静态特征、动态行为和约束条件,为数据库系统的信息表示与操作提供一个抽象的框 架。(2)数据模型所描述的内容有三个部分,它们是数据 结构、数据操作与数据约束。1)数据结构:数据结构是所研究的对象类型的集合,包括与数据类型、内容、性质有关的对象,以及与数 据之间联系有关的对象。它用于描述系统的
33、静态特性。2)数据操作:数据操作是对数据库中各种对象(型)的实例(值)允许执行的操作的集合,包括操作的含 义、符号、操作规则及实现操作的语句等。它用于描 述系统的动态特性。3)数据的约束条件:数据的约束条件是一组完整性规 则的集合。完整性规则是给定的数据模型中数据及其 联系所具有的制约和依存规则,用以限定符号数据模 型的数据库状态及状态的变化,以保证数据的正确、有效和相容。(3)数据模型分为概念模型、逻辑数据模型和物理模 型三类:1)概念数据模型:简称概念模型,是对客观世界复杂 事物的结构描述及它们之间的内在联系的刻画。概念 模型主要有:E-R模型(实体联系模型)、扩充的E-R 模型、面向对象
34、模型及谓词模型等。2)逻辑数据模型:又称数据模型,是一种面向数据库 系统的模型,该模型着重于在数据库系统一级的实现。逻辑数据模型主要有:层次模型、网状模型、关系模 型、面向对象模型等。3)物理数据模型:又称物理模型,它是一种面向计算 机物理表示的模型,此模型给出了数据模型在计算机 上物理结构的表示。2、实体联系模型及E-R图(1)E-R模型的基本概念:1)实体:现实世界中的事物。2)属性:事物的特性。3)联系:现实世界中事物间的关系。实体集的关系有对对多、多对多的联系。E-R模型三个基本概念之间的联接关系:1)实体集(联 系)与属性间的联接关系;2)实体(集)与联系。*:E-R模型的基本成分是
35、实体和联系。(2)E-R模型的图示法:1)实体集:用矩形表示。2)属性:用椭圆形表示。3)联系:用菱形表示。4)实体集与属性间的联接关系:用无向线段表示。5)实体集与联系间的联接关系:用无向线段表示。(3)数据库管理系统常见的数据模型有层次模型、网 状模型和关系模型三种。1)层次模型的基本结构是树形结构,具有以下特点:A、每棵树有且仅有一个无双亲结点,称为根;B、树 中除根外所有结点有且仅有一个双亲。部门员工 商品2)网状模型是层次模型的一个特例,从图论上看,网 状模型是一个不加任何条件限制的无向图。(a)教学关系E-R图(b)工作与设备3)关系模型采用二维表来表示,简称表,由表框架及 表的元
36、组组成。一个二维表就是一个关系。二维表的表框架由n个命名的属性组成,n称为属性 元数。每个属性有一个取值范围称为值域。表框架对 应了关系的模式,即类型的概念。在表框架中按行可 以存放数据,每行数据称为元组,实际上,一个元组 是由n个元组分量所组成,每个元组分量是表框架中 每个属性的投影值。学号姓名,性另U出生年月班级籍贯2007102张洁然男07-07-8807动画1班天津*:同一个关系模型的任两个元组值不能完全相同。2007203李一明男05-01-8707播音5班)西南 宁2007305王丽女04-09-8807管理4班辽宁沈 阳2007406刘宏男10-11-8807新闻3班江苏南 京主
37、码:或称为关键字、主键,简称码、键,表中的一 个属性或几个属性的组合、其值能唯一地标识表中一 个元组的,称为关系的主码或关键字。例如,学生的 学号。主码属性不能取空值。外部关键字:或称为外键,在一个关系中含有与另一 个关系的关键字相对应的属性组称为该关系的外部关 键字。外部关键字取空值或为外部表中对应的关键字 值。例如,在学生表中含有的所属班级名字,是班级 表中的关键字属性,它是学生表中的外部关键字。(4)关系中的数据约束:1)|实体完整性约词:要求关系的主键中属性值不能为 空值,因为主键是唯一决定元组的,如为空值则其唯 一性就成为不可能的了。2)惨照完整性约束|:关系之间相互关联的基本约束,
38、不允许关系引用不存在的元组,即在关系中的外键要 么是所关联关系中实际存在的元组,要么为空值。3)|用户定义的完整性约束|:反映某一具体应用所涉及 的数据必须满足的语义要求。例如某个属性的取值范 围在0100之间等。3、从E-R图导出关系数据模型数据库的逻辑设计的主要工作是将E-R图转换成指定 RDBMS(关系数据库管理系统)中的关系模式。首先,从E-R图到关系模式的转换是比较直接的,实体与联 系都可以表示成关系,E-R图中属性也可以转换成关 系的属性。实体集也可以转换成关系。4.3关系代数1、关系的数据结构关系是由若干个不同的元组所组成,因此关系可视为 元组的集合。n元关系是一个n元有序组的集
39、合。关系模型的基本运算:1)插入;2)删除;3)修改;4)查询(包括投影、选择、笛卡尔积运算)。2、关系操纵关系模型的数据操纵即是建立在关系上的数据操纵,一般有查询、增力口、删除和修改四种操作。3、集合运算及选择、投影、连接运算(1)并(U):关系R和S具有相同的关系模式,R 和S的并是由属于R或属于S的元组构成的集合。(2)差(一):关系R和S具有相同的关系模式,R 和S的差是由属于R但不属于S的元组构成的集合。(3)交(A):关系R和S具有相同的关系模式,R 和S的交是由属于R且属于S的元组构成的集合。(4)广义笛卡尔积(X):设关系R和S的属性个数 分别为n、m,则R和S的广义笛卡尔积是
40、一个有(n+m)列的元组的集合。每个元组的前n 列来自R的一个元组,后口列来自S的一个元组,记为RXS。*:根据笛卡尔积的定义:有n兀关系R及口兀关系S,它们分别有P、q个元组,则关系R与S经笛卡尔积记 为RX S,该关系是一个n+m元关系,元组个数是pXq,由R与S的有序组组合而成。例:有两个关系R和S,分别进行并、差、交和广义 笛卡尔积运算。RRuSABCalblclalb2c2a2b2clalb3b2b2(c)R.AR.BR.CS.AS.BS.Calblclalb2c2alblclalb3c2alblclo2b2clalb2c2alb2c2alb2c2alb3c2alb2c2a2b2cl
41、a2b2clalb2c2立b2clalb3c2a2b2cla2b2cl(5)在关系型数据库管理系统中,基本的关系运算有选择、投影与联接三种操作:1)选择:选择指的是从二维关系表的全部记录中,把 那些符合指定条件的记录挑出来。2)投影:投影是从所有字段中选取一部分字段及其值 进行操作,它是一种纵向操作。3)联接:联接将两个关系模式拼接成一个更宽的关系 模式,生成的新关系中包含满足联接条件的元组。4.4数据库设计方法和步骤(1)数据库设计阶段包括:需求分析、概念分析、逻 辑设计、物理设计。(2)数据库设计的每个阶段都有各自的任务:1)I需求分析阶段I:这是数据库设计的第一个阶段,任 务主要是收集和分析数据,这一阶段收集到的基础数 据和数据流图是下一步设计概念结构的基础。2)|概念设计阶阂:分析数据间内在语义关联,在此基 础上建立一个数据的抽象模型,即形成E-R图。*:数据库概念设计的过程包括选择局部应用、视图设 计和视图集成。3)|逻辑设计阶网将E-R图转换成指定RDBMS中的关 系模式。4)胸理设计阶朝:对数据库内部物理结构作调整并选 择合理的存取路径,以提高数据库访问速度及有效利 用存储空间。