搜索
1第03章栈和队列3.1栈的基本概念一、一般线性表、栈、队列的对比一般线性表栈队列插入ListInsert(L,i,e)1≤i≤ListLength(L)+1StackInsert(S,n+1,e)QueueInsert(Q,n+1,e)删除ListDelete(L,i,&e)1≤i≤ListLength(L)StackDelete(S,n,&e)QueueDelete(S,1,&e)二、栈的知识点（一）栈顶top位置的说明：1.在空栈中，top和base都指向整个栈的起始地址（也就是即将分配的第一个元素的地址）；2.在非空栈中，top始终是指向栈顶元素的下一个元素的地址。（二）入栈操作（先压后加）：Stack[top++]=e（三）出栈操作（先减后弹）：e=Stack[--top]（四）栈不存在的判断条件：base==NULL（五）栈空的判断条件：base==top（六）栈满的判断条件：top–base=MaxSize三、顺序栈的C语言实现typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针intStackSize;//顺序栈的初始容量（初始分配的能够容纳的元素个数）}SqStack;四、顺序栈的操作1.初始化栈——构造一个空栈StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(Stack_Init_Size*sizeof(SElemType));if(S.base==NULL)exit(OverFlow);//存储空间分配失败S.top=S.base;S.StackSize=Stack_Init_Size;}2.获取栈顶元素——若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERRORStatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;//栈空e=*(top–1);returnOK;}3.入栈——插入元素e作为新的栈顶元素StatusPush(SqStack&S,SElemTypee){if(S.top–S.base=S.StackSize)//栈已满，需要追加存储空间{S.base=(SElemType*)realloc(S.base,(S.StackSize+StackIncrement)*sizeof(SElemType));if(!S.base)exit(OverFlow);//存储空间分配失败S.top=S.base+S.StackSize;S.StackSize+=StackIncrement;}*S.top++=e;//*指针运算符和++自加运算符优先级相同，但是其结合方向是自右向左ReturnOK;}24.出栈——若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORStatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top；returnOK;}五、链栈的操作1.入栈intStackPush(LSNode*head,DataTypex){LSNode*p;if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL){printf(内存空间不足无法插入!\n);return0;}p-data=x;p-next=head-next;//新结点链入栈顶head-next=p;//新结点成为新的栈顶return1;}2.出栈intStackPop(LSNode*head,DataType*d){LSNode*p=head-next;if(p==NULL){printf(堆栈已空出错！);return0;}head-next=p-next;//删除原栈顶结点*d=p-data;//原栈顶结点元素赋予dfree(p);//释放原栈顶结点内存空间return1;}3.2栈的应用举例一、数制转换——例如(1348)10-(2504)81.将n（=1348）和8取余得4，入栈；2.n=n/8（此处是整数相除），重复步骤1，直到商为零；3.直接将栈遍历输出即可。程序框架：voidconversion(){initstack(S);scanf(“%d”,n);while(n){push(S,n%8);n=n/8;}while(!Stackempty(S)){pop(S,e);printf(“%d”,e);}}二、括号匹配的检验1.凡出现左括弧，入栈；2.出现右括弧，首先检查栈是否为空，若空则表示右括弧多了，否则和栈顶元素比较，匹配则左括弧出栈，否则括弧不匹配，出现异常；33.表达式检验结束时，若栈空则匹配正确，否则表明左括弧多了。程序框架：Statusmatching(string&exp){intstate=1;//假设匹配while(i=Length(exp)&&state){switchofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case)：{if（!StackEmpty(S)&&GetTop(S)=(){Pop(S,e);i++}else{state=0;}break;}case]:……}if(StackEmpty(S)&&state)returnOK;}三、回文字符串——回文：顺读与逆读字符串一样（不含空格），如字符串：madamimadam解题思路：1.读入字符串；2.去掉空格（原串）；3.将回文字符依次全部压入栈；4.原串字符与出栈字符依次比较，若不等，非回文，若直到栈空都相等，回文。四、行编辑程序——即在行编辑过程中不能进行回退的编辑模式，例如纸带编程模式。算法如下:voidLineEdit(){InitStack(s);ch=getchar();while(ch!=eof){while(ch!=eof&&ch!=‘\n’){//EOF为全文结束符switch(ch){case‘#’:pop(s,c);case‘@’:clearstack(s);//重置S为空栈default:push(s,ch);}ch=getchar();//从终端接收下一个字符}//将从栈底到栈顶的字符传送至调用过程的数据区；ClearStack(s);if(ch!=eof)ch=getchar();}DestroyStack(s);}五、表达式求值操作数：常数、变量标识符、常量标识符表达式运算符：算术运算符、逻辑运算符、关系运算符界限符：括号（）、表达式结束符；（一）表达式中相邻操作符的计算次序1.优先级高的先计算；2.优先级相同的自左向右计算；3.当使用括号时从最内层括号开始计算，逐层向外展开。（二）表达式的标识方法：4设Exp=S1+OP+S2(S1是第一操作数，S2是第二操作数，OP是操作符)，以运算符所在位置命名1.前缀式表示(prefix)——波兰式（Polish——因由波兰的数理逻辑学家J.Lukasiewicz提出）OP+S1+S22.中缀式表示（infix）：S1+OP+S23.后缀式表示（postfix）——逆波兰式（reversePolish）S1+S2+OP例如：Exp=a×b+(c-d/e)×f前缀式：+×ab×-c/def中缀式：a×b+c-d/e×f——将括号直接去掉即可后缀式：ab×cde/-f×+结论：1.操作数之间的相对次序不变；2.运算符的相对次序中缀式不变，前缀和后缀式发生变化；3.中缀式丢失了括号信息，致使运算的次序不确定了，故中缀式无意义；4.前缀式的运算规则是：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式；5.后缀式的运算规则为：运算符在式中出现的顺序恰为表达式的运算顺序；每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。6.计算后缀表达式所花费的时间复杂度为)(nO，当一个表达式以后缀记号的形式给出时，没有必要直到运算符的优先级就可以进行准确的计算。（三）利用栈对表达式的后缀式求值——先找运算符，再找操作数1.基本思想（1）设置一个空栈S。（2）依次读取表达式中的元素，如果元素是一个操作数，则将其压入栈S中；否则，元素为一个计算符，这时将S的两个栈顶元素弹出（第一个栈顶元素为右操作数，第二个栈顶元素为左操作数），并采用此运算符做相应的运算操作。然后把两个栈顶元素运算后的结果作为一个新操作数再压入栈中，如此直到整个表达式计算完毕。（3）最后栈S中唯一的元素即为表达式的求值结果。2.实例解析——（中缀式）3*4+5+6*7-（后缀式）34*5+67*+步骤栈中的内容(栈底-栈顶)操作剩下的字符0空34*5+67*+13读取3，Push(S,'3')4*5+67*+234读取4，Push(S,'4')*5+67*+312读取*，Push(S,Pop(S)*Pop(S))5+67*+4125读取5，Push(S,'5')+67*+517读取+，Push(S,Pop(S)+Pop(S))67*+6176读取6，Push(S,'6')7*+71767读取6，Push(S,'7')*+81742读取*，Push(S,Pop(S)*Pop(S))+959读取+，Push(S,Pop(S)+Pop(S))10空到达结尾，结果为Pop(S)3.练习题：对后缀式abc*+de/f*-（其对应的中缀式为：a+b*c–d/e*f）进行计算求值（四）利用栈将表达式的中缀式转后缀式51.基本思想（1）设置一个空栈S（用来存放操作符）。（2）依次读取中缀表达式中的元素。①如果读入的是操作数，则将其直接输出给后缀表达式。②如果读入的是“（”，则直接入栈，“（”对它之前后的运算符起隔离作用；③“）”可视为自相应左括号开始的表达式的结束符，如果读入的是“）”，则将栈元素依次弹出并输出，直至遇到“（”。注意“（”只弹出不输出，“（”也不输出。④如果读入的是其他操作符，则将其与栈顶元素相比较，若其优先级高于栈顶元素，则将其压入栈S中；否则(优先级低于或等于的都)从栈中弹出栈顶元素并输出，直到发现优先级更低的元素为止，再将其压入栈S中。（3）最后，直至读到输入的表达式的末尾。然后依次将栈元素弹出直到S变空，最后将弹出的元素输出。2.实例解析——（中缀式）a+b*c+(d+e)*f-（后缀式）abc*+de+f*+步骤栈中的内容(栈底-栈顶)操作剩下的字符输出0空a+b*c+(d+e)*f1读取a，输出a+b*c+(d+e)*fa2+读取+，Push(S,'+')b*c+(d+e)*fa3读取b，输出b*c+(d+e)*fab4+*读取*，*优先级高于+，Push(S,'*')c+(d+e)*fab5+*读取c，输出c+(d+e)*fabc6+读取+，+优先级低于栈顶的*，则*出栈并输出(d+e)*fabc*7读取到的+继续和栈中的+比较，因二者优先级相等，栈内的+也弹出并输出(d+e)*fabc*+8+此时栈内没有操作符，当前读取的+优先级高，则入栈(d+e)*fabc*+9+(读取(，优先级大于+，直接入栈d+e)*fabc*+10+(读取d，输出d+e)*fabc*+d+(+读取+，Push(S,’+’)，注意这里的后一个+是括号内的+，栈底的+是括号外的+，括号内的+优先级要高于括号外的+，所以直接入栈e)*fabc*+d+(+读取e，输出)*fabc*+de+读取)，将（开始，）结束之间的所有运算符依次弹出并输出，左右括号不输出*fabc*+de++*读取*，Push(S,*)fabc*+de++*读取f，输出fabc*+de+f+表达式读取完毕，直接将栈中的元素依次弹出并输出：先弹出*并输出abc*+de+f*再弹出+并输出abc*+de+f*+3.练习题：求中缀式a+(b-c/d)*e对应的后缀式。答案：abcd/-e*+六、迷宫求解基本思想：61.若当前位置的当前方向“可