《数据结构教学课件》chap003

第三章栈和队列通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型3.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现3.1栈的类型定义ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack栈的特点栈：限定只能在表的一端进行插入和删除的特殊的线性表设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。a1a2….an进栈出栈栈顶栈底设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=0栈中的运算：1.设置空栈；2.插入一个新的栈顶元素3.删除栈顶元素；4.读取栈顶元素。10S[4]2310bases[top]=xtop=top+1top102530S[4]2310topbasetop=top-1x=s[top]栈空10进栈30出栈S[4]2310top=0top栈满top=stacksize10253040S[4]2310top=4base栈的定义（顺序表）#defineSTACK_INI_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)•初始条件：栈S已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane……Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1……3.2栈类型的实现顺序栈链栈//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。StatusInitStack(SqStack&S){//构造一个空栈SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusPush(SqStack&S,SElemTypee){if(S.top-S.base=S.stacksize){//栈满，追加存储空间S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，//用e返回其值，并返回OK；//否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}注意：判定栈空的条件S.top==S.baseStatusGetTop(SqStack&S,SElemType&e){//若栈不空，用e返回其值，并返回OK；//否则返回ERRORif(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}StatusStackEmpty(SqStackS){if(S.top==S.base)return1;elsereturn0;}栈顶指针链栈∧a1an注意:链栈中指针的方向an-13.3栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归例一、数制转换算法基于原理：N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202计算顺序输出顺序voidconversion(){InitStack(S);scanf(%d,&N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf(%d,e);}}//conversion例二、括号匹配的检验假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（（）］)均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。分析可能出现的不匹配的情况:•到来的右括弧并非是所“期待”的；例如：考虑下列括号序列：[([][])]12345678•到来的是“不速之客”；•直到结束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。Statusmatching(string&exp){intstate=1;while(i=Length(exp)&&state){switchofexp[i]{case左括弧:{Push(S,exp[i]);i++;break;}case”)”:{if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}else{state=0;}break;}……}if(StackEmpty(S)&&state)returnOK;…...例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器”?并不恰当！设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。合理的作法是：假设从终端接受了这样两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：while(*s)putchar(*s++);while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;case'@':ClearStack(S);break;//重置S为空栈default:Push(S,ch);break;}ch=getchar();//从终端接收下一个字符}ClearStack(S);//重置S为空栈if(ch!=EOF)ch=getchar();while(ch!=EOF){//EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；例四、迷宫求解通常用的是“穷举求解”的方法############$$$####$$$###$$#####################################求迷宫路径算法的基本思想是：•若当前位置“可通”，则纳入路径，继续前进;•若当前位置“不可通”，则后退，换方向继续探索;•若四周“均无通路”，则将当前位置从路径中删除出去。设定当前位置的初值为入口位置；do｛若当前位置可通，则｛将当前位置插入栈顶；若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为新的当前位置；｝否则{｝｝while(栈不空）；求迷宫中一条从入口到出口的路径的算法：……若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；//从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝若栈空，则表明迷宫没有通路。限于二元运算符的表达式定义:表达式::=(操作数)+(运算符)+(操作数)操作数::=简单变量|表达式简单变量::=标识符|无符号整数例五、表达式求值表达式的三种标识方法：设Exp=S1+OP+S2则称OP+S1+S2为前缀表示法S1+OP+S2为中缀表示法S1+S2+OP为后缀表示法一个中缀式到其他式子的转换方法~~这里给出一个中缀表达式~a+b*c-(d+e)第一步：按照运算符的优先级对所有的运算单位加括号~式子变成：((a+(b*c))-(d+e))第二步：转换前缀与后缀表达式前缀：把运算符号移动到对应的括号前面则变成拉：-(+(a*(bc))+(de))把括号去掉：-+a*bc+de前缀式子出现后缀：把运算符号移动到对应的括号后面则变成拉：((a(bc)*)+(de)+)-把括号去掉：abc*+de+-后缀式子出现前缀式，后缀式是不需要用括号来进行优先级的确定的。例如:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。如何从后缀式求值？先找运算符，再找操作数例如：abcde/f+abd/ec-d/e(c-d/e)f如何从原表达式求得后缀式？每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f从原表达式求得后缀式的规律为：1)设立操作数栈；2)设表达式的结束符为“#”，予设运算符栈的栈底为“#”；3)若当前字符是操作数，则直接发送给后缀式。4)若当前运算符的优先数高于栈顶运算符，则进栈；5)否则，退出栈顶运算符发送给后缀式；6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#)