数据结构（一）———线性表之顺序表、单向链表

一、线性表

线性表是n 个数据类型相同的元素组成的有限序列（n≥0，n=0 时叫 “空表”）

（1）特点

• 有唯一的 “第一个元素” 和 “最后一个元素”
• 除第一个元素外，每个元素只有一个前驱；除最后一个元素外，每个元素只有一个后继

（2）按存储方式分类

1. 顺序存储结构 → 顺序表

• 定义：用连续的内存空间存储线性表的元素，逻辑上相邻的元素物理地址也相邻。
• 底层实现：基于数组实现，分为静态顺序表和动态顺序表。
  • 静态顺序表：使用固定长度的数组，容量不可变。
  • 动态顺序表：使用动态分配的数组（如 C 语言的malloc/realloc），容量可按需扩容。
• 特点：
• 支持随机访问：通过下标直接访问，时间复杂度 O(1）
• 插入、删除：需要移动大量元素 时间复杂度 O(n)

2. 链式存储结构 → 链表

• 定义：用任意的内存空间存储元素，元素（节点）之间通过指针 / 引用链接，逻辑相邻的元素物理地址不一定相邻。
• 底层实现：基于节点结构体实现，节点包含数据域和指针域。
• 特点：
• 不支持随机访问，只能从头节点顺序遍历 时间复杂度 O(n)
• 插入、删除：只需修改指针 时间复杂度 O(1)

二、顺序表

1. 顺序表的定义

顺序表是用连续的内存空间存储线性表元素的结构 —— 逻辑上相邻的元素，物理存储位置也相邻。

2. 顺序表的存储结构

先拆解代码里的关键概念：

• #define MAXSIZE 100：定义顺序表的最大容量
• typedef int ElemType：给数据类型起别名（这里用int举例，可替换为其他类型）
• struct结构体：包含两个核心成员
  • data[MAXSIZE]：存储元素的数组
  • length：记录顺序表当前的实际长度

// 定义顺序表的最大容量 #define MAXSIZE 100 // 定义元素的数据类型（这里用int，可根据需求修改） typedef int ElemType; // 定义顺序表的结构体（静态分配版） typedef struct { ElemType data[MAXSIZE]; // 存储元素的数组 int length; // 顺序表当前的实际长度 } SeqList; // SeqList是这个结构体的别名（方便后续使用）

3. 顺序表的相关操作

（1）初始化顺序表

静态分配版初始化

作用：把顺序表初始化为 “空表”（长度设为 0）

// 初始化顺序表（静态分配版）：参数是顺序表的指针 void initList(SeqList *L) { L->length = 0; // 空表的长度为0 }

动态分配内存初始化

作用：通过malloc动态申请内存，更灵活地管理顺序表空间

// 定义顺序表的结构体（动态分配版） typedef struct { ElemType *data; // 指向动态分配数组的指针 int length; // 顺序表当前的实际长度 } SeqList; // 初始化顺序表（动态分配版）：返回初始化后的顺序表指针 SeqList* initList(SeqList *L) { // 为顺序表结构体本身分配内存 L = (SeqList*)malloc(sizeof(SeqList)); // 为存储元素的数组分配内存（容量为MAXSIZE） L->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE); L->length = 0; // 初始化为空表 return L; }

（2）在尾部添加元素

作用：在顺序表的末尾插入新元素，要先判断表是否已满

// 在顺序表尾部添加元素e，成功返回1，失败返回0 int appendElem(SeqList *L, ElemType e) { // 先判断：如果当前长度≥最大容量，表已满 if (L->length >= MAXSIZE) { printf("顺序表已满\n"); return 0; // 失败返回0 } // 把元素e存到数组的“当前长度”位置（因为数组从0开始） L->data[L->length] = e; L->length++; // 长度+1 return 1; // 成功返回1 }

（3）遍历顺序表

作用：打印顺序表中所有元素

// 遍历顺序表，打印所有元素 void listElem(SeqList *L) { // 循环从0到length-1（因为数组下标从0开始） for (int i = 0; i < L->length; i++) { printf("%d ", L->data[i]); // 打印第i个元素 } printf("\n"); // 换行 }

（4）在指定位置插入元素

作用：在第pos个位置插入元素 e（注意：pos 是 “逻辑位置”，要转成数组的 “物理下标”）

// 在第pos个位置插入元素e，成功返回1 int insertElem(SeqList *L, int pos, ElemType e) { // 先判断：pos的范围是否合法（不能超过当前长度） if (pos <= L->length) { // 从最后一个元素开始，向后移动一位（给新元素腾位置） for (int i = L->length-1; i >= pos-1; i--) { L->data[i+1] = L->data[i]; } // 把e存到pos对应的下标（pos-1，因为数组从0开始） L->data[pos-1] = e; L->length++; // 长度+1 } return 1; }

（5）删除指定位置的元素

作用：删除第pos个位置的元素，并通过指针e返回被删除的元素值

// 删除第pos个位置的元素，用e返回被删除的值，成功返回1 int deleteElem(SeqList *L, int pos, ElemType *e) { // 先把要删除的元素存到e中（pos转成数组下标：pos-1） *e = L->data[pos-1]; // 判断pos是否合法（不能超过当前长度） if (pos < L->length) { // 从pos位置开始，向前移动元素（覆盖被删除的位置） for (int i = pos; i < L->length; i++) { L->data[i-1] = L->data[i]; } } L->length--; // 长度减1 return 1; }

（6）查找元素

作用：查找元素e在顺序表中的逻辑位置（找不到返回 0）

// 查找元素e，返回其逻辑位置（从1开始），找不到返回0 int findElem(SeqList *L, ElemType e) { // 遍历顺序表所有元素 for (int i = 0; i < L->length; i++) { if (L->data[i] == e) { return i + 1; // 逻辑位置=数组下标+1 } } return 0; // 没找到返回0 }

三、顺序表总结

顺序表是线性表的基础实现方式，优点是随机访问快（通过数组下标直接访问），缺点是插入 / 删除元素时需要移动数据（效率较低）

四、链表

链表是线性表的链式存储结构，核心特点是：

• 用任意存储单元（连续 / 不连续）存储元素
• 每个元素（称为节点 node）包含两部分：
  • 数据域：存储元素本身信息
  • 指针域：存储下一个节点的地址（即 “链”）
• n 个节点通过指针域链接成一个链表，代表线性表的逻辑结构

五、单向链表的存储结构

链表的基本单元是 “节点”，用结构体定义：

// 定义元素的数据类型（这里用int举例） typedef int ElemType; // 定义链表节点的结构体 typedef struct node{ ElemType data; // 数据域：存储元素值 struct node *next; // 指针域：存储下一个节点的地址 }Node; // Node是结构体的别名（简化后续使用）

关键概念：

• struct node：自定义结构体类型，用于描述链表的单个节点
• ElemType data：数据域，存储节点的实际数据（可替换为 char、float 等类型）
• struct node *next：指针域，本质是一个指向struct node类型的指针，用于链接下一个节点
• Node：通过typedef给结构体起的别名，后续定义节点时可直接用Node代替struct node

六、单向链表的相关操作

（1）初始化链表

作用：创建一个头节点（作为链表的起始标识，数据域可存空值或链表长度），初始化为空链表

// 初始化链表：返回头节点的指针 Node* initList() { // 1. 为头节点分配内存（malloc函数动态申请空间） Node *head = (Node*)malloc(sizeof(Node)); // 2. 头节点数据域赋值（可存0或链表长度，空链表时暂存0） head->data = 0; // 3. 空链表时，头节点的next指针指向NULL（表示无后续节点） head->next = NULL; return head; // 返回头节点地址，后续操作通过头节点访问链表 } // 调用示例（main函数中使用） int main() { Node *list = initList(); // 得到初始化后的空链表 return 1; }

（2）头插法：在链表头部插入元素

作用：新元素插入到头节点之后（链表的第一个有效节点位置），插入顺序与最终存储顺序相反（比如先插 10 再插 20，链表为头→20→10）

// 头插法：向链表L（头节点指针）中插入元素e int insertHead(Node* L, ElemType e) { // 1. 为新节点分配内存（每个新元素都需要单独的节点空间） Node *p = (Node*)malloc(sizeof(Node)); // 2. 给新节点的data域赋值（存储要插入的元素） p->data = e; // 3. 新节点的next指向头节点原来的next（即原第一个有效节点） p->next = L->next; // 4. 头节点的next指向新节点（完成新节点的插入） L->next = p; return 1; // 插入成功返回1 } // 调用示例 int main() { Node *list = initList(); insertHead(list, 10); // 插入元素10 insertHead(list, 20); // 插入元素20（最终链表：头节点→20→10） return 1; }

（3）遍历链表

作用：打印链表中所有有效元素（跳过头节点，只输出数据域内容）

// 遍历链表L，打印所有有效元素 void listNode(Node* L) { // p指向第一个有效节点（头节点的next，跳过头节点本身） Node *p = L->next; // 循环条件：p不为NULL（未到达链表末尾） while(p != NULL) { printf("%d ", p->data); // 打印当前节点的data值 p = p->next; // p指向下一个节点，继续遍历 } printf("\n"); // 换行，优化输出格式 } // 调用示例（接上面main函数） int main() { Node *list = initList(); insertHead(list, 10); insertHead(list, 20); listNode(list); // 输出结果：20 10 return 1; }

（4）尾插法：更高效的尾部插入实现

作用：直接传入当前尾节点指针，避免重复遍历链表找尾，提升插入效率

// 尾插法（优化版）：传入当前尾节点tail，插入元素e，返回新的尾节点 Node* insertTail(Node *tail, ElemType e) { // 1. 为新节点分配内存 Node *p = (Node*)malloc(sizeof(Node)); // 2. 新节点数据域赋值 p->data = e; // 3. 原尾节点的next指向新节点 tail->next = p; // 4. 新节点的next指向NULL（作为新的尾节点） p->next = NULL; return p; // 返回新的尾节点，供下一次插入使用 } // 调用示例 int main() { Node *list = initList(); Node *tail = list; // 初始尾节点是头节点 tail = insertTail(tail, 10); // 插入10，更新尾节点 tail = insertTail(tail, 20); // 插入20，更新尾节点 listNode(list); // 输出结果：10 20 return 1; }

（5）指定位置插入元素

作用：在链表的第pos个有效节点位置插入元素（逻辑位置从 1 开始）。

原理：找到目标位置的前驱节点，将新节点的next指向前驱节点的原next，再将前驱节点的next指向新节点

// 在第pos个位置插入元素e，成功返回1，失败返回0 int insertNode(Node *L, int pos, ElemType e) { Node *p = L; // p指向头节点，用于找前驱节点 int i = 0; // 记录当前位置（头节点为0） // 1. 找到第pos-1个节点（目标位置的前驱节点） while(i < pos-1) { p = p->next; i++; // 若p为空，说明pos超出链表长度 if (p == NULL) { return 0; } } // 2. 为新节点分配内存并赋值 Node *q = (Node*)malloc(sizeof(Node)); q->data = e; // 3. 新节点的next指向前驱节点的原next q->next = p->next; // 4. 前驱节点的next指向新节点 p->next = q; return 1; } // 调用示例 int main() { Node *list = initList(); insertTail(list, 70); insertTail(list, 80); insertNode(list, 2, 75); // 在第2个位置插入75 listNode(list); // 输出结果：70 75 80 return 1; }

（6）删除指定位置的节点

作用：删除第pos个有效节点，释放节点内存避免泄漏

步骤：

1. 找到待删除节点的前驱节点
2. 用指针记录待删除节点
3. 前驱节点的next指向待删除节点的next
4. 释放待删除节点的内存

// 删除第pos个节点，成功返回1，失败返回0 int deleteNode(Node *L, int pos) { Node *p = L; // p指向头节点，找前驱节点 int i = 0; // 记录当前位置（头节点为0） // 1. 找到第pos-1个节点（前驱节点） while(i < pos-1) { p = p->next; i++; if (p == NULL) { return 0; } } // 2. 若前驱节点的next为空，说明pos超出范围 if(p->next == NULL) { printf("要删除的位置错误\n"); return 0; } // 3. 记录待删除节点 Node *q = p->next; // 4. 前驱节点的next跳过待删除节点 p->next = q->next; // 5. 释放待删除节点的内存 free(q); return 1; } // 调用示例 int main() { Node *list = initList(); insertTail(list, 70); insertTail(list, 80); deleteNode(list, 1); // 删除第1个节点（70） listNode(list); // 输出结果：80 return 1; }

（7）释放链表内存

作用：销毁链表，释放所有节点的内存（避免内存泄漏）

// 释放链表所有节点的内存 void freeList(Node *L) { Node *p = L->next; // p指向第一个有效节点 Node *q; // 记录下一个节点的地址 // 遍历链表，逐个释放节点 while(p != NULL) { q = p->next; // 先记录下一个节点 free(p); // 释放当前节点 p = q; // p指向下一个节点 } L->next = NULL; // 头节点的next置空，链表恢复为空 } // 调用示例 int main() { Node *list = initList(); insertTail(list, 70); insertTail(list, 80); freeList(list); // 释放链表 listNode(list); // 无输出（链表已空） return 1; }

（8）获取链表长度

作用：统计链表中有效节点的个数（跳过头节点）

// 获取链表的有效节点个数 int listLength(Node *L) { Node *p = L; // p从头节点开始 int len = 0; // 记录长度 while(p != NULL) { p = p->next; // 向后移动 len++; // 计数+1 } return len - 1; // 减去头节点的计数 } // 调用示例 int main() { Node *list = initList(); insertTail(list, 70); insertTail(list, 80); printf("链表长度：%d\n", listLength(list)); // 输出：2 return 1; }

七、链表与顺序表的区别

概念补充：

• 时间复杂度 O (1)：操作时间与数据量无关（比如顺序表下标访问）
• 时间复杂度 O (n)：操作时间随数据量增长而线性增长（比如链表遍历）