第二章线性表

2.1 线性表的顺序表示

线性表（list）：n个具有相同数据类型的数据元素的优先序列。
顺序表：用一组地址连续的存储单元依次存储线性表中的数据元素。
特点：
1. 逻辑相邻的两个元素在物理地址上也相邻；
2. 随机存取；
3. 存储密度高；
4. 插入删除不方便，需要移动大量元素。
操作：
1. 插入：在表长为n的顺序表的第i个位置上插入元素，将插入位置开始的元素都向后移动一个位置，移动 n-i+1 个元素，平均时间复杂度：O(n)。
2. 删除：在表长为n的顺序表中删除第i个元素，将ai~an都向前移动一个位置，共移动n-i个元素，平均时间复杂度：O(n)。
3. 查找：
  - 按照序号查找：根据线性表随机存取的特点，时间复杂度为O(1)；
  - 按值查找：比较次数与查找值在表中位置、表长有关，平均比较次数(n+1)/2，时间复杂度O(n)。

2.2 线性表的链式存储

一、单向链表

单链表：通过指针连接各数据元素，不需要使用物理地址连续的存储单元，非随机存取

js
//线性表的单链表存储结构：
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

结点(node)：结点构成链表，由数据域和指针域（存储后续位置）构成，结构为：

数据域(data) 指针域(next)
头指针：用来标识单链表，指向链表中第一个结点的存储位置。头指针为NULL时为空表。
头结点：为了方便操作，在单链表的第一个结点之前设置一个数据域不存储任何信息、指针域指向第一结点的指针的结点。
- 头结点与头指针：无论带不带头结点，头指针始终指向链表的第一个结点；
- 头结点是带头结点的链表的第一个结点，结点内通常不存储信息。
带头结点的优点：
- 由于第一个数据结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表中其他位置上的操作一致，无需进行特殊处理。
- 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。
基本操作
1. 头插法建表：从空表开始将新结点插入当前链表的头结点后。读入数据的顺序与生成链表中元素的顺序相反。时间复杂度为O(n) 核心代码：
```
js
s->next = L->next; //1⃣先用新结点S的指针指向原链表的第一个结点；
L->next = s; //2⃣再将头结点的指针L指向新结点。
```
2. 尾插法：将新结点插入当前表尾，使用尾指针r始终指向尾结点。读入数据的顺序与生成链表中元素的顺序一致。时间复杂度为O(n) 核心代码：
```
js
r->next = s; //1⃣原尾结点指向新的结点；
r = s; //2⃣插入的结点成为新的尾结点。
```
3. 查找：按值查找和按序号查找；链表非随机存取，两种查找方式都需要从头结点开始遍历查找。时间复杂度为O(n)
4. 插入：将数据域为x的新结点S插入第i个位置。时间复杂度为O(n) 核心代码：
```
js
p = GetElem(L, i-1); //1⃣找到插入的位置；
s->next = p->next; //2⃣新结点s指向插入位置的下一结点；
p->next = s; //3⃣结点P指向S
```
5. 删除：删除链表中的第i个结点。时间复杂度为O(n) 核心代码：
```
js
p = GetElem(L, i-1);
q = p->next;
p->next = q->next
```
  注
  插入删除时注意顺序，插入时要让新结点先指向插入位置的后一个结点，删除时要先让前驱结点指向删除位置的后继结点，避免链表断开结点丢失。

二、循环链表

表中最后一个结点的指针域指向头结点，整个链表形成一个环。可以从表的任意位置开始遍历整个链表。
判空条件：头结点的指针等于头指针。

三、双向链表

克服单链表只能顺指针往后查找其他结点的缺点，双向链表中有两个指针域：一个指向前驱，一个指向后继。
双向链表也可以有循环表示。

目录

第二章 线性表

2.1 线性表的顺序表示

2.2 线性表的链式存储

一、单向链表

二、循环链表

三、双向链表

第二章线性表