# 什么是数据结构

数据结构研究计算机数据间关系
包括数据的逻辑结构和存储结构及其操作

# 基本概念

1. 数据（Data）：数据即信息的载体，是指计算机中可以被计算机程序处理、存储、传输、处理的有意义的信息。
2. 数据元素（Data Element）：是指数据中最小的单位，是数据的不可分割的基本单位。又称记录；
3. 数据对象（Data Object）：是指数据元素的集合。
4. 数据类型（Data Type）：是指数据对象的集合及其特征的集合。

# 数据的逻辑结构（线性结构和非线性结构）

集合
线性结构：一个对一个（线、串、队列、栈、链表）
树形：一个对多个（树）
图状结构：多个对多个（图）

# 数据的存储结构

顺序存储结构：数据元素按顺序存储在一块连续的存储区中，每个数据元素占用一个存储单元。
链接存储结构：数据元素存储在一块连续的存储区中，每个数据元素占用一个存储单元，但每个数据元素除了存储其值外，还存储了指向下一个数据元素的指针。
索引存储结构：在存储数据的同时，建立索引存储结构 = 数据文件 + 索引表
散列存储结构：根据数据元素的特殊字段（称为关键字 key），计算数据元素的存放地址，然后数据元素按地址存放。

# 数据的运算：检索、排序、插入、删除、合并、分解、复制、转换、计算等

# 线性表

什么是线性表
定义：线性表是包含若干数据元素的一个线性序列
线性表 L 可用二元组形式描述：L=(a1,a2,…,an)
其中，a1,a2,…,an 为数据元素，n 为元素个数。
L=(D,R)
D 为数据元素的集合，R 为关系，即数据元素之间的关系。
特征：
1. 对非空表，a0 是表头，无前驱；
2.an-1 是表尾，无后继；
3. 其它的每个元素 ai 都有唯一的前驱 ai-1 和唯一的后继 ai+1；
4. 表中元素的个数为 n。

# 顺序存储结构的表示

不足：
1. 插入和删除操作效率低，需要移动大量元素；
2. 占用大量存储空间。

优点：
1. 访问元素的效率高，直接访问存储单元；
2. 便于实现动态集合。

在 C 语言中，可借助于一堆数组类型来描述顺序存储结构的线性表。

# 线性表的链式存储结构

定义
- 线性表的链式存储结构是指用一组任意的存储单元来存储线性表中的数据元素。这些存储单元可以是连续的，也可以是不连续的。它通过指针（链）来链接数据元素，形成一种动态的存储结构。
基本结构
- 每个链表的结点（链式存储结构中的基本单元）一般包括两个部分：一个是用于存储数据元素的数据域，另一个是用于存储下一个结点地址的指针域。
- 例如，在单链表中，每个结点的结构可以表示为：
  Data（数据域） | Next（指针域）
链表的分类
- 单链表 ：
  - 它是最简单的一种链表结构。每个结点只有一个指向下一个结点的指针。在单链表中，要访问某个结点，必须从头结点开始，沿着指针依次遍历。
  - 头指针是用来指向单链表的第一个结点的指针，头结点是指在单链表的第一个元素结点之前附加的一个结点，头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。头指针和头结点的区别在于，头指针是整个链表的标识，有了头指针才能访问到链表的第一个结点；而头结点则主要用于方便链表的操作，如在删除和插入操作时不用对第一个结点进行特殊处理。
- 双链表 ：
  - 双链表的每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。这样使得在链表中的插入和删除操作更加灵活，因为在双链表中可以从两个方向进行操作。
  - 例如，在删除一个结点时，只需要修改其前驱结点和后继结点的指针就可以了，而单链表删除结点时需要先找到被删除结点的前驱结点。
- 循环链表 ：
  - 循环链表是另一种形式的链表。在单链表中，最后一个结点的指针域为空（NULL），而在循环链表中，最后一个结点的指针域指向链表的头结点或者第一个结点，形成一个环。这样在遍历链表时可以很方便地循环访问整个链表。
特点
- 优点：
  - 动态存储分配，在使用过程中根据需要申请或释放存储单元，不存在顺序存储中可能出现的 “假溢出”（存储空间还有，但分配方式不支持继续存储）现象。
  - 插入和删除操作方便，只需要修改指针，不需要像顺序存储那样进行大量元素的移动。
- 缺点：
  - 存储密度较低。因为除了存储数据元素本身外，还需要存储指针等额外信息，相对于顺序存储结构来说，空间开销较大。
  - 不能随机访问，只能顺序访问。不能像顺序存储那样通过计算地址直接访问某个位置的元素，需要从头结点开始逐个遍历。

线性表的链式存储结构在很多实际应用中都有广泛使用，如在实现各种复杂的数据结构（如图的邻接表存储等）和算法（如多项式相加等场景）中都有重要作用。

note