C语言指针与复杂数据结构：链表、栈与队列实战

一、指针与复杂数据结构：链表、栈与队列实战

1.1 学习目标与重点

💡 掌握指针结合结构体实现线性数据结构的核心原理，理解链表、栈、队列的存储特性与访问规则；
💡 精通单链表、双向链表的创建、插入、删除、查找等基础操作，能够解决链表环检测、反转等进阶问题；
💡 熟练使用数组栈、链式栈及循环队列、链式队列的实现逻辑，明确不同结构的适用场景；
💡 结合实际项目案例，体会指针在复杂数据结构中的内存管理技巧，提升代码的模块化与高效性。

1.2 指针与结构体：复杂数据结构的基础

在C语言中，结构体用于封装多个不同类型的数据，而指针则负责连接这些数据单元，形成灵活的复杂数据结构。指针与结构体的结合，是实现链表、栈、队列等动态数据结构的核心基础——通过结构体存储数据，指针指向结构体实例，实现数据单元的链式关联。

1.2.1 结构体与指针的基本操作

结构体指针的声明与使用是基础，其核心语法为：

// 结构体定义struct 结构体名 { 成员类型 成员名;// ... 其他成员};// 结构体指针声明struct 结构体名 *指针变量名;

💡 技巧：通过 -> 运算符访问结构体指针的成员（等价于 (*指针变量名).成员名），是后续复杂数据结构操作的常用语法。

示例1：结构体指针的基本使用

#include<stdio.h>#include<stdlib.h>// 包含malloc函数// 定义学生结构体structStudent{int id;// 学号char name[20];// 姓名float score;// 成绩structStudent*next;// 指向另一个Student的指针（为链表做铺垫）};intmain(){// 方式1：栈上创建结构体，指针指向该结构体structStudent stu1 ={101,"张三",92.5,NULL};structStudent*pStu1 =&stu1;// 访问结构体成员（两种等价方式）printf("学号：%d，姓名：%s，成绩：%.1f\n", pStu1->id,(*pStu1).name, pStu1->score);// 方式2：堆上创建结构体（动态内存分配），指针指向堆内存structStudent*pStu2 =(structStudent*)malloc(sizeof(structStudent));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;// 置空指针，避免野指针return0;}

运行结果：

学号：101，姓名：张三，成绩：92.5 学号：102，姓名：李四，成绩：88.0 

⚠️ 注意：堆上的结构体必须通过 malloc 分配内存，且使用后需通过 free 释放，否则会导致内存泄漏；释放后需将指针置空，避免野指针访问。

1.2.2 typedef简化结构体指针声明

频繁使用 struct 结构体名 * 声明指针会显得繁琐，通过 typedef 为结构体类型起别名，可极大简化代码：

// 方式1：先定义结构体，再typedefstructStudent{int id;char name[20];};typedefstructStudent Student;// 别名Student，后续可直接用Student代替struct Student// 方式2：定义结构体时直接typedef（推荐）typedefstructStudent{int id;char name[20];structStudent*next;} Student,*PStudent;// Student是结构体类型别名，PStudent是结构体指针类型别名

示例2：typedef简化结构体指针使用

#include<stdio.h>#include<stdlib.h>#include<string.h>// 定义结构体并起别名typedefstructStudent{int id;char name[20];float score;structStudent*next;} Student,*PStudent;// PStudent = struct Student*// 函数：创建学生节点（返回结构体指针） PStudent createStudent(int id,constchar*name,float score){ PStudent pStu =(PStudent)malloc(sizeof(Student));if(pStu ==NULL){printf("⚠️ 节点创建失败！\n");returnNULL;} pStu->id = id;strcpy(pStu->name, name); pStu->score = score; pStu->next =NULL;// 初始化next指针为NULL，避免野指针return pStu;}// 函数：打印学生信息voidprintStudent(PStudent pStu){if(pStu !=NULL){printf("学号：%d，姓名：%s，成绩：%.1f\n", pStu->id, pStu->name, pStu->score);}}intmain(){ PStudent pStu1 =createStudent(101,"王五",95.0); PStudent pStu2 =createStudent(102,"赵六",89.5);printStudent(pStu1);printStudent(pStu2);// 释放内存free(pStu1);free(pStu2); pStu1 =NULL; pStu2 =NULL;return0;}

运行结果：

学号：101，姓名：王五，成绩：95.0 学号：102，姓名：赵六，成绩：89.5 

✅ 结论：typedef 不仅简化了结构体指针的声明，还提升了代码的可读性和可维护性，是复杂数据结构开发中的必备技巧。

1.3 链表：动态数据结构的核心

链表是一种线性数据结构，其数据单元（节点）通过指针串联，节点在内存中无需连续存储——这种特性使其支持动态扩容（无需预先指定大小），插入、删除操作效率高（无需移动大量元素）。链表主要分为单链表、双向链表、循环链表，本节重点讲解最常用的单链表和双向链表。

1.3.1 单链表的实现与基础操作

单链表的每个节点包含“数据域”和“指针域”：数据域存储数据，指针域（next）指向后一个节点，最后一个节点的 next 指针为 NULL（表示链表结尾）。

单链表的核心操作

1. 链表初始化：创建头节点（或空链表）；
2. 节点插入：头插法、尾插法、指定位置插入；
3. 节点删除：按位置删除、按值删除；
4. 链表遍历：遍历所有节点并访问数据；
5. 链表查找：按值查找、按位置查找；
6. 链表销毁：释放所有节点的内存。

示例3：单链表的完整实现

#include<stdio.h>#include<stdlib.h>#include<string.h>// 定义单链表节点结构体typedefstructListNode{int data;// 数据域structListNode*next;// 指针域：指向后一个节点} ListNode,*LinkList;// 1. 链表初始化：创建空链表（头节点为NULL） LinkList initLinkList(){returnNULL;// 空链表的头指针为NULL}// 2. 节点插入：尾插法（在链表末尾添加节点）intinsertTail(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;return0;}// 情况2：链表非空，遍历到末尾节点 ListNode *p =*head;while(p->next !=NULL){ p = p->next;// 移动到下一个节点} p->next = newNode;// 末尾节点的next指向新节点return0;}// 3. 节点插入：头插法（在链表头部添加节点）intinsertHead(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;return0;}// 4. 节点插入：指定位置插入（位置从1开始）intinsertPos(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){returninsertHead(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指向新节点return0;}// 5. 链表遍历：打印所有节点数据voidtraverseLinkList(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）intfindByValue(LinkList head,int data){if(head ==NULL){printf("⚠️ 链表为空！\n");return0;} ListNode *p = head;int pos =1;while(p !=NULL){if(p->data == data){return pos;// 找到，返回位置} p = p->next; pos++;}return0;// 未找到}// 7. 链表查找：按位置查找（返回该位置的节点指针；位置非法返回NULL） ListNode *findByPos(LinkList head,int pos){if(head ==NULL|| pos <1){printf("⚠️ 链表为空或位置非法！\n");returnNULL;} ListNode *p = head;int count =1;while(p !=NULL&& count < pos){ p = p->next; count++;}return p;// 若pos超出长度，返回NULL}// 8. 节点删除：按值删除（删除第一个匹配的节点）intdeleteByValue(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;return0;}// 情况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;return0;}// 9. 节点删除：按位置删除（位置从1开始）intdeleteByPos(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;return0;}// 情况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;return0;}// 10. 链表销毁：释放所有节点内存voiddestroyLinkList(LinkList *head){ ListNode *p =*head;while(p !=NULL){ ListNode *temp = p;// 保存当前节点 p = p->next;// 移动到下一个节点free(temp);// 释放当前节点 temp =NULL;}*head =NULL;// 头指针置空，避免野指针printf("✅ 链表销毁成功！\n");}// 11. 链表长度：返回节点个数intgetLinkListLength(LinkList head){int len =0; ListNode *p = head;while(p !=NULL){ len++; p = p->next;}return len;}// 主函数测试intmain(){ 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 30deleteByPos(&head,2);printf("删除位置2的节点后：");traverseLinkList(head);// 输出：5 20 30// 链表长度printf("链表当前长度：%d\n",getLinkListLength(head));// 输出：3// 销毁链表destroyLinkList(&head);traverseLinkList(head);// 输出：链表为空return0;}

运行结果：

尾插法插入后：链表元素：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 ✅ 链表销毁成功！ ⚠️ 链表为空！ 

💡 技巧：单链表操作的核心是“找到目标节点的前驱节点”——插入时需让前驱节点指向新节点，新节点指向原后继；删除时需让前驱节点指向目标节点的后继，再释放目标节点内存。

1.3.2 单链表进阶问题：反转与环检测

问题1：单链表反转

链表反转是面试高频题，核心思路是“遍历链表，逐个改变节点的next指针方向”，需要三个指针（prev、curr、next）记录前驱、当前、后继节点。

示例4：单链表反转实现

#include<stdio.h>#include<stdlib.h>typedefstructListNode{int data;structListNode*next;} ListNode,*LinkList;// 辅助函数：尾插法创建链表voidcreateLinkList(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;}}}// 辅助函数：遍历链表voidtraverse(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成为新的头节点}intmain(){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）return0;}

运行结果：

反转前链表：1 2 3 4 5 反转后链表：5 4 3 2 1 

问题2：单链表环检测

链表环是指链表的尾节点next指针不指向NULL，而是指向链表中的某个节点，导致遍历无法结束。检测链表环的经典算法是“快慢指针法”（ Floyd 算法）：

• 定义两个指针：快指针（fast）每次走2步，慢指针（slow）每次走1步；
• 若链表无环，快指针会先到达NULL；
• 若链表有环，快指针会追上慢指针（两者指向同一节点）。

示例5：单链表环检测实现

#include<stdio.h>#include<stdlib.h>typedefstructListNode{int data;structListNode*next;} ListNode,*LinkList;// 创建带环链表（尾节点指向第pos个节点，pos从1开始）voidcreateCycleLinkList(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;}}// 环检测：快慢指针法inthasCycle(LinkList head){if(head ==NULL|| head->next ==NULL){return0;// 无环} ListNode *slow = head;// 慢指针：每次走1步 ListNode *fast = head->next;// 快指针：每次走2步while(slow != fast){// 快指针到达NULL，无环if(fast ==NULL|| fast->next ==NULL){return0;} slow = slow->next;// 慢指针走1步 fast = fast->next->next;// 快指针走2步}return1;// 快慢指针相遇，有环}intmain(){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)?"是":"否");// 输出：是// 注意：带环链表无法通过常规遍历销毁，需单独处理（略）return0;}

运行结果：

链表1是否有环：否 链表2是否有环：是 

✅ 结论：快慢指针法是链表环检测的最优解，时间复杂度O(n)，空间复杂度O(1)，无需额外存储节点信息。

1.3.3 双向链表的实现与优势

单链表的节点只有一个next指针，只能从前往后遍历；双向链表的每个节点增加了一个prev指针（指向前一个节点），支持双向遍历，插入、删除操作更灵活（无需遍历查找前驱节点）。

双向链表的核心操作

#include<stdio.h>#include<stdlib.h>// 定义双向链表节点结构体typedefstructDListNode{int data;structDListNode*prev;// 指向前一个节点structDListNode*next;// 指向后一个节点} DListNode,*DLinkList;// 1. 双向链表初始化（带头节点，简化操作） DLinkList initDLinkList(){// 创建头节点（不存储数据） DListNode *head =(DListNode *)malloc(sizeof(DListNode));if(head ==NULL){printf("⚠️ 头节点内存分配失败！\n");returnNULL;} head->prev =NULL; head->next =NULL;return head;}// 2. 尾插法插入节点intinsertTail(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;return0;}// 3. 头插法插入节点（在头节点之后插入）intinsertHead(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;return0;}// 4. 双向遍历：正向遍历（头->尾）voidtraverseForward(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. 双向遍历：反向遍历（尾->头）voidtraverseBackward(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. 节点删除：按值删除（删除第一个匹配节点）intdeleteByValue(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;return0;} p = p->next;}printf("⚠️ 未找到值为%d的节点！\n", data);return-1;}// 7. 双向链表销毁voiddestroyDLinkList(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");}// 主函数测试intmain(){ DLinkList head =initDLinkList();// 尾插法插入节点insertTail(head,10);insertTail(head,20);insertTail(head,30);traverseForward(head);// 输出：10 20 30traverseBackward(head);// 输出：30 20 10// 头插法插入节点insertHead(head,5);traverseForward(head);// 输出：5 10 20 30traverseBackward(head);// 输出：30 20 10 5// 删除节点deleteByValue(head,20);traverseForward(head);// 输出：5 10 30traverseBackward(head);// 输出：30 10 5// 销毁链表destroyDLinkList(&head);traverseForward(head);// 输出：链表为空return0;}

运行结果：

正向遍历：10 20 30 反向遍历：30 20 10 正向遍历：5 10 20 30 反向遍历：30 20 10 5 正向遍历：5 10 30 反向遍历：30 10 5 ✅ 双向链表销毁成功！ ⚠️ 链表为空！ 

💡 技巧：双向链表通常设计带头节点（不存储数据），可避免处理头节点为空的特殊情况，简化插入、删除逻辑；prev指针使反向遍历和节点删除更高效（无需查找前驱节点）。

1.4 栈：先进后出（LIFO）的数据结构

栈是一种遵循“先进后出”（Last In First Out）规则的线性数据结构，仅允许在一端（栈顶）进行插入（入栈）和删除（出栈）操作。栈的实现有两种方式：数组栈（基于数组）和链式栈（基于链表）。

1.4.1 数组栈的实现

数组栈基于固定大小的数组实现，优点是实现简单、访问速度快；缺点是容量固定，扩容不便。核心操作包括：初始化、入栈、出栈、取栈顶元素、判空、判满。

示例6：数组栈的完整实现

#include<stdio.h>#include<stdlib.h>#defineMAX_SIZE100// 栈的最大容量// 定义数组栈结构体typedefstruct{int data[MAX_SIZE];// 存储栈元素的数组int top;// 栈顶指针（-1表示栈空，top == MAX_SIZE-1表示栈满）} ArrayStack;// 1. 栈初始化voidinitArrayStack(ArrayStack *stack){ stack->top =-1;// 栈空状态}// 2. 判空：栈为空返回1，否则返回0intisEmpty(ArrayStack *stack){return stack->top ==-1?1:0;}// 3. 判满：栈为满返回1，否则返回0intisFull(ArrayStack *stack){return stack->top == MAX_SIZE -1?1:0;}// 4. 入栈：将元素压入栈顶intpush(ArrayStack *stack,int data){if(isFull(stack)){printf("⚠️ 栈满，无法入栈！\n");return-1;} stack->top++;// 栈顶指针上移 stack->data[stack->top]= data;// 存入数据return0;}// 5. 出栈：弹出栈顶元素，返回元素值（栈空返回-1）intpop(ArrayStack *stack){if(isEmpty(stack)){printf("⚠️ 栈空，无法出栈！\n");return-1;}int data = stack->data[stack->top];// 取出栈顶元素 stack->top--;// 栈顶指针下移return data;}// 6. 取栈顶元素：返回栈顶元素值（不弹出，栈空返回-1）intgetTop(ArrayStack *stack){if(isEmpty(stack)){printf("⚠️ 栈空，无栈顶元素！\n");return-1;}return stack->data[stack->top];}// 7. 栈遍历：从栈顶到栈底打印元素voidtraverseArrayStack(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. 栈大小：返回栈中元素个数intgetStackSize(ArrayStack *stack){return stack->top +1;}// 主函数测试intmain(){ ArrayStack stack;initArrayStack(&stack);// 入栈push(&stack,10);push(&stack,20);push(&stack,30);push(&stack,40);printf("入栈4个元素后：");traverseArrayStack(&stack);// 输出：40 30 20 10printf("栈当前大小：%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 10printf("栈当前大小：%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 10printf("栈当前大小：%d\n",getStackSize(&stack));// 输出：9// 测试栈满入栈push(&stack,110);// 输出：栈满，无法入栈！return0;}

运行结果：

入栈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 重新分配数组内存）。

1.4.2 链式栈的实现

链式栈基于单链表实现，优点是容量动态扩展（无需预先指定大小），缺点是插入、删除操作需额外的指针操作。链式栈通常将链表头部作为栈顶（入栈、出栈操作更高效）。

示例7：链式栈的完整实现

#include<stdio.h>#include<stdlib.h>// 定义链式栈节点结构体typedefstructStackNode{int data;structStackNode*next;} StackNode,*LinkStack;// 1. 栈初始化：空栈的栈顶指针为NULLvoidinitLinkStack(LinkStack *top){*top =NULL;}// 2. 判空：栈为空返回1，否则返回0intisLinkStackEmpty(LinkStack top){return top ==NULL?1:0;}// 3. 入栈：在栈顶（链表头部）插入节点intlinkStackPush(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;// 栈顶指针指向新节点return0;}// 4. 出栈：弹出栈顶节点，返回元素值（栈空返回-1）intlinkStackPop(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）intlinkStackGetTop(LinkStack top){if(isLinkStackEmpty(top)){printf("⚠️ 栈空，无栈顶元素！\n");return-1;}return top->data;}// 6. 栈遍历：从栈顶到栈底打印元素voidtraverseLinkStack(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. 栈大小：返回栈中元素个数intgetLinkStackSize(LinkStack top){int size =0; StackNode *p = top;while(p !=NULL){ size++; p = p->next;}return size;}// 8. 链式栈销毁voiddestroyLinkStack(LinkStack *top){ StackNode *p =*top;while(p !=NULL){ StackNode *temp = p; p = p->next;free(temp); temp =NULL;}*top =NULL;printf("✅ 链式栈销毁成功！\n");}// 主函数测试intmain(){ LinkStack top;initLinkStack(&top);// 入栈linkStackPush(&top,10);linkStackPush(&top,20);linkStackPush(&top,30);printf("入栈3个元素后：");traverseLinkStack(top);// 输出：30 20 10printf("栈当前大小：%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 10printf("栈当前大小：%d\n",getLinkStackSize(top));// 输出：2// 继续入栈多个元素linkStackPush(&top,40);linkStackPush(&top,50);linkStackPush(&top,60);printf("继续入栈3个元素后：");traverseLinkStack(top);// 输出：60 50 40 20 10printf("栈当前大小：%d\n",getLinkStackSize(top));// 输出：5// 销毁栈destroyLinkStack(&top);traverseLinkStack(top);// 输出：栈空return0;}

运行结果：

入栈3个元素后：栈元素（栈顶->栈底）：30 20 10 栈当前大小：3 当前栈顶元素：30 弹出的栈顶元素：30 出栈1个元素后：栈元素（栈顶->栈底）：20 10 栈当前大小：2 继续入栈3个元素后：栈元素（栈顶->栈底）：60 50 40 20 10 栈当前大小：5 ✅ 链式栈销毁成功！ ⚠️ 栈空！ 

✅ 结论：数组栈和链式栈各有优劣——数组栈适合元素数量固定、追求高效访问的场景；链式栈适合元素数量不确定、需要动态扩容的场景。

1.4.3 栈的应用场景：括号匹配

栈的“先进后出”特性使其非常适合解决括号匹配问题：

• 遍历字符串，遇到左括号（(、{、[）则入栈；
• 遇到右括号（)、}、]），弹出栈顶元素，判断是否为对应的左括号；
• 遍历结束后，若栈为空且所有右括号都找到匹配的左括号，则匹配成功；否则匹配失败。

示例8：栈实现括号匹配

#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX_STACK_SIZE100// 数组栈实现（简化版）typedefstruct{char data[MAX_STACK_SIZE];int top;} Stack;voidinitStack(Stack *stack){ stack->top =-1;}intpush(Stack *stack,char c){if(stack->top == MAX_STACK_SIZE -1){return-1;} stack->data[++stack->top]= c;return0;}charpop(Stack *stack){if(stack->top ==-1){return'\0';// 栈空标识}return stack->data[stack->top--];}intisEmpty(Stack *stack){return stack->top ==-1?1:0;}// 判断左右括号是否匹配intisMatch(char left,char right){return(left =='('&& right ==')')||(left =='{'&& right =='}')||(left =='['&& right ==']');}// 括号匹配函数：匹配成功返回1，失败返回0intbracketMatch(constchar*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);}// 遇到右括号，判断匹配elseif(c ==')'|| c =='}'|| c ==']'){char left =pop(&stack);if(left =='\0'||!isMatch(left, c)){return0;// 栈空（右括号多）或不匹配}}// 忽略其他字符else{continue;}}// 遍历结束后，栈为空则所有左括号都匹配returnisEmpty(&stack)?1:0;}intmain(){constchar*str1 ="({[]})";constchar*str2 ="({[)]}";constchar*str3 ="((()))";constchar*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)?"成功":"失败");// 失败return0;}

运行结果：

字符串"({[]})"括号匹配：成功 字符串"({[)]}"括号匹配：失败 字符串"((()))"括号匹配：成功 字符串"(()"括号匹配：失败 

💡 技巧：括号匹配是栈的经典应用，类似场景还包括表达式求值（前缀、中缀、后缀表达式转换）、函数调用栈等。

1.5 队列：先进先出（FIFO）的数据结构

队列是一种遵循“先进先出”（First In First Out）规则的线性数据结构，允许在一端（队尾）插入元素（入队），在另一端（队头）删除元素（出队）。队列的实现有两种方式：循环队列（基于数组）和链式队列（基于链表）。

1.5.1 循环队列的实现

普通数组队列存在“假溢出”问题（队尾到达数组末尾，但队头前仍有空闲空间），循环队列通过“取模运算”将数组首尾相连，解决假溢出问题，提高内存利用率。

循环队列的核心设计：

• 定义队头指针 front（指向队头元素）和队尾指针 rear（指向队尾元素的下一个位置）；
• 队空条件：front == rear；
• 队满条件：(rear + 1) % MAX_SIZE == front（预留一个空闲位置区分队空和队满）；
• 元素个数：(rear - front + MAX_SIZE) % MAX_SIZE。

示例9：循环队列的完整实现

#include<stdio.h>#include<stdlib.h>#defineMAX_QUEUE_SIZE5// 队列最大容量（实际可存储4个元素，预留1个区分队满）// 定义循环队列结构体typedefstruct{int data[MAX_QUEUE_SIZE];int front;// 队头指针int rear;// 队尾指针} CircularQueue;// 1. 队列初始化voidinitCircularQueue(CircularQueue *queue){ queue->front =0; queue->rear =0;}// 2. 判空：队列空返回1，否则返回0intisQueueEmpty(CircularQueue *queue){return queue->front == queue->rear ?1:0;}// 3. 判满：队列满返回1，否则返回0intisQueueFull(CircularQueue *queue){return(queue->rear +1)% MAX_QUEUE_SIZE == queue->front ?1:0;}// 4. 入队：将元素插入队尾intenQueue(CircularQueue *queue,int data){if(isQueueFull(queue)){printf("⚠️ 队列满，无法入队！\n");return-1;} queue->data[queue->rear]= data;// 存入数据 queue->rear =(queue->rear +1)% MAX_QUEUE_SIZE;// 队尾指针后移（循环）return0;}// 5. 出队：删除队头元素，返回元素值（队空返回-1）intdeQueue(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）intgetQueueFront(CircularQueue *queue){if(isQueueEmpty(queue)){printf("⚠️ 队列为空，无队头元素！\n");return-1;}return queue->data[queue->front];}// 7. 队列遍历：从队头到队尾打印元素voidtraverseCircularQueue(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. 队列大小：返回队列中元素个数intgetQueueSize(CircularQueue *queue){return(queue->rear - queue->front + MAX_QUEUE_SIZE)% MAX_QUEUE_SIZE;}// 主函数测试intmain(){ CircularQueue queue;initCircularQueue(&queue);// 入队enQueue(&queue,10);enQueue(&queue,20);enQueue(&queue,30);enQueue(&queue,40);printf("入队4个元素后：");traverseCircularQueue(&queue);// 输出：10 20 30 40printf("队列当前大小：%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 40printf("队列当前大小：%d\n",getQueueSize(&queue));// 输出：3// 再次入队enQueue(&queue,50);printf("入队元素50后：");traverseCircularQueue(&queue);// 输出：20 30 40 50printf("队列当前大小：%d\n",getQueueSize(&queue));// 输出：4// 继续出队deQueue(&queue);deQueue(&queue);printf("连续出队2个元素后：");traverseCircularQueue(&queue);// 输出：40 50printf("队列当前大小：%d\n",getQueueSize(&queue));// 输出：2return0;}

运行结果：

入队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 实现指针的循环移动，解决普通数组队列的假溢出问题。

1.5.2 链式队列的实现

链式队列基于单链表实现，队头指向链表的头节点，队尾指向链表的尾节点，入队操作在队尾添加节点，出队操作删除队头节点。链式队列无容量限制，适合元素数量不确定的场景。

示例10：链式队列的完整实现

#include<stdio.h>#include<stdlib.h>// 定义链式队列节点结构体typedefstructQueueNode{int data;structQueueNode*next;} QueueNode;// 定义链式队列结构体（包含队头和队尾指针）typedefstruct{ QueueNode *front;// 队头指针（指向头节点） QueueNode *rear;// 队尾指针（指向尾节点）} LinkQueue;// 1. 队列初始化：创建头节点，队头和队尾都指向头节点voidinitLinkQueue(LinkQueue *queue){// 创建头节点（不存储数据） queue->front =(QueueNode *)malloc(sizeof(QueueNode));if(queue->front ==NULL){printf("⚠️ 头节点内存分配失败！\n");return;} queue->front->next =NULL; queue->rear = queue->front;// 队尾初始指向头节点}// 2. 判空：队头和队尾指向同一节点（头节点），则队空intisLinkQueueEmpty(LinkQueue *queue){return queue->front == queue->rear ?1:0;}// 3. 入队：在队尾添加节点intlinkQueueEnQueue(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;// 队尾指针指向新节点return0;}// 4. 出队：删除队头节点（头节点的下一个节点）intlinkQueueDeQueue(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）intlinkQueueGetFront(LinkQueue *queue){if(isLinkQueueEmpty(queue)){printf("⚠️ 队列为空，无队头元素！\n");return-1;}return queue->front->next->data;}// 6. 队列遍历：从队头到队尾打印元素voidtraverseLinkQueue(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. 队列大小：返回队列中元素个数intgetLinkQueueSize(LinkQueue *queue){int size =0; QueueNode *p = queue->front->next;while(p !=NULL){ size++; p = p->next;}return size;}// 8. 链式队列销毁voiddestroyLinkQueue(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");}// 主函数测试intmain(){ LinkQueue queue;initLinkQueue(&queue);// 入队linkQueueEnQueue(&queue,10);linkQueueEnQueue(&queue,20);linkQueueEnQueue(&queue,30);printf("入队3个元素后：");traverseLinkQueue(&queue);// 输出：10 20 30printf("队列当前大小：%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 30printf("队列当前大小：%d\n",getLinkQueueSize(&queue));// 输出：2// 继续入队多个元素linkQueueEnQueue(&queue,40);linkQueueEnQueue(&queue,50);printf("继续入队2个元素后：");traverseLinkQueue(&queue);// 输出：20 30 40 50printf("队列当前大小：%d\n",getLinkQueueSize(&queue));// 输出：4// 连续出队linkQueueDeQueue(&queue);linkQueueDeQueue(&queue);printf("连续出队2个元素后：");traverseLinkQueue(&queue);// 输出：40 50printf("队列当前大小：%d\n",getLinkQueueSize(&queue));// 输出：2// 销毁队列destroyLinkQueue(&queue);traverseLinkQueue(&queue);// 输出：队列为空return0;}

运行结果：

入队3个元素后：队列元素（队头->队尾）：10 20 30 队列当前大小：3 当前队头元素：10 出队的元素：10 出队1个元素后：队列元素（队头->队尾）：20 30 队列当前大小：2 继续入队2个元素后：队列元素（队头->队尾）：20 30 40 50 队列当前大小：4 连续出队2个元素后：队列元素（队头->队尾）：40 50 队列当前大小：2 ✅ 链式队列销毁成功！ ⚠️ 队列为空！ 

✅ 结论：循环队列适合元素数量固定、追求内存高效利用的场景；链式队列适合元素数量不确定、需要动态扩容的场景，且无需处理循环指针，实现更直观。

1.5.3 队列的应用场景：生产者-消费者模型

队列是“生产者-消费者模型”的核心数据结构——生产者线程向队列中添加数据（入队），消费者线程从队列中获取数据（出队），队列起到缓冲和同步的作用，解耦生产者和消费者。

示例11：模拟生产者-消费者模型（单线程简化版）

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<unistd.h>// 包含sleep函数（Linux系统）#defineMAX_QUEUE_SIZE5// 队列最大容量// 循环队列实现（存储字符串数据）typedefstruct{char data[MAX_QUEUE_SIZE][20];// 存储字符串int front;int rear;} MsgQueue;// 队列初始化voidinitMsgQueue(MsgQueue *queue){ queue->front =0; queue->rear =0;}// 判空intisMsgQueueEmpty(MsgQueue *queue){return queue->front == queue->rear ?1:0;}// 判满intisMsgQueueFull(MsgQueue *queue){return(queue->rear +1)% MAX_QUEUE_SIZE == queue->front ?1:0;}// 入队（生产者生产数据）intproduce(MsgQueue *queue,constchar*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);return0;}// 出队（消费者消费数据）intconsume(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);return0;}intmain(){ 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);return0;}

运行结果：

📥 生产者生产：任务1 📥 生产者生产：任务2 📥 生产者生产：任务3 📥 生产者生产：任务4 📤 消费者消费：任务1 📤 消费者消费：任务2 📥 生产者生产：任务5 ⚠️ 队列满，生产者等待... 📤 消费者消费：任务3 📤 消费者消费：任务4 📤 消费者消费：任务5 ⚠️ 队列空，消费者等待... 

💡 技巧：在多线程环境中，生产者-消费者模型需要添加互斥锁（如pthread_mutex_t）和条件变量（如pthread_cond_t）保证线程安全，避免并发读写冲突。队列的缓冲特性使生产者和消费者可以异步工作，无需等待对方立即响应，提升系统吞吐量。

1.6 实际项目案例：基于链表的学生成绩管理系统

1.6.1 案例需求

实现一个学生成绩管理系统，支持以下功能：

1. 新增学生信息（学号、姓名、三门课程成绩）；
2. 查找学生信息（按学号查找）；
3. 修改学生成绩（按学号修改指定课程成绩）；
4. 删除学生信息（按学号删除）；
5. 统计功能（计算平均分、排序输出、统计及格人数）；
6. 遍历输出所有学生信息；
7. 销毁系统（释放所有内存）。

1.6.2 案例实现

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<stdbool.h>// 定义学生结构体typedefstructStudent{char id[20];// 学号（唯一标识）char name[20];// 姓名float scores[3];// 三门课程成绩：语文、数学、英语float avgScore;// 平均分structStudent*next;// 指向后一个学生的指针（链表节点）} Student,*StudentList;// ==================== 工具函数 ====================// 计算平均分floatcalculateAvg(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. 新增学生信息（尾插法）intaddStudent(StudentList head,constchar*id,constchar*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);return0;}// 3. 按学号查找学生（返回学生节点指针，未找到返回NULL） Student *findStudentByID(StudentList head,constchar*id){ Student *p = head->next;while(p !=NULL){if(strcmp(p->id, id)==0){return p;// 找到，返回节点指针} p = p->next;}printf("⚠️ 未找到学号%s的学生！\n", id);returnNULL;}// 4. 按学号修改学生成绩intmodifyStudentScore(StudentList head,constchar*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);constchar*courseNames[]={"语文","数学","英语"};printf("✅ 学号%s学生的%s成绩修改成功：%.1f → %.1f，新平均分为%.1f\n", id, courseNames[courseIdx], oldScore, newScore, student->avgScore);return0;}// 5. 按学号删除学生信息intdeleteStudentByID(StudentList head,constchar*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);return0;} prev = curr; curr = curr->next;}printf("⚠️ 未找到学号%s的学生，删除失败！\n", id);return-1;}// 6. 遍历输出所有学生信息voidtraverseStudentList(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. 统计功能：按平均分降序排序voidsortStudentsByAvg(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分）voidcountPassedStudents(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;}constchar*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. 销毁学生链表（释放所有内存）voiddestroyStudentList(StudentList *head){ Student *p =*head;while(p !=NULL){ Student *temp = p; p = p->next;free(temp); temp =NULL;}*head =NULL;printf("✅ 学生成绩管理系统销毁成功，所有内存已释放！\n");}// ==================== 主菜单与测试 ====================voidprintMenu(){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）：");}intmain(){ 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){case1:// 新增学生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;case2:// 查找学生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;case3:// 修改成绩printf("请输入要修改的学生学号：");scanf("%s", id);printf("请选择要修改的课程（0=语文，1=数学，2=英语）：");scanf("%d",&courseIdx);printf("请输入新成绩（0-100）：");scanf("%f",&newScore);modifyStudentScore(head, id, courseIdx, newScore);break;case4:// 删除学生printf("请输入要删除的学生学号：");scanf("%s", id);deleteStudentByID(head, id);break;case5:// 遍历所有学生traverseStudentList(head);break;case6:// 按平均分排序sortStudentsByAvg(head);break;case7:// 统计及格人数countPassedStudents(head);break;case0:// 退出系统destroyStudentList(&head);printf("👋 感谢使用学生成绩管理系统，再见！\n");return0;default:printf("⚠️ 无效的功能选择，请重新输入！\n");break;}}}

1.6.3 案例测试与运行结果

===== 学生成绩管理系统 ===== 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 ✅ 学生成绩管理系统销毁成功，所有内存已释放！ 👋 感谢使用学生成绩管理系统，再见！ 

✅ 案例总结：该系统基于单链表实现，充分利用了链表“动态扩容、插入删除高效”的特性，支持学生信息的全生命周期管理。核心亮点包括：

1. 数据校验（学号唯一、成绩合法），提升系统稳定性；
2. 模块化设计（新增、查找、修改等功能独立封装），便于维护和扩展；
3. 实用统计功能（排序、及格率统计），贴合实际应用场景；
4. 严格的内存管理（销毁时释放所有节点），避免内存泄漏。

1.7 常见问题与避坑指南

1.7.1 链表操作中的野指针与内存泄漏

野指针问题

• 错误场景1：节点next指针未初始化，指向随机地址；
• 错误场景2：释放节点后未将指针置空，后续误访问。

✅ 避坑方案：

1. 新建节点时，next指针立即初始化为NULL；
2. 释放节点后，将指向该节点的指针（如curr、temp）置空；
3. 遍历链表时，判断指针非NULL后再访问成员。

内存泄漏问题

• 错误场景：只删除链表节点的引用，未调用free释放内存。

✅ 避坑方案：

1. 任何通过malloc分配的节点，在删除时必须调用free；
2. 链表销毁时，需遍历所有节点逐一释放，不可只释放头节点；
3. 复杂操作（如排序、反转）后，确保所有节点都能被正常访问和释放。

1.7.2 栈与队列的边界条件处理

栈的边界问题

• 错误场景1：栈空时执行出栈或取栈顶操作；
• 错误场景2：数组栈满时执行入栈操作。

✅ 避坑方案：

1. 所有栈操作前先判断栈空/栈满状态；
2. 数组栈可通过realloc实现动态扩容，避免固定容量限制；
3. 链式栈无需判满，但需检查malloc节点是否成功。

队列的边界问题

• 错误场景1：循环队列队空/队满判断混淆；
• 错误场景2：链式队列出队时未处理“队列只有一个元素”的情况。

✅ 避坑方案：

1. 循环队列严格遵循“队空front==rear，队满(rear+1)%MAX_SIZE==front”；
2. 链式队列出队时，若删除的是最后一个元素，需将rear指针重置为头节点；
3. 入队/出队操作后，及时更新指针位置，避免指针越界。

1.7.3 数据结构选择误区

💡 技巧：数据结构的选择需结合“操作频率”和“数据特性”——高频插入删除选链表，高频访问选数组；按顺序存取选栈/队列，按逻辑选对应结构。

1.7.4 复杂操作中的逻辑错误

链表反转逻辑错误

• 错误场景：未保存后继节点，导致链表断裂。

✅ 避坑方案：

1. 迭代法反转时，必须用next指针临时保存当前节点的后继；
2. 反转完成后，更新头节点指针，确保链表入口正确。

循环队列指针移动错误

• 错误场景：指针移动时未使用取模运算，导致指针越界。

✅ 避坑方案：

1. 队头/队尾指针移动时，严格使用(index + 1) % MAX_SIZE；
2. 计算元素个数时，使用(rear - front + MAX_SIZE) % MAX_SIZE，避免负数。

1.8 本章总结

本章围绕“指针+结构体”核心，深入讲解了C语言中三大基础复杂数据结构——链表、栈、队列，核心要点如下：

1. 指针与结构体的结合是实现复杂数据结构的基础，typedef可简化结构体指针声明，提升代码可读性；
2. 链表支持动态扩容，插入删除高效，单链表适合单向遍历场景，双向链表支持双向遍历，循环链表适用于环形数据存储；
3. 栈遵循LIFO规则，数组栈实现简单、访问高效，链式栈容量灵活，经典应用包括括号匹配、表达式求值；
4. 队列遵循FIFO规则，循环队列解决数组假溢出问题，链式队列无容量限制，经典应用包括生产者-消费者模型、任务调度；
5. 实际开发中，需根据场景选择合适的数据结构，同时注重内存管理和边界条件处理，避免野指针、内存泄漏等问题。

💡 学习建议：复杂数据结构的核心是“指针操作”和“逻辑建模”——建议先手动模拟链表反转、栈入栈出栈、队列入队出队等操作的内存变化过程，再通过大量案例练习巩固。后续学习中，可基于本章知识扩展到更复杂的数据结构（如二叉树、哈希表），为C语言进阶开发（如嵌入式编程、内核开发）打下坚实基础。

下一章，我们将学习C语言文件操作与数据持久化，掌握文件的读写、定位、权限控制等核心技能，实现数据的长期存储与共享。