一. 线性表
1.定义
线性表是由n(n>=0)个具有相同数据类型的数据元素构成的有限序列。其中，元素之间通过顺序关系排列，每个元素有且只有一个直接前驱和一个直接后继(除首尾元素外)
二.线性表的顺序表示(顺序表)
1.存储方式
使用连续的内存空间(数组)存储元素，逻辑相邻的元素在物理位置上也相邻
2.特点
优点：支持随机访问，时间复杂度为O(1)
缺点：进行插入/删除操作时，需要移动元素，平均时间复杂度为O(n)
3.动态扩容
当数组空间不足时，可以重新分配更大的空间，并复制数据
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 100 // 顺序表初始最大容量
// 顺序表结构体定义
typedef struct SeqList{
int *data; // 指向动态分配数组的指针
int length; // 当前表长（有效元素个数）
int capacity; // 当前分配的存储容量
}SeqList;
/* 初始化顺序表
* 参数：L - 指向顺序表结构的指针
* 流程：
* 1. 申请MAXSIZE大小的连续内存空间
* 2. 初始化长度为0
* 3. 设置当前容量为MAXSIZE
*/
void InitList(SeqList *L){
L->data = (int *)malloc(sizeof(int) * MAXSIZE); // 分配初始内存
L->length = 0; // 初始空表
L->capacity = MAXSIZE; // 记录最大容量
}
/* 插入元素函数
* 参数：L - 顺序表指针，index - 插入位置（从1开始），value - 插入值
* 返回值：bool - 是否插入成功
* 流程：
* 1. 位置有效性检查（1<=index<=length+1）
* 2. 空间不足时自动扩容（2倍扩容策略）
* 3. 元素后移操作（从最后一个元素开始到目标位置）
* 4. 插入新元素并更新表长
*/
bool InsertList(SeqList *L, int index, int value){
// 位置合法性校验（包括空表情况下的校验）
if(index < 1 || index > L->length + 1){
return false; // 插入位置非法
}
// 空间扩容机制（当表满时自动扩容）
if(L->length >= L->capacity){
// 尝试扩容为当前容量的2倍
int *NewData = (int *)realloc(L->data, sizeof(int) * L->capacity * 2);
if(!NewData){ // 内存分配失败
return false;
}
L->data = NewData; // 更新数据指针
L->capacity *= 2; // 更新容量记录
}
// 元素后移操作（从后往前移动防止覆盖）
for(int i = L->length; i >= index; i--){
L->data[i] = L->data[i-1]; // 将index-1位置后的元素依次后移
}
// 插入新元素并更新表长
L->data[index-1] = value; // 数组下标从0开始，故减1
L->length++; // 表长增加
return true;
}
/* 打印顺序表
* 参数：L - 顺序表指针
* 流程：
* 1. 遍历有效元素
* 2. 空格分隔元素
* 3. 末尾换行
*/
void PrintList(SeqList *L){
for(int i = 0; i < L->length; i++){
printf("%d ", L->data[i]); // 逐个输出元素
}
printf("\n"); // 换行保持输出格式
}
/* 主函数测试流程
* 测试策略：
* 1. 初始化测试
* 2. 正常插入（头部、中间、尾部）
* 3. 边界测试（尾部追加）
* 4. 异常测试（非法位置插入）
*/
int main() {
SeqList L;
InitList(&L);
// 初始状态验证
printf("初始顺序表：");
PrintList(&L); // 应输出 []
// 正常插入测试（验证不同位置的插入逻辑）
InsertList(&L, 1, 10); // 首部插入（空表插入）
InsertList(&L, 2, 30); // 尾部插入（容量足够时）
InsertList(&L, 2, 20); // 中间插入（触发元素移动）
printf("插入3个元素后：");
PrintList(&L); // 应输出 [10 20 30]
// 边界测试（验证最大容量的插入）
InsertList(&L, 4, 40); // 尾部追加（验证边界条件）
printf("尾部追加后：");
PrintList(&L); // 应输出 [10 20 30 40]
// 异常测试（验证错误处理能力）
bool result = InsertList(&L, 6, 50); // 非法位置（当前长度4，只能插入到位置5）
printf("非法插入结果：%s\n", result ? "成功" : "失败"); // 应输出失败
return 0;
}三.线性表的链式表示和实现(链表)
1.存储方式
通过节点(包含数据域和指针域)动态分配内存，逻辑相邻的元素在物理位置上不一定相邻
2.类型
单链表： 每个节点指向下一个结点
双链表： 节点包含前驱和后继指针
循环链表： 尾节点指向头节点
3.特点
优点： 进行插入/删除操作时高效，时间复杂度为O(1)
缺点： 无法随机访问节点值，必须从头遍历，时间复杂度为O(n)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/* 链表节点结构体
* Data: 节点存储的数据（整型）
* Next: 指向下一个节点的指针 */
typedef struct Node{
int Data;
struct Node *Next;
}Node;
/* 初始化链表头节点
* 返回值：已分配内存的头节点指针
* 注意：头节点不存储有效数据，仅作为链表入口 */
Node* InitList(){
Node* Head = (Node*)malloc(sizeof(Node));
Head->Next = NULL;
return Head;
}
/* 头插法插入节点
* Head: 链表头节点指针
* Value: 要插入的整型数据
* 流程：1.创建新节点 2.调整指针指向 */
void InsertHead(Node* Head, int Value){
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = Value;
NewNode->Next = Head->Next;
Head->Next = NewNode;
}
/* 尾插法插入节点
* Head: 链表头节点指针
* Value: 要插入的整型数据
* 流程：1.遍历到最后一个节点 2.在末尾插入新节点 */
void InsertTail(Node* Head, int Value){
Node* Current = Head;
while(Current->Next != NULL){
Current = Current->Next;
}
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = Value;
NewNode->Next = NULL;
Current->Next = NewNode;
}
/* 删除指定值的节点
* Head: 链表头节点指针
* Value: 要删除的整型数据
* 返回值：true删除成功，false未找到数据
* 流程：双指针法遍历，找到后调整指针并释放内存 */
bool DeleteNode(Node* Head, int Value){
Node* Previous = Head;
Node* Current = Head->Next;
while(Current!=NULL){
if(Current->Data == Value){
Previous->Next = Current->Next;
free(Current);
return true;
}
Previous = Current;
Current = Current->Next;
}
return false;
}
/* 修改指定位置节点的值
* Head: 链表头节点指针
* pos: 要修改的位置（从0开始计数）
* NewValue: 新的整型数据值
* 注意：如果位置超出链表长度，不会修改任何节点 */
void ModifyNode(Node* Head, int pos, int NewValue){
Node* Current = Head->Next;
int count = 0;
while(Current!=NULL && count<pos){
Current = Current->Next;
count++;
}
if(Current!=NULL){
Current->Data = NewValue;
}
}
/* 搜索节点位置
* Head: 链表头节点指针
* Value: 要查找的整型数据
* 返回值：找到返回位置索引（从0开始），未找到返回-1 */
int SearchNode(Node* Head, int Value){
Node* Current = Head->Next;
int pos = 0;
while(Current!=NULL){
if(Current->Data == Value){
return pos;
}
Current = Current->Next;
pos++;
}
return -1;
}
/* 打印整个链表
* Head: 链表头节点指针
* 输出格式：数据->数据->...->NULL */
void PrintList(Node* Head){
Node* Current = Head->Next;
while(Current!=NULL){
printf("%d->", Current->Data);
Current = Current->Next;
}
printf("NULL \n");
}
/* 反转链表
* Head: 链表头节点指针
* 实现方式：三指针法原地反转
* 流程：1.逐个节点反转指向 2.最后更新头节点指针 */
void ReverseList(Node* Head){
Node* Previous = NULL;
Node* Current = Head->Next;
Node* Next = NULL;
while(Current!=NULL){
Next = Current->Next;
Current->Next = Previous;
Previous = Current;
Current = Next;
}
Head->Next = Previous;
}
/* 清空链表（保留头节点）
* Head: 链表头节点指针
* 流程：逐个释放所有节点内存，最后重置头节点指针 */
void ClearList(Node* Head){
Node* Current = Head->Next;
Node* Next = NULL;
while(Current!=NULL){
Next = Current->Next;
free(Current);
Current = Next;
}
Head->Next = NULL;
}
int main(){
Node* Head = InitList();
InsertHead(Head, 1);
InsertHead(Head, 2);
InsertHead(Head, 3);
InsertTail(Head, 4);
InsertTail(Head, 5);
PrintList(Head);
DeleteNode(Head, 3);
PrintList(Head);
ModifyNode(Head, 1, 6);
PrintList(Head);
printf("Position of 6: %d\n", SearchNode(Head, 6));
ReverseList(Head);
PrintList(Head);
ClearList(Head);
PrintList(Head);
return 0;
}4.部分函数解析
(1)链表逆置(ReverseList):
/* 三指针法实现链表逆置
* 时间复杂度：O(n) 空间复杂度：O(1)
* 执行过程：
* 1. 初始化三个指针：Previous(前驱)、Current(当前)、Next(后继)
* 2. 遍历链表，逐个反转节点指向
* 3. 最后更新头节点指针 */
void ReverseList(Node* Head){
Node* Previous = NULL; // 前驱指针初始化为空
Node* Current = Head->Next; // 当前指针指向第一个有效节点
Node* Next = NULL; // 后继指针用于临时存储
while(Current != NULL){
Next = Current->Next; // 保存下一个节点
Current->Next = Previous;// 反转指针方向
Previous = Current; // 前驱指针前移
Current = Next; // 当前指针前移
}
Head->Next = Previous; // 更新头节点指向新的首节点
}(2) 头插法(InsertHead)
/* 头插法特点：
* 1. 新节点总是插入在链表头部
* 2. 插入顺序与最终链表顺序相反
* 3. 时间复杂度：O(1) */
void InsertHead(Node* Head, int Value){
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = Value;
NewNode->Next = Head->Next; // 新节点指向原首节点
Head->Next = NewNode; // 头节点指向新节点
}(3)尾插法(InsertTail)
/* 尾插法特点：
* 1. 新节点总是追加在链表末尾
* 2. 插入顺序与最终链表顺序一致
* 3. 时间复杂度：O(n) */
void InsertTail(Node* Head, int Value){
Node* Current = Head;
while(Current->Next != NULL){ // 遍历到最后一个节点
Current = Current->Next;
}
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = Value;
NewNode->Next = NULL; // 新节点作为末节点
Current->Next = NewNode; // 原末节点指向新节点
}