本文深入讲解 C 语言中指针与结构体的结合应用，涵盖单链表、双向链表的创建与操作（插入、删除、反转、环检测），以及数组栈、链式栈和循环队列、链式队列的实现原理。通过括号匹配、生产者 - 消费者模型及学生成绩管理系统等案例，演示了动态内存管理、边界条件处理及常见错误避坑指南，帮助读者掌握复杂数据结构的底层逻辑与工程实践。
[提示] 掌握指针结合结构体实现线性数据结构的核心原理，理解链表、栈、队列的存储特性与访问规则； [提示] 精通单链表、双向链表的创建、插入、删除、查找等基础操作，能够解决链表环检测、反转等进阶问题； [提示] 熟练使用数组栈、链式栈及循环队列、链式队列的实现逻辑，明确不同结构的适用场景； [提示] 结合实际项目案例，体会指针在复杂数据结构中的内存管理技巧，提升代码的模块化与高效性。
在 C 语言中，结构体用于封装多个不同类型的数据，而指针则负责连接这些数据单元，形成灵活的复杂数据结构。指针与结构体的结合，是实现链表、栈、队列等动态数据结构的核心基础——通过结构体存储数据，指针指向结构体实例，实现数据单元的链式关联。
结构体指针的声明与使用是基础，其核心语法为：
// 结构体定义
struct 结构体名 {
成员类型 成员名;
// ... 其他成员
};
// 结构体指针声明
struct 结构体名 *指针变量名;
[提示] 技巧：通过 -> 运算符访问结构体指针的成员（等价于 (*指针变量名).成员名），是后续复杂数据结构操作的常用语法。
示例 1：结构体指针的基本使用
#include <stdio.h>
#include <stdlib.h>
// 定义学生结构体
struct Student {
int id; // 学号
char name[20]; // 姓名
float score; // 成绩
struct Student* next; // 指向另一个 Student 的指针（为链表做铺垫）
};
int main() {
// 方式 1：栈上创建结构体，指针指向该结构体
struct Student stu1 = {101, "张三", 92.5, NULL};
struct Student* pStu1 = &stu1;
// 访问结构体成员（两种等价方式）
printf("学号：%d，姓名：%s，成绩：%.1f\n", pStu1->id, (*pStu1).name, pStu1->score);
// 方式 2：堆上创建结构体（动态内存分配），指针指向堆内存
struct Student* pStu2 = (struct Student*)malloc(sizeof(struct Student));
if(pStu2 == NULL) {
// 检查内存分配是否成功
printf("[注意] 内存分配失败！\n");
return -1;
}
// 给堆上的结构体赋值
pStu2->id = 102;
strcpy(pStu2->name, "李四"); // 字符串赋值需用 strcpy
pStu2->score = 88.0;
pStu2->next = NULL;
printf("学号：%d，姓名：%s，成绩：%.1f\n", pStu2->id, pStu2->name, pStu2->score);
// 释放堆内存（避免内存泄漏）
free(pStu2);
pStu2 = NULL; // 置空指针，避免野指针
return 0;
}
运行结果：
学号：101，姓名：张三，成绩：92.5
学号：102，姓名：李四，成绩：88.0
[注意] 堆上的结构体必须通过 malloc 分配内存，且使用后需通过 free 释放，否则会导致内存泄漏；释放后需将指针置空，避免野指针访问。
频繁使用 struct 结构体名 * 声明指针会显得繁琐，通过 typedef 为结构体类型起别名，可极大简化代码：
// 方式 1：先定义结构体，再 typedef
struct Student {
int id;
char name[20];
};
typedef struct Student Student; // 别名 Student，后续可直接用 Student 代替 struct Student
// 方式 2：定义结构体时直接 typedef（推荐）
typedef struct Student {
int id;
char name[20];
struct Student* next;
} Student, *PStudent; // Student 是结构体类型别名，PStudent 是结构体指针类型别名
示例 2：typedef 简化结构体指针使用
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义结构体并起别名
typedef struct Student {
int id;
char name[20];
float score;
struct Student* next;
} Student, *PStudent; // PStudent = struct Student*
// 函数：创建学生节点（返回结构体指针）
PStudent createStudent(int id, const char* name, float score) {
PStudent pStu = (PStudent)malloc(sizeof(Student));
if(pStu == NULL) {
printf("[注意] 节点创建失败！\n");
return NULL;
}
pStu->id = id;
strcpy(pStu->name, name);
pStu->score = score;
pStu->next = NULL; // 初始化 next 指针为 NULL，避免野指针
return pStu;
}
// 函数：打印学生信息
void printStudent(PStudent pStu) {
if(pStu != NULL) {
printf("学号：%d，姓名：%s，成绩：%.1f\n", pStu->id, pStu->name, pStu->score);
}
}
int main() {
PStudent pStu1 = createStudent(101, "王五", 95.0);
PStudent pStu2 = createStudent(102, "赵六", 89.5);
printStudent(pStu1);
printStudent(pStu2);
// 释放内存
free(pStu1);
free(pStu2);
pStu1 = NULL;
pStu2 = NULL;
return 0;
}
运行结果：
学号：101，姓名：王五，成绩：95.0
学号：102，姓名：赵六，成绩：89.5
[成功] 结论：typedef 不仅简化了结构体指针的声明，还提升了代码的可读性和可维护性，是复杂数据结构开发中的必备技巧。
链表是一种线性数据结构，其数据单元（节点）通过指针串联，节点在内存中无需连续存储——这种特性使其支持动态扩容（无需预先指定大小），插入、删除操作效率高（无需移动大量元素）。链表主要分为单链表、双向链表、循环链表，本节重点讲解最常用的单链表和双向链表。
单链表的每个节点包含'数据域'和'指针域'：数据域存储数据，指针域（next）指向后一个节点，最后一个节点的 next 指针为 NULL（表示链表结尾）。
示例 3：单链表的完整实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义单链表节点结构体
typedef struct ListNode {
int data; // 数据域
struct ListNode* next; // 指针域：指向后一个节点
} ListNode, *LinkList;
// 1. 链表初始化：创建空链表（头节点为 NULL）
LinkList initLinkList() {
return NULL; // 空链表的头指针为 NULL
}
// 2. 节点插入：尾插法（在链表末尾添加节点）
int insertTail(LinkList *head, int data) {
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
if(newNode == NULL) {
printf("[注意] 节点内存分配失败！\n");
return -1;
}
newNode->data = data;
newNode->next = NULL;
// 情况 1：链表为空（头指针为 NULL），新节点作为头节点
if(*head == NULL) {
*head = newNode;
return 0;
}
// 情况 2：链表非空，遍历到末尾节点
ListNode *p = *head;
while(p->next != NULL) {
p = p->next; // 移动到下一个节点
}
p->next = newNode; // 末尾节点的 next 指向新节点
return 0;
}
// 3. 节点插入：头插法（在链表头部添加节点）
int insertHead(LinkList *head, int data) {
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
if(newNode == NULL) {
printf("[注意] 节点内存分配失败！\n");
return -1;
}
newNode->data = data;
// 新节点的 next 指向原头节点，头指针指向新节点
newNode->next = *head;
*head = newNode;
return 0;
}
// 4. 节点插入：指定位置插入（位置从 1 开始）
int insertPos(LinkList *head, int pos, int data) {
// 检查位置合法性（pos < 1 或 链表为空但 pos > 1）
if(pos < 1 || (*head == NULL && pos > 1)) {
printf("[注意] 插入位置非法！\n");
return -1;
}
// 位置 1：等价于头插法
if(pos == 1) {
return insertHead(head, data);
}
// 查找第 pos-1 个节点（插入位置的前驱节点）
ListNode *p = *head;
int count = 1;
while(p != NULL && count < pos - 1) {
p = p->next;
count++;
}
// 若 pos 超过链表长度（p 为 NULL），插入失败
if(p == NULL) {
printf("[注意] 插入位置超出链表长度！\n");
return -1;
}
// 创建新节点并插入
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
if(newNode == NULL) {
printf("[注意] 节点内存分配失败！\n");
return -1;
}
newNode->data = data;
newNode->next = p->next; // 新节点的 next 指向前驱节点的原后继
p->next = newNode; // 前驱节点的 next 指向新节点
return 0;
}
// 5. 链表遍历：打印所有节点数据
void traverseLinkList(LinkList head) {
if(head == NULL) {
printf("[注意] 链表为空！\n");
return;
}
ListNode *p = head;
printf("链表元素：");
while(p != NULL) {
printf("%d ", p->data);
p = p->next; // 移动到下一个节点
}
printf("\n");
}
// 6. 链表查找：按值查找（返回第一个匹配节点的位置，从 1 开始；未找到返回 0）
int findByValue(LinkList head, int data) {
if(head == NULL) {
printf("[注意] 链表为空！\n");
return 0;
}
ListNode *p = head;
int pos = 1;
while(p != NULL) {
if(p->data == data) {
return pos; // 找到，返回位置
}
p = p->next;
pos++;
}
return 0; // 未找到
}
// 7. 链表查找：按位置查找（返回该位置的节点指针；位置非法返回 NULL）
ListNode *findByPos(LinkList head, int pos) {
if(head == NULL || pos < 1) {
printf("[注意] 链表为空或位置非法！\n");
return NULL;
}
ListNode *p = head;
int count = 1;
while(p != NULL && count < pos) {
p = p->next;
count++;
}
return p; // 若 pos 超出长度，返回 NULL
}
// 8. 节点删除：按值删除（删除第一个匹配的节点）
int deleteByValue(LinkList *head, int data) {
if(*head == NULL) {
printf("[注意] 链表为空，无法删除！\n");
return -1;
}
ListNode *p = *head; // 当前节点
ListNode *prev = NULL; // 前驱节点
// 情况 1：头节点就是要删除的节点
if(p->data == data) {
*head = p->next; // 头指针指向头节点的后继
free(p); // 释放头节点内存
p = NULL;
return 0;
}
// 情况 2：查找要删除的节点及其前驱节点
while(p != NULL && p->data != data) {
prev = p;
p = p->next;
}
// 未找到要删除的节点
if(p == NULL) {
printf("[注意] 未找到值为%d的节点！\n", data);
return -1;
}
// 前驱节点的 next 指向当前节点的后继，释放当前节点内存
prev->next = p->next;
free(p);
p = NULL;
return 0;
}
// 9. 节点删除：按位置删除（位置从 1 开始）
int deleteByPos(LinkList *head, int pos) {
if(*head == NULL || pos < 1) {
printf("[注意] 链表为空或位置非法！\n");
return -1;
}
ListNode *p = *head; // 当前节点
ListNode *prev = NULL; // 前驱节点
// 情况 1：删除头节点（pos=1）
if(pos == 1) {
*head = p->next;
free(p);
p = NULL;
return 0;
}
// 情况 2：查找第 pos 个节点及其前驱节点
int count = 1;
while(p != NULL && count < pos) {
prev = p;
p = p->next;
count++;
}
// 位置超出链表长度
if(p == NULL) {
printf("[注意] 删除位置超出链表长度！\n");
return -1;
}
// 删除节点
prev->next = p->next;
free(p);
p = NULL;
return 0;
}
// 10. 链表销毁：释放所有节点内存
void destroyLinkList(LinkList *head) {
ListNode *p = *head;
while(p != NULL) {
ListNode *temp = p; // 保存当前节点
p = p->next; // 移动到下一个节点
free(temp); // 释放当前节点
temp = NULL;
}
*head = NULL; // 头指针置空，避免野指针
printf("[成功] 链表销毁成功！\n");
}
// 11. 链表长度：返回节点个数
int getLinkListLength(LinkList head) {
int len = 0;
ListNode *p = head;
while(p != NULL) {
len++;
p = p->next;
}
return len;
}
// 主函数测试
int main() {
LinkList head = initLinkList(); // 初始化空链表
// 尾插法插入节点
insertTail(&head, 10);
insertTail(&head, 20);
insertTail(&head, 30);
printf("尾插法插入后：");
traverseLinkList(head); // 输出：10 20 30
// 头插法插入节点
insertHead(&head, 5);
printf("头插法插入后：");
traverseLinkList(head); // 输出：5 10 20 30
// 指定位置插入
insertPos(&head, 3, 15);
printf("位置 3 插入 15 后：");
traverseLinkList(head); // 输出：5 10 15 20 30
// 查找节点
int pos = findByValue(head, 20);
if(pos != 0) {
printf("值为 20 的节点位置：%d\n", pos); // 输出：4
} else {
printf("未找到值为 20 的节点\n");
}
ListNode *pNode = findByPos(head, 4);
if(pNode != NULL) {
printf("位置 4 的节点数据：%d\n", pNode->data); // 输出：20
}
// 删除节点
deleteByValue(&head, 15);
printf("删除值为 15 的节点后：");
traverseLinkList(head); // 输出：5 10 20 30
deleteByPos(&head, 2);
printf("删除位置 2 的节点后：");
traverseLinkList(head); // 输出：5 20 30
// 链表长度
printf("链表当前长度：%d\n", getLinkListLength(head)); // 输出：3
// 销毁链表
destroyLinkList(&head);
traverseLinkList(head); // 输出：链表为空
return 0;
}
运行结果：
尾插法插入后：链表元素：10 20 30
头插法插入后：链表元素：5 10 20 30
位置 3 插入 15 后：链表元素：5 10 15 20 30
值为 20 的节点位置：4
位置 4 的节点数据：20
删除值为 15 的节点后：链表元素：5 10 20 30
删除位置 2 的节点后：链表元素：5 20 30
链表当前长度：3
[成功] 链表销毁成功！
[注意] 链表为空！
[提示] 技巧：单链表操作的核心是'找到目标节点的前驱节点'——插入时需让前驱节点指向新节点，新节点指向原后继；删除时需让前驱节点指向目标节点的后继，再释放目标节点内存。
链表反转是面试高频题，核心思路是'遍历链表，逐个改变节点的 next 指针方向'，需要三个指针（prev、curr、next）记录前驱、当前、后继节点。
示例 4：单链表反转实现
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int data;
struct ListNode* next;
} ListNode, *LinkList;
// 辅助函数：尾插法创建链表
void createLinkList(LinkList *head, int arr[], int len) {
*head = NULL;
for(int i = 0; i < len; i++) {
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
newNode->data = arr[i];
newNode->next = NULL;
if(*head == NULL) {
*head = newNode;
} else {
ListNode *p = *head;
while(p->next != NULL) p = p->next;
p->next = newNode;
}
}
}
// 辅助函数：遍历链表
void traverse(LinkList head) {
ListNode *p = head;
while(p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 单链表反转函数（迭代法）
LinkList reverseLinkList(LinkList head) {
if(head == NULL || head->next == NULL) {
return head; // 空链表或只有一个节点，无需反转
}
ListNode *prev = NULL; // 前驱节点
ListNode *curr = head; // 当前节点
ListNode *next = NULL; // 后继节点（临时保存）
while(curr != NULL) {
next = curr->next; // 保存当前节点的后继
curr->next = prev; // 当前节点的 next 指向前驱
prev = curr; // 前驱节点后移
curr = next; // 当前节点后移
}
return prev; // 反转后，prev 成为新的头节点
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int len = sizeof(arr)/sizeof(arr[0]);
LinkList head = NULL;
createLinkList(&head, arr, len);
printf("反转前链表：");
traverse(head); // 输出：1 2 3 4 5
LinkList reversedHead = reverseLinkList(head);
printf("反转后链表：");
traverse(reversedHead); // 输出：5 4 3 2 1
// 销毁链表（略，参考示例 3）
return 0;
}
运行结果：
反转前链表：1 2 3 4 5
反转后链表：5 4 3 2 1
链表环是指链表的尾节点 next 指针不指向 NULL，而是指向链表中的某个节点，导致遍历无法结束。检测链表环的经典算法是'快慢指针法'（Floyd 算法）：
示例 5：单链表环检测实现
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int data;
struct ListNode* next;
} ListNode, *LinkList;
// 创建带环链表（尾节点指向第 pos 个节点，pos 从 1 开始）
void createCycleLinkList(LinkList *head, int arr[], int len, int pos) {
*head = NULL;
ListNode *cycleNode = NULL; // 存储环的入口节点
ListNode *tail = NULL; // 存储尾节点
for(int i = 0; i < len; i++) {
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
newNode->data = arr[i];
newNode->next = NULL;
if(*head == NULL) {
*head = newNode;
} else {
tail->next = newNode;
}
tail = newNode; // 更新尾节点
// 记录第 pos 个节点（环的入口）
if(i + 1 == pos) {
cycleNode = newNode;
}
}
// 尾节点指向环的入口，创建环
if(cycleNode != NULL) {
tail->next = cycleNode;
}
}
// 环检测：快慢指针法
int hasCycle(LinkList head) {
if(head == NULL || head->next == NULL) {
return 0; // 无环
}
ListNode *slow = head; // 慢指针：每次走 1 步
ListNode *fast = head->next;// 快指针：每次走 2 步
while(slow != fast) {
// 快指针到达 NULL，无环
if(fast == NULL || fast->next == NULL) {
return 0;
}
slow = slow->next; // 慢指针走 1 步
fast = fast->next->next;// 快指针走 2 步
}
return 1; // 快慢指针相遇，有环
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int len = sizeof(arr)/sizeof(arr[0]);
LinkList head1 = NULL, head2 = NULL;
// 创建无环链表（pos=0 表示无环）
createCycleLinkList(&head1, arr, len, 0);
printf("链表 1 是否有环：%s\n", hasCycle(head1) ? "是" : "否"); // 输出：否
// 创建有环链表（尾节点指向第 2 个节点）
createCycleLinkList(&head2, arr, len, 2);
printf("链表 2 是否有环：%s\n", hasCycle(head2) ? "是" : "否"); // 输出：是
// 注意：带环链表无法通过常规遍历销毁，需单独处理（略）
return 0;
}
运行结果：
链表 1 是否有环：否
链表 2 是否有环：是
[成功] 结论：快慢指针法是链表环检测的最优解，时间复杂度 O(n)，空间复杂度 O(1)，无需额外存储节点信息。
单链表的节点只有一个 next 指针，只能从前往后遍历；双向链表的每个节点增加了一个 prev 指针（指向前一个节点），支持双向遍历，插入、删除操作更灵活（无需遍历查找前驱节点）。
#include <stdio.h>
#include <stdlib.h>
// 定义双向链表节点结构体
typedef struct DListNode {
int data;
struct DListNode* prev; // 指向前一个节点
struct DListNode* next; // 指向后一个节点
} DListNode, *DLinkList;
// 1. 双向链表初始化（带头节点，简化操作）
DLinkList initDLinkList() {
// 创建头节点（不存储数据）
DListNode *head = (DListNode *)malloc(sizeof(DListNode));
if(head == NULL) {
printf("[注意] 头节点内存分配失败！\n");
return NULL;
}
head->prev = NULL;
head->next = NULL;
return head;
}
// 2. 尾插法插入节点
int insertTail(DLinkList head, int data) {
if(head == NULL) {
printf("[注意] 链表未初始化！\n");
return -1;
}
// 创建新节点
DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));
if(newNode == NULL) {
printf("[注意] 节点内存分配失败！\n");
return -1;
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
// 遍历到尾节点（head->next 为 NULL 时，head 是尾节点）
DListNode *p = head;
while(p->next != NULL) {
p = p->next;
}
// 插入新节点
p->next = newNode;
newNode->prev = p;
return 0;
}
// 3. 头插法插入节点（在头节点之后插入）
int insertHead(DLinkList head, int data) {
if(head == NULL) {
printf("[注意] 链表未初始化！\n");
return -1;
}
// 创建新节点
DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));
if(newNode == NULL) {
printf("[注意] 节点内存分配失败！\n");
return -1;
}
newNode->data = data;
// 插入逻辑：新节点在头节点和原第一个节点之间
newNode->next = head->next;
newNode->prev = head;
if(head->next != NULL) {
// 若原链表非空，更新原第一个节点的 prev
head->next->prev = newNode;
}
head->next = newNode;
return 0;
}
// 4. 双向遍历：正向遍历（头->尾）
void traverseForward(DLinkList head) {
if(head == NULL || head->next == NULL) {
printf("[注意] 链表为空！\n");
return;
}
DListNode *p = head->next;
printf("正向遍历：");
while(p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 5. 双向遍历：反向遍历（尾->头）
void traverseBackward(DLinkList head) {
if(head == NULL || head->next == NULL) {
printf("[注意] 链表为空！\n");
return;
}
// 遍历到尾节点
DListNode *p = head;
while(p->next != NULL) {
p = p->next;
}
printf("反向遍历：");
while(p != head) {
printf("%d ", p->data);
p = p->prev;
}
printf("\n");
}
// 6. 节点删除：按值删除（删除第一个匹配节点）
int deleteByValue(DLinkList head, int data) {
if(head == NULL || head->next == NULL) {
printf("[注意] 链表为空，无法删除！\n");
return -1;
}
DListNode *p = head->next;
while(p != NULL) {
if(p->data == data) {
// 前驱节点的 next 指向当前节点的后继
p->prev->next = p->next;
// 后继节点的 prev 指向当前节点的前驱（若后继存在）
if(p->next != NULL) {
p->next->prev = p->prev;
}
free(p);
p = NULL;
return 0;
}
p = p->next;
}
printf("[注意] 未找到值为%d的节点！\n", data);
return -1;
}
// 7. 双向链表销毁
void destroyDLinkList(DLinkList *head) {
if(*head == NULL) {
return;
}
DListNode *p = *head;
while(p != NULL) {
DListNode *temp = p;
p = p->next;
free(temp);
temp = NULL;
}
*head = NULL;
printf("[成功] 双向链表销毁成功！\n");
}
// 主函数测试
int main() {
DLinkList head = initDLinkList();
// 尾插法插入节点
insertTail(head, 10);
insertTail(head, 20);
insertTail(head, 30);
traverseForward(head); // 输出：10 20 30
traverseBackward(head); // 输出：30 20 10
// 头插法插入节点
insertHead(head, 5);
traverseForward(head); // 输出：5 10 20 30
traverseBackward(head); // 输出：30 20 10 5
// 删除节点
deleteByValue(head, 20);
traverseForward(head); // 输出：5 10 30
traverseBackward(head); // 输出：30 10 5
// 销毁链表
destroyDLinkList(&head);
traverseForward(head); // 输出：链表为空
return 0;
}
运行结果：
正向遍历：10 20 30
反向遍历：30 20 10
正向遍历：5 10 20 30
反向遍历：30 20 10 5
正向遍历：5 10 30
反向遍历：30 10 5
[成功] 双向链表销毁成功！
[注意] 链表为空！
[提示] 技巧：双向链表通常设计带头节点（不存储数据），可避免处理头节点为空的特殊情况，简化插入、删除逻辑；prev 指针使反向遍历和节点删除更高效（无需查找前驱节点）。
栈是一种遵循'先进后出'（Last In First Out）规则的线性数据结构，仅允许在一端（栈顶）进行插入（入栈）和删除（出栈）操作。栈的实现有两种方式：数组栈（基于数组）和链式栈（基于链表）。
数组栈基于固定大小的数组实现，优点是实现简单、访问速度快；缺点是容量固定，扩容不便。核心操作包括：初始化、入栈、出栈、取栈顶元素、判空、判满。
示例 6：数组栈的完整实现
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100 // 栈的最大容量
// 定义数组栈结构体
typedef struct {
int data[MAX_SIZE]; // 存储栈元素的数组
int top; // 栈顶指针（-1 表示栈空，top == MAX_SIZE-1 表示栈满）
} ArrayStack;
// 1. 栈初始化
void initArrayStack(ArrayStack *stack) {
stack->top = -1; // 栈空状态
}
// 2. 判空：栈为空返回 1，否则返回 0
int isEmpty(ArrayStack *stack) {
return stack->top == -1 ? 1 : 0;
}
// 3. 判满：栈为满返回 1，否则返回 0
int isFull(ArrayStack *stack) {
return stack->top == MAX_SIZE - 1 ? 1 : 0;
}
// 4. 入栈：将元素压入栈顶
int push(ArrayStack *stack, int data) {
if(isFull(stack)) {
printf("[注意] 栈满，无法入栈！\n");
return -1;
}
stack->top++; // 栈顶指针上移
stack->data[stack->top] = data; // 存入数据
return 0;
}
// 5. 出栈：弹出栈顶元素，返回元素值（栈空返回 -1）
int pop(ArrayStack *stack) {
if(isEmpty(stack)) {
printf("[注意] 栈空，无法出栈！\n");
return -1;
}
int data = stack->data[stack->top]; // 取出栈顶元素
stack->top--; // 栈顶指针下移
return data;
}
// 6. 取栈顶元素：返回栈顶元素值（不弹出，栈空返回 -1）
int getTop(ArrayStack *stack) {
if(isEmpty(stack)) {
printf("[注意] 栈空，无栈顶元素！\n");
return -1;
}
return stack->data[stack->top];
}
// 7. 栈遍历：从栈顶到栈底打印元素
void traverseArrayStack(ArrayStack *stack) {
if(isEmpty(stack)) {
printf("[注意] 栈空！\n");
return;
}
printf("栈元素（栈顶->栈底）：");
for(int i = stack->top; i >= 0; i--) {
printf("%d ", stack->data[i]);
}
printf("\n");
}
// 8. 栈大小：返回栈中元素个数
int getStackSize(ArrayStack *stack) {
return stack->top + 1;
}
// 主函数测试
int main() {
ArrayStack stack;
initArrayStack(&stack);
// 入栈
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);
printf("入栈 4 个元素后：");
traverseArrayStack(&stack); // 输出：40 30 20 10
printf("栈当前大小：%d\n", getStackSize(&stack)); // 输出：4
// 取栈顶元素
int topVal = getTop(&stack);
if(topVal != -1) {
printf("当前栈顶元素：%d\n", topVal); // 输出：40
}
// 出栈
int popVal = pop(&stack);
if(popVal != -1) {
printf("弹出的栈顶元素：%d\n", popVal); // 输出：40
}
printf("出栈 1 个元素后：");
traverseArrayStack(&stack); // 输出：30 20 10
printf("栈当前大小：%d\n", getStackSize(&stack)); // 输出：3
// 继续入栈到满
for(int i = 50; i <= 100; i += 10) {
push(&stack, i);
}
printf("多次入栈后：");
traverseArrayStack(&stack); // 输出：100 90 80 70 60 50 30 20 10
printf("栈当前大小：%d\n", getStackSize(&stack)); // 输出：9
// 测试栈满入栈
push(&stack, 110); // 输出：栈满，无法入栈！
return 0;
}
运行结果：
入栈 4 个元素后：栈元素（栈顶->栈底）：40 30 20 10
栈当前大小：4
当前栈顶元素：40
弹出的栈顶元素：40
出栈 1 个元素后：栈元素（栈顶->栈底）：30 20 10
栈当前大小：3
多次入栈后：栈元素（栈顶->栈底）：100 90 80 70 60 50 30 20 10
栈当前大小：9
[注意] 栈满，无法入栈！
[注意] 数组栈的容量由 MAX_SIZE 固定，若实际需求超过容量，需手动修改 MAX_SIZE 或实现动态扩容（通过 realloc 重新分配数组内存）。
链式栈基于单链表实现，优点是容量动态扩展（无需预先指定大小），缺点是插入、删除操作需额外的指针操作。链式栈通常将链表头部作为栈顶（入栈、出栈操作更高效）。
示例 7：链式栈的完整实现
#include <stdio.h>
#include <stdlib.h>
// 定义链式栈节点结构体
typedef struct StackNode {
int data;
struct StackNode* next;
} StackNode, *LinkStack;
// 1. 栈初始化：空栈的栈顶指针为 NULL
void initLinkStack(LinkStack *top) {
*top = NULL;
}
// 2. 判空：栈为空返回 1，否则返回 0
int isLinkStackEmpty(LinkStack top) {
return top == NULL ? 1 : 0;
}
// 3. 入栈：在栈顶（链表头部）插入节点
int linkStackPush(LinkStack *top, int data) {
// 创建新节点
StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
if(newNode == NULL) {
printf("[注意] 节点内存分配失败！\n");
return -1;
}
newNode->data = data;
newNode->next = *top; // 新节点的 next 指向原栈顶
*top = newNode; // 栈顶指针指向新节点
return 0;
}
// 4. 出栈：弹出栈顶节点，返回元素值（栈空返回 -1）
int linkStackPop(LinkStack *top) {
if(isLinkStackEmpty(*top)) {
printf("[注意] 栈空，无法出栈！\n");
return -1;
}
StackNode *temp = *top; // 保存栈顶节点
int data = temp->data; // 取出栈顶元素
*top = temp->next; // 栈顶指针下移
free(temp); // 释放原栈顶节点内存
temp = NULL;
return data;
}
// 5. 取栈顶元素：返回栈顶元素值（不弹出，栈空返回 -1）
int linkStackGetTop(LinkStack top) {
if(isLinkStackEmpty(top)) {
printf("[注意] 栈空，无栈顶元素！\n");
return -1;
}
return top->data;
}
// 6. 栈遍历：从栈顶到栈底打印元素
void traverseLinkStack(LinkStack top) {
if(isLinkStackEmpty(top)) {
printf("[注意] 栈空！\n");
return;
}
StackNode *p = top;
printf("栈元素（栈顶->栈底）：");
while(p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 7. 栈大小：返回栈中元素个数
int getLinkStackSize(LinkStack top) {
int size = 0;
StackNode *p = top;
while(p != NULL) {
size++;
p = p->next;
}
return size;
}
// 8. 链式栈销毁
void destroyLinkStack(LinkStack *top) {
StackNode *p = *top;
while(p != NULL) {
StackNode *temp = p;
p = p->next;
free(temp);
temp = NULL;
}
*top = NULL;
printf("[成功] 链式栈销毁成功！\n");
}
// 主函数测试
int main() {
LinkStack top;
initLinkStack(&top);
// 入栈
linkStackPush(&top, 10);
linkStackPush(&top, 20);
linkStackPush(&top, 30);
printf("入栈 3 个元素后：");
traverseLinkStack(top); // 输出：30 20 10
printf("栈当前大小：%d\n", getLinkStackSize(top)); // 输出：3
// 取栈顶元素
int topVal = linkStackGetTop(top);
if(topVal != -1) {
printf("当前栈顶元素：%d\n", topVal); // 输出：30
}
// 出栈
int popVal = linkStackPop(&top);
if(popVal != -1) {
printf("弹出的栈顶元素：%d\n", popVal); // 输出：30
}
printf("出栈 1 个元素后：");
traverseLinkStack(top); // 输出：20 10
printf("栈当前大小：%d\n", getLinkStackSize(top)); // 输出：2
// 继续入栈多个元素
linkStackPush(&top, 40);
linkStackPush(&top, 50);
linkStackPush(&top, 60);
printf("继续入栈 3 个元素后：");
traverseLinkStack(top); // 输出：60 50 40 20 10
printf("栈当前大小：%d\n", getLinkStackSize(top)); // 输出：5
// 销毁栈
destroyLinkStack(&top);
traverseLinkStack(top); // 输出：栈空
return 0;
}
运行结果：
入栈 3 个元素后：栈元素（栈顶->栈底）：30 20 10
栈当前大小：3
当前栈顶元素：30
弹出的栈顶元素：30
出栈 1 个元素后：栈元素（栈顶->栈底）：20 10
栈当前大小：2
继续入栈 3 个元素后：栈元素（栈顶->栈底）：60 50 40 20 10
栈当前大小：5
[成功] 链式栈销毁成功！
[注意] 栈空！
[成功] 结论：数组栈和链式栈各有优劣——数组栈适合元素数量固定、追求高效访问的场景；链式栈适合元素数量不确定、需要动态扩容的场景。
栈的'先进后出'特性使其非常适合解决括号匹配问题：
(、{、[）则入栈；)、}、]），弹出栈顶元素，判断是否为对应的左括号；示例 8：栈实现括号匹配
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100 // 数组栈实现（简化版）
typedef struct {
char data[MAX_STACK_SIZE];
int top;
} Stack;
void initStack(Stack *stack) {
stack->top = -1;
}
int push(Stack *stack, char c) {
if(stack->top == MAX_STACK_SIZE - 1) {
return -1;
}
stack->data[++stack->top] = c;
return 0;
}
char pop(Stack *stack) {
if(stack->top == -1) {
return '\0'; // 栈空标识
}
return stack->data[stack->top--];
}
int isEmpty(Stack *stack) {
return stack->top == -1 ? 1 : 0;
}
// 判断左右括号是否匹配
int isMatch(char left, char right) {
return (left == '(' && right == ')') ||
(left == '{' && right == '}') ||
(left == '[' && right == ']');
}
// 括号匹配函数：匹配成功返回 1，失败返回 0
int bracketMatch(const char* str) {
Stack stack;
initStack(&stack);
int len = strlen(str);
for(int i = 0; i < len; i++) {
char c = str[i];
// 遇到左括号，入栈
if(c == '(' || c == '{' || c == '[') {
push(&stack, c);
}
// 遇到右括号，判断匹配
else if(c == ')' || c == '}' || c == ']') {
char left = pop(&stack);
if(left == '\0' || !isMatch(left, c)) {
return 0; // 栈空（右括号多）或不匹配
}
}
// 忽略其他字符
else {
continue;
}
}
// 遍历结束后，栈为空则所有左括号都匹配
return isEmpty(&stack) ? 1 : 0;
}
int main() {
const char* str1 = "({[]})";
const char* str2 = "({[)]}";
const char* str3 = "((()))";
const char* str4 = "(()";
printf("字符串\"%s\"括号匹配：%s\n", str1, bracketMatch(str1) ? "成功" : "失败"); // 成功
printf("字符串\"%s\"括号匹配：%s\n", str2, bracketMatch(str2) ? "成功" : "失败"); // 失败
printf("字符串\"%s\"括号匹配：%s\n", str3, bracketMatch(str3) ? "成功" : "失败"); // 成功
printf("字符串\"%s\"括号匹配：%s\n", str4, bracketMatch(str4) ? "成功" : "失败"); // 失败
return 0;
}
运行结果：
字符串"({[]})"括号匹配：成功
字符串"({[)]}"括号匹配：失败
字符串"((()))"括号匹配：成功
字符串"(()"括号匹配：失败
[提示] 技巧：括号匹配是栈的经典应用，类似场景还包括表达式求值（前缀、中缀、后缀表达式转换）、函数调用栈等。
队列是一种遵循'先进先出'（First In First Out）规则的线性数据结构，允许在一端（队尾）插入元素（入队），在另一端（队头）删除元素（出队）。队列的实现有两种方式：循环队列（基于数组）和链式队列（基于链表）。
普通数组队列存在'假溢出'问题（队尾到达数组末尾，但队头前仍有空闲空间），循环队列通过'取模运算'将数组首尾相连，解决假溢出问题，提高内存利用率。
循环队列的核心设计：
front（指向队头元素）和队尾指针 rear（指向队尾元素的下一个位置）；front == rear；(rear + 1) % MAX_SIZE == front（预留一个空闲位置区分队空和队满）；(rear - front + MAX_SIZE) % MAX_SIZE。示例 9：循环队列的完整实现
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5 // 队列最大容量（实际可存储 4 个元素，预留 1 个区分队满）
// 定义循环队列结构体
typedef struct {
int data[MAX_QUEUE_SIZE];
int front; // 队头指针
int rear; // 队尾指针
} CircularQueue;
// 1. 队列初始化
void initCircularQueue(CircularQueue *queue) {
queue->front = 0;
queue->rear = 0;
}
// 2. 判空：队列空返回 1，否则返回 0
int isQueueEmpty(CircularQueue *queue) {
return queue->front == queue->rear ? 1 : 0;
}
// 3. 判满：队列满返回 1，否则返回 0
int isQueueFull(CircularQueue *queue) {
return (queue->rear + 1) % MAX_QUEUE_SIZE == queue->front ? 1 : 0;
}
// 4. 入队：将元素插入队尾
int enQueue(CircularQueue *queue, int data) {
if(isQueueFull(queue)) {
printf("[注意] 队列满，无法入队！\n");
return -1;
}
queue->data[queue->rear] = data; // 存入数据
queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE; // 队尾指针后移（循环）
return 0;
}
// 5. 出队：删除队头元素，返回元素值（队空返回 -1）
int deQueue(CircularQueue *queue) {
if(isQueueEmpty(queue)) {
printf("[注意] 队列为空，无法出队！\n");
return -1;
}
int data = queue->data[queue->front]; // 取出队头元素
queue->front = (queue->front + 1) % MAX_QUEUE_SIZE; // 队头指针后移（循环）
return data;
}
// 6. 取队头元素：返回队头元素值（不删除，队空返回 -1）
int getQueueFront(CircularQueue *queue) {
if(isQueueEmpty(queue)) {
printf("[注意] 队列为空，无队头元素！\n");
return -1;
}
return queue->data[queue->front];
}
// 7. 队列遍历：从队头到队尾打印元素
void traverseCircularQueue(CircularQueue *queue) {
if(isQueueEmpty(queue)) {
printf("[注意] 队列为空！\n");
return;
}
int i = queue->front;
printf("队列元素（队头->队尾）：");
while(i != queue->rear) {
printf("%d ", queue->data[i]);
i = (i + 1) % MAX_QUEUE_SIZE; // 循环遍历
}
printf("\n");
}
// 8. 队列大小：返回队列中元素个数
int getQueueSize(CircularQueue *queue) {
return (queue->rear - queue->front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
// 主函数测试
int main() {
CircularQueue queue;
initCircularQueue(&queue);
// 入队
enQueue(&queue, 10);
enQueue(&queue, 20);
enQueue(&queue, 30);
enQueue(&queue, 40);
printf("入队 4 个元素后：");
traverseCircularQueue(&queue); // 输出：10 20 30 40
printf("队列当前大小：%d\n", getQueueSize(&queue)); // 输出：4
// 测试队满入队
enQueue(&queue, 50); // 输出：队列满，无法入队！
// 取队头元素
int frontVal = getQueueFront(&queue);
if(frontVal != -1) {
printf("当前队头元素：%d\n", frontVal); // 输出：10
}
// 出队
int deVal = deQueue(&queue);
if(deVal != -1) {
printf("出队的元素：%d\n", deVal); // 输出：10
}
printf("出队 1 个元素后：");
traverseCircularQueue(&queue); // 输出：20 30 40
printf("队列当前大小：%d\n", getQueueSize(&queue)); // 输出：3
// 再次入队
enQueue(&queue, 50);
printf("入队元素 50 后：");
traverseCircularQueue(&queue); // 输出：20 30 40 50
printf("队列当前大小：%d\n", getQueueSize(&queue)); // 输出：4
// 继续出队
deQueue(&queue);
deQueue(&queue);
printf("连续出队 2 个元素后：");
traverseCircularQueue(&queue); // 输出：40 50
printf("队列当前大小：%d\n", getQueueSize(&queue)); // 输出：2
return 0;
}
运行结果：
入队 4 个元素后：队列元素（队头->队尾）：10 20 30 40
队列当前大小：4
[注意] 队列满，无法入队！
当前队头元素：10
出队的元素：10
出队 1 个元素后：队列元素（队头->队尾）：20 30 40
队列当前大小：3
入队元素 50 后：队列元素（队头->队尾）：20 30 40 50
队列当前大小：4
连续出队 2 个元素后：队列元素（队头->队尾）：40 50
队列当前大小：2
[提示] 技巧：循环队列的核心是'取模运算'，通过 (index + 1) % MAX_SIZE 实现指针的循环移动，解决普通数组队列的假溢出问题。
链式队列基于单链表实现，队头指向链表的头节点，队尾指向链表的尾节点，入队操作在队尾添加节点，出队操作删除队头节点。链式队列无容量限制，适合元素数量不确定的场景。
示例 10：链式队列的完整实现
#include <stdio.h>
#include <stdlib.h>
// 定义链式队列节点结构体
typedef struct QueueNode {
int data;
struct QueueNode* next;
} QueueNode;
// 定义链式队列结构体（包含队头和队尾指针）
typedef struct {
QueueNode *front; // 队头指针（指向头节点）
QueueNode *rear; // 队尾指针（指向尾节点）
} LinkQueue;
// 1. 队列初始化：创建头节点，队头和队尾都指向头节点
void initLinkQueue(LinkQueue *queue) {
// 创建头节点（不存储数据）
queue->front = (QueueNode *)malloc(sizeof(QueueNode));
if(queue->front == NULL) {
printf("[注意] 头节点内存分配失败！\n");
return;
}
queue->front->next = NULL;
queue->rear = queue->front; // 队尾初始指向头节点
}
// 2. 判空：队头和队尾指向同一节点（头节点），则队空
int isLinkQueueEmpty(LinkQueue *queue) {
return queue->front == queue->rear ? 1 : 0;
}
// 3. 入队：在队尾添加节点
int linkQueueEnQueue(LinkQueue *queue, int data) {
// 创建新节点
QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
if(newNode == NULL) {
printf("[注意] 节点内存分配失败！\n");
return -1;
}
newNode->data = data;
newNode->next = NULL;
// 新节点插入队尾
queue->rear->next = newNode;
queue->rear = newNode; // 队尾指针指向新节点
return 0;
}
// 4. 出队：删除队头节点（头节点的下一个节点）
int linkQueueDeQueue(LinkQueue *queue) {
if(isLinkQueueEmpty(queue)) {
printf("[注意] 队列为空，无法出队！\n");
return -1;
}
QueueNode *temp = queue->front->next; // 保存队头元素节点
int data = temp->data; // 取出队头元素
queue->front->next = temp->next; // 头节点指向队头元素的下一个节点
// 若队尾就是要删除的节点（队列只有一个元素），队尾指向头节点
if(queue->rear == temp) {
queue->rear = queue->front;
}
free(temp);
temp = NULL;
return data;
}
// 5. 取队头元素：返回队头元素值（不删除，队空返回 -1）
int linkQueueGetFront(LinkQueue *queue) {
if(isLinkQueueEmpty(queue)) {
printf("[注意] 队列为空，无队头元素！\n");
return -1;
}
return queue->front->next->data;
}
// 6. 队列遍历：从队头到队尾打印元素
void traverseLinkQueue(LinkQueue *queue) {
if(isLinkQueueEmpty(queue)) {
printf("[注意] 队列为空！\n");
return;
}
QueueNode *p = queue->front->next;
printf("队列元素（队头->队尾）：");
while(p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 7. 队列大小：返回队列中元素个数
int getLinkQueueSize(LinkQueue *queue) {
int size = 0;
QueueNode *p = queue->front->next;
while(p != NULL) {
size++;
p = p->next;
}
return size;
}
// 8. 链式队列销毁
void destroyLinkQueue(LinkQueue *queue) {
// 销毁所有元素节点
QueueNode *p = queue->front->next;
while(p != NULL) {
QueueNode *temp = p;
p = p->next;
free(temp);
temp = NULL;
}
// 销毁头节点
free(queue->front);
queue->front = NULL;
queue->rear = NULL;
printf("[成功] 链式队列销毁成功！\n");
}
// 主函数测试
int main() {
LinkQueue queue;
initLinkQueue(&queue);
// 入队
linkQueueEnQueue(&queue, 10);
linkQueueEnQueue(&queue, 20);
linkQueueEnQueue(&queue, 30);
printf("入队 3 个元素后：");
traverseLinkQueue(&queue); // 输出：10 20 30
printf("队列当前大小：%d\n", getLinkQueueSize(&queue)); // 输出：3
// 取队头元素
int frontVal = linkQueueGetFront(&queue);
if(frontVal != -1) {
printf("当前队头元素：%d\n", frontVal); // 输出：10
}
// 出队
int deVal = linkQueueDeQueue(&queue);
if(deVal != -1) {
printf("出队的元素：%d\n", deVal); // 输出：10
}
printf("出队 1 个元素后：");
traverseLinkQueue(&queue); // 输出：20 30
printf("队列当前大小：%d\n", getLinkQueueSize(&queue)); // 输出：2
// 继续入队多个元素
linkQueueEnQueue(&queue, 40);
linkQueueEnQueue(&queue, 50);
printf("继续入队 2 个元素后：");
traverseLinkQueue(&queue); // 输出：20 30 40 50
printf("队列当前大小：%d\n", getLinkQueueSize(&queue)); // 输出：4
// 连续出队
linkQueueDeQueue(&queue);
linkQueueDeQueue(&queue);
printf("连续出队 2 个元素后：");
traverseLinkQueue(&queue); // 输出：40 50
printf("队列当前大小：%d\n", getLinkQueueSize(&queue)); // 输出：2
// 销毁队列
destroyLinkQueue(&queue);
traverseLinkQueue(&queue); // 输出：队列为空
return 0;
}
运行结果：
入队 3 个元素后：队列元素（队头->队尾）：10 20 30
队列当前大小：3
当前队头元素：10
出队的元素：10
出队 1 个元素后：队列元素（队头->队尾）：20 30
队列当前大小：2
继续入队 2 个元素后：队列元素（队头->队尾）：20 30 40 50
队列当前大小：4
连续出队 2 个元素后：队列元素（队头->队尾）：40 50
队列当前大小：2
[成功] 链式队列销毁成功！
[注意] 队列为空！
[成功] 结论：循环队列适合元素数量固定、追求内存高效利用的场景；链式队列适合元素数量不确定、需要动态扩容的场景，且无需处理循环指针，实现更直观。
队列是'生产者 - 消费者模型'的核心数据结构——生产者线程向队列中添加数据（入队），消费者线程从队列中获取数据（出队），队列起到缓冲和同步的作用，解耦生产者和消费者。
示例 11：模拟生产者 - 消费者模型（单线程简化版）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h> // 包含 sleep 函数（Linux 系统）
#define MAX_QUEUE_SIZE 5 // 队列最大容量
// 循环队列实现（存储字符串数据）
typedef struct {
char data[MAX_QUEUE_SIZE][20]; // 存储字符串
int front;
int rear;
} MsgQueue;
// 队列初始化
void initMsgQueue(MsgQueue *queue) {
queue->front = 0;
queue->rear = 0;
}
// 判空
int isMsgQueueEmpty(MsgQueue *queue) {
return queue->front == queue->rear ? 1 : 0;
}
// 判满
int isMsgQueueFull(MsgQueue *queue) {
return (queue->rear + 1) % MAX_QUEUE_SIZE == queue->front ? 1 : 0;
}
// 入队（生产者生产数据）
int produce(MsgQueue *queue, const char* msg) {
if(isMsgQueueFull(queue)) {
printf("[注意] 队列满，生产者等待...\n");
return -1;
}
strcpy(queue->data[queue->rear], msg);
queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
printf("[入队] 生产者生产：%s\n", msg);
return 0;
}
// 出队（消费者消费数据）
int consume(MsgQueue *queue, char* msg) {
if(isMsgQueueEmpty(queue)) {
printf("[注意] 队列空，消费者等待...\n");
return -1;
}
strcpy(msg, queue->data[queue->front]);
queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
printf("[出队] 消费者消费：%s\n", msg);
return 0;
}
int main() {
MsgQueue queue;
initMsgQueue(&queue);
char msg[20];
// 模拟生产者生产数据
produce(&queue, "任务 1");
produce(&queue, "任务 2");
produce(&queue, "任务 3");
produce(&queue, "任务 4");
sleep(1); // 生产者暂停 1 秒
// 模拟消费者消费数据
consume(&queue, msg);
consume(&queue, msg);
sleep(1); // 消费者暂停 1 秒
// 生产者继续生产
produce(&queue, "任务 5");
produce(&queue, "任务 6");
// 队列满，生产者等待
sleep(1);
// 消费者继续消费
consume(&queue, msg);
consume(&queue, msg);
consume(&queue, msg);
sleep(1);
// 消费者尝试消费空队列
consume(&queue, msg);
return 0;
}
运行结果：
[入队] 生产者生产：任务 1
[入队] 生产者生产：任务 2
[入队] 生产者生产：任务 3
[入队] 生产者生产：任务 4
[出队] 消费者消费：任务 1
[出队] 消费者消费：任务 2
[入队] 生产者生产：任务 5
[注意] 队列满，生产者等待...
[出队] 消费者消费：任务 3
[出队] 消费者消费：任务 4
[出队] 消费者消费：任务 5
[注意] 队列空，消费者等待...
[提示] 技巧：在多线程环境中，生产者 - 消费者模型需要添加互斥锁（如 pthread_mutex_t）和条件变量（如 pthread_cond_t）保证线程安全，避免并发读写冲突。队列的缓冲特性使生产者和消费者可以异步工作，无需等待对方立即响应，提升系统吞吐量。
实现一个学生成绩管理系统，支持以下功能：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// 定义学生结构体
typedef struct Student {
char id[20]; // 学号（唯一标识）
char name[20]; // 姓名
float scores[3]; // 三门课程成绩：语文、数学、英语
float avgScore; // 平均分
struct Student* next; // 指向后一个学生的指针（链表节点）
} Student, *StudentList;
// ==================== 工具函数 ====================
// 计算平均分
float calculateAvg(float scores[]) {
return (scores[0] + scores[1] + scores[2]) / 3.0f;
}
// 验证成绩合法性（0-100 分）
bool isValidScore(float score) {
return score >= 0.0f && score <= 100.0f;
}
// ==================== 链表核心操作 ====================
// 1. 初始化学生链表（带头节点）
StudentList initStudentList() {
Student *head = (Student *)malloc(sizeof(Student));
if(head == NULL) {
printf("[注意] 链表初始化失败！\n");
exit(-1);
}
head->next = NULL;
return head;
}
// 2. 新增学生信息（尾插法）
int addStudent(StudentList head, const char* id, const char* name, float scores[]) {
// 检查学号是否已存在
Student *p = head->next;
while(p != NULL) {
if(strcmp(p->id, id) == 0) {
printf("[注意] 学号%s已存在，新增失败！\n", id);
return -1;
}
p = p->next;
}
// 检查成绩合法性
for(int i = 0; i < 3; i++) {
if(!isValidScore(scores[i])) {
printf("[注意] 成绩%.1f 非法（需在 0-100 之间），新增失败！\n", scores[i]);
return -1;
}
}
// 创建新学生节点
Student *newStudent = (Student *)malloc(sizeof(Student));
if(newStudent == NULL) {
printf("[注意] 节点内存分配失败！\n");
return -1;
}
strcpy(newStudent->id, id);
strcpy(newStudent->name, name);
memcpy(newStudent->scores, scores, sizeof(scores));
newStudent->avgScore = calculateAvg(scores);
newStudent->next = NULL;
// 插入链表尾部
p = head;
while(p->next != NULL) {
p = p->next;
}
p->next = newStudent;
printf("[成功] 学号%s学生信息新增成功！\n", id);
return 0;
}
// 3. 按学号查找学生（返回学生节点指针，未找到返回 NULL）
Student *findStudentByID(StudentList head, const char* id) {
Student *p = head->next;
while(p != NULL) {
if(strcmp(p->id, id) == 0) {
return p; // 找到，返回节点指针
}
p = p->next;
}
printf("[注意] 未找到学号%s的学生！\n", id);
return NULL;
}
// 4. 按学号修改学生成绩
int modifyStudentScore(StudentList head, const char* id, int courseIdx, float newScore) {
// 检查课程索引合法性（0-语文，1-数学，2-英语）
if(courseIdx < 0 || courseIdx > 2) {
printf("[注意] 课程索引非法（0=语文，1=数学，2=英语）！\n");
return -1;
}
// 检查成绩合法性
if(!isValidScore(newScore)) {
printf("[注意] 成绩%.1f 非法（需在 0-100 之间）！\n", newScore);
return -1;
}
// 查找学生
Student *student = findStudentByID(head, id);
if(student == NULL) {
return -1;
}
// 修改成绩并更新平均分
float oldScore = student->scores[courseIdx];
student->scores[courseIdx] = newScore;
student->avgScore = calculateAvg(student->scores);
const char* courseNames[] = {"语文", "数学", "英语"};
printf("[成功] 学号%s学生的%s成绩修改成功：%.1f → %.1f，新平均分为%.1f\n", id, courseNames[courseIdx], oldScore, newScore, student->avgScore);
return 0;
}
// 5. 按学号删除学生信息
int deleteStudentByID(StudentList head, const char* id) {
Student *prev = head; // 前驱节点
Student *curr = head->next; // 当前节点
while(curr != NULL) {
if(strcmp(curr->id, id) == 0) {
// 前驱节点指向当前节点的后继
prev->next = curr->next;
// 释放当前节点内存
free(curr);
curr = NULL;
printf("[成功] 学号%s学生信息删除成功！\n", id);
return 0;
}
prev = curr;
curr = curr->next;
}
printf("[注意] 未找到学号%s的学生，删除失败！\n", id);
return -1;
}
// 6. 遍历输出所有学生信息
void traverseStudentList(StudentList head) {
Student *p = head->next;
if(p == NULL) {
printf("[注意] 系统中暂无学生信息！\n");
return;
}
printf("\n==================== 学生成绩列表 ====================\n");
printf("%-10s %-10s %-8s %-8s %-8s %-8s\n", "学号", "姓名", "语文", "数学", "英语", "平均分");
printf("------------------------------------------------------\n");
while(p != NULL) {
printf("%-10s %-10s %-8.1f %-8.1f %-8.1f %-8.1f\n", p->id, p->name, p->scores[0], p->scores[1], p->scores[2], p->avgScore);
p = p->next;
}
printf("======================================================\n\n");
}
// 7. 统计功能：按平均分降序排序
void sortStudentsByAvg(StudentList head) {
Student *p = head->next;
if(p == NULL || p->next == NULL) {
printf("[注意] 学生数量不足 2 人，无需排序！\n");
return;
}
// 冒泡排序（修改节点指针，而非数据）
bool swapped;
Student *ptr1;
Student *lptr = NULL; // 标记已排序部分的尾部
do {
swapped = false;
ptr1 = head->next;
while(ptr1->next != lptr) {
if(ptr1->avgScore < ptr1->next->avgScore) {
// 交换两个节点的数据（简化实现，也可交换指针）
Student temp = *ptr1;
*ptr1 = *(ptr1->next);
*(ptr1->next) = temp;
// 修复交换后的指针指向（关键！）
Student *tempNext = ptr1->next;
ptr1->next = tempNext->next;
tempNext->next = ptr1;
swapped = true;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
} while(swapped);
printf("[成功] 学生按平均分降序排序完成！\n");
traverseStudentList(head);
}
// 8. 统计功能：统计各课程及格人数（≥60 分）
void countPassedStudents(StudentList head) {
Student *p = head->next;
if(p == NULL) {
printf("[注意] 系统中暂无学生信息，无法统计！\n");
return;
}
int passCount[3] = {0}; // 语文、数学、英语及格人数
int totalCount = 0; // 总学生数
while(p != NULL) {
totalCount++;
for(int i = 0; i < 3; i++) {
if(p->scores[i] >= 60.0f) {
passCount[i]++;
}
}
p = p->next;
}
const char* courseNames[] = {"语文", "数学", "英语"};
printf("\n==================== 及格人数统计 ====================\n");
for(int i = 0; i < 3; i++) {
float passRate = (float)passCount[i] / totalCount * 100;
printf("%s：及格人数%d/%d，及格率%.1f%%\n", courseNames[i], passCount[i], totalCount, passRate);
}
printf("======================================================\n\n");
}
// 9. 销毁学生链表（释放所有内存）
void destroyStudentList(StudentList *head) {
Student *p = *head;
while(p != NULL) {
Student *temp = p;
p = p->next;
free(temp);
temp = NULL;
}
*head = NULL;
printf("[成功] 学生成绩管理系统销毁成功，所有内存已释放！\n");
}
// ==================== 主菜单与测试 ====================
void printMenu() {
printf("\n===== 学生成绩管理系统 =====\n");
printf("1. 新增学生信息\n");
printf("2. 查找学生信息\n");
printf("3. 修改学生成绩\n");
printf("4. 删除学生信息\n");
printf("5. 遍历所有学生\n");
printf("6. 按平均分排序\n");
printf("7. 统计及格人数\n");
printf("0. 退出系统\n");
printf("===========================\n");
printf("请选择功能（0-7）：");
}
int main() {
StudentList head = initStudentList();
int choice;
char id[20], name[20];
float scores[3], newScore;
int courseIdx;
Student *student;
while(1) {
printMenu();
scanf("%d", &choice);
getchar(); // 吸收换行符
switch(choice) {
case 1: // 新增学生
printf("请输入学号：");
scanf("%s", id);
printf("请输入姓名：");
scanf("%s", name);
printf("请输入语文、数学、英语成绩（用空格分隔）：");
scanf("%f %f %f", &scores[0], &scores[1], &scores[2]);
addStudent(head, id, name, scores);
break;
case 2: // 查找学生
printf("请输入要查找的学号：");
scanf("%s", id);
student = findStudentByID(head, id);
if(student != NULL) {
printf("\n找到学生信息：\n");
printf("学号：%s，姓名：%s\n", student->id, student->name);
printf("语文：%.1f，数学：%.1f，英语：%.1f，平均分：%.1f\n", student->scores[0], student->scores[1], student->scores[2], student->avgScore);
}
break;
case 3: // 修改成绩
printf("请输入要修改的学生学号：");
scanf("%s", id);
printf("请选择要修改的课程（0=语文，1=数学，2=英语）：");
scanf("%d", &courseIdx);
printf("请输入新成绩（0-100）：");
scanf("%f", &newScore);
modifyStudentScore(head, id, courseIdx, newScore);
break;
case 4: // 删除学生
printf("请输入要删除的学生学号：");
scanf("%s", id);
deleteStudentByID(head, id);
break;
case 5: // 遍历所有学生
traverseStudentList(head);
break;
case 6: // 按平均分排序
sortStudentsByAvg(head);
break;
case 7: // 统计及格人数
countPassedStudents(head);
break;
case 0: // 退出系统
destroyStudentList(&head);
printf("[再见] 感谢使用学生成绩管理系统，再见！\n");
return 0;
default:
printf("[注意] 无效的功能选择，请重新输入！\n");
break;
}
}
}
===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：1
请输入学号：2024001
请输入姓名：张三
请输入语文、数学、英语成绩（用空格分隔）：85 92 78
[成功] 学号 2024001 学生信息新增成功！
===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：1
请输入学号：2024002
请输入姓名：李四
请输入语文、数学、英语成绩（用空格分隔）：72 68 95
[成功] 学号 2024002 学生信息新增成功！
===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：5
==================== 学生成绩列表 ====================
学号 姓名 语文 数学 英语 平均分
------------------------------------------------------
2024001 张三 85.0 92.0 78.0 85.0
2024002 李四 72.0 68.0 95.0 78.3
======================================================
===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：3
请输入要修改的学生学号：2024002
请选择要修改的课程（0=语文，1=数学，2=英语）：1
请输入新成绩（0-100）：75
[成功] 学号 2024002 学生的数学成绩修改成功：68.0 → 75.0，新平均分为 80.7
===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：6
[成功] 学生按平均分降序排序完成！
==================== 学生成绩列表 ====================
学号 姓名 语文 数学 英语 平均分
------------------------------------------------------
2024001 张三 85.0 92.0 78.0 85.0
2024002 李四 72.0 75.0 95.0 80.7
======================================================
===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：7
==================== 及格人数统计 ====================
语文：及格人数 2/2，及格率 100.0%
数学：及格人数 2/2，及格率 100.0%
英语：及格人数 2/2，及格率 100.0%
======================================================
===== 学生成绩管理系统 =====
1. 新增学生信息
2. 查找学生信息
3. 修改学生成绩
4. 删除学生信息
5. 遍历所有学生
6. 按平均分排序
7. 统计及格人数
0. 退出系统
===========================
请选择功能（0-7）：0
[成功] 学生成绩管理系统销毁成功，所有内存已释放！
[再见] 感谢使用学生成绩管理系统，再见！
[成功] 案例总结：该系统基于单链表实现，充分利用了链表'动态扩容、插入删除高效'的特性，支持学生信息的全生命周期管理。核心亮点包括：
next 指针未初始化，指向随机地址；✅ 避坑方案：
next 指针立即初始化为 NULL；curr、temp）置空；NULL 后再访问成员。free 释放内存。✅ 避坑方案：
malloc 分配的节点，在删除时必须调用 free；✅ 避坑方案：
realloc 实现动态扩容，避免固定容量限制；malloc 节点是否成功。✅ 避坑方案：
front==rear，队满 (rear+1)%MAX_SIZE==front'；rear 指针重置为头节点；| 场景需求 | 推荐数据结构 | 不推荐数据结构 | 原因分析 |
|---|---|---|---|
| 频繁插入/删除，元素数量不固定 | 链表、链式栈/队列 | 数组、数组栈/队列 | 链表插入删除无需移动元素，动态扩容更灵活 |
| 频繁访问元素，追求高效查询 | 数组、数组栈/队列 | 链表、链式栈/队列 | 数组支持随机访问（O(1)），链表需遍历（O(n)） |
| 元素需先进先出 | 队列 | 栈 | 队列天然支持 FIFO，栈为 LIFO，逻辑不符 |
| 元素需先进后出 | 栈 | 队列 | 栈天然支持 LIFO，队列为 FIFO，逻辑不符 |
| 需双向遍历或快速查找前驱节点 | 双向链表 | 单链表 | 双向链表 prev 指针直接获取前驱，单链表需遍历 |
[提示] 技巧：数据结构的选择需结合'操作频率'和'数据特性'——高频插入删除选链表，高频访问选数组；按顺序存取选栈/队列，按逻辑选对应结构。
✅ 避坑方案：
next 指针临时保存当前节点的后继；✅ 避坑方案：
(index + 1) % MAX_SIZE；(rear - front + MAX_SIZE) % MAX_SIZE，避免负数。本章围绕'指针 + 结构体'核心，深入讲解了 C 语言中三大基础复杂数据结构——链表、栈、队列，核心要点如下：
typedef 可简化结构体指针声明，提升代码可读性；[提示] 学习建议：复杂数据结构的核心是'指针操作'和'逻辑建模'——建议先手动模拟链表反转、栈入栈出栈、队列入队出队等操作的内存变化过程，再通过大量案例练习巩固。后续学习中，可基于本章知识扩展到更复杂的数据结构（如二叉树、哈希表），为 C 语言进阶开发（如嵌入式编程、内核开发）打下坚实基础。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online