数据结构第3章栈和队列.

数据结构第三章栈和队列数据结构第三章栈和队列1、栈和队列的定义及特点；2、栈的顺序存储表示；3、队列的顺序存储表示；队列的链接存储表示；4、栈和队列的应用举例。教学内容数据结构第三章栈和队列限定仅在表尾进行插入或删除操作。3.1栈3.1.1抽象数据类型栈的定义栈的定义a1a2an-1an…栈顶(top)栈底(bottom)出栈进栈栈底元素栈顶元素栈：线性表后进先出(LIFO结构)。数据结构第三章栈和队列栈的抽象数据类型的定义ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。数据结构第三章栈和队列GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。数据结构第三章栈和队列ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack数据结构第三章栈和队列3.1.2栈的表示和实现顺序栈顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。topbaseAtopBtopCtopDtopEtop空栈若再进行元素“出栈”操作，将产生“下溢”。top栈满若再进行元素“入栈”操作，将产生“上溢”。数据结构第三章栈和队列#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//数组指针，指示线性表的基地址intlength;//当前长度intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;SelemType*base;//栈底指针，它始终指向栈底的位置。SelemType*top;//栈顶指针。intstacksize;//当前分配的栈可使用的最大存储容量。Sqstack;注：base的值为NULL，表明栈结构不存在。#defineSTACK_INIT_SIZE100//栈存储空间的初始分配量#defineSTACKINCREMENT10//栈存储空间的分配增量数据结构第三章栈和队列栈的基本操作在顺序栈中的实现#definemaxs9;main(){intstack[maxs];inttop=0;while(topmaxs){scanf(“%d”,&stack[top]);top++;}inte;e=stack[top-1];while(top0)e=stack[top-1];top-=1;}InitStackPushPoptop12toptoptop2topGetTop21StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusPush(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;}//PushStatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top–1);returnOK;}//GetTopStatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//Pop数据结构第三章栈和队列栈顶指针链栈an注意:链栈中指针的方向an-1a1…^▲数据结构第三章栈和队列3.2栈的应用举例3.2.1数制转换十进制数N和其他d进制数M的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法是逐次除以基数d取余法，它基于下列原理：N=(Ndivd)*d+Nmodd具体作法为：首先用N除以d，得到的余数是d进制数M的最低位M0，接着以前一步得到的商作为被除数，再除以d，得到的余数是d进制数M的次最低位M1，依次类推，直到商为0时得到的余数是M的最高位Ms（假定M共有s+1位）。数据结构第三章栈和队列例：(1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202计算顺序输出顺序数据结构第三章栈和队列bottomtop4052top1348168voidconversion(){intstack[4];inttop=0;intN;scanf(“%d”,N);while(N){stack[top]=N%8;top++;N=N/8;}for(top=top-1;top=0;top--)printf(“%d”,stack[top]);}21top2top0top2504InitStack(S)Push(S,N%S)While(!Stackempty(S)){Pop(S,e);printf(“%d”,e);}数据结构第三章栈和队列3.2.2括号匹配的检验假设表达式中允许括号嵌套，则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：[([][])]12345678bottomtop[([toptoptoptoptoptoptoptop[可能出现的不匹配的情况：盼来的右括号不是所“期待”的；到来的是“不速之客”（右括号多）；到结束也未盼来所“期待”的括号（左括号多）。数据结构第三章栈和队列算法的设计思想：1）凡出现左括号，则进栈；2）凡出现右括号，首先检查栈是否空。若栈空，则表明该“右括号”多余；否则和栈顶元素比较，若相匹配，则“左括号出栈”，否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括号”有多余的。数据结构第三章栈和队列3.2.3行编辑程序功能：接受用户从终端输入的数据并存入用户的数据区。bottomtoptoptop接受一个字符即存入数据区。（差！难纠错。）设一个输入缓冲区，接受完一行字符后再存入用户的数据区。（好！可及时纠错。）做法纠错办法#退格符，表示前一个字符无效。@退行符，表示整行字符均无效。例：接受的字符为：whli##ileoutch@putch实际有效的为：whileputchwhltopitoptoptopitopletoptop数据结构第三章栈和队列voidLineEdit(){InitStack(S);ch=getchar();while(ch!=EOF){//EOF为全文结束符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();}DestroyStack(S);}数据结构第三章栈和队列3.2.4迷宫求解出口入口0123456789012345678911122232333424252616151431415152536364657585868788穷举求解求迷宫路径算法的基本思想：若当前位置“可通”，则纳入路径，继续前进；若当前位置“不可通”，则后退，换方向（按东南西北的顺序）继续探索；若四周“均无通路”，则将当前位置从路径中删除出去。数据结构第三章栈和队列3.2.5表达式求值运算规则先乘除，后加减；从左算到右；先括号内，后括号外；例：求表达式4+23-10/5的值。计算顺序为：4+23-10/5=4+6-10/5=10-10/5=10-2=8操作数或结果运算符#4+23610-10/582▲数据结构第三章栈和队列“四染色”定理是计算机科学中著名定理之一，即可以用不多于四种颜色对地图着色，使相邻的行政区域不重色。补充：地图四染色问题算法思想：从第一号行政区开始逐一染色，每一个区域逐次用颜色1、2、3、4进行试探。若当前所取的色数与周围已染色的行政区不重色，则用栈记下该行政区的色数，否则依次用下一色数进行试探；若出现用1至4色均与相邻区域发生重色，则需退栈回溯，修改当前栈顶的色数，再进行试探。直至所有行政区域都已分配合适的颜色。数据结构第三章栈和队列例：已知7个行政区域地图，对其进行染色。1234567101111102100001031001100410101105101101061101100700000001234123456712234431(3)(1)(2)(4)(5)(6)(7)3243数据结构第三章栈和队列作业：3.1、3.2、3.3、3.4、3.18选择题部分1、若入栈序列是a,b,c,d,e，则不可能的出栈序列是（）。（A）edcba（B）decba（C）dceab（D）abcde2、判定一个栈ST(最多元素为m0)为空的条件是（）。（A）ST.top!=0（B）ST.top=0（C）ST.top!=m0（D）ST.top=m03、判定一个栈ST(最多元素为m0)为满的条件是（）。（A）ST.top!=0（B）ST.top=0（C）ST.top!=m0（D）ST.top=m0数据结构第三章栈和队列3.3栈与递归的实现递归：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。例：阶乘函数0)1(01)(nnFactnnnFact若若相应的C语言函数是：floatfact(intn){floats;if(n==0)s=1;elses=n*fact(n-1);return(s);}若求5!，则有main(){printf(“5!=%f\n”,fact(5));}数据结构第三章栈和队列当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：1.将实参等传递给被调用函数，保存返回地址（入栈）；2.为被调用函数的局部变量分配存储区；3.将控制转移到被调用函数的入口。从被调用函数返回调用函数之前，应该完成：1.保存被调函数的计算结果；2.释放被调函数的数据区；3.按被调函数保存的返回地址（出栈）将控制转移到调用函数。多个函数嵌套调用的规则是：后调用先返回。此时的内存管理实行“栈式管理”。数据结构第三章栈和队列floatfact(intn){floats;if(n==0)s=1;elses=n*fact(n-1);return(s);}递归调用执行过程：主函数main()Printf(fact(5)