本书主要包括两大部分，*部分为数据结构，包括线性表、栈、队列、串、数组、树和图等，以及查找和排序等操作；第二部分为数据库技术，包括数据库系统概论、关系模型与关系代数，关系数据库标准语言SQL、数据库设计与优化、数据库安全与完整、事务管理与恢复等。 目录
*部分数 据 结 构
第1章绪论3
1.1数据结构的概念3
1.1.1数据结构的范畴3
1.1.2相关概念和术语4
1.2算法和算法分析7
1.2.1算法的基本概念7
1.2.2算法复杂度11
小结13
习题14第2章线性表15
2.1线性表的逻辑结构15
2.1.1线性表的定义15
2.1.2线性表的基本操作16
2.2线性表的顺序存储及运算实现17
2.2.1顺序存储的特点17
2.2.2顺序表上的运算实现17
2.3线性表的链式存储及运算实现21
2.3.1链式存储的特点22
2.3.2链表上的运算实现24
小结26
习题27第3章特殊线性表28
3.1栈28
3.1.1栈的定义28
3.1.2栈的存储及运算实现29
3.2队列31
3.2.1队列的定义31
3.2.2队列的存储及运算实现33
3.3串35
3.3.1串的定义35
3.3.2串的存储37
小结37
习题38第4章数组39
4.1数组的定义39
4.2数组的存储及运算实现40
小结42
习题42第5章树与二叉树43
5.1树43
5.1.1树的定义43
5.1.2相关术语44
5.2二叉树45
5.2.1二叉树的定义45
5.2.2二叉树的性质46
5.2.3二叉树的存储结构47
5.3二叉树的遍历48
小结50
习题50第6章图51
6.1图的定义和术语51
6.2图的存储表示53
6.3图的遍历55
小结57
习题58第7章查找59
7.1基本概念59
7.2静态查找表60
7.2.1顺序查找60
7.2.2折半查找61
7.2.3索引查找62
7.3动态查找表63
7.3.1二叉排序树64
7.3.2平衡二叉树66
7.4哈希表的查找66
小结69
习题69第8章排序70
8.1基本概念70
8.2插入排序71
8.2.1直接插入排序71
8.2.2希尔排序73
8.3交换排序74
8.3.1冒泡排序74
8.3.2快速排序76
8.4选择排序78
8.5归并排序79
小结81
习题82
第二部分数据库技术
第9章数据库系统概述85
9.1数据库系统的作用85
9.1.1数据与数据管理85
9.1.2数据库应用88
9.2数据库处理技术的发展过程91
9.2.1人工管理阶段91
9.2.2文件系统阶段92
9.2.3数据库系统阶段93
9.2.4高级数据库阶段95
9.3数据模型97
9.3.1概念模型97
9.3.2数据模型101
9.3.3层次模型103
9.3.4网状模型104
9.3.5关系模型106
9.3.6面向对象模型109
9.4数据库系统的结构111
9.4.1数据库系统的三级模式结构111
9.4.2数据库系统的二级映像113
9.4.3数据库体系结构114
9.5数据库管理系统117
9.5.1DBMS的工作模式117
9.5.2DBMS的主要功能118
9.5.3DBMS的组成119
小结120
习题121第10章关系模型与关系代数122
10.1关系模型122
10.2关系代数126
10.2.1集合的三种基本运算——交、并、差126
10.2.2关系的基本运算129
小结133
习题134第11章关系数据库标准语言——SQL135
11.1SQL概述及特点135
11.1.1SQL概述135
11.1.2SQL的特点136
11.1.3SQL的基本概念137
11.2SQL的数据定义138
11.2.1数据库的定义138
11.2.2基本表的定义141
11.2.3索引的定义147
11.3SQL的单表查询149
11.3.1SELECT语句概述149
11.3.2投影运算151
11.3.3选择运算153
11.3.4排序运算157
11.3.5查询表158
11.4SQL的连接查询159
11.4.1等值与非等值连接159
11.4.2自表连接162
11.4.3外连接163
11.5SQL的聚合查询166
11.5.1聚合函数166
11.5.2分组聚合167
11.6SQL的嵌套子查询169
11.6.1使用IN的子查询169
11.6.2使用比较运算符的子查询170
11.6.3使用存在量词EXISTS的子查询172
11.7集合运算173
11.8SQL的数据操纵174
11.8.1插入数据174
11.8.2更新数据176
11.8.3删除数据178
11.9视图179
11.9.1创建视图179
11.9.2查询视图181
11.9.3视图更新182
11.9.4删除视图183
小结184
习题184第12章数据库设计及优化189
12.1数据库设计方法189
12.1.1数据库和信息系统189
12.1.2数据库设计过程190
12.2需求分析192
12.2.1需求分析的任务192
12.2.2需求分析的步骤193
12.2.3需求分析的方法193
12.3概念结构设计195
12.3.1概念模型的基本概念195
12.3.2概念模型的表示方法195
12.3.3概念结构的特点196
12.3.4概念结构设计的方法197
12.3.5概念结构设计的步骤198
12.4规范化200
12.4.1关系模式规范化的必要性200
12.4.2函数依赖201
12.4.3范式与规范化203
12.4.4模式分解原则207
12.4.5规范化的本质分析与总结207
12.5逻辑结构设计208
12.5.1概念模型向关系模型的转换208
12.5.2数据模型的优化211
12.5.3数据库逻辑设计案例212
12.6数据库的物理设计214
12.6.1数据库物理设计的方法214
12.6.2确定数据库的物理结构215
12.6.3对物理结构进行评价216
12.7数据库的实施与维护216
12.7.1数据库的实施216
12.7.2数据库的维护218
小结219
习题219第13章数据库安全性与完整性221
13.1数据库安全性221
13.1.1数据库安全的基本概念221
13.1.2用户管理223
13.1.3角色管理225
13.2数据库完整性226
13.2.1完整性约束的概念和类型227
13.2.2完整性约束的管理228
13.3TransactSQL基础233
13.3.1SQL对象的命名规则和注释233
13.3.2数据类型233
13.3.3变量237
13.3.4函数239
13.3.5批处理和流程控制242
13.4游标246
13.4.1游标的使用247
13.4.2当前游标集的修改250
13.5存储过程252
13.5.1存储过程概述252
13.5.2创建和执行存储过程252
13.5.3修改和删除存储过程254
13.6触发器255
13.6.1触发器概述255
13.6.2创建触发器256
13.6.3删除和修改触发器258
小结259
习题259第14章事务管理与恢复260
14.1事务260
14.1.1并发操作时产生的问题260
14.1.2事务的概念262
14.1.3事务的特性263
14.2并发控制264
第5章树与二叉树
本章学习目标 掌握树的定义及相关术语。
 理解二叉树的定义及性质。
 了解二叉树的存储结构。
 掌握二叉树遍历的基本方法。

本章介绍的树状结构是一类重要的非线性结构,也是一种分层结构,其中以二叉树*为常用。因为在实际应用中,对于给定的问题,许多是能够抽取层级模型的,而树和二叉树是处理层次模型的典型结构。因此,我们研究树和二叉树的存储与应用是非常有实际意义的。
5.1树〖*4/5〗5.1.1树的定义树是一种简单的非线性结构。在树这种数据结构中,所有数据元素之间的关系具有明显的层次特性。图5.1一般的树
图5.1表示了一棵一般的树。由图5.1可以看出,在用图形表示树这种数据结构时,很像自然界中的树,只不过是一棵倒长的树,因此,这种数据结构就用“树”来命名。
在树的图形表示中,总是认为在用直线连起来的两端结点中,上端结点是前驱,下端结点是后继。这样表示前后继关系的箭头就可以省略。
树(Tree)是n(n≥0)个有限数据元素的集合。当n=0时,称这棵树是空树。在一棵非空树T中:
(1) 有一个特殊的数据元素称为树的根结点,根结点没有前驱结点。
(2) 当n＞1时,除根结点之外的其余数据元素被分为m(m＞0)个互不相交的集合T1,T2,…,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1,T2,…,Tm称为这个根结点的子树。
从树的定义可以看出,树具有下面两个特点。
(1) 树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。
(2) 树中所有结点可以有零个或多个后继结点。
在现实世界中,能用树这种数据结构表示的例子有很多。例如,图5.2中的树表示了学校行政关系结构。图5.2学校行政层次结构树由于树具有明显的层次关系,因此,树与二叉树都可以用树这种数据结构来描述。在所有的层次关系中,人们*熟悉的是血缘关系,按血缘关系可以很直观地理解树结构中各数据元素结点之间的关系,因此,在描述树结构时,也经常使用血缘关系中的一些术语。
抽象数据类型树的定义如下。ADT Tree {
数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:若D为空集,则称为空树。否则:
(1)在D中存在*的称为根的数据元素root;
(2)当n>1时,其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm,其中每一个子集本身又是一棵符合本定义的树,称为根root的子树。
基本操作:P={初始化树,销毁树,插入树,删除树,… }
} ADT Tree树的基本操作有以下几种。
(1) 初始化操作: InitTree (&T)。
初始条件: 树T不存在。
操作结果: 构造空树T。
(2) 销毁操作: DestroyTree (&T)。
初始条件: 树T存在。
操作结果: 销毁树T。
(3) 插入树操作: InsertChild(&T, &p, i, c)。
初始条件: 树T存在。
操作结果: 将以c为根的树插入为结点p的第i棵子树。
(4) 删除树操作: DeleteChild(&T, &p, i)。
初始条件: 树T存在。
操作结果: 删除结点p的第i棵子树。
5.1.2相关术语
下面介绍树这种数据结构中的一些基本术语。
(1) 根结点: 在树结构中,每一个结点只有一个前驱,称为父结点,没有前驱的结点只有一个,称为树的根结点,简称为树的根。例如,在图5.1中,结点A是树的根结点。
(2) 叶子结点: 在树结构中,每一个结点可以有多个后继,它们都称为该结点的子结点。没有后继的结点称为叶子结点。例如,在图5.1中,结点C、E、G、H、I、J均为叶子结点。
(3) 度: 在树结构中,一个结点所拥有的后继个数称为该结点的度。例如,在图5.1中,根结点A的度为3;结点B的度为2;叶子结点的度为0。在树中,所有结点中的*的度称为树的度。例如,图5.1所示的树的度为3。前面已经说过,树结构具有明显的层次关系,即树是一种层次结构。在树结构中,一般按如下原则分层: 根结点在第1层,同一层上所有结点的所有子结点都在下一层。例如,在图5.1中,根结点A在第1层;结点B、C、D在第2层;结点E、F、G、H在第3层;结点I、J在第4层。树的*层次称为树的深度。例如,如图5.1所示的树的深度为4。
(4) 孩子、双亲、兄弟: 在树中,以某结点的一个子结点为根构成的树称为该结点的一棵子树。树中某个结点的子树之根称为该结点的孩子,相应地,该结点称为孩子的双亲或父亲。例如,在图5.1中,结点B、C、D是A的孩子;A是B结点的双亲。同一个双亲的孩子称为兄弟,E、F是兄弟,B、C、D是兄弟。
(5) 有序树和无序树: 如果一棵树中结点的各子树之间存在确定的次序关系,称这棵树为有序树;反之,则称为无序树。
5.2二叉树
二叉树是树状结构的另一个重要类型,许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换成二叉树。二叉树的结构规律性强,其存储结构及其算法都较为简单,因此,二叉树特别重要。
5.2.1二叉树的定义
二叉树(Binary Tree)是一种很有用的非线性结构,它是n(n≥0)个结点的有限集合,它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。
二叉树具有以下两个特点。
(1) 非空二叉树只有一个根结点;
(2) 每一个结点*多有两棵子树,且分别称为该结点的左子树与右子树。
图5.3二叉树
由以上特点可以看出,在二叉树中,每一个结点的度*为2,即所有子树(左子树或右子树)也均为二叉树,而树结构中的每一个结点的度可以是任意的。另外,二叉树中的每一个结点的子树被明显地分为左子树与右子树。在二叉树中,一个结点可以只有左子树而没有右子树,也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时,该结点即是叶子结点。如图5.3所示是一棵深度为4的二叉树。
5.2.2二叉树的性质
二叉树具有下列重要特性。
性质1 在二叉树的第k层上,*多有2k-1个结点。
根据二叉树的特点,这个性质是显然的。
性质2深度为k的二叉树*多有2k-1个结点。
深度为k的二叉树是指二叉树共有k层。根据性质1,只要将第1层到第k层上的*的结点数相加,就可以得到整个二叉树中结点数的*值,即1 21 22 … 2k-1=2k-1一棵深度为k且有2k-1个结点的二叉树称为满二叉树。完全二叉树是由满二叉树而引出来的。对于深度为k,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称为完全二叉树。即除第k层外,其他各层 (1～k-1) 的结点数都达到*个数,第k层所有的结点都连续集中在*左边,这就是完全二叉树。
性质3在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个,即n0=n2 1对于这个性质说明如下: 假设二叉树中有n0个叶子结点,n1个度为1的结点,n2个度为2的结点,则二叉树中总的结点数为n=n0 n1 n2(51)在二叉树中除了根结点外,其余每一个结点都有*的一个分支进入。设二叉树中所有进入分支的总数为m,则二叉树中总的结点数为n,除了根结点,其余结点都有一个分支进入,即n=m 1。
又由于二叉树中这m个进入分支是分别由非叶子结点射出的,其中度为1的每个结点射出一个分支,度为2 的每个结点射出两个分支,因此,二叉树中所有度为1与度为2的结点射出的分支总数为n1 2n2。而在二叉树中,总的射出分支数应与总的进入分支数相等,即m=n1 2n2,于是得n=n1 2n2 1(52)*后比较式(51)和式(52),有n0 n1 n2=n1 2n2 1化简后得n0=n2 1。
即,在二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。
性质4具有n个结点的完全二叉树的深度为log2n 1。
证明: 设完全二叉树的深度为k,则根据性质2得2k-1≤n＜2k,即k-1≤log2n＜k,因为k只能是整数,因此,k=log2n 1。
性质5若对含n个结点的完全二叉树从上到下且从左至右进行1～n的编号,则对完全二叉树中任意一个编号为i的结点,有:
(1) 若i=1,则该结点是二叉树的根,无双亲;否则,其双亲结点编号为i/2,其左孩子结点编号为2i,右孩子结点编号为2i 1。
(2) 若2i＞n,则该结点无左孩子。
(3) 若2i 1＞n,则该结点无右孩子。
5.2.3二叉树的存储结构
二叉树也可以采用两种存储方式: 顺序存储结构和链式存储结构。
二叉树的《数据结构与数据库应用教程》是为“数据结构与数据库”课程编写的教材，也可作为学习数据结构与数据库技术的参考教材。本书的前半部分为数据结构，包括线性表、栈、队列、串、数组、树和图等，以及查找和排序等操作；后半部分为数据库技术，包括数据库系统概论、关系模型与关系代数，关系数据库标准语言SQL、数据库设计与优化、数据库安全与完整、事务管理与恢复等，*后以一个综合实例介绍了数据库应用系统的开发过程。本书概念清楚、重点突出、内容丰富、结构合理、思路清晰、示例翔实，每章后均附有习题。本书主要面向数据结构与数据库初学者，可作为信息管理与信息系统、计算机及相关专业的本科教学，也可供自学计算机基础知识的读者参考。............