数据结构域算法设计--数据结构-栈与队列 教案

《数据结构域算法设计--数据结构-栈与队列 教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ThanksWangqiongofZhongbeicollegeattachingtoNanjing Normal University第三章栈与队列栈与队列：限定操作的线性表。第一节栈一、逻辑结构1、栈的定义限定只能在表的一端进行插入、删除的线性表。　　栈顶top，栈底bottom。　　后进先出LIFO表(LastInFirstOut)实例：“进制数转换”、“表达式求值”、“函数调用关系”、“括号匹配问题”、“汉诺塔问题”、“迷宫问题”……2、基本操作进栈Push/出栈Pop取栈顶元素GetTop判别栈空StackEmpty/栈满StackFull3、栈的应用背景许多问题的求解

2、分为若干步骤，而当前步骤的解答，是建立在后继步骤的解答基础上的。=》问题分解的步骤和求解的步骤次序恰好相反。3-9ThanksWangqiongofZhongbeicollegeattachingtoNanjing Normal University二、顺序存储结构动态顺序存储结构：存储空间随栈的大小而变化。#defineSTACK_INIT_SIZE100//初始化时分配的空间typedefstruct//定义栈类型{ElemType*base,*top;//栈底、栈顶指针intstacksize;//栈的存储空间大小}SqStack;SqStackS;//定义一个栈结构1、初

3、始化栈StatusSqStack_Init(SqStack&S){S.base=malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)return(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);}栈空：S.top==S.base栈满：S.top==S.base+S.stacksize2、进栈StatusSqStack_Push(SqStack&S,ElemTypee){if(S.top==S.base+S.stacksize)return(OVERFLO

4、W);S.top=e;S.top++;return(OK);}3、出栈算法StatusSqStack_Pop(SqStack&S,ElemType&e){if(S.top==S.base)return(UNDERFLOW);S.top--;e=S.top;3-9ThanksWangqiongofZhongbeicollegeattachingtoNanjing Normal Universityreturn(OK);}缺点：空间浪费思考：二栈合用同一顺序空间？#definemaxsize=100intstack[maxsize],top0=0,top1=maxsize-1;int

5、push0(inte){if(top0>top1)return(0);stack[top0]=e;top0++;return(1);}intpush1(inte){if(top0>top1)return(0);stack[top1]=e;top1--;return(1);}intpop0(int*e){if(top0==0)return(0);top0--;*e=stack[top0];return(1);}intpop1(int*e){if(top0==0)return(0);top0++;*e=stack[top1];return(1);}三、链栈typedefstructl

6、inknode//栈中结点类型{ElemTypedata;structlinknode*link;}LinkNode;typedefstruct//定义栈类型{LinkNode*top;//栈顶指针intstacksize;//栈的大小(可选)}LinkStack;3-9ThanksWangqiongofZhongbeicollegeattachingtoNanjing Normal UniversityLinkStackS;初始化:S.top==NULL;S.stacksize==0栈空：S.top==NULL栈满：系统内存不够1、进栈StatusLinkStack_Push(

7、LinkStack&S，ElemTypee){LinkNode*p;p=(LinkNode*)malloc(sizeof(LinkNode));if(p==NULL)return(OVERFLOW);//上溢p->data=e;p->link=S.top;S.top=p;return(OK);}2、出栈StatusLinkStack_Pop(LinkStack&S,ElemType&e){LinkNode*p;if(S.top==NULL)return(UNDERFLOW);p=