一、场景与问题分析川剧 “扯脸” 是极具特色的变脸手法事先将白色、黄色、黑色、红色、青色、金色、银色的脸谱依次贴在脸上表演时在动作掩护下从最后贴的那张开始一张一张扯下。从数据结构视角看“贴脸” 是元素依次入栈“扯脸” 是元素从栈顶依次出栈完全符合栈 “先进后出LIFO” 的核心特性。本文将用 3 种不同的栈实现方式静态顺序栈、动态顺序栈、链式栈一步步拆解并求解 “扯脸序列” 问题代码注释详尽、逻辑层层递进适合初学数据结构的大学生理解。核心需求贴脸顺序白色 → 黄色 → 黑色 → 红色 → 青色 → 金色 → 银色扯脸序列银色 → 金色 → 青色 → 红色 → 黑色 → 黄色 → 白色二、方案一静态顺序栈入门基础版核心特点用静态数组存储栈元素内存由编译器自动分配 / 释放无需手动管理代码最简单适合刚接触栈的初学者理解 “栈顶指针” 核心概念。/* * 文件名: stack_static_complete.c * 功能: 用静态顺序栈实现川剧扯脸序列求解 * 适用人群: 数据结构初学者理解栈的基本概念 * 核心特性: 静态数组存储内存自动管理无需手动malloc/free */ #include stdio.h #include stdlib.h // -------------------------- 全局常量与通用函数 -------------------------- // 颜色编号映射1白色, 2黄色, 3黑色, 4红色, 5青色, 6金色, 7银色 // 功能将整数编号转换为直观的颜色字符串 char* getColorName(int colorCode) { // 静态数组下标与编号一一对应避免冗余switch-case易维护 static const char* colorMap[] {未知颜色, 白色, 黄色, 黑色, 红色, 青色, 金色, 银色}; // 边界安全检查防止非法编号导致数组越界 if (colorCode 1 || colorCode 7) { return (char*)colorMap[0]; } return (char*)colorMap[colorCode]; } // 贴脸谱的原始顺序固定常量 const int faceOrder[] {1, 2, 3, 4, 5, 6, 7}; // 自动计算脸谱数量无需手动修改 const int colorCount sizeof(faceOrder) / sizeof(faceOrder[0]); // -------------------------- 静态顺序栈核心定义 -------------------------- // 元素类型别名后续修改存储类型仅需改此行 typedef int ElemType; // 静态顺序栈结构体定义 typedef struct { ElemType data[100]; // 静态数组容量足够存储7个脸谱预留冗余 int top; // 栈顶指针-1空栈0第一个元素以此类推 } Stack; // -------------------------- 栈操作接口 -------------------------- /** * 函数名: initStack * 功能: 初始化静态顺序栈 * 参数: s - 指向栈结构体的指针传指针才能修改主函数中的栈 * 说明: 空栈的核心标志是top-1 */ void initStack(Stack *s) { s-top -1; // 初始化栈顶指针为-1标记栈为空 } /** * 函数名: isEmpty * 功能: 判断栈是否为空 * 参数: s - 指向栈的指针 * 返回值: 1空栈、0非空栈 */ int isEmpty(Stack *s) { return (s-top -1) ? 1 : 0; } /** * 函数名: push * 功能: 入栈操作对应“贴脸谱” * 参数: * s - 指向栈的指针 * e - 要入栈的元素颜色编号 * 返回值: 1入栈成功、0入栈失败栈满 */ int push(Stack *s, ElemType e) { // 栈满判断数组最大下标为99top99时无法入栈 if (s-top 99) { printf(入栈失败栈已满\n); return 0; } s-top; // 栈顶指针上移一位指向新位置 s-data[s-top] e; // 将颜色编号存入新栈顶位置 return 1; } /** * 函数名: pop * 功能: 出栈操作对应“扯脸谱” * 参数: * s - 指向栈的指针 * e - 指针用于存储出栈的颜色编号传出参数 * 返回值: 1出栈成功、0出栈失败栈空 */ int pop(Stack *s, ElemType *e) { // 栈空判断无元素可出栈 if (isEmpty(s)) { printf(出栈失败栈为空\n); return 0; } *e s-data[s-top]; // 取出栈顶元素颜色编号 s-top--; // 栈顶指针下移逻辑上删除栈顶元素 return 1; } /** * 函数名: printPushOrder * 功能: 打印贴脸顺序栈底→栈顶 * 参数: s - 指向栈的指针 */ void printPushOrder(Stack *s) { if (isEmpty(s)) { printf(栈为空无脸谱可打印\n); return; } printf(贴脸顺序栈底→栈顶); // 遍历数组从下标0第一个贴的到top最后一个贴的 for (int i 0; i s-top; i) { printf(%s , getColorName(s-data[i])); } printf(\n\n); } // -------------------------- 主函数业务逻辑 -------------------------- int main() { printf( 静态顺序栈实现川剧扯脸序列 \n\n); // 1. 定义并初始化静态栈内存分配在栈区编译器自动管理 Stack faceStack; initStack(faceStack); // 2. 执行“贴脸谱”入栈 printf(【贴脸谱过程】\n); for (int i 0; i colorCount; i) { push(faceStack, faceOrder[i]); printf(贴第%d张脸谱%s\n, i1, getColorName(faceOrder[i])); } // 打印贴脸顺序验证入栈结果 printPushOrder(faceStack); // 3. 执行“扯脸谱”出栈输出最终序列 printf(【扯脸谱结果】\n); ElemType popCode; // 存储每次出栈的颜色编号 printf(最终扯脸序列); while (!isEmpty(faceStack)) { pop(faceStack, popCode); printf(%s , getColorName(popCode)); } printf(\n\n\n); return 0; }三、方案二动态顺序栈进阶内存管理版核心特点用malloc动态分配数组内存容量可灵活调整本文仍设 100仅演示逻辑需手动调用free释放内存理解 “堆区内存” 管理避免内存泄漏。/* * 文件名: stack_dynamic_complete.c * 功能: 用动态顺序栈实现川剧扯脸序列求解 * 适用人群: 进阶学习者理解堆区内存管理 * 核心特性: 动态数组存储需手动malloc分配、free释放内存 */ #include stdio.h #include stdlib.h // -------------------------- 全局常量与通用函数 -------------------------- // 颜色编号转字符串1白色, 2黄色, 3黑色, 4红色, 5青色, 6金色, 7银色 char* getColorName(int colorCode) { static const char* colorMap[] {未知颜色, 白色, 黄色, 黑色, 红色, 青色, 金色, 银色}; if (colorCode 1 || colorCode 7) { return (char*)colorMap[0]; } return (char*)colorMap[colorCode]; } // 贴脸谱顺序与数量固定常量 const int faceOrder[] {1, 2, 3, 4, 5, 6, 7}; const int colorCount sizeof(faceOrder) / sizeof(faceOrder[0]); // -------------------------- 动态顺序栈核心定义 -------------------------- typedef int ElemType; // 动态顺序栈结构体数组指针指向堆区内存 typedef struct { ElemType *data; // 动态数组指针需手动分配/释放 int top; // 栈顶指针-1空栈 } Stack; // -------------------------- 栈操作接口 -------------------------- /** * 函数名: initStack * 功能: 初始化动态顺序栈分配堆区内存 * 返回值: 指向栈结构体的指针NULL表示内存分配失败 * 说明: 动态栈需先分配结构体内存再分配数组内存 */ Stack* initStack() { // 1. 为栈结构体分配内存 Stack *s (Stack*)malloc(sizeof(Stack)); if (s NULL) { printf(错误栈结构体内存分配失败\n); return NULL; } // 2. 为存储脸谱的数组分配内存100个元素足够使用 s-data (ElemType*)malloc(sizeof(ElemType) * 100); if (s-data NULL) { printf(错误数组内存分配失败\n); free(s); // 释放已分配的结构体避免内存泄漏 s NULL; return NULL; } s-top -1; // 初始化空栈 return s; } /** * 函数名: isEmpty * 功能: 判断栈是否为空增加指针非空检查更健壮 * 参数: s - 指向栈的指针 * 返回值: 1空栈、0非空栈 */ int isEmpty(Stack *s) { // 先检查指针是否有效再判断栈是否为空 return (s ! NULL s-top -1) ? 1 : 0; } /** * 函数名: push * 功能: 入栈操作贴脸谱 * 参数: s - 栈指针e - 颜色编号 * 返回值: 1成功、0失败 */ int push(Stack *s, ElemType e) { // 健壮性检查指针为空或栈满直接返回失败 if (s NULL || s-top 99) { printf(入栈失败栈指针为空或栈已满\n); return 0; } s-data[s-top] e; // 栈顶指针上移 存入元素简化写法 return 1; } /** * 函数名: pop * 功能: 出栈操作扯脸谱 * 参数: s - 栈指针e - 存储出栈元素的指针 * 返回值: 1成功、0失败 */ int pop(Stack *s, ElemType *e) { if (s NULL || isEmpty(s)) { printf(出栈失败栈指针为空或栈为空\n); return 0; } *e s-data[s-top--]; // 取出元素 栈顶指针下移简化写法 return 1; } /** * 函数名: printPushOrder * 功能: 打印贴脸顺序栈底→栈顶 * 参数: s - 栈指针 */ void printPushOrder(Stack *s) { if (s NULL || isEmpty(s)) { printf(栈为空无脸谱可打印\n); return; } printf(贴脸顺序栈底→栈顶); for (int i 0; i s-top; i) { printf(%s , getColorName(s-data[i])); } printf(\n\n); } /** * 函数名: destroyStack * 功能: 销毁动态栈释放所有堆区内存 * 参数: s - 栈指针的指针需修改原指针避免野指针 * 说明: 动态内存必须手动释放否则造成内存泄漏 */ void destroyStack(Stack **s) { if (s NULL || *s NULL) return; free((*s)-data); // 第一步释放数组内存 free(*s); // 第二步释放结构体内存 *s NULL; // 第三步置空指针避免野指针 } // -------------------------- 主函数业务逻辑 -------------------------- int main() { printf( 动态顺序栈实现川剧扯脸序列 \n\n); // 1. 初始化动态栈内存分配在堆区 Stack *faceStack initStack(); if (faceStack NULL) { // 内存分配失败直接退出程序 return -1; } // 2. 执行贴脸谱入栈 printf(【贴脸谱过程】\n); for (int i 0; i colorCount; i) { push(faceStack, faceOrder[i]); printf(贴第%d张脸谱%s\n, i1, getColorName(faceOrder[i])); } // 打印贴脸顺序验证入栈结果 printPushOrder(faceStack); // 3. 执行扯脸谱出栈 printf(【扯脸谱结果】\n); ElemType popCode; printf(最终扯脸序列); while (!isEmpty(faceStack)) { pop(faceStack, popCode); printf(%s , getColorName(popCode)); } printf(\n); // 4. 销毁栈必做释放堆区内存避免泄漏 destroyStack(faceStack); printf(\n提示动态栈已销毁内存释放完成\n); printf(\n); return 0; }四、方案三链式栈链表实战版核心特点用链表节点存储栈元素无需预先分配固定容量按需创建节点考察指针操作、链表头插法核心逻辑理解 “逻辑上的栈” 与 “物理存储” 的分离。/* * 文件名: stack_linked_complete.c * 功能: 用链式栈实现川剧扯脸序列求解 * 适用人群: 进阶学习者理解链表与指针操作 * 核心特性: 链表节点存储无需固定容量按需分配节点内存 */ #include stdio.h #include stdlib.h // -------------------------- 全局常量与通用函数 -------------------------- // 颜色编号转字符串1白色, 2黄色, 3黑色, 4红色, 5青色, 6金色, 7银色 char* getColorName(int colorCode) { static const char* colorMap[] {未知颜色, 白色, 黄色, 黑色, 红色, 青色, 金色, 银色}; if (colorCode 1 || colorCode 7) { return (char*)colorMap[0]; } return (char*)colorMap[colorCode]; } // 贴脸谱顺序与数量固定常量 const int faceOrder[] {1, 2, 3, 4, 5, 6, 7}; const int colorCount sizeof(faceOrder) / sizeof(faceOrder[0]); // -------------------------- 链式栈核心定义 -------------------------- typedef int ElemType; // 栈节点结构体存储数据指向下一节点的指针 typedef struct StackNode { ElemType data; // 数据域存储颜色编号 struct StackNode *next; // 指针域指向后继节点 } StackNode; // 链式栈管理结构体仅需栈顶指针即可管理整个栈 typedef struct { StackNode *top; // 栈顶指针指向第一个有效节点空栈时为NULL } Stack; // -------------------------- 栈操作接口 -------------------------- /** * 函数名: initStack * 功能: 初始化链式栈创建管理结构体 * 返回值: 指向栈的指针NULL表示分配失败 */ Stack* initStack() { Stack *s (Stack*)malloc(sizeof(Stack)); if (s NULL) { printf(错误栈管理结构体分配失败\n); return NULL; } s-top NULL; // 空栈栈顶指针指向NULL return s; } /** * 函数名: isEmpty * 功能: 判断链式栈是否为空 * 参数: s - 栈指针 * 返回值: 1空栈、0非空栈 */ int isEmpty(Stack *s) { return (s ! NULL s-top NULL) ? 1 : 0; } /** * 函数名: push * 功能: 入栈操作头插法链表头部即为栈顶 * 参数: s - 栈指针e - 颜色编号 * 返回值: 1成功、0失败 * 说明: 链式栈入栈链表头插无需考虑栈满内存足够即可 */ int push(Stack *s, ElemType e) { if (s NULL) { printf(入栈失败栈指针为空\n); return 0; } // 1. 创建新节点并分配内存 StackNode *newNode (StackNode*)malloc(sizeof(StackNode)); if (newNode NULL) { printf(错误新节点内存分配失败\n); return 0; } // 2. 新节点赋值 newNode-data e; // 3. 头插法核心新节点指向原栈顶 newNode-next s-top; // 4. 栈顶指针更新为新节点 s-top newNode; return 1; } /** * 函数名: pop * 功能: 出栈操作删除栈顶节点 * 参数: s - 栈指针e - 存储出栈元素的指针 * 返回值: 1成功、0失败 */ int pop(Stack *s, ElemType *e) { if (s NULL || isEmpty(s)) { printf(出栈失败栈指针为空或栈为空\n); return 0; } // 1. 临时指针指向栈顶节点避免断链 StackNode *temp s-top; // 2. 取出栈顶节点数据 *e temp-data; // 3. 栈顶指针后移指向原第二个节点 s-top temp-next; // 4. 释放原栈顶节点内存避免泄漏 free(temp); return 1; } /** * 函数名: printPushOrder * 功能: 打印贴脸顺序栈顶→栈底链表遍历方向 * 参数: s - 栈指针 */ void printPushOrder(Stack *s) { if (s NULL || isEmpty(s)) { printf(栈为空无脸谱可打印\n); return; } printf(贴脸顺序栈顶→栈底); StackNode *p s-top; while (p ! NULL) { printf(%s , getColorName(p-data)); p p-next; } printf(\n\n); } /** * 函数名: destroyStack * 功能: 销毁链式栈释放所有节点管理结构体 * 参数: s - 栈指针的指针 */ void destroyStack(Stack **s) { if (s NULL || *s NULL) return; // 第一步遍历所有节点并释放 StackNode *p (*s)-top; while (p ! NULL) { StackNode *temp p; p p-next; free(temp); } // 第二步释放管理结构体 free(*s); *s NULL; } // -------------------------- 主函数业务逻辑 -------------------------- int main() { printf( 链式栈实现川剧扯脸序列 \n\n); // 1. 初始化链式栈 Stack *faceStack initStack(); if (faceStack NULL) { return -1; } // 2. 执行贴脸谱入栈链表头插 printf(【贴脸谱过程】\n); for (int i 0; i colorCount; i) { push(faceStack, faceOrder[i]); printf(贴第%d张脸谱%s\n, i1, getColorName(faceOrder[i])); } // 打印贴脸顺序验证入栈结果 printPushOrder(faceStack); // 3. 执行扯脸谱出栈删除链表头节点 printf(【扯脸谱结果】\n); ElemType popCode; printf(最终扯脸序列); while (!isEmpty(faceStack)) { pop(faceStack, popCode); printf(%s , getColorName(popCode)); } printf(\n); // 4. 销毁栈释放所有节点内存 destroyStack(faceStack); printf(\n提示链式栈已销毁内存释放完成\n); printf(\n); return 0; }五、核心总结逻辑统一3 种实现的核心逻辑均围绕 “入栈贴脸→ 出栈扯脸”栈 “先进后出” 的特性是求解问题的关键存储差异静态顺序栈数组固定容量内存自动管理简单但不灵活动态顺序栈数组动态分配需手动释放内存灵活但需注意泄漏链式栈链表节点按需分配无容量限制考察指针与链表操作本文通过川剧 “扯脸” 的趣味场景将抽象的栈结构落地为可运行的 C 语言代码从入门到进阶层层递进希望能帮助大家理解栈的核心特性与实际应用。
【数据结构实战】川剧 “扯脸” 与栈的 LIFO 特性 ：用 C 语言实现 3 种栈结构
一、场景与问题分析川剧 “扯脸” 是极具特色的变脸手法事先将白色、黄色、黑色、红色、青色、金色、银色的脸谱依次贴在脸上表演时在动作掩护下从最后贴的那张开始一张一张扯下。从数据结构视角看“贴脸” 是元素依次入栈“扯脸” 是元素从栈顶依次出栈完全符合栈 “先进后出LIFO” 的核心特性。本文将用 3 种不同的栈实现方式静态顺序栈、动态顺序栈、链式栈一步步拆解并求解 “扯脸序列” 问题代码注释详尽、逻辑层层递进适合初学数据结构的大学生理解。核心需求贴脸顺序白色 → 黄色 → 黑色 → 红色 → 青色 → 金色 → 银色扯脸序列银色 → 金色 → 青色 → 红色 → 黑色 → 黄色 → 白色二、方案一静态顺序栈入门基础版核心特点用静态数组存储栈元素内存由编译器自动分配 / 释放无需手动管理代码最简单适合刚接触栈的初学者理解 “栈顶指针” 核心概念。/* * 文件名: stack_static_complete.c * 功能: 用静态顺序栈实现川剧扯脸序列求解 * 适用人群: 数据结构初学者理解栈的基本概念 * 核心特性: 静态数组存储内存自动管理无需手动malloc/free */ #include stdio.h #include stdlib.h // -------------------------- 全局常量与通用函数 -------------------------- // 颜色编号映射1白色, 2黄色, 3黑色, 4红色, 5青色, 6金色, 7银色 // 功能将整数编号转换为直观的颜色字符串 char* getColorName(int colorCode) { // 静态数组下标与编号一一对应避免冗余switch-case易维护 static const char* colorMap[] {未知颜色, 白色, 黄色, 黑色, 红色, 青色, 金色, 银色}; // 边界安全检查防止非法编号导致数组越界 if (colorCode 1 || colorCode 7) { return (char*)colorMap[0]; } return (char*)colorMap[colorCode]; } // 贴脸谱的原始顺序固定常量 const int faceOrder[] {1, 2, 3, 4, 5, 6, 7}; // 自动计算脸谱数量无需手动修改 const int colorCount sizeof(faceOrder) / sizeof(faceOrder[0]); // -------------------------- 静态顺序栈核心定义 -------------------------- // 元素类型别名后续修改存储类型仅需改此行 typedef int ElemType; // 静态顺序栈结构体定义 typedef struct { ElemType data[100]; // 静态数组容量足够存储7个脸谱预留冗余 int top; // 栈顶指针-1空栈0第一个元素以此类推 } Stack; // -------------------------- 栈操作接口 -------------------------- /** * 函数名: initStack * 功能: 初始化静态顺序栈 * 参数: s - 指向栈结构体的指针传指针才能修改主函数中的栈 * 说明: 空栈的核心标志是top-1 */ void initStack(Stack *s) { s-top -1; // 初始化栈顶指针为-1标记栈为空 } /** * 函数名: isEmpty * 功能: 判断栈是否为空 * 参数: s - 指向栈的指针 * 返回值: 1空栈、0非空栈 */ int isEmpty(Stack *s) { return (s-top -1) ? 1 : 0; } /** * 函数名: push * 功能: 入栈操作对应“贴脸谱” * 参数: * s - 指向栈的指针 * e - 要入栈的元素颜色编号 * 返回值: 1入栈成功、0入栈失败栈满 */ int push(Stack *s, ElemType e) { // 栈满判断数组最大下标为99top99时无法入栈 if (s-top 99) { printf(入栈失败栈已满\n); return 0; } s-top; // 栈顶指针上移一位指向新位置 s-data[s-top] e; // 将颜色编号存入新栈顶位置 return 1; } /** * 函数名: pop * 功能: 出栈操作对应“扯脸谱” * 参数: * s - 指向栈的指针 * e - 指针用于存储出栈的颜色编号传出参数 * 返回值: 1出栈成功、0出栈失败栈空 */ int pop(Stack *s, ElemType *e) { // 栈空判断无元素可出栈 if (isEmpty(s)) { printf(出栈失败栈为空\n); return 0; } *e s-data[s-top]; // 取出栈顶元素颜色编号 s-top--; // 栈顶指针下移逻辑上删除栈顶元素 return 1; } /** * 函数名: printPushOrder * 功能: 打印贴脸顺序栈底→栈顶 * 参数: s - 指向栈的指针 */ void printPushOrder(Stack *s) { if (isEmpty(s)) { printf(栈为空无脸谱可打印\n); return; } printf(贴脸顺序栈底→栈顶); // 遍历数组从下标0第一个贴的到top最后一个贴的 for (int i 0; i s-top; i) { printf(%s , getColorName(s-data[i])); } printf(\n\n); } // -------------------------- 主函数业务逻辑 -------------------------- int main() { printf( 静态顺序栈实现川剧扯脸序列 \n\n); // 1. 定义并初始化静态栈内存分配在栈区编译器自动管理 Stack faceStack; initStack(faceStack); // 2. 执行“贴脸谱”入栈 printf(【贴脸谱过程】\n); for (int i 0; i colorCount; i) { push(faceStack, faceOrder[i]); printf(贴第%d张脸谱%s\n, i1, getColorName(faceOrder[i])); } // 打印贴脸顺序验证入栈结果 printPushOrder(faceStack); // 3. 执行“扯脸谱”出栈输出最终序列 printf(【扯脸谱结果】\n); ElemType popCode; // 存储每次出栈的颜色编号 printf(最终扯脸序列); while (!isEmpty(faceStack)) { pop(faceStack, popCode); printf(%s , getColorName(popCode)); } printf(\n\n\n); return 0; }三、方案二动态顺序栈进阶内存管理版核心特点用malloc动态分配数组内存容量可灵活调整本文仍设 100仅演示逻辑需手动调用free释放内存理解 “堆区内存” 管理避免内存泄漏。/* * 文件名: stack_dynamic_complete.c * 功能: 用动态顺序栈实现川剧扯脸序列求解 * 适用人群: 进阶学习者理解堆区内存管理 * 核心特性: 动态数组存储需手动malloc分配、free释放内存 */ #include stdio.h #include stdlib.h // -------------------------- 全局常量与通用函数 -------------------------- // 颜色编号转字符串1白色, 2黄色, 3黑色, 4红色, 5青色, 6金色, 7银色 char* getColorName(int colorCode) { static const char* colorMap[] {未知颜色, 白色, 黄色, 黑色, 红色, 青色, 金色, 银色}; if (colorCode 1 || colorCode 7) { return (char*)colorMap[0]; } return (char*)colorMap[colorCode]; } // 贴脸谱顺序与数量固定常量 const int faceOrder[] {1, 2, 3, 4, 5, 6, 7}; const int colorCount sizeof(faceOrder) / sizeof(faceOrder[0]); // -------------------------- 动态顺序栈核心定义 -------------------------- typedef int ElemType; // 动态顺序栈结构体数组指针指向堆区内存 typedef struct { ElemType *data; // 动态数组指针需手动分配/释放 int top; // 栈顶指针-1空栈 } Stack; // -------------------------- 栈操作接口 -------------------------- /** * 函数名: initStack * 功能: 初始化动态顺序栈分配堆区内存 * 返回值: 指向栈结构体的指针NULL表示内存分配失败 * 说明: 动态栈需先分配结构体内存再分配数组内存 */ Stack* initStack() { // 1. 为栈结构体分配内存 Stack *s (Stack*)malloc(sizeof(Stack)); if (s NULL) { printf(错误栈结构体内存分配失败\n); return NULL; } // 2. 为存储脸谱的数组分配内存100个元素足够使用 s-data (ElemType*)malloc(sizeof(ElemType) * 100); if (s-data NULL) { printf(错误数组内存分配失败\n); free(s); // 释放已分配的结构体避免内存泄漏 s NULL; return NULL; } s-top -1; // 初始化空栈 return s; } /** * 函数名: isEmpty * 功能: 判断栈是否为空增加指针非空检查更健壮 * 参数: s - 指向栈的指针 * 返回值: 1空栈、0非空栈 */ int isEmpty(Stack *s) { // 先检查指针是否有效再判断栈是否为空 return (s ! NULL s-top -1) ? 1 : 0; } /** * 函数名: push * 功能: 入栈操作贴脸谱 * 参数: s - 栈指针e - 颜色编号 * 返回值: 1成功、0失败 */ int push(Stack *s, ElemType e) { // 健壮性检查指针为空或栈满直接返回失败 if (s NULL || s-top 99) { printf(入栈失败栈指针为空或栈已满\n); return 0; } s-data[s-top] e; // 栈顶指针上移 存入元素简化写法 return 1; } /** * 函数名: pop * 功能: 出栈操作扯脸谱 * 参数: s - 栈指针e - 存储出栈元素的指针 * 返回值: 1成功、0失败 */ int pop(Stack *s, ElemType *e) { if (s NULL || isEmpty(s)) { printf(出栈失败栈指针为空或栈为空\n); return 0; } *e s-data[s-top--]; // 取出元素 栈顶指针下移简化写法 return 1; } /** * 函数名: printPushOrder * 功能: 打印贴脸顺序栈底→栈顶 * 参数: s - 栈指针 */ void printPushOrder(Stack *s) { if (s NULL || isEmpty(s)) { printf(栈为空无脸谱可打印\n); return; } printf(贴脸顺序栈底→栈顶); for (int i 0; i s-top; i) { printf(%s , getColorName(s-data[i])); } printf(\n\n); } /** * 函数名: destroyStack * 功能: 销毁动态栈释放所有堆区内存 * 参数: s - 栈指针的指针需修改原指针避免野指针 * 说明: 动态内存必须手动释放否则造成内存泄漏 */ void destroyStack(Stack **s) { if (s NULL || *s NULL) return; free((*s)-data); // 第一步释放数组内存 free(*s); // 第二步释放结构体内存 *s NULL; // 第三步置空指针避免野指针 } // -------------------------- 主函数业务逻辑 -------------------------- int main() { printf( 动态顺序栈实现川剧扯脸序列 \n\n); // 1. 初始化动态栈内存分配在堆区 Stack *faceStack initStack(); if (faceStack NULL) { // 内存分配失败直接退出程序 return -1; } // 2. 执行贴脸谱入栈 printf(【贴脸谱过程】\n); for (int i 0; i colorCount; i) { push(faceStack, faceOrder[i]); printf(贴第%d张脸谱%s\n, i1, getColorName(faceOrder[i])); } // 打印贴脸顺序验证入栈结果 printPushOrder(faceStack); // 3. 执行扯脸谱出栈 printf(【扯脸谱结果】\n); ElemType popCode; printf(最终扯脸序列); while (!isEmpty(faceStack)) { pop(faceStack, popCode); printf(%s , getColorName(popCode)); } printf(\n); // 4. 销毁栈必做释放堆区内存避免泄漏 destroyStack(faceStack); printf(\n提示动态栈已销毁内存释放完成\n); printf(\n); return 0; }四、方案三链式栈链表实战版核心特点用链表节点存储栈元素无需预先分配固定容量按需创建节点考察指针操作、链表头插法核心逻辑理解 “逻辑上的栈” 与 “物理存储” 的分离。/* * 文件名: stack_linked_complete.c * 功能: 用链式栈实现川剧扯脸序列求解 * 适用人群: 进阶学习者理解链表与指针操作 * 核心特性: 链表节点存储无需固定容量按需分配节点内存 */ #include stdio.h #include stdlib.h // -------------------------- 全局常量与通用函数 -------------------------- // 颜色编号转字符串1白色, 2黄色, 3黑色, 4红色, 5青色, 6金色, 7银色 char* getColorName(int colorCode) { static const char* colorMap[] {未知颜色, 白色, 黄色, 黑色, 红色, 青色, 金色, 银色}; if (colorCode 1 || colorCode 7) { return (char*)colorMap[0]; } return (char*)colorMap[colorCode]; } // 贴脸谱顺序与数量固定常量 const int faceOrder[] {1, 2, 3, 4, 5, 6, 7}; const int colorCount sizeof(faceOrder) / sizeof(faceOrder[0]); // -------------------------- 链式栈核心定义 -------------------------- typedef int ElemType; // 栈节点结构体存储数据指向下一节点的指针 typedef struct StackNode { ElemType data; // 数据域存储颜色编号 struct StackNode *next; // 指针域指向后继节点 } StackNode; // 链式栈管理结构体仅需栈顶指针即可管理整个栈 typedef struct { StackNode *top; // 栈顶指针指向第一个有效节点空栈时为NULL } Stack; // -------------------------- 栈操作接口 -------------------------- /** * 函数名: initStack * 功能: 初始化链式栈创建管理结构体 * 返回值: 指向栈的指针NULL表示分配失败 */ Stack* initStack() { Stack *s (Stack*)malloc(sizeof(Stack)); if (s NULL) { printf(错误栈管理结构体分配失败\n); return NULL; } s-top NULL; // 空栈栈顶指针指向NULL return s; } /** * 函数名: isEmpty * 功能: 判断链式栈是否为空 * 参数: s - 栈指针 * 返回值: 1空栈、0非空栈 */ int isEmpty(Stack *s) { return (s ! NULL s-top NULL) ? 1 : 0; } /** * 函数名: push * 功能: 入栈操作头插法链表头部即为栈顶 * 参数: s - 栈指针e - 颜色编号 * 返回值: 1成功、0失败 * 说明: 链式栈入栈链表头插无需考虑栈满内存足够即可 */ int push(Stack *s, ElemType e) { if (s NULL) { printf(入栈失败栈指针为空\n); return 0; } // 1. 创建新节点并分配内存 StackNode *newNode (StackNode*)malloc(sizeof(StackNode)); if (newNode NULL) { printf(错误新节点内存分配失败\n); return 0; } // 2. 新节点赋值 newNode-data e; // 3. 头插法核心新节点指向原栈顶 newNode-next s-top; // 4. 栈顶指针更新为新节点 s-top newNode; return 1; } /** * 函数名: pop * 功能: 出栈操作删除栈顶节点 * 参数: s - 栈指针e - 存储出栈元素的指针 * 返回值: 1成功、0失败 */ int pop(Stack *s, ElemType *e) { if (s NULL || isEmpty(s)) { printf(出栈失败栈指针为空或栈为空\n); return 0; } // 1. 临时指针指向栈顶节点避免断链 StackNode *temp s-top; // 2. 取出栈顶节点数据 *e temp-data; // 3. 栈顶指针后移指向原第二个节点 s-top temp-next; // 4. 释放原栈顶节点内存避免泄漏 free(temp); return 1; } /** * 函数名: printPushOrder * 功能: 打印贴脸顺序栈顶→栈底链表遍历方向 * 参数: s - 栈指针 */ void printPushOrder(Stack *s) { if (s NULL || isEmpty(s)) { printf(栈为空无脸谱可打印\n); return; } printf(贴脸顺序栈顶→栈底); StackNode *p s-top; while (p ! NULL) { printf(%s , getColorName(p-data)); p p-next; } printf(\n\n); } /** * 函数名: destroyStack * 功能: 销毁链式栈释放所有节点管理结构体 * 参数: s - 栈指针的指针 */ void destroyStack(Stack **s) { if (s NULL || *s NULL) return; // 第一步遍历所有节点并释放 StackNode *p (*s)-top; while (p ! NULL) { StackNode *temp p; p p-next; free(temp); } // 第二步释放管理结构体 free(*s); *s NULL; } // -------------------------- 主函数业务逻辑 -------------------------- int main() { printf( 链式栈实现川剧扯脸序列 \n\n); // 1. 初始化链式栈 Stack *faceStack initStack(); if (faceStack NULL) { return -1; } // 2. 执行贴脸谱入栈链表头插 printf(【贴脸谱过程】\n); for (int i 0; i colorCount; i) { push(faceStack, faceOrder[i]); printf(贴第%d张脸谱%s\n, i1, getColorName(faceOrder[i])); } // 打印贴脸顺序验证入栈结果 printPushOrder(faceStack); // 3. 执行扯脸谱出栈删除链表头节点 printf(【扯脸谱结果】\n); ElemType popCode; printf(最终扯脸序列); while (!isEmpty(faceStack)) { pop(faceStack, popCode); printf(%s , getColorName(popCode)); } printf(\n); // 4. 销毁栈释放所有节点内存 destroyStack(faceStack); printf(\n提示链式栈已销毁内存释放完成\n); printf(\n); return 0; }五、核心总结逻辑统一3 种实现的核心逻辑均围绕 “入栈贴脸→ 出栈扯脸”栈 “先进后出” 的特性是求解问题的关键存储差异静态顺序栈数组固定容量内存自动管理简单但不灵活动态顺序栈数组动态分配需手动释放内存灵活但需注意泄漏链式栈链表节点按需分配无容量限制考察指针与链表操作本文通过川剧 “扯脸” 的趣味场景将抽象的栈结构落地为可运行的 C 语言代码从入门到进阶层层递进希望能帮助大家理解栈的核心特性与实际应用。
