【考点分析】：
本章考察算法题的可能性极大，历年来该章节的算法题考了10次，其中链表考察了5次，数组5次；重点掌握后面提到的技巧及思想，没时间就暴力解！
【考频统计】
| 年份 | 考点 | 分值 |
| 2009 | 双指针问题（前后指针）：查找单链表中倒数第 k 个结点 | 15分 |
| 2010 | 数组循环左移（数组逆置问题） | 13分 |
| 2011 | 寻找两个数组的中位数 | 15分 |
| 2012 | 相交链表找交点 | 15分 |
| 2013 | 将两个升序链表合并为一条降序链表（选择）、数组主元素（摩尔投票法） 应用题线性表的顺序存储结构与链式存储结构的ASL问题 | 25分 |
| 2014 | 未考察 | |
| 2015 | 删除链表重复结点 | 15分 |
| 2016 | 单链表插入及其物理存储结构、双向循环链表删除结点操作、快排思想划分数组问题 | 19分 |
| 2017 | 未考察 | |
| 2018 | 数组中未出现的最小正整数 | 13分 |
| 2019 | 重排链表（快慢指针求中间结点、链表逆置、交叉合并链表） | 13分 |
| 2020 | 三元组的最短距离（多指针） | 13分 |
| 2021 | 单循环链表删除节点 | 2分 |
| 2022 | 未考察 | |
| 2023 | 顺序表的基本操作、非空双向链表删除结点 | 4分 |
一、顺序表的基本操作
1.1 顺序表的定义
1.1.1 静态分配 – 定义
#define MAX_SIZE 1024 // 定义顺序表的最大容量
typedef int ElemType; // 定义元素类型为 int
typedef struct {
ElemType data[MAX_SIZE]; // 静态数组，存储最多 MAX_SIZE 个元素
int length; // 当前元素个数
} SqList;1.1.2 动态分配 – 定义
typedef int ElemType; // 定义元素类型为 int
typedef struct {
ElemType* array; // 动态分配的数组指针
size_t max_size; // 数组最大容量
size_t length; // 当前元素个数
} SeqList;C语言中使用 malloc 和 free 进行空间的申请和释放 (C++则使用new和delete)。
1.1.3 静态分配 – 初始化
void InitList(SqList* L) {
if (L == NULL) return; // 检查空指针
L->length = 0; // 初始化长度为 0
}1.1.4 动态分配 – 初始化
int InitList(SeqList* L, size_t max_size) {
if (L == NULL || max_size == 0) return -1; // 检查空指针或无效容量
L->array = (ElemType *)malloc(sizeof(ElemType) * max_size); // 分配数组内存
if (L->array == NULL) return -1; // 检查内存分配失败
L->max_size = max_size; // 设置最大容量
L->length = 0; // 初始化长度为 0
return 0; // 成功
}1.2 插入操作
在顺序表的第i个位置（位序，非下标）插入元素x；
bool Insert(seqList &L, int i, int x) {
if(i > L.length + 1 || i < 1 || L.length == MaxSize) { //如果位序不在有效范围内或者顺序表已满，则插入失败；
return false;
}
for(int j = L.length; j >= i; --j) { //将待插入元素后面的元素通通后移一位；
L.data[j] = L.data[j-1];
}
L.data[i-1] = x; //在位序为i的位置放入元素x；
L.length ++; //数组长度+1；
return true;
}插入操作时间复杂度计算
设 Pi 是在第 i 个位置插入一个节点的概率，则在长度n的顺序表中插入一个元素，所需移动元素的平均次数为
1.3 删除操作
删除顺序表L中的第i个元素；
bool ListDelete(seqList &L, int i ) {
if(i < 1 || i > L.length) //如果删除元素的位置不在有效范围内，则删除失败；
return false;
int a = L.data[i-1]; //用变量a接收删除的元素；
for(int j = i - 1; j < L.length - 1; ++j) { //将待删除元素的后面位置的元素通通前移一位；
L.data[j] = L.data[j+1];
}
L.length --; //长度减1；
return true;
}删除操作时间复杂度
1.4 按值查找
在顺序表中查找第一个值为x的元素，并返回其位序；
int LocateElem(seqList &L, int x) {
for(int i = 0; i < L.length; ++i ) {
if(L.data[i] == x)
return i+1;
}
return -1; //查找失败
}按值查找的时间复杂度
由上面的几个操作可以看出，只要该操作涉及到遍历操作，那么其时间复杂度就为 O(n)
1.5 遍历输出
void ListVisit(seqList&L) {
for(int i = 0; i < L.length; ++i) {
printf("%d",L.data[i]);
}
}二、链表的定义和基本操作
2.1 单链表结点的数据结构描述
typedef struct LNode{
int data; //数据域
struct LNode *next; //代表指针域，指向直接后继元素；
}LNode,*LinkList; //结构体别名单链表是由表头指针唯一确定，因此单链表可以用头指针的名字来命名。若头指针名是L，则简称该链表为表L。
2.2 单链表的初始化
有头结点的单链表的初始化
LNode* InitList(void) {
LNode* head = malloc(sizeof(LNode)); // 分配头节点内存
if (head == NULL) return NULL; // 检查内存分配失败
head->next = NULL; // 初始化为空链表
head->data = 0; // 初始化数据字段（可选）
return head; // 返回头节点指针
}
无头结点的单链表的初始化
//无头结点的单链表的初始化
LNode InitList(){
LNode *head = NULL; //直接指向NULL，初始为空链表
return head;
}
由于带有头结点的链表更容易操作，因此如果题目中给的链表无头结点，可以自己申请一个 dummy 结点指向第一个结点，然后 dummy 就是新的头节点，之后就可以按照有头结点的链表进行操作
LNode* dummy = malloc(sizeof(LNode));
if (dummy == NULL) return NULL; // 检查内存分配失败
dummy->next = head; // 设置哑节点的下一个指针
dummy->data = 0; // 可选：初始化数据字段（视需求而定）2.3 单链表求表长（不含头结点）
int ListLength(LinkList L) {
if (L == NULL) return 0; // 检查无效链表
LNode* p = L->next; // 从第一个数据节点开始（带头部节点的情况）
int length = 0;
while (p) { // 遍历链表，计数节点
length++;
p = p->next;
}
return length; // 返回链表长度
}该操作遍历了整个链表，因此时间复杂度为O(n)
2.4 单链表按位查找
由于单链表不支持随机存取，所以只能从头结点开始遍历，直到找到目标结点，所以时间复杂度为 O(n)
LNode* getElem(LinkList L, int i) {
if (L == NULL || i < 0) return NULL; // 检查无效链表或负索引
LNode* p = L; // 从头节点开始（带头部节点的情况）
// 遍历直到第 i 个节点或链表末尾
while (p && i > 0) {
p p->next;
i--;
}
return p; // 返回第 i 个节点指针，或未找到返回 NULL
}2.5 单链表的按值查找
LNode* LocateElem(LinkList L, int target) {
if (L == NULL) return NULL; // 检查输入链表是否为空
LNode* p = L->next; // 从第一个数据节点开始（带头部节点的情况）
while (p && p->data != target) { // 遍历直到找到目标或链表末尾
p = p->next;
}
return p; // 返回指向目标节点的指针，或未找到返回 NULL
}2.6 头插法建立单链表
LinkList List_head_insert(LNode *&L) { //若链表要改变的话注意带上&
LNode *newNode;
int x; //假设输入x = -1 代表输入结束
L = (LinkList)malloc(sizeof(LNode)); // 创立头结点；
L->next = NULL; //初始化为空链表；
scanf("%d", &x); //输入结点的值；
while(x != -1) {
newNode = (LNode*)malloc(sizeof(LNode));
newNode->data = x;
newNode->next = L->next;
L->next = newNode;
scanf("%d", &x); // 读取下一个值
}
return L;
}采用头插法建立链表时，读入数据的顺序与生成链表中的元素的顺序是相反的，该重要特性常应用与链表的逆置。
由于插入每个结点的时间复杂度为O(1)，设单链表表长为 n,则总的时间复杂度为 O(n).
2.7 尾插法建立单链表
LinkList List_tail_insert(LNode *&L) { //LNode *&L == LinkList &L
LNode *newNode, *tail; //tail为指向链表的表尾指针；
int x;
L = (LinkList) malloc(sizeof(LNode));
L->next = NULL;
tail = L; // 初始时尾指针指向头结点
scanf("%d", &x);
while(x != -1) {
newNode = (LNode*)malloc(sizeof(LNode));
newNode->data = x;
newNode->next = NULL;
tail->next = newNode;
tail = newNode; // 尾指针指向新插入的节点
scanf("%d", &x); // 读取下一个值
}
return L;
}尾插法关键点在于建立一个始终指向表尾的指针Lnode *r,因此插入的总体时间复杂度为O(n)
2.8 插入结点操作
将值为x的新结点插入单链表的第 i 个位置；
后插法，找到第 i-1 个元素将新结点插入其后面
/**
* 在单链表的第i个位置插入新节点
* @param L 指向头指针的引用，用于修改头指针
* @param i 插入位置，从1开始计数
* @param x 新节点的数据值
* @return 插入成功返回true，失败返回false
*/
bool InsertNode(LNode *&L, int i, int x) {
// 定义三个指针：新节点、前驱节点、当前节点
LNode *newNode, *preNode, *curNode;
// 插入位置合法性检查，i必须大于0
if (i <= 0) return false;
// 查找第i-1个节点，即新节点的前驱节点
preNode = getElem(L, i-1);
// 如果前驱节点不存在（i超出链表长度），插入失败
if (preNode == NULL) return false;
// 保存前驱节点的下一个节点，即原来的第i个节点
curNode = preNode->next;
// 创建新节点并分配内存
newNode = (LNode*)malloc(sizeof(LNode));
// 检查内存分配是否成功
if (newNode == NULL) {
return false; // 内存分配失败
}
// 设置新节点的数据域和指针域
newNode->data = x;
newNode->next = curNode;
// 将前驱节点的next指向新节点，完成插入
preNode->next = newNode;
return true; // 插入成功
}该算法由于在查找第i-1个位置时涉及到了遍历操作，因此时间复杂度为 O(n)；
扩展：由上面的操作可知，对某个结点的前插操作可以转化为后插操作，前提是要找到第i-1个结点，如果题目已经给出了当前结点，我们可以将待插入结点插入当前结点的后面，然后交换这两个结点的值，那么就可以实现 O(1) 时间复杂度的算法
例如：将值为x的结点插入P结点的后面
void insertnode(LNode *p,int x ){
LNode *newNode;
newNode = (LNode*)malloc(sizeof(LNode));
newNode -> data = p-> data; //交换数据域
newNode -> next = p -> next; //修改指针域，注意不能颠倒顺序；
p -> next = newNode;
p -> data = x; //交换数据域
}2.9 删除结点操作
- 如果仅仅给出了要删除结点的位置 i，那么需要调用getElem来找到第i-1个结点p，然后p->next = p -> next -> next,再将该结点释放掉即可，由于查找i-1个结点需要遍历，因此该程序的时间复杂度为O(n)；
- 如果给出了当前结点的指针，那么要删除该结点的话就可以用下面的方法：既然不能干掉自己，那就变成儿子，在干掉儿子
/**
* 删除指定节点的后续节点（优化版）
* @param p 指向要删除节点的前一个节点的指针
* @return 删除成功返回true，失败（p为空或p的下一个节点为空）返回false
*/
bool deleteNextNode(LNode *p) {
// 防御性编程：检查输入指针是否有效
if (p == NULL || p->next == NULL) {
return false; // 删除失败
}
LNode *q = p->next; // 保存待删除节点的指针
p->next = q->next; // 从链表中移除待删除节点
free(q); // 释放待删除节点的内存
return true; // 删除成功
}本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客
