1 基本概念及术语
- 数据(Data) ：是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。 数据的含义非常广泛，除了通常的数值数据、字符、字符串是数据以外，声音、图像等一切 可以输入计算机并能被处理的都是数据。例如除了表示人的姓名、身高、体重等的字符、数 字是数据，人的照片、指纹、三维模型、语音指令等也都是数据。
- 数据元素（data element）是数据的基本单位，是数据集合的个体，在计算机程序中通 常作为一个整体来进行处理。例如一条描述一位学生的完整信息的数据记录就是一个数据元 素；空间中一点的三维坐标也可以是一个数据元素。数据元素可由若干个数据项组成，例 如描述学生相关信息的姓名、性别、学号等都是数据项；三维坐标中的每一维坐标值也是数 据项。数据项具有原子性，是不可分割的小单位。数据项是对客观
事物某一方面特性的数据描述。- 数据对象（data object）是性质相同的数据元素的集合，是数据的子集。例如一个学校 的所有学生的集合就是数据对象，空间中所有点的集合也是数据对象,如字符集合C={‘A’,’B’,’C,…} 。
- 数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素的集合。
- 表示一组数据元素及其相互关系的数据结构同样也有两种不同的 表现形式，一种是数据结构的逻辑层面，即数据的逻辑结构；一种是存在于计算机世界的物理层面，即数据的存储结构。
2 逻辑结构分类
数据的逻辑结构按照数据元素之间相互关系的特性来分，可以分为以下四种结构：集合、线性结构、树形结构和图状结构。
- ① 集合 结构中的数据元素除了“ 同属于一个集合”外，没有其它关系。
- ② 线性结构 结构中的数据元素之间存在一对一的关系。
- ③ 树型结构 结构中的数据元素之间存在一对多的关系
- ④ 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。
3 逻辑结构的描述
数据的逻辑结构可以采用两种方法来描述：二元组、图形。
3.1 数据结构 graph 的图形表示
- 当使用图形来表示数据结构时，是用图形中的点来表示数据元素，用图形中的弧来表示 数据元素之间的关系。如果数据元素 x 与 y 之间有关系<x , y>，则在图形中有从表示 x 的点 出发到达表示 y 的点的一条弧。
QQ截图20180520200250.png
3.2 数据结构的二元组表示
- 数据结构的二元组表示形式为： 数据结构 = {D , S}
- 其中 D 是数据元素的集合；S 是 D 中数据元素之间的关系集合，并且数据元素之间的 关系是使用序偶来表示的。
- 序偶是由两个元素 x 和 y 按一定顺序排列而成的二元组，记作 <x , y>，x 是它的第一元素，y 是它的第二元素(下面提到的前元素即：x，后元素即：y)
集合set
- 二元组表示为 set = (K,R)，其中 K = {01, 02, 03, 04, 05} R = {}
- 可以看到在数据结构 set 中，只有数据元素的集合非空，而数据元素之间除了同属一个 集合之外不存在任何关系（关系集合为空）。
线性结构linearity
- 二元组表示为 linearity = (K,R)，其中 K = {01, 02, 03, 04, 05} R = {<02,04>, <03,05>, <05,02>, <01,03>}
- 在这些数据元素中有一个可 以被称为“第一个”（元素 01）的数据元素；还有一个可以被称为“后一个”（元素 04） 的数据元素；
- 除第一个元素以外每个数据元素有且仅有一个直接前驱元素，除后一个元素 以外每个数据元素有且仅有一个直接后续元素。
- 这种数据结构的特点是数据元素之间是 1 对 1 的联系，即线性关系
- 把具有此种特点的数据结构称为线性结构。
树结构tree
- tree = (K,R)，其中 K = {01, 02, 03, 04, 05, 06} R = {<01,02>, <01,03>, <02,04>, <02,05>, <03,06>}
- 除了一个数据元素（元素 01）以外每个数据元素有且仅 有一个直接前驱元素，但是可以有多个直接后续元素。
- 特点是数据元素之间 是 1 对 N 的联系
- 把具有此种特点的数据结构称为树结构。
图结构graph
graph = (K,R)，其中 K = {01, 02, 03, 04, 05} R = {<01,02>, <01,05>, <02,01>, <02,03>, <02,04>, <03,02>, <04,02>, <04,05>, <05,01>, <05,04>}
- 每个数据元素可以有多个直接前驱元素，也可以有多个 直接后续元素。
- 特点是数据元素之间是 M 对 N 的联系
- 具有此种特 点的数据结构称为图结构。
4 数据结构的存储方式
- 数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示 。
- 元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。
- 由此得出两种不同的存储结构：顺序存储结构和链式存储结构 。
- 顺序存储结构 ：数据元素的存储对应于一块连续的存储空间，数据元素之间的前驱和后续关系通过数据元素 在存储器中的相对位置来反映。
- 链式存储结构 ：在每一个数据元素中增加一个存放另一个**元素地址的指针(pointer ) **，用该指针来表示数据元素之间的逻辑结构( 关系(即前后元素关系)) 。
5 数据结构的三个组成部分
- 数据结构的三个组成部分：
- 逻辑结构： 数据元素之间逻辑关系的描述
D_S= （D ，S ）- 存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。
- 数据操作： 对数据要进行的运算。
QQ截图20180520204516.png
6 数据结构的运算
- 数据结构的主要运算包括：
- ⑴ 建立(Create) 一个数据结构；
- ⑵ 消除(Destroy) 一个数据结构；
- ⑶ 从一个数据结构中删除(Delete) 一个数据元素；
- ⑷ 把一个数据元素插入(Insert) 到一个数据结构中；
- ⑸ 对一个数据结构进行访问(Access) ；
- ⑹ 对一个数据结构( 中的数据元素) 进行修改(Modify) ；
- ⑺ 对一个数据结构进行排序(Sort) ；
- ⑻ 对一个数据结构进行查找(Search) 。
