资源描述：
《数据结构第三章栈和队列概况ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列3.1栈3.2桟的应用举例3.3栈与递归的实现3.4队列栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈的修改是按照后进先出的原则进行的，栈又称为后进先出的线性表。栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈,栈的删除操作通常称为出栈。3.1.1栈的定义a1an-1…栈顶栈底进栈出栈栈的示意图a0例3.1设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是
2、。(A)A,B,C,D(B)D,C,B,A(C)A,C,D,B(D)D,A,B,C例3.2已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值。(A)i(B)n-i(C)n-i+1(D)不确定3.1.2栈的类型定义ADTStack{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStackInitStack(&S)DestroyStac
5、k(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;3.1.3几个基本操作的实现StatusInitStack(SqSt
6、ack&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;}StatusDestroyStack(SqStack&S){/*销毁栈S，S不再存在*/free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;returnOK;}Status
7、ClearStack(SqStackS){/*把S置为空栈*/S.top=S.base;returnOK;}StatusStackEmpty(SqStackS){/*若栈S为空栈，则返回TRUE，否则返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;}intStackLength(SqStackS){/*返回S的元素个数，即栈的长度*/returnS.top-S.base;}StatusGetTop(SqStackS,SElemType&e){if(S.top>S.base){e
8、=*(S.top-1);returnOK;}elsereturnERROR;}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+=STACK
9、INCREMENT;}*S.top++=e;returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，//用e返回其值，并返回OK；//否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}StatusStackTraverse(SqStackS){SElemType*p;p=S.base;while(p10、2栈的应用举例例一、数制转换例四、括号匹配的检验例五、行编辑程序问题例二、表达式求值例六、迷宫求解例三、判断字符串是否对称例一、数制转换十进制数Nd进制数的原理：N＝(Ndivd)*d+Nmodd例如:(1348)10(
