数据结构基础
基本概念
1. 数据
是描述客观事实的符号，是计算机中可以操作的对象，能被计算机识别，并输入给计算机处理的符号集合。
2. 数据对象
性质相同的数据元素集合，是数据的子集。
3. 数据元素
是组成数据的、具有一定意义的基本单位，被计算机当作整体来处理。
4. 数据项
数据不可再分的最小单位。
5. 数据结构研究数据元素之间的关系
逻辑关系（结构）：从逻辑上存在的一种联系。 存储关系（结构）：存储到计算机的结构。
6. 数据结构的三要素
不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。 包括：逻辑结构、物理结构、算法。
逻辑结构与物理结构
常见的逻辑结构
逻辑结构是指数据对象中数据元素之间的相互关系。
1. 集合结构
数据元素除了同属一个集合之外，它们之间没有必然联系。
2. 线性结构
其中的数据元素之间是一对一的关系。
3. 树形结构
其中的数据元素之间存在一对多的层次关系。
4. 图形结构
其中的数据元素之间是多对多的关系。
物理结构
物理结构是指：数据的逻辑结构在计算机中的存储形式。
1. 顺序结构
- 定义：是把数据元素存放在地址连续的存储单元里，其数据之间的逻辑关系和物理关系是一致的。
- 特性：
- 访问元素方便，时间复杂度为 O(1)
- 插入和删除不方便
2. 链式结构
把数据元素存放在任意的存储单元里，这组存储单元可以说连续的，也可以是不连续的。
2) 特性：
- 访问元素不便，需要遍历，时间复杂度为 O(n)
- 插入和删除数据方便
3. 索引结构
根据地址就可以找到对应的关键字。可以理解成一个黄页，你根据一个人的名字，就可以找到他的电话。所以索引存储又被称为直接寻址。数组就是一个常见的索引存储结构，可以通过下标来直接访问。索引表是有序的。
4. 散列结构（哈希结构）
'散列存储'名字中的'散列'就是常听到的 hash（哈希值），hash 是通过一种算法来运算出来的，比如 MD5。在这种存储格式下，地址会通过 hash 算法来运算成一个相同长度的 hash 值，然后存放这个 hash 值，而不是直接存放地址。在访问关键字的时候会通过运算解码 hash 值，然后再访问。
算法
算法是解决问题的步骤，不同的数据结构决定了所对应的算法不同。
1. 特性
输入、输出、有穷性、确定性、可行性。
2. 设计
准正确性、健壮性、可读性、时间和空间效率。
3. 算法好坏的度量——算法效率
时间复杂度、空间复杂度。
线性表
零个或多个数据元素的有限序列。
1. 顺序表
以顺序结构存储的线性表。
2. 链表
- 定义：以链式结构存储的线性表。
- 特性：
- 一个节点分为数据域和指针域，数据域存放当前节点的数据部分，指针域存放链表的下一个节点（后继位置）的地址。
- 链表的第一个节点的存储位置叫做头指针，第一个节点叫头节点。线性链表的最后一个节点指针为 NULL。头节点的后一个节点是首节点，头节点的数据域可以不存储任何信息，一般对链表的操作是从首节点开始，但是删除链表的尾删方式是从头节点开始的。
- 头指针和头节点的异同
链表的基本操作
编写程序时要充分考虑空链表、只有一个有效节点、用户输入数据为 NULL 等特殊情况的排查。在判断条件中要考虑到逻辑与的短路特性，基本操作的前提都是在链表内完成的。
1. 创建链表
指针域的定义如下所示。
2. 增加节点
1) 头插
从头部插入，先插入的后输出。例如头插：1, 2, 3, 4；打印输出是：4, 3, 2, 1。
- Step 1: 创建一个新节点并给值。
- Step 2: 让新节点指向原首节点：将原首节点的地址存在新节点的指针域。
- Step 3: 让头节点指向新节点：将新节点的地址存放在头节点指针域中。
Step 2 和 Step 3 的顺序不可以变，如果 Step 3 先操作，头节点的指针域信息会被覆盖，首节点的地址会丢失。
2) 尾插
从尾部插入，先插入的先输出。例如尾插：1, 2, 3, 4；打印输出是：1, 2, 3, 4。
- Step 1: 创建一个新节点并给值，将新节点的指针域初始化为 NULL。
- Step 2: 找到尾节点。
- Step 3: 链接链表：将新节点的地址存放到当前尾节点的指针域，链接成功后，新节点是新的尾节点。
p_new->pnext = NULL;必须写，因为此时插入的节点是尾节点，尾节点指针域必须为空。
3. 删除节点
1) 头删
- Step 1: 定义一个指针变量指向首节点。
- Step 2: 链接节点：让头节点指向即将删除的节点的下一个节点：将首节点的下一个节点地址装入头的指针域。
- Step 3: 释放 p 所在的空间。
链表只有一个节点时也适用。
2) 尾删
- Step 1: 找到尾节点的前一个节点，由于边界条件的判断需要两次 next，指针
p必须从头节点（phead）开始遍历，而不是从首节点（phead->pnext）开始，主要是为了安全处理链表只有一个有效节点的边界情况。当头节点作为起始点时，当链表仅有一个节点时，p->pnext->pnext直接为NULL，循环不会执行，可直接释放尾节点并更新头节点的指针；若从首节点开始，此时p即为尾节点，p->pnext为NULL，访问p->pnext->pnext会导致对空指针解引用，引发段错误。因此，从头节点出发能统一处理各种节点数量情况，避免非法内存访问。 - Step 2: 释放尾节点。
- Step 3: 将尾节点的前一个节点指针域设为 NULL。
4. 修改节点
- Step 1: 从头节点开始比较，找到指定值所在的节点。
while((p != NULL) && (p->data != old))这里的条件不能调换顺序，因为如果调换为(p->data != old) && (p != NULL)，当p为NULL时，会先访问p->data导致段错误。目前的顺序是正确的，利用了逻辑与的短路特性。 - Step 2: 将指定节点的值修改为指定值。
以下 if 条件语句中
&& (p->data == old)这个判断是多余的。因为循环结束的条件只有两种可能： p == NULL（遍历完链表没找到）p->data == old（找到了） 所以只要p != NULL，就一定是找到了目标节点。
5. 查找节点
- Step 1: 从头节点开始遍历查找指定值所在的节点。
- Step 2: 找到指定节点后返回节点地址，若链表为空或遍历结束未找到则返回
NULL。while 的条件语句也不可以调换顺序，因为逻辑与的短路特性存在，指定值和节点数据域相等的前提应该是在链表内。
6. 补充
-
判断链表是否为空 在非空链表中，判断链表是否只有一个有效节点是：
phead->pnext->pnext == NULL；
-
遍历打印链表数据域
-
计算链表长度
