数据结构

数据结构

数据结构：

线性表、栈、队列、串、数组、广义表、树、二叉树、图

重点是线性表、二叉树

数据

数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号的集合

声音、图像等一切可以输入计算机并能被处理的都是数据

数据项：

具有原子性，数据的最小单位

数据元素

数据元素是数据的基本单位，通常由若干个数据项组成，

例如一条描述一个学生的完整信息的数据记录

数据对象

数据对象时性质相同的数据元素的集合吗，是数据的子集

数据结构

是指相互之间存在一种或多种特定关系的数据元素的集合。

是组织并存储数据以便能够有效使用的一种专门格式，用来反映一个数据的内部构成

数据的逻辑结构：数据结构的逻辑层面

数据的存储结构：数据机构的存储层面

数据结构=逻辑结构+存储结构

数据结构=逻辑结构+存储结构+（在存储结构上的）运算/操作

数据的逻辑结构

数据的逻辑结构是指数据元素之间的逻辑关系，和实现无关

分类1.线性结构和非线性结构

线性结构：有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继

线性表就是一个典型的线性结构，他有四个基本特征：

1.集合中比存在唯一的一个“第一个元素”；

2.集合中必存在唯一的一个“最后的元素”；

3.除了最后元素之外，其他数据元素均有唯一的直接“后继”；

4.除了第一元素之外，其他数据元素均有唯一的直接“前驱”；

相对于线性结构，非线性结构的逻辑特征就是一个结点元素可能对应多个直接前驱或多个直接后继

常见的非线性结构有：树（二叉树）、图（网）等

分类2：集合结构 线性结构 树状结构 网络结构

逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构

线性结构：“一对一”

树状结构：“一对多”

网状结构：“多对多”

数据的存储结构

数据的存储结构有：

顺序存储、链式存储索引存储、以及散列存储

顺序存储结构：把逻辑上相邻的节点存储在物理位置上的相邻的存储单元中，节点之间的逻辑关系由存储单元的邻接关系来体现

有此得到的存储结构为顺序存储结构，通常是借助于计算机的数组来描述的。

优点：是节省存储空间，因为分配给数据库的存储单元全用来存放节点数据，节点之间的逻辑关系没有占用额外的存储空间

采用这种方法时，可以实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址

缺点：插入和删除操作需要移动元素，效率较低

链式存储结构：数据元素的存储对应的是不连续的存储空间，每个存储节点对应一个需要存储的数据元素

每一个结点是由数据域和指针域组成。元素之间的逻辑关系通过存储节点之间的链式关系反映出来

特点：

1.比顺序存储结构的存储密度小（每个节点都是由数据域和指针域组成，所以相同空间内假设全存满的话会比链式存储更多）

2.逻辑上相邻的结点物理上不必相邻

3.插入、删除灵活（不必移动结点，只需改变结点中的指针）

4.查找结点时链式存储比顺序存储慢

索引存储结构：

除建立存储节点信息外慢，还建立附加的索引来标识节点的地址

比如图书、字典的目录

散列存储结构：

```plain text 根据节点的关键字直接计算出该节点的存储地址

一种神奇的结构，添加、查询速度快。 ```

同一逻辑结构可以对应多种存储结构

同样的运算，在不同的存储结构中，其实现过程是不同的