一、关系模型
 
为什么学习关系模型？
 
我们可以通过关系模型这种简单的数据结构能够描述出现实世界的实体及实体间的各种联系。

 

 什么是关系模型？

 
关系模型的基本假定是所有数据都表示为数学上的关系，就是以集合的形式表示。关系模型是采用二维表格结构表达实体类型及实体间联系的数据模型。

 

 关系模型是1970年由E.F.Codd提出的。

 它和层次、网状模型相比，有以下特点：

 1.数据结构简单（二维表格）

 2.扎实的理论基础。

 a.关系运算理论

 b.关系模式设计理论

 

 几个重要定义

 域：

 
相同的数据类型，又名属性。

 笛卡尔积：

 
一组域D1，D2,D3...Dn的笛卡尔积为：

 
D1 x D2 x D3 x Dn = {(d1,d2,d3,...,dn) | di∈Di,i=1,2,3...n}

 
笛卡尔积的每个元素(d1,d2,d3...dn)称做一个n元组，元组的每一个值叫做一个分量。

 

 

 关系模型（二维表）

 

 


 

 
关系模型的基本术语共有十三个，它们分别是：
 
1、关系：一个关系对应着一个二维表，二维表就是关系名。
 
2、属性和值域：在二维表中的列，称为属性。属性的个数称为关系的元或度。列的值称为属性值；属性值的取值范围为值域。
 
3、关系模式：在二维表中的行定义，即对关系的描述称为关系模式
 
4、元组：在二维表中的一行，称为一个元组。
 
5、分量：元组中的一个属性值
 
6、键或者码：如果在一个关系中存在这样的一个属性，使得在该关系的任何一个关系状态中的两个元组，在该属性上的值的组合都不同，即这些属性的值都能够用来唯一标识该关系的元组，则称这些属性为该关系的键或者码。
 
7、超键或者超码：如果在关系的一个键中移去某个属性，它仍然是这个关系的键，则称这样的键为关系的超键或者超码。
 
8、候选键或者候选码：如果在关系的一个键中不能移去任何一个属性，否则它就不是这个关系的键，则称这个被指定的候选键为该关系的候选键或者候选码。
 
9、主键或者主码：在一个关系的若干候选键中指定一个用来唯一标识该关系的元组，则称这个被指定的候选键为该关系的主键或者主码。
 
10、全键或者全码：一个关系模式中的所有属性的集合。
 
11、主属性和非主属性：关系中包含在任何一个候选键中的属性称为主属性，不包含在任何一个候选键中的属性为非主属性。
 
12、外键或者外码：关系中的某个属性虽然不是这个关系的主键，或者只是主键的，但它却是另外一个关系的主键时，则称之为外键或者外码。
 
13、参照关系与被参照关系：是指以外键相互联系的两个关系，可以相互转化。
 

 
 
二、关系运算
 
关系的基本运算有两类：一类是传统的集合运算（并、差、交等），另一类是专门的关系运算（选择、投影、连接、除法、外连接等）。
 一、传统的集合运算
 1、并（UNION）　设有两个关系R和S，它们具有相同的结构。R和S的并是由属于R或属于S的元组组成的集合，运算符为∪。记为T＝R∪S。
 2、差（DIFFERENCE）　R和S的差是由属于R但不属关系运算组成的集合，运算符为－。记为T＝R－S。
 3、交（INTERSECTION）　R和S的交是由既属于R又属于S的元组组成的集合，运算符为∩。记为T＝R∩S。　R∩S＝R－（R－S）。
 
二、选择运算
 从关系中找出满足给定条件的那些元组称为选择。其中的条件是以逻辑表达式给出的，值为真的元组将被选取。这种运算是从水平方向抽取元组。　在FOXPRO中的短语FOR＜条件＞和WHILE＜条件＞均相当于选择运算。
 
如：LIST　FOR　出版单位＝'高等教育出版社'　AND　单价＜＝20
 
三、投影运算
 从关系模式中挑选若干属性组成新的关系称为投影。这是从列的角度进行的运算，相当于对关系进行垂直分解。在FOXPRO中短语FIELDS＜字段1，字段2，…＞相当于投影运算。　如：　LIST　FIELDS　单位，姓名
 
四、连接运算
 连接运算是从两个关系的笛卡尔积中选择属性间满足一定条件的元组。
 
五、除法运算
 在关系代数中，除法运算可理解为笛卡尔积的逆运算。
 设被除关系R为m元关系，除关系S为n元关系，那么它们的商为m-n元关系，记为R÷S。商的构成原则是：将被除关系R中的m-n列，按其值分成若干组，检查每一组的n列值的集合是否包含除关系S，若包含则取m-n列的值作为商的一个元组，否则不取。
 

 
 
注：部分摘自百度百科

转自点击打开链接

关系代数的运算是一种数学运算，你主要功能是通过这种数学运行来指导数据库在关系操作上的程序实现。
如图所示，下面是关系代数的操作，上面是对应的SQL语句。如果我们熟悉关系代数的操作那么就很容易写出复杂的SQL语句了。

关系代数的操作
对关系进行运算时，我们可以采用对待集合的方式来操作，这些操作被称为集合操作。其他的一些操作不能在集合上使用，那么被成为纯关系操作。

对于集合操作中U,∩，-操作需要满足并相容性
并操作

举例
 
差运算

举例

笛卡儿积
笛卡儿积是将关系R中的每个元组与关系S中的每个元组进行拼接组成一个新的关系

 
下面是RxS的结果，R和S使用上图中的R，S


选择操作
选择操作就是从关系中选出符合条件的元组,选出某一些行来进行操作

举例

 
选择A2值为a或b的元祖


投影操作
投影操作是从关系R中选出某些列。

举例

 
将A1和A3进行投影，如果投影中有重复的元组则需要去掉


连接操作
连接操作是先对两个关系做笛卡儿积生成一个新的关系，然后在新的关系上做选择操作

Ɵ是比较运算符，如>,<,=等
举例

 
下图中先将R和S进行笛卡尔积运算，然后在选出B<=H的元组来。



 
下图中使用了自连接操作


自然连接
自然连接是一种特殊的等值链接，他要求关系R和关系S具有相同的属性组B(b1,b2,b3……),这些属性组的取值是相等的，在最后生成的关系中去掉属性重复的列。

举例

 
下图中属性相同的只有一项B


除操作
除操作比较复杂，它是一种全包含操作，通过下面的例子来解释除操作

在(1)中计算R除以S操作，首先生成的关系中没有R和S的公共属性A3。其次生成的关系中每个元组与S中的元组进行组合都能出现在R中。
在(3)中只有(a,e)的原因是只有(a,e)与S中的每个元组组合才能出现在R中，而像(d,b)这种元组如果如S中每个元组组合的话不能全部出现在R中。
在(2)中我们可以这样来理解除法运算，找出即出现c又出现f的元组，并且这些元组的其余属性值是相等的。如包含c和f的元组有【(a,b,c)】,【(d,b,c),(d,b,f)】【(a,e,c),(a,e,f)】,其余属性值相等的有(a,e),(d,b)。
外连接操作
提出问题
有三张表分别是Teacher(T#, Tname, Salary), Course(C#, Cname), Teach(T#, C#)
请列出所有老师的信息，包括姓名，工资，所教课程
下面是关系代数公式：


通过自然连接然后进行投影，我们可以选出需要的信息。但是我们发现遗漏了一个老师，这是因为在自然连接的时候只有相等的才能被选择出来，而在Teach表中没有编号为003的老师，也就是说编号为003的老师没有教授课程，所以在最终结果中我们遗漏了一个老师。

 
两个关系R和S进行连接时，如果关系R中的元组在S中没有找到相匹配的元组，或者关系S中元组在R中没有找到相匹配的。为了避免元组信息的丢失，假定R或S中存在一个值全为空的元组，然后将未匹配的元组与全为空的元组连接起来。


如同所示R中的第二行和第三行记录在S中未找到匹配的，那么就与空元组进行连接，S中的元组亦然。所以最后的外连接结果如上图所示。
左外连接，保证左边表中的元组不丢失
右外连接，保证右边表中的元组不丢失
全外连接，保证两个表中的元组都不丢失
下面是左外连接和右外连接，全外链接如上图所示

关系数据库
 
一、关系数据结构及形式化定义
 
1.关系
 
单一的数据结构----关系
 现实世界的实体以及实体间的各种联系均用关系来表示
 
逻辑结构----二维表
 从用户角度，关系模型中数据的逻辑结构是一张二维表
 
建立在集合代数的基础上
 
1. 1域（Domain）
 
域是一组具有相同数据类型的值的集合。例:
 整数、实数、介于某个取值范围的整数、指定长度的字符串集合、{‘男’，‘女’}
 
1.2 笛卡尔积（Cartesian Product）
 
笛卡尔积：
 给定一组域D1，D2，…，Dn，允许其中某些域是相同的。
 
 
 
D1，D2，…，Dn的笛卡尔积为：
D1×D2×…×Dn ＝ （d1，d2，…，dn）｜diDi，i＝1，2，…，n｝
 
 
所有域的所有取值的一个组合，不能重复。
 
元组（Tuple）
 笛卡尔积中每一个元素（d1，d2，…，dn）叫作一个n元组（n-tuple）或简元组
 (张清玫，计算机专业，李勇)、(张清玫，计算机专业，刘晨) 等 都是元组
 
分量（Component）
 笛卡尔积元素（d1，d2，…，dn）中的每一个值di 叫作一个分量
 张清玫、计算机专业、李勇、刘晨等都是分量
 
基数（Cardinal number）
 若Di（i＝1，2，…，n）为有限集，其基数为mi（i＝1，2，…，n），则D1×D2×…×Dn的基数M为：
 
 
笛卡尔积的表示方法
 笛卡尔积可表示为一张二维表
 表中的每行对应一个元组，表中的每列对应一个域
 
例如，给出3个域：
 D1=导师集合SUPERVISOR=｛张清玫，刘逸｝
 D2=专业集合SPECIALITY=｛计算机专业，信息专业｝
 D3=研究生集合POSTGRADUATE=｛李勇，刘晨，王敏｝
 D1，D2，D3的笛卡尔积为
 D1×D2×D3＝｛
 (张清玫，计算机专业，李勇)，(张清玫，计算机专业，刘晨)，
 (张清玫，计算机专业，王敏)，(张清玫，信息专业，李勇)，
 (张清玫，信息专业，刘晨)，(张清玫，信息专业，王敏)，
 (刘逸，计算机专业，李勇)，(刘逸，计算机专业，刘晨)，
 (刘逸，计算机专业，王敏)，(刘逸，信息专业，李勇)，
 (刘逸，信息专业，刘晨)，(刘逸，信息专业，王敏) ｝
 基数为2×2×3＝12
 
1.3.关系（Relation）
 
（1） 关系
 
D1×D2×…×Dn的子集叫作在域D1，D2，…，Dn上的关系，表示为
 
     R（D1，D2，…，Dn）
 
R：关系名
 n：关系的目或度（Degree）
 
（2）元组
 
关系中的每个元素是关系中的元组，通常用t表示。
 
（3）单元关系与二元关系
 
当n=1时，称该关系为单元关系（Unary relation）或一元关系
 当n=2时，称该关系为二元关系（Binary relation）
 
（4）关系的表示
 
关系也是一个二维表，表的每行对应一个元组，表的每列对应一个域
 
（5）属性
 
关系中不同列可以对应相同的域,为了加以区分，必须对每列起一个名字，称为属性（Attribute）,n目关系必有n个属性.
 
（6）码
 
候选码（Candidate key）
 若关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为候选码,简单的情况：候选码只包含一个属性.
 全码（All-key）
 最极端的情况：关系模式的所有属性组是这个关系模式的候选码，称为全码（All-key）
 
主码
 若一个关系有多个候选码，则选定其中一个为主码（Primary key）
 主属性
 候选码的诸属性称为主属性（Prime attribute),不包含在任何侯选码中的属性称为非主属性（Non-Prime attribute）或非码属性（Non-key attribute）
 
D1，D2，…，Dn的笛卡尔积的某个子集才有实际含义
 
（7）三类关系
 
基本关系（基本表或基表）:实际存在的表，是实际存储数据的逻辑表示
 查询表:查询结果对应的表
 视图表:由基本表或其他视图表导出的表，是虚表，不对应实际存储的数据
 
（8）基本关系的性质
 
① 列是同质的（Homogeneous）
 ② 不同的列可出自同一个域,其中的每一列称为一个属性,不同的属性要给予不同的属性名.
 ③ 列的顺序无所谓,，列的次序可以任意交换
 ④ 任意两个元组的候选码不能相同
 ⑤ 行的顺序无所谓，行的次序可以任意交换
 ⑥ 分量必须取原子值
 
2.关系模式
 
2.1什么是关系模式
 
关系模式（Relation Schema）是型
 关系是值
 关系模式是对关系的描述,元组集合的结构、属性构成、属性来自的域 、属性与域之间的映象关系
 完整性约束条件
 
2.2定义关系模式
 
关系模式可以形式化地表示为：
 
 
 
R（U，D，DOM，F）
 R 关系名
 U 组成该关系的属性名集合
 D U中属性所来自的域
 DOM 属性向域的映象集合
 F 属性间数据的依赖关系的集合
 
 
关系模式通常可以简记为
 R (U) 或 R (A1，A2，…，An)
 R: 关系名
 A1，A2，…，An : 属性名
 注：域名及属性向域的映象常常直接说明为
 属性的类型、长度
 
2.3.关系模式与关系
 
关系模式：关系的描述、静态的、稳定的
 关系：关系模式在某一时刻的状态或内容、动态的、随时间不断变化的
 关系模式和关系往往笼统称为关系、通过上下文加以区别
 
3.关系数据库
 
关系数据库
 在一个给定的应用领域中，所有关系的集合构成一个关系数据库
 
关系数据库的型与值
 关系数据库的型: 关系数据库模式，是对关系数据库的描述。
 关系数据库的值: 关系模式在某一时刻对应的关系的集合，通常称为关系数据库
 
4.关系模型的存储结构
 
关系数据库的物理组织
 
有的关系数据库管理系统中一个表对应一个操作系统文件，将物理数据组织交给操作系统完成。
有的关系数据库管理系统从操作系统那里申请若干个大的文件，自己划分文件空间，组织表、索引等存储结构，并进行存储管理
 
二、关系操作
 
基本的关系操作
 
常用的关系操作：
 
查询操作：选择、投影、连接、除、并、差、交、笛卡尔积
 选择、投影、并、差、笛卡尔基是5种基本操作
数据更新：插入、删除、修改
 
关系操作的特点
 集合操作方式：操作的对象和结果都是集合，一次一集合的方式
 
关系数据库语言的分类
 
关系代数语言
 用对关系的运算来表达查询要求
 代表：ISBL
 
关系演算语言：用谓词来表达查询要求
 元组关系演算语言、谓词变元的基本对象是元组变量
 代表：APLHA, QUEL
 
域关系演算语言、谓词变元的基本对象是域变量
 代表：QBE
 
具有关系代数和关系演算双重特点的语言
 代表：SQL（Structured Query Language）
 
三、关系的完整性
 
约束
 实体完整性和参照完整性、关系模型必须满足的完整性约束条件称为关系的两个不变性，应该由关系系统自动支持。
 
用户定义的完整性、应用领域需要遵循的约束条件，体现了具体领域中的语义约束 。
 
1 实体完整性
 
规则：
 
若属性A是基本关系R的主属性，则属性A不能取空值
空值就是“不知道”或“不存在”或“无意义”的值
 
规则的说明
 （1）实体完整性规则是针对基本关系而言的。一个基本表通常对应现实世界的一个实体集。
 （2）现实世界中的实体是可区分的，即它们具有某种唯一性标识。
 （3）关系模型中以主码作为唯一性标识。
 （4）主码中的属性即主属性不能取空值。主属性取空值，就说明存在某个不可标识的实体，即存在不可区分的实体，这与第（2）点相矛盾，因此这个规则称为实体完整性
 
2 参照完整性
 
2.1.关系间的引用
 
在关系模型中实体及实体间的联系都是用关系来描述的，自然存在着关系与关系间的引用。
 
 
 
例[1] 学生、课程、学生与课程之间的多对多联系
 学生（学号，姓名，性别，专业号，年龄）
 课程（课程号，课程名，学分）
 选修（学号，课程号，成绩）
 
 
例[2] 学生实体及其内部的一对多联系
 学生（学号，姓名，性别，专业号，年龄，班长）
 
 
 
 
“学号”是主码，“班长”是外码，它引用了本关系的“学号”
 “班长” 必须是确实存在的学生的学号
 
 
2.2 外码
 
设F是基本关系R的一个或一组属性，但不是关系R的码。如果F与基本关系S的主码Ks相对应，则称F是R的外码
基本关系R称为参照关系（Referencing Relation）
基本关系S称为被参照关系（Referenced Relation）或目标关系（Target Relation）
 
 
 
[例]中学生关系的“专业号”与专业关系的主码“专业号”相对应
 “专业号”属性是学生关系的外码
 专业关系是被参照关系，学生关系为参照关系
 
 
 
关系R和S不一定是不同的关系.
 目标关系S的主码Ks 和参照关系的外码F必须定义在同一个（或一组）域上
 外码并不一定要与相应的主码同名,当外码与相应的主码属于不同关系时，往往取相同的名 字，以便于识别.
 
2.3 参照完整性规则
 
若属性（或属性组）F是基本关系R的外码它与基本关系S的主码Ks相对应（基本关系R和S不一定是不同的关系），则对于R中每个元组在F上的值必须为：
 
或者取空值（F的每个属性值均为空值）
或者等于S中某个元组的主码值
 
3 用户定义的完整性
 
针对某一具体关系数据库的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求
关系模型应提供定义和检验这类完整性的机制，以便用统一的系统的方法处理它们，而不需由应用程序承担这一功能
 
 
 
例:
 课程（课程号，课程名，学分）
 “课程号”属性必须取唯一值
 非主属性“课程名”也不能取空值
 “学分”属性只能取值{1，2，3，4}
 
 
四、关系代数
 
关系代数是一种抽象的查询语言，它用对关系的运算来表达查询
关系代数:运算对象是关系、运算结果亦为关系、关系代数的运算符有两类：集合运算符和专门的关系运算符
传统的集合运算是从关系的“水平”方向即行的角度进行
专门的关系运算不仅涉及行而且涉及列
 
关系代数运算符：
 
 
1.传统的集合运算
 
R:
 
 
S:
 
 
1.1并
 
R和S
 具有相同的目n（即两个关系都有n个属性）
 相应的属性取自同一个域
 
R∪S
 仍为n目关系，由属于R或属于S的元组组成
 R∪S = { t|t  R∨t S }
 
RUS:
 
 
1.2差
 
R - S
 仍为n目关系，由属于R而不属于S的所有元组组成
 R -S = { t|tR∧tS }
 
 
1.3交
 
R∩S
 仍为n目关系，由既属于R又属于S的元组组成
 R∩S = { t|t  R∧t S }
 R∩S = R –(R-S）
 
 
1.4笛卡尔积
 
R: n目关系，k1个元组
 S: m目关系，k2个元组
 R×S
 
列：（n+m）列元组的集合
 元组的前n列是关系R的一个元组
 后m列是关系S的一个元组
 
行：k1×k2个元组
 R×S = {tr ts |tr R ∧ tsS }
 
 
2.专门的关系运算
 
几个概念：
 
 几个表格数据：
 
Student
 
 
Course：
 
 SC ：
 
 
2.1.选择
 
选择又称为限制（Restriction）
 选择运算符的含义
 在关系R中选择满足给定条件的诸元组
 σF® = {t|tR∧F(t)= ‘真’}
 F：选择条件，是一个逻辑表达式，取值为“真”或“假”
 基本形式为：X1θY1
 θ表示比较运算符，它可以是＞，≥，＜，≤，＝或<>
 
选择运算是从关系R中选取使逻辑表达式F为真的元组，是从行的角度进行的运算
 
 
 
例： 查询信息系（IS系）全体学生。
 σSdept = ‘IS’ (Student)
 结果：
 
 
 
2.2 投影
 
从R中选择出若干属性列组成新的关系
 πA® = { t[A] | t R }
 A：R中的属性列
 
投影操作主要是从列的角度进行运算
 

 投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组（避免重复行）
 
 
 
例：查询学生的姓名和所在系。
 即求Student关系上学生姓名和所在系两个属性上的投影
 πSname,Sdept(Student)
 结果：
 
 
 
2.3.连接
 
连接也称为θ连接
 
 
两类常用连接运算
 

 外连接（Outer Join）
 
如果把悬浮元组也保存在结果关系中，而在其他属性上填空值(Null)，就叫做外连接
左外连接(LEFT OUTER JOIN或LEFT JOIN)，只保留左边关系R中的悬浮元
右外连接(RIGHT OUTER JOIN或RIGHT JOIN)，只保留右边关系S中的悬浮元组
 
2.4 除运算
 
给定关系R (X，Y) 和S (Y，Z)，其中X，Y，Z为属性组。
 R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集。
 R与S的除运算得到一个新的关系P(X)，
 P是R中满足下列条件的元组在 X 属性列上的投影：
 元组在X上分量值x的象集Yx包含S在Y上投影的集合，记作：
 
 除操作是同时从行和列角度进行运算
 
 设关系R、S分别为下图的(a)和(b)，RS的结果为图©
 R：
 S：
 
 R÷S：
 
 
在关系R中，A可以取四个值{a1，a2，a3，a4}
 a1的象集为 {(b1，c2)，(b2，c3)，(b2，c1)}
 a2的象集为 {(b3，c7)，(b2，c3)}
 a3的象集为 {(b4，c6)}
 a4的象集为 {(b6，c6)}
 
S在(B，C)上的投影为
 {(b1，c2)，(b2，c1)，(b2，c3) }
 
只有a1的象集包含了S在(B，C)属性组上的投影
 所以 R÷S ={a1}
 
关系代数运算小结
 
关系代数运算
 并、差、交、笛卡尔积、投影、选择、连接、除
 基本运算
 并、差、笛卡尔积、投影、选择
 交、连接、除
 可以用5种基本运算来表达
 引进它们并不增加语言的能力，但可以简化表达
 
关系代数表达式
 关系代数运算经有限次复合后形成的式子
 
小结
 
关系数据库系统是目前使用最广泛的数据库系统
 
关系数据库系统与非关系数据库系统的区别：
 
关系系统只有“表”这一种数据结构
非关系数据库系统还有其他数据结构，以及对这些数据结构的操作
 
关系数据结构
 
关系 
  
域
笛卡尔积
关系
 - 关系，属性，元组
 - 候选码，主码，主属性
 - 基本关系的性质
 
关系模式
关系数据库
关系模型的存储结构
 
关系操作
 
查询
 - 选择、投影、连接、除、并、交、差
数据更新
 - 插入、删除、修改
 
关系的完整性约束
 
实体完整性
参照完整性
 - 外码
用户定义的完整性

什么是数据结构？数据结构是什么？
 
 
 
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
 
 
 
定义
 
名词定义
 
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。也就是说，数组结构指的是数据集合及数据之间关系的集合，是两个集合。
 
记为：Data_Structure=(D,R)
 
其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。 
 
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
 
 
 
其它定义
 
Sartaj Sahni在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实 例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。
 Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT（抽象数据类型Abstract Data Type） 的物理实现。”
 Robert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。
 数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。
 
 
 
研究对象
 
一、数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。逻辑结构包括：
 集合
 数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
 2.线性结构
 数据结构中的元素存在一对一的相互关系；
 3.树形结构
 数据结构中的元素存在一对多的相互关系；
 4.图形结构
 数据结构中的元素存在多对多的相互关系。
 二、数据的物理结构：指数据的逻辑结构在计算机存储空间的存放形式。 
 数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。
 数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与个数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。
 关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。
 三、数据结构的运算。
 
 
 
重要意义
 
          一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。
 
         在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。
 
         选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。
 
 
 
研究内容
 
         在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
 
         “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 1968年美国唐纳德·克努特（Donald Ervin Knuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课，数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。
 
         计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理 。
 
         而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。数据的结构，直接影响算法的选择和效率。
 
         计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。
 
         寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。当人们用计算机处理数值计算问题时，所用的数学模型是用数学方程描述。所涉及的运算对象一般是简单的整形、实型和逻辑型数据，因此程序设计者的主要精力集中于程序设计技巧上，而不是数据的存储和组织上。然而，计算机应用的更多领域是“非数值型计算问题”，它们的数学模型无法用数学方程描述，而是用数据结构描述，解决此类问题的关键是设计出合适的数据结构，描述非数值型问题的数学模型是用线性表、树、图等结构来描述的。
 
         计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。
 
         数据是信息的载体，是可以被计算机识别存储并加工处理的描述客观事物的信息符号的总称。所有能被输入计算机中，且能被计算机处理的符号的集合，它是计算机程序加工处理的对象。客观事物包括数值、字符、声音、图形、图像等，它们本身并不是数据，只有通过编码变成能被计算机识别、存储和处理的符号形式后才是数据。
 
         数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑。一个数据元素由若干个数据项组成。数据项是数据结构中讨论的最小单位。有两类数据元素：若数据元素可再分，则每一个独立的处理单元就是数据项，数据元素是数据项的集合；若数据元素不可再分，则数据元素和数据项是同一概念，如：整数"5"，字符 "N" 等。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出生日期又可以由三个数据项："年"、"月"和"日"组成，则称"出生日期"为组合项，而其它不可分割的数据项为原子项。
 
         关键字指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 "主" 关键字，否则称之为 "次" 关键字。
 
         数据对象是性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。
 
         数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。
 
 
 
结构分类
 
         数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是从具体问题抽象出来的数学模型，是描述数据元素及其关系的数学特性的，有时就把逻辑结构简称为数据结构。逻辑结构是在计算机存储中的映像，形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。
 
         根据数据元素间关系的不同特性，通常有下列四类基本的结构： ⑴集合结构。该结构的数据元素间的关系是“属于同一个集合”。 ⑵线性结构。该结构的数据元素之间存在着一对一的关系。 ⑶树型结构。该结构的数据元素之间存在着一对多的关系。 ⑷图形结构。该结构的数据元素之间存在着多对多的关系，也称网状结构。 从上面所介绍的数据结构的概念中可以知道，一个数据结构有两个要素。一个是数据元素的集合，另一个是关系的集合。在形式上，数据结构通常可以采用一个二元组来表示。
 
         数据结构的形式定义为：数据结构是一个二元组 ：Data_Structure=（D，R），其中，D是数据元素的有限集，R是D上关系的有限集。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型; 一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。
 
         线性表是最简单、最基本、也是最常用的一种线性结构。 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) ，其中n为表长， n=0 时称为空表。 它有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。
 
         数据结构在计算机中的表示（映像）称为数据的物理（存储）结构。它包括数据元素的表示和关系的表示。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。
 
         顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
 
         链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现
 
         索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
 
         散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
 
         数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。线性结构的顺序存储结构是一种顺序存取的存储结构，线性表的链式存储结构是一种随机存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。
 
 
 
结构算法
 
         算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的存储结构实质上是它的逻辑结构在计算机存储器中的实现，为了全面的反映一个数据的逻辑结构，它在存储器中的映象包括两方面内容，即数据元素之间的信息和数据元素之间的关系。不同数据结构有其相应的若干运算。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新和排序等。
 
         数据的运算是数据结构的一个重要方面，讨论任一种数据结构时都离不开对该结构上的数据运算及其实现算法的讨论。
 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。
 
         数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分为两类：原子类型、结构类型。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。
 
         计算机中表示数据的最小单位是二进制数的一位，叫做位。我们用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。元素或结点可看成是数据元素在计算机中的映象。
 
         一个软件系统框架应建立在数据之上，而不是建立在操作之上。一个含抽象数据类型的软件模块应包含定义、表示、实现三个部分。
 对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。
 
         不同的数据结构其操作集不同，但下列操作必不可缺：
          1,结构的生成；
          2.结构的销毁；
          3,在结构中查找满足规定条件的数据元素；
          4,在结构中插入新的数据元素；
          5,删除结构中已经存在的数据元素；
          6,遍历。
 
         抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。抽象数据类型可用以下三元组表示：（D，S，P）。D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT的定义为：
 
         ADT 抽象数据类型名：{数据对象：（数据元素集合），数据关系：（数据关系二元组结合），基本操作：（操作函数的罗列）}； ADT抽象数据类型名;抽象数据类型有两个重要特性：
 
         数据抽象
 
         用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
 
         数据封装
 
         将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。
 
         数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。计算机科学中，所谓数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数或复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像、语音等。数据元素（Data Element）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，学生信息检索系统中学生信息表中的一个记录等，都被称为一个数据元素。
 有时，一个数据元素可由若干个数据项（Data Item）组成，例如，学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫做初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割的最小单位；另一种叫做组合项，如学生的成绩，它可以再划分为数学、物理、化学等更小的项。通常，在解决实际应用问题时是把每个学生记录当作一个基本单位进行访问和处理的。
 
         数据对象（Data Object）或数据元素类（Data Element Class）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A和顶点B各自代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。 数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。
 
 
 
常用结构
 
数组
          在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中， 数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。
 
栈
          是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
 
队列
          一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。队列中没有元素时，称为空队列。
 
链表
          是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
 
树
          是包含n（n>0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件：
          （1）有且仅有一个结点 K0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。　 
          （2）除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。
          （3）K中各结点，对关系N来说可以有m个后继（m>=0）。
 
图
          图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
 
堆
          在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。
 
散列表
          若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。
 
 
 
简而言之，数据结构说的是：计算机组织数据和存储数据的方式。