本章内容、图片较多，为全书重点！建议配合文章右侧目录观看本章。
本章涉及到数据库、算法与数据结构——线性表、栈、队列、树与二叉树等相关知识。
本章右侧目录忽略以2开头的标题分级，全部以6开头的标题分级以及子标题为准。
由于篇幅较多，课后习题见下一章。
由于篇幅较多，“计算机的世界-课外拓展”栏目在本章停止。

第六章

软件开发基础

6.1 数据库设计基础

6.1.1 数据库系统的基本概念

数据库（DB）是依照某种数据模型组织起来并存放在计算机外存储器中的数据的集合。

数据库管理系统（DBMS）是一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、数据控制及数据保护等。

数据库系统（DBS）是指计算机系统中引进数据库技术后的整个系统，包括：系统硬件平台、系统软件平台、数据库管理系统、数据库、数据库系统管理员及用户等部分，它们构成了一个以数据库为核心的完整运行实体。

数据库管理技术发展至今已经历了人工管理、文件系统和数据库系统三个阶段。

数据库在其内部具有三级模式和二级映射。三级模式分别是概念级模式、内部级模式与外部级模式。二级映射则分别是概念级到内部级的映射以及外部级到概念级的映射。

6.1.2 数据模型

数据描述就是以符号的形式，从满足用户需求出发，对客观事物的属性及其运动状态进行描述。也就是说，要将客观事物转换成计算机能够处理的数据。
这种转换分为两个阶段：由现实世界开始，经历信息世界，最终转换至计算机世界。

数据模型是数据特征的抽象，它是对数据库如何组织数据的一种模型化表示。

数据模型所描述的内容包含三个部分，它们是数据结构、数据操作与数据约束。

数据模型按不同的应用层次分成三种类型：概念数据模型、逻辑数据模型和物理数据模型。

2023年12月26日 P283-287

层次模型的基本结构是树形结构。

层次模型与树形结构一样，具有下列特征：
1.有且仅有一个无双亲节点，称为根（root）。
2.树中除根外所有节点有且仅有一个双亲。

网状模型具有以下特点：
1.有一个以上节点无双亲。
2.一个双亲允许有多个子女。
3.允许且至少有一个节点有多于一个双亲。

关系模型是将数据组织成二维表格的形式，通过表格来描述实体的属性及实体间的联系的数据模型。

在关系模型中，表格第一行的全部栏目称为关系框架，也成为关系模式。
表格中的每一列均称为属性，属性的第一行称为属性名，其他行称为属性值，整个表格称为一个关系。

二维表中的每行数据称为元组，每行中的各个数据称为元组的分量。

作为关系的二维表必须要满足下面7个性质：

1.元组个数有限性。
2.元组唯一性。
3.元组次序无关性。
4.元组分量的原子性。
5.属性名唯一值。
6.属性次序无关性。
7.分量值域的同一性。

关键字是一个关系中的一个或多个属性的集合，它能唯一地标识关系中每一个元组。

关系操纵是建立在关系上的数据操纵，一般有查询、增加、删除及修改4种操作。

关系模型允许定义三类数据约束，它们是实体完整性约束、参照完整性约束以及用户自定义的完整性约束。

2023年12月26日 P287-289

6.1.3 关系运算

关系型数据库管理系统具有严谨的数学理论基础-关系代数。

关系数据库中的集合运算主要有：并（∪）、差（-）、交（∩）和笛卡尔积（×）。

关系运算主要有选择（σ）、投影（π）和连接（⊳⊲）。

选择运算：将一个关系中满足条件的元组选出来，组成一个新关系。
投影运算：从一个关系中选择所需要的属性，组成一个新关系。
连接运算：连接运算是从两个关系中抽取全部或部分属性拼接起来，组成一个新关系。

自然连接需要满足下面的条件：
1.两关系间有公共属性。
2.通过公共属性的相等值进行连接。
3.去掉重复属性。

6.1.4 数据库设计与管理

数据库设计的六个阶段：

1.需求分析。
2.概念结构设计。
3.逻辑结构设计。
4.物理结构设计。
5.数据库实施。
6.数据库运行和维护。

E-R称为实体-联系方法
E-R图称为实体关系图

E-R图中包括实体、属性、联系和连线四种基本图素。
实体用方框表示，属性用椭圆框表示，联系用菱形框表示。

逻辑结构设计阶段主要工作是将概念结构设计阶段产生的E-R图转换成与具体的数据库管理系统所支持的数据模型相一致的逻辑结构模型。

数据库物理结构指的是数据库在实际的物理设备上的存储结构和存取方法。

数据库实施阶段的工作就是根据逻辑结构设计和物理结构设计的结果，在选用DBMS（数据库管理系统）上建立起数据库。

数据库实施具体有以下三项工作：
1.建立数据库的结构。
2.载入实验数据并测试应用程序。
3.载入全部实际数据并试运行应用程序。

数据库的运行和维护主要工作包括：
1.数据库的调整。
2.数据库的重组。
3.数据库的安全性控制与完整性控制。
4.数据库的故障恢复和数据库的监控。

2023年12月27日 P289-296

6.1.5 Access 2010数据库及其应用

Access是关系型数据库管理系统。

Access 2010数据库主要包括6种对象，分别是表、查询、窗体、报表、宏和模块。

在Access 2010数据库中创建表分为两个步骤：创建表结构和向表中输入数据。

在Access中，查询的结果称为结果集。

Access常见的查询类型有：选择查询、参数查询、交叉表查询、操作查询和SQL查询。

2023年12月27日 P296-305

6.2 算法与数据结构

6.2.1 数据结构的基本概念

数据：计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。

数据项：具有独立意义的最小数据单位。

数据元素：是数据集合中的一个具体的实体，是数据的基本单位。

数据对象：是具有相同特性的数据元素的集合，是数据的一个子集。

数据结构：计算机存储、组织数据的方式，反映一个数据的内部构成。

常见的数据结构有：线性结构、树形结构和图形结构。

数据结构包含以下三个方面的内容：
1.数据逻辑结构。
2.数据存储结构。
3.数据运算。

数据的逻辑结构有两大类：
1.线性结构。
2.非线性结构。

树形、图形都是非线性结构。

数据的存储结构可以用以下四种基本的存储方法实现：
1.顺序存储。
2.链接存储。
3.索引存储。
4.散列存储。

最常用的数据运算有检索、插入、删除、更新、排序。

6.2.2 算法

算法是人们在解决问题时采用的一种思维方法和过程，是解题方法和途径的一种描述。

算法一般应具有以下几个基本特征：

1.有零个或多个输入。
2.有一个或多个输出。
3.有效性。
4.确定性。
5.有穷性。

一个算法通常由两种基本要素组成：
1.对数据对象的运算和操作。
2.算法的控制结构。

常用的算法设计方法：

1.列举法。
2.迭代法。
3.归纳法。
4.递推。
5.递归。

列举法：根据问题，列举出所有可能情况，从中找出符合条件的相关项。
迭代法：寻找近似解来解决问题。
归纳法：列举少量特殊情况，经过分析，最后找出一般关系。
递推：从已知条件出发，逐次推出所要求的各中间结果和最后结果。
递归：将复杂问题分解为同类的子问题，再沿着分解路径逐步回推求解。

常用的算法描述方式：

1.自然语言。
2.伪代码。
3.程序流程图。
4.N/S盒图。
5.PAD图（问题分析图）。

算法的时间度量记作T(n)=O(f(n))，简称时间复杂度。

算法的时间复杂度按数量级递增排列，依次为常数阶O(1)、对数阶log_2⁡n、线性阶O(n)、线性对数阶n∙log_2⁡n、平方阶O(n^2)、立方阶O(n^3)、指数阶O(2^n)、阶乘阶O(n!)。

算法空间复杂度：算法耗费的存储空间，包括存储算法本身占用空间、算法输入输出数据占用空间和算法运行临时占用空间。

2023年12月28日 P305-311

6.2.3 线性表

alt text
图6-1 线性表在顺序存储结构下的插入与删除

线性表是由n个具有相同数据类型的数据元素构成的有限序列。

线性表中节点的个数n称为线性表的长度。

在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。

在用一维数组存放线性表时，该一维数组的长度通常要定义的比线性表实际长度大一些，以便对线性表进行各种运算，特别是插入运算。

2023年12月28日 P311-313

6.2.4 栈

alt text
图6-2 栈示意图

栈是一种特殊线性表，其插入与删除运算都只在线性表的一端进行。

在栈中，允许插入与删除的一端被称为栈顶，而不允许插入与删除的另一端称为栈底。

栈是按照“先进后出”或“后进先出”的原则组织数据的。

在栈中插入一个元素称为入栈运算，从栈中删除一个元素称为退栈运算。

在程序设计语言中，用一维数组S(1:m)作为栈的顺序存储空间，其中m为栈的最大容量。

栈的基本运算有三种：入栈、退栈与读栈顶元素。
alt text
图6-3 栈在顺序存储结构下的运算

入栈：在栈顶位置插入一个新元素。
退栈：取出栈顶元素并赋给一个指定的变量。
读栈顶元素：将栈顶元素赋给一个指定的变量。

当栈顶指针指向存储空间的最后一个位置时，说明栈空间已满，不能进行入栈操作。这种情况称为栈“上溢”。
当栈顶指针为0时，说明栈空，不能进行退栈操作。这种情况称为栈“下溢”。

6.2.5 队列

alt text
图6-4 队列示意图

队列是指允许在一端进行插入，而在另一端进行删除的线性表。

在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。
alt text
图6-5 队列运算示意图

队列是“先进先出”或“后进后出”的线性表。

在队列的队尾插入一个元素称为入队运算，从队列的队头删除一个元素称为退队运算。

6.2.6 树与二叉树

1.树的基本概念

alt text
图6-6 一般的树

树是一种简单的非线性结构。

在树的图形表示中，总是认为在用直线连起来的两端节点中，上端节点是前趋，下端节点是后继。

树结构基本术语：
1.根节点：节点的前趋称为父节点。没有前趋的节点称为根节点，简称为树的根。图6-6中，节点A是树的根节点。
2.叶子节点：节点的后继称为子节点。没有后继的节点称为叶子节点。图6-6中，K、E、I、J均为叶子节点。
3.节点的度：一个节点的子节点的个数称为该节点的度。图6-6中，根节点A的度为2；节点B、C的度为2；节点D、H、F、G的度为1；叶子节点的度为0.。
4.树的度：所有节点中最大的度称为树的度。图6-6所示的树的度为2.。
5.节点的层次：根节点在第一层。同一层上所有节点的所有子节点都在下一层。图6-6中，根节点A在第一层；节点B、C在第二层；节点D、E、F、G在第三层；节点H、I、J在第四层；节点K在第五层。
6.树的深度：树的最大层次称为树的深度。图6-6所示的树的深度为5。
7.子树：以某节点的一个子节点为根构成的树称为该节点的一颗子树。图6-6中，节点A有2棵子树。

2023年12月29日 P313-316

2.二叉树及其基本性质

alt text
图6-7 二叉树

(1)二叉树的概念

二叉树是n个节点的有限集合，这个有限集合或者为空集，或者由一个根节点及两棵不相交的、分别称作这个根的左子树和右子树的二叉树组成。

在二叉树中，每一个节点的度最大为2，即所有子树也均为二叉树。

(2)二叉树的基本性质

性质1：在二叉树的第i层上，最多有2^i-1个节点。
性质2：深度为k的二叉树最多有2^k-1个节点。
性质3：在任意一棵二叉树中，度为0（即叶子节点数n_0）的节点个数总是比度为2的节点个数（n_2）多一个，即：n_0=n_2+1。
性质4：具有n个节点的二叉树，其深度至少为[log_2⁡n]+1，其中[log_2⁡n]表示取log_2⁡n的整数部分。