《数据结构》课件 第3章 栈

第3章栈(Stack)后进先出的艺术课程内容概览01栈的基本概念定义、特性、抽象数据类型02栈的顺序存储实现顺序栈的结构、操作与实现03栈的链式存储实现链栈的结构、操作与实现04栈的经典应用括号匹配、表达式求值、函数调用05综合应用案例迷宫求解06总结与练习知识点回顾与巩固练习我们身边的"栈"01食堂的餐盘食堂阿姨总是把新洗好的餐盘放在最上面,同学们取用时也总是拿最上面的那一个。最先放上去的餐盘,最后才能被取走。特性后进先出(LIFO)02浏览器的后退按钮我们访问网页时,每打开一个新页面,就相当于把它压入一个"历史记录栈"。点击"后退"按钮,就相当于从栈顶弹出最近访问的页面。特性后进先出(LIFO)03Word的撤销操作(Ctrl+Z)我们每进行一次编辑操作,Word都会将其记录在一个栈中。当我们需要撤销时,总是撤销最后一次操作。特性后进先出(LIFO)栈的诞生:严谨与创新的科学精神弗里德里希·路德维希·鲍尔FriedrichLudwigBauer简介德国著名数学家和计算机科学家,被誉为"栈"概念的发明者。贡献20世纪50年代,在计算机编程尚处于萌芽阶段,程序执行顺序容易混乱。鲍尔教授提出了使用"栈"来管理程序运行过程中的数据和指令,这一思想彻底改变了程序的组织方式,为现代程序设计奠定了基础。精神体现勇于创新在没有成熟理论指导的年代,他能够从复杂的程序执行过程中抽象出"栈"这一简洁而强大的模型,解决了当时的关键难题。艾兹赫尔·戴克斯特拉EdsgerW.Dijkstra简介荷兰计算机科学家,图灵奖得主,对栈的应用做出了巨大贡献。贡献Dijkstra在设计第一个Algol60编译器时,深入研究了递归的实现机制。他明确指出,支持递归调用的运行时系统必须包含某种形式的栈机制。精神体现严谨求实他不仅使用栈,更深入探究了栈在程序运行时的本质作用。他的名言"程序测试可以显示错误的存在,但不能证明错误的不存在"提醒我们在编程中要保持严谨和敬畏之心。本章学习目标01理解栈的基本概念掌握栈的定义、LIFO特性及其抽象数据类型(ADT)。02掌握栈的两种实现熟练掌握顺序栈和链栈的结构定义、基本操作及其C语言实现。03精通栈的经典应用学会运用栈解决括号匹配、表达式求值等经典问题。04理解栈的深层作用理解栈在函数调用和递归中的核心作用。05解决综合应用问题运用栈解决如"迷宫求解"等复杂问题,培养综合应用能力。什么是栈?(Stack)定义·栈是一种特殊的线性表,它只允许在表的一端进行插入和删除操作。关键术语栈顶(Top)允许进行插入和删除操作的一端。栈底(Bottom)固定的,不允许进行插入和删除操作的另一端。空栈不含任何元素的栈。操作名称入栈(Push)在栈顶插入一个元素,也称为压栈。出栈(Pop)删除栈顶元素,也称为弹栈。栈顶Top栈底Bottom入栈Push出栈Pop栈的核心特性:后进先出(LIFO)解释最后被插入(入栈)的元素,将会是第一个被删除(出栈)的元素。"叠罗汉"最后一个爬上罗汉塔的人,会第一个下来。"子弹夹"最后压入的子弹,会最先被射出。动画演示01依次入栈元素A→B→C入栈,栈内为A,B,C02执行出栈C被弹出,栈内剩余A,B03再次出栈B被弹出,栈内剩余A04最终状态A被弹出,栈变为空栈的抽象数据类型(ADT)数据对象D={a_i|a_i∈ElemSet,i=1,2,...,n,n≥0}数据关系R={<a_{i-1},a_i>|i=2,...,n}其中,a_1端为栈底,a_n端为栈顶。基本操作1InitStack(&S)初始化操作。构造一个空栈S。2StackEmpty(S)判空操作。若栈S为空,则返回TRUE,否则返回FALSE。3Push(&S,e)入栈操作。将元素e压入栈S,成为新的栈顶元素。4Pop(&S,&e)出栈操作。删除栈S的栈顶元素,并用e返回其值。5GetTop(S,&e)取栈顶元素。用e返回栈顶元素,但不改变栈的状态。6ClearStack(&S)清空栈操作。将栈S清空。7DestroyStack(&S)销毁栈操作。释放栈S占用的存储空间。栈在计算机科学中的应用01函数调用与递归程序运行时,系统使用栈来管理函数的调用和返回。02表达式求值编译器使用栈来处理复杂的算术表达式,如中缀表达式转后缀表达式。03括号匹配检查代码中的括号是否成对出现。04深度优先搜索(DFS)在图和树的遍历中,栈是实现DFS的核心数据结构。05回溯算法解决如迷宫求解、八皇后问题等需要"尝试-失败-回退"的问题。06浏览器历史记录用于实现后退功能。本节小结01数据结构定义栈是一种后进先出(LIFO)的线性表。02操作位置限制所有操作都在栈顶进行。03核心基本操作基本操作包括入栈(Push)和出栈(Pop)。04应用与地位栈的应用非常广泛,是计算机科学的基础数据结构之一。栈是计算机科学中不可或缺的基础数据结构,接下来,我们将学习如何具体实现栈。顺序栈的结构思想使用一段连续的存储空间(数组)来存储栈中的元素。结构定义一个数组data用于存放栈中元素。一个整型变量top用于指示栈顶元素在数组中的位置。图示说明数组下标从0到MAXSIZE-1,栈底固定在下标0。top变量指向栈顶元素所在的数组下标。C语言代码实现#defineMAXSIZE100//栈的最大容量//顺序栈结构定义typedefstruct{intdata[MAXSIZE];//存放栈元素的数组inttop;//栈顶指针,指向栈顶元素的下标}SeqStack;顺序栈的状态判定栈空条件top==-1解释:初始化时,`top`被设置为-1,表示栈中没有元素。图示:数组为空,`top`指针指向-1的位置。栈满条件top==MAXSIZE-1解释:栈顶指针已经到达数组的最后一个位置,无法再插入新元素。图示:数组被元素填满,`top`指针指向最后一个元素的下标。讨论为什么不把`top==0`作为栈空条件?如果`top==0`表示栈空,那么栈底元素将存放在`data[1]`,会浪费一个数组空间。使用`top==-1`可以充分利用数组空间。顺序栈操作:初始化(InitStack)算法思路1为栈结构分配内存。2将栈顶指针top设置为-1,表示栈为空。图示一个新创建的栈结构,top指针指向-1。top=-1C语言代码实现//初始化顺序栈voidInitStack(SeqStack*S){S->top=-1;//将栈顶指针置为-1,表示空栈}这行代码就完成了一个空栈的创建。顺序栈操作:入栈(Push)算法思路1判断栈是否已满。如果已满,则返回错误(上溢)。2将栈顶指针top向上移动一位(top++)。3将新元素e存入data[top]的位置。状态图示初始状态栈中元素:A·Btop指针指向B→执行操作新元素C准备入栈执行top++与赋值结束状态top上移一位,指向C,元素C成功存入数组。C语言实现intPush(SeqStack*S,inte){//入栈操作if(S->top==MAXSIZE-1){//栈满printf("栈上溢!\\n");return0;//入栈失败}S->top++;S->data[S->top]=e;//指针上移,压入新元素return1;//入栈成功顺序栈操作:出栈(Pop)算法思路1判断栈是否为空。如果为空,则返回错误(下溢)。2将栈顶元素data[top]的值赋给e。3将栈顶指针top向下移动一位(top--)。操作图示初始状态栈内元素:A·B·Ctop指向C执行操作执行出栈Pop取出栈顶元素C结束状态top下移指向B返回值:CC语言实现//出栈操作intPop(SeqStack*S,int*e){if(S->top==-1){//栈空,返回错误printf("栈下溢!\\n");return0;}e=S->data[S->top];//赋值给e|S->top--;//指针下移|return1;}顺序栈操作:取栈顶元素(GetTop)算法思路1判断栈是否为空。如果为空,则返回错误。2将栈顶元素data[top]的值赋给e。注意此操作不改变栈的状态,top指针保持不变。栈状态示意CtopBA操作后,C的值被返回,但栈的状态与top指针均无变化。C语言实现代码//取栈顶元素intGetTop(SeqStack*S,int*e){if(S->top==-1){//栈空printf("栈为空!\n");return0;//获取失败}e=S->data[S->top];//将栈顶元素赋值给ereturn1;//获取成功}核心:不改变栈的结构,仅读取栈顶元素的值。顺序栈操作:判空(StackEmpty)算法思路01条件判断判断top是否等于-1。02结果返回如果是,则栈为空,返回TRUE;否则返回FALSE。C语言代码//判断栈是否为空intStackEmpty(SeqStack*S){returnS->top==-1;//若top为-1则返回1(真),否则返回0(假)}顺序栈完整实现与测试C语言实现代码#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];inttop;}SeqStack;//...(此处省略上述所有操作的函数定义)...intmain(){SeqStackS;inte;InitStack(&S);Push(&S,1);Push(&S,2);Push(&S,3);Push(&S,4);Push(&S,5);GetTop(&S,&e);printf("栈顶元素为:%d\\n",e);printf("出栈顺序为:");while(!StackEmpty(&S)){Pop(&S,&e);printf("%d",e);}if(StackEmpty(&S))printf("栈已为空\\n");return0;}程序执行结果读取栈顶元素栈顶元素为·5出栈打印顺序输出·54321循环结束后状态栈已被清空·栈已为空动手运行代码,验证结果是否符合预期顺序栈的复杂度分析时间复杂度初始化O(1)入栈(Push)O(1)仅需移动指针和赋值。出栈(Pop)O(1)仅需移动指针和赋值。取栈顶(GetTop)O(1)仅需访问数组元素。判空(StackEmpty)O(1)仅需一次比较。结论:顺序栈的所有基本操作都具有常数时间复杂度。空间复杂度O(n)需要预先分配大小为MAXSIZE的数组。缺点存在空间浪费和栈溢出的风险。一旦数组大小确定,就无法动态扩展。顺序栈的优缺点优点实现简单基于数组,代码直观易懂。效率高所有操作的时间复杂度均为O(1)。存储密度大元素连续存储,没有额外的指针开销。缺点空间固定栈的容量在初始化时就已确定,无法动态调整。易溢出当需要存储的元素数量超过预设的MAXSIZE时,会发生栈上溢。空间浪费如果实际存储的元素远少于MAXSIZE,会造成内存空间的浪费。链栈的结构思想使用链表来存储栈中的元素。栈顶对应链表的头结点,栈底对应链表的尾结点。优点克服了顺序栈空间固定的缺点,可以动态地分配内存。结构定义定义一个包含数据域和指针域的结点,以及一个指向栈顶的链栈结构。结构图示topdatanextdatanextNULL头指针top指向第一个结点(栈顶),最后一个结点的next为NULL(栈底)。C语言代码实现//链栈结点结构定义typedefstructStackNode{intdata;//数据域structStackNode*next;}StackNode;//链栈结构定义typedefstruct{StackNode*top;//栈顶指针}LinkStack;链栈的栈空条件栈空条件top==NULL解释初始化时,栈顶指针top被设置为NULL,表示链表中没有结点。图示栈顶指针top指向目标NULL链栈操作:初始化(InitStack)算法思路1为链栈结构分配内存。2将栈顶指针top设置为NULL,表示空栈。图示一个新创建的链栈结构,top指针指向NULL。栈顶指针topNULL此时栈内无任何元素,处于空栈状态。C语言代码实现//初始化链栈voidInitStack(LinkStack*S){S->top=NULL;//将栈顶指针置为NULL,表示空栈}链栈操作:入栈(Push)算法思路01创建一个新的结点,并为其分配内存。02将新结点的数据域赋值为`e`。03将新结点的指针域指向当前的栈顶结点`S->top`。04将栈顶指针`S->top`指向新结点。图示流程初始状态栈顶为结点B,`top`指向B执行操作元素C入栈结束状态创建新结点C,`top`指向CC语言实现代码//入栈操作intPush(LinkStack*S,inte){StackNode*newNode=(StackNode*)malloc(sizeof(StackNode));if(newNode==NULL){//内存分配失败printf("内存分配失败!\\n");return0;}newNode->data=e;//赋值newNode->next=S->top;//新结点指向原栈顶S->top=newNode;//栈顶指针指向新结点return1;//入栈成功}链栈操作:出栈(Pop)算法思路1判断栈是否为空。如果为空,则返回错误。2用一个临时指针p指向当前的栈顶结点。3将栈顶元素p->data的值赋给e。4将栈顶指针S->top指向原栈顶结点的下一个结点。5释放临时指针p所指向的结点内存。状态图示初始状态栈顶为结点C,`top`指向C操作执行出栈操作,临时指针p指向C结束状态`top`指向B,C结点被释放,出栈成功。intPop(LinkStack*S,int*e){if(S->top==NULL){printf("栈下溢!");return0;}StackNode*p=S->top;//临时指针指向栈顶e=p->data;S->top=p->next;free(p);//指针下移,释放内存链栈操作:取栈顶元素(GetTop)算法思路01判断栈是否为空。如果为空,则返回错误。02将栈顶结点的数据S->top->data的值赋给e。注意此操作不改变栈的状态,不进行出栈操作。图示说明栈顶为结点C,top指向C。操作后,C的值被返回,但栈的状态不变。C语言代码实现//取栈顶元素intGetTop(LinkStack*S,inte){if(S->top==NULL){//栈空printf("栈为空!\\n");return0;}e=S->top->data;//将栈顶元素赋值给ereturn1;}链栈操作:判空(StackEmpty)算法思路01判断top是否等于NULL。02如果是,则栈为空,返回TRUE;否则返回FALSE。C语言代码//判断栈是否为空intStackEmpty(LinkStack*S){returnS->top==NULL;}通过检查top指针是否指向NULL,即可高效判断链栈状态。链栈操作:销毁栈(DestroyStack)算法思路01循环出栈循环执行出栈操作,直到栈为空。02释放内存每次出栈时,都会释放相应结点的内存。C语言代码实现//销毁栈voidDestroyStack(LinkStack*S){inte;while(Pop(S,&e));//不断出栈,直到栈空}通过复用Pop操作,将内存释放的工作交给出栈函数,代码简洁高效。链栈完整实现与测试C语言代码#include<stdio.h>#include<stdlib.h>//...(此处省略上述所有操作的函数定义)...intmain(){LinkStackS;inte;InitStack(&S);Push(&S,1);Push(&S,2);Push(&S,3);Push(&S,4);Push(&S,5);GetTop(&S,&e);printf("栈顶元素为:%d\n",e);//输出5顺序栈vs.链栈顺序栈链栈存储基础数组存储基础链表空间分配静态分配,固定大小空间分配动态分配,灵活空间效率可能浪费,可能溢出空间效率无浪费,无溢出,但有指针开销时间效率O(1),数组访问快时间效率O(1),指针操作稍慢实现复杂度简单实现复杂度稍复杂适用场景栈大小可预估适用场景栈大小变化大或无法预估应用一:括号匹配问题描述给定一个只包含'(',')','{','}','[',']'的字符串,判断字符串是否有效。01有效字符串需满足左括号必须用相同类型的右括号闭合。02有效字符串需满足左括号必须以正确的顺序闭合。示例()[]{}'有效(]'无效([)]'无效{[]}'有效括号匹配算法思路核心思想利用栈的LIFO(后进先出)特性,处理字符的匹配关系。01遍历字符串依次检查字符串中的每一个字符。02遇到左括号若为({[,将其入栈。03遇到右括号栈空则直接返回false;否则弹出栈顶,不匹配即返回false。04遍历结束后检查栈是否为空,不空说明有左括号未匹配,返回false;否则返回true。示例演示以字符串{[]}为例,展示每一步的入栈和出栈过程:第1步·遇到'{'左括号,执行入栈栈内容:[{]第2步·遇到']'弹出栈顶'[',匹配成功栈内容:[{]第3步·结束匹配完成,栈为空结果:True括号匹配算法步骤详解示例:({[]})——依次遍历每个字符,遵循"左括号入栈,右括号出栈匹配"的规则1遇到'('入栈栈状态:['(']2遇到'{'入栈栈状态:['(','{']3遇到'['入栈栈状态:['(','{','[']4遇到']'匹配成功栈状态:['(','{']5遇到'}'匹配成功栈状态:['(']6遇到')'匹配成功栈状态:[]7遍历结束栈为空最终返回:true通过栈的"后进先出"特性,严格遵循"左括号入栈,右括号出栈匹配"的规则,最终栈为空即代表所有括号正确匹配。括号匹配的C语言实现#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXSIZE100//顺序栈定义typedefstruct{chardata[MAXSIZE];inttop;}SeqStack;//括号匹配主函数intisValid(char*s){SeqStackstack;InitStack(&stack);intlen=strlen(s);for(inti=0;i<len;i++){if(isLeftBracket(s[i]))Push(&stack,s[i]);//左括号入栈elseif(StackEmpty(&stack)||!isMatch(top,s[i]))return0;}returnStackEmpty(&stack);//最终栈必须为空才匹配成功数据结构使用顺序栈(SeqStack)作为核心存储结构,先进后出的特性天然适合匹配场景。核心逻辑遍历字符串,遇到左括号入栈;遇到右括号则出栈顶元素进行匹配。关键判断若栈空仍有右括号,或类型不匹配,立即返回0(失败);最终栈为空才返回1(成功)。括号匹配的复杂度分析时间复杂度O(n)我们只需要遍历字符串一次,每个字符最多入栈和出栈一次。空间复杂度O(n)在最坏情况下,例如((((((,所有字符都是左括号,需要全部入栈,此时栈的大小为n。应用二:表达式求值问题描述如何让计算机理解并计算像3+4*2/(1-5)这样的中缀表达式?挑战运算符优先级运算符有不同的优先级,其中/高于+-。括号改变顺序括号的存在会强制改变原有的计算优先级,增加了处理的复杂度。解决方案将中缀表达式转换为后缀表达式(逆波兰表示法),然后对后缀表达式进行求值。什么是后缀表达式?(PostfixNotation)定义运算符位于操作数之后的表达式。示例中缀3+4后缀34+中缀3+4*2后缀342*+中缀(3+4)*2后缀34+2*优点后缀表达式没有括号,也不需要考虑运算符优先级,非常适合计算机进行计算。算法:中缀表达式转后缀表达式核心思想使用一个运算符栈,按规则处理每个Token。01遍历中缀表达式的每个Token。02操作数如果是操作数,直接输出。03左括号'('如果是左括号,直接将其入栈。04右括号')'将栈顶运算符依次弹出并输出,直到遇到左括号;弹出左括号,但不输出。05运算符+-*/弹出栈顶优先级高于当前的运算符,直到栈空或遇左括号;再将当前运算符入栈。06遍历结束后将栈中剩余的所有运算符,依次弹出并输出。运算符优先级/的优先级高于+-转换过程示例:a+b*c-(d+e)/f1Token:a输出:a2Token:+栈空,入栈。栈:['+']3Token:b输出:ab4Token:*优先级高于+,入栈。栈:['+','*']5Token:c输出:abc6Token:-优先级低于*,弹出*→输出abc*;优先级等于+,弹出+→输出abc*+。入栈-,栈:['-']7–14处理(d+e)/f,括号内运算符正常入栈,遇到右括号弹出至左括号。遍历结束后,依次弹出栈内剩余的/和-,追加到输出。最终后缀表达式abc*+de+f/-关键思路回顾利用运算符栈暂存待处理的操作符,通过比较优先级决定是入栈还是弹出。括号可视为局部优先级的"重置"。中缀转后缀的C语言实现getPriority·获取运算符优先级根据运算符类型返回其优先级数值,决定出栈或入栈的判断依据。intgetPriority(charop){if(op=='(')return0;//左括号优先级最低if(op=='+'||op=='-')return1;//加减优先级为1if(op=='*'||op=='/')return2;//乘除优先级为2infixToPostfix·中缀表达式转后缀表达式核心转换逻辑:遍历中缀表达式,根据字符类型(操作数/括号/运算符)进行不同处理。while(infix[i]!='\0'){if(infix[i]>='0'&&infix[i]<='9')postfix[j++]=infix[i++];//操作数直接输出elseif(infix[i]=='(')Push(&stack,infix[i++]);//左括号入栈elseif(infix[i]==')'){/*右括号,弹出直到左括号*/}else{/*运算符,比较优先级后处理*/}遍历结束后,依次弹出栈中剩余运算符,添加至后缀表达式末尾,最终形成完整结果。算法:后缀表达式求值核心思想使用一个操作数栈,通过入栈、计算、出栈的循环完成表达式求解。01遍历遍历后缀表达式的每个Token。02遇到操作数将其转换为整数,并入栈。03遇到运算符弹出两个元素计算,结果再入栈。04遍历结束栈中仅剩的一个元素,即为最终结果。示例演示以表达式342*+为例:依次处理每个Token,观察栈的状态变化。依次入栈操作数342→遇到,计算4×2=838结果8入栈,替换原两个操作数遇到+,再次计算3+8=11→遍历结束,栈中剩余最终结果11求值过程示例:`342*+`013→入栈栈状态:[3]024→入栈栈状态:[3,4]032→入栈栈状态:[3,4,2]04→运算弹出2和4,计算4×2=8栈:[3,8]05+→运算弹出8和3,计算3+8=11栈:[11]最终结果表达式的计算值为11后缀表达式求值的C语言实现核心运算函数intcalculate(inta,intb,charop)根据传入的运算符,计算两个操作数的结果。switch(op){case'+':returna+b;case'-':returna-b;case'/':if(b==0){printf("除数不能为0!");exit(1);}default:printf("无效的运算符!");exit(1);}后缀表达式求值主逻辑intevaluatePostfix(char*postfix)利用顺序栈存储操作数,遍历字符串完成求值。SeqStackstack;InitStack(&stack);while(postfix[i]!='\0'){if(是数字)Push(数值);//操作数入栈else{Pop(b);Pop(a);//注意顺序:先弹出的是右操作数bPush(calculate(a,b,op));}}intresult;Pop(result);returnresult;综合示例:计算3+4*2/(1-5)中缀转后缀转换后的后缀表达式为:342*15-/+后缀求值过程342*→383815-→38-438-4/→3-23-2+→1最终结果表达式3+4*2/(1-5)的计算结果为:1应用三:函数调用与递归概念每个程序在运行时都有一个调用栈(CallStack),也称为运行时栈(RuntimeStack)。作用用于管理函数的调用和返回。栈帧(StackFrame)每次调用一个函数时,系统会在调用栈上创建一个栈帧,包含该次函数调用的所有信息:局部变量函数内部定义的变量。参数传递给函数的参数。返回地址函数执行完毕后,程序应该返回到哪里继续执行。寄存器状态保存调用前的CPU寄存器状态。图示·一个调用栈的示意图,包含多个栈帧,每个栈帧对应一次函数调用。栈帧A·对应最近一次函数调用栈帧B·前一次函数调用的上下文调用栈CallStack函数调用的栈操作示例代码voidfuncB(){/*...*/}voidfuncA(){funcB();}intmain(){funcA();return0;}执行过程1main()开始执行,main的栈帧被压入调用栈。2main()调用funcA(),funcA的栈帧被压入调用栈。3funcA()调用funcB(),funcB的栈帧被压入调用栈。4funcB()执行完毕,其栈帧从调用栈弹出,返回到funcA()。5funcA()执行完毕,其栈帧从调用栈弹出,返回到main()。6main()执行完毕,其栈帧从调用栈弹出,程序结束。调用栈状态示意funcB()·当前栈顶,正在执行funcA()·等待funcB()返回后继续执行main()·等待funcA()返回后继续执行执行过程严格遵循"后进先出(LIFO)"栈帧压入顺序:main→funcA→funcB,弹出顺序则相反。递归的本质:栈的应用递归函数调用自身的过程,就是不断地将新的栈帧压入调用栈的过程。示例:计算factorial(3)intfactorial(intn){if(n==1)return1;returnn*factorial(n-1);调用栈执行过程01factorial(3)被调用,栈帧1(n=3)入栈。02调用factorial(2)栈帧2(n=2)入栈。03调用factorial(1)栈帧3(n=1)入栈。04执行return1触发终止,栈帧3弹出。05计算2*1=2执行return2,栈帧2弹出。06计算3*2=6执行return6,栈帧1弹出。什么是栈溢出(StackOverflow)?定义当调用栈的深度超过了系统为其分配的内存空间时,就会发生栈溢出。原因无限递归没有终止条件的递归函数会不断创建栈帧,直到栈溢出。递归深度过大即使有终止条件,如果递归的层数太深,也可能导致栈溢出。局部变量过大在函数内部定义了非常大的数组或对象,也会消耗大量的栈空间。示例voidinfiniteRecursion(){infiniteRecursion();//无限递归}——调用此函数会导致栈溢出错误。综合应用案例:迷宫求解问题描述给定一个mxn的迷宫,由0(通路)和1(障碍)组成。迷宫有一个入口和一个出口,请找出一条从入口到出口的路径。示例迷宫111111100001101101100001矩阵含义说明数字0代表可通行的通路数字1代表不可通行的障碍入口迷宫起点坐标(1,1)出口迷宫终点坐标(4,4)迷宫求解算法思路:深度优先搜索(DFS)+回溯核心思想01起点标记从入口开始,将当前位置标记为已访问。02方向探索尝试向四个方向(上、下、左、右)探索。03通路判定若方向是通路(值为0)且未被访问,则移动并将当前位置入栈。04循环执行重复步骤2和3,直到找到出口。05回溯处理若四周不通,执行回溯:当前位置出栈,返回上一位置。数据结构使用栈来保存走过的路径,以便在需要时进行回溯。迷宫求解数据结构设计迷宫表示使用二维数组来存储迷宫的地形信息。intmaze[ROW][COL];通过二维数组的行列索引,快速定位并判断该位置是否可通行。位置表示定义一个结构体来封装迷宫中的坐标。typedefstruct{intx;//行号inty;//列号}PosType;将行号与列号打包,便于统一管理和传递位置信息。栈元素栈中存储的是PosType类型的位置信息。//栈元素类型PosTypestack[MAX_SIZE];利用栈先进后出的特性,记录探索路径,便于回溯。方向数组定义一个数组来表示四个探索方向。//上、右、下、左PosTypedirs[]={{-1,0},{0,1},{1,0},{0,-1}};避免冗长的条件判断,通过循环即可遍历所有方向。迷宫求解算法步骤详解01将入口位置入栈,并标记为已访问(例如,将其值改为2)。02循环,直到栈为空:a获取栈顶位置cur。b如果cur是出口,返回成功。c依次尝试四个方向,计算新位置next。若在范围内且是通路(值为0),则入栈并标记为已访问(值改为2)。d若四方向均不通,出栈并标记为死路(值改为3)。图示·探索路径与回溯过程的动态展示通过入栈探索与出栈回溯,逐步遍历迷宫直至找到出口。迷宫求解的C语言实