资源描述：
《数据结构_严蔚敏_第3章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列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
2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
3、a
4、i-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStack栈的特点栈：限定只能在表的一端进行插入和删除的特殊的线性表设栈s=（a1，a2，...,ai，...，an），其中a1是栈底元素，an是栈顶元素。a1a2….an进栈出栈栈顶栈底栈中的运算：1.设置空栈；2.插入一个新的栈顶元素3.删除栈顶元素；4.读取栈顶元素。设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=010S[4]2310bases[top]=xtop=top+1top102530S[4]2310top
5、basetop=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(&
6、S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())InitStack(&S)操作结果：构造一个空栈S。StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INI_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INI_SIZE;returnO
7、K;}DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StatusStackEmpty(SqStackS){if(S.top==S.base)return1;elsereturn0;}StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……ClearStack(&S)初始条件
8、：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane……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.stac
9、ksize;S.stacksize+=STACKINCREMENT;}*S.top=e;S.top++;returnOK;}Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1……StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}3.2栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归例一、数制转换算法
10、基于原理：N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod813481684 168210 2125 202计算顺序输出顺序voidconversion(){
