1.1 数据结构基础
1.1.1 基本概念及举例
1. 基本概念
数据（Data）：能够被计算机程序识别、存储、加工和处理的描述客观事物的符号集合。数据是信息的载体，数据被赋予含义则成为信息。
数据项（Data Item）：又称为字段或域，是数据元素的组成部分，具有不可分割性和独立含义。
数据元素（Data Element）：又称为元素，是数据的基本单位，是一个数据整体的基本表示。
数据对象（Data Object）：又称为数据元素类，是性质相同的数据元素的集合。数据元素是数据对象的实例。
数据结构（Data Structure）：相互之间存在一种或多种关系的数据元素的集合。
抽象数据类型（Abstract Data Type，ADT）：从数学模型角度抽象出来的逻辑数据结构及相关运算，不考虑具体存储结构和实现细节。它反映的是定义与实现相分离的设计哲学，包含数据对象、数据关系和基本运算。例如，定义复数抽象数据类型Complex，描述语句如下。
ADT Complex
{
数据对象
D={e1,e2| e1,e2均为实数}
数据关系
R={<e1,e2>|e1是复数的实部，e2是复数的虚部}
基本运算
AssignComplex(&z，v1，v2 )：构造复数z。
GetReal(z，&real)：返回复数z的实部值。
GetImag(z，&Imag)：返回复数z的虚部值。
Add (z1，z2，&sum)：返回两个复数z1、z2的和。
} ADT Complex
2. 举例
地球上居住着人类，人口众多，且有男性和女性之分。人与人之间关系各异，有不认识的，有认识的；有熟悉的，有模糊的；有沾亲带故的，有非亲非的；有直接上下级关系的，有间接上下级关系的；等等（见图1.1）。
图1.1 地球人关系复杂
上例中，地球是装人的容器；人是数据对象；具体的某个人如张三是数据元素；人的某个属性如肤色是数据项；人与人之间存在的关系与人一起在地球上构成了数据结构；而地球上有人，人与人之间有直接或间接关系发生，这就是抽象数据类型的表示。
数据结构包含3方面的内容：数据的逻辑结构、数据的存储结构和数据的操作。下面讲解数据的逻辑结构和存储结构，数据的操作在后续内容中讲解。
1.1.2 逻辑结构
数据的逻辑结构是对数据元素之间关系的描述，分为集合、线性结构、树状结构、图形结构4类。
1. 集合
具有相同性质的数据元素构成集合。集合中数据元素的关系极为松散，关系为“属于同一个集合”。
➢ 举例：之前，同学们互不认识，是数据结构这门课程让同学们有缘走到了一起，来到这间教室学习。将教室看作集合，将教室里的人看作数据元素，有些同学相互之间一学期也不说话交流（没有关系），但他们归属于同一个教室。
2. 线性结构
线性结构指数据元素之间是线性关系的数据结构，其特点是数据元素之间为一对一关系。
➢ 举例1：甲用暗号1联系乙，乙用暗号2联系丙，丙用暗号3联系丁。保密工作只能单线联系。甲、乙、丙、丁这些数据元素之间的关系是单一的、一个对一个的。
➢ 举例2：教室里坐了n个学生，他们按照学号顺序依次回答问题“什么是数据结构？”n个学生（数据元素）的这种依次关系，就是一对一的关系。
3. 树状结构
树状结构指数据元素之间是层次关系的数据结构，其特点是数据元素之间可以为一对多关系。
➢ 举例1：旧楼房的楼梯间，有线电视同轴电缆从1层到顶层通过分支器连接和分户，使户户有电视看。这种分支器输入1个通道、输出n个通道，构成了一对多关系；层层分支整个同轴电缆，则分支器与用户构成了树状结构。
➢ 举例2：单位的组织结构，是典型的层次树状结构，且是倒立的树状结构。
4. 图形结构
图形结构中数据元素之间的关系复杂，可以包含一对一、一对多、多对一、多对多的关系。其特点是数据元素之间可以为多对多关系。
➢ 举例：新同学进学校找不到路，没有老同学在身边带路没关系，打开校园地图App，线路一目了然（与打开百度地图App、高德地图App咨询城市交通类似）。从宿舍到教室有多条路，从教室到食堂有多条路，从食堂回宿舍还是有很多条路。这个例子体现了数据元素之间多对多的关系。
数据结构的各类逻辑结构如图1.2所示。
图1.2 数据结构的各类逻辑结构
1.1.3 存储结构
逻辑结构在计算机中的存储表示叫数据的存储结构，也叫物理结构。数据的存储结构分为顺序存储结构、链式存储结构、索引存储结构、散列存储结构4类。
1. 顺序存储结构
顺序存储结构是在连续的存储单元中存放数据元素，数据元素的物理存储次序与逻辑次序一致，即物理位置相邻的数据元素在逻辑上也是相邻的。这种结构的物理存储体现了数据元素之间的逻辑关系。
➢ 举例：大学英语四六级考试考场座位编号，是按照准考证号的顺序连续编号的。在这个例子中，相邻准考证号在物理座位上也是相邻的。
2. 链式存储结构
链式存储结构使用地址分散的存储单元存放数据元素，即物理上相邻的数据元素逻辑上不一定相邻，数据元素之间的逻辑关系通常用指针表示，记录前驱和后继的存储地址。
➢ 举例：大学教室里，学生来上课可以随便坐，学号相邻的同学不一定坐在一起；当老师让学生按照学号从小到大举手/站立报号考勤时，这种乱坐现象并不影响考勤。在这个例子中，虽然学号连续，但是学生可以分散坐，体现了链式存储结构。
3. 索引存储结构
索引存储结构在存储数据元素的基础上增加了索引表，可以用它来实现快速查找数据元素。
➢ 举例：班干部名单，叫到某个班干部，如“第二组组长张三”，其职责和管理对象也就呼之而出。在这个例子中，班干部名单可以看作索引表。
4. 散列存储结构
散列存储结构又叫哈希存储结构，数据元素的存储地址由该数据元素关键字通过散列函数计算出来。
➢ 举例：学生照毕业照，按照个子高矮站位，中间站高个子两边站矮个子，若有相同身高则分站两边，各排以此类推。在这个例子中，通过散列函数对身高求值，从而决定所站位置（存储地址）。
数据结构的各类存储结构如图1.3所示。
图1.3 数据结构的各类存储结构