资源描述：
《程序设计教案 程序设计——数据结构》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第8页基本概念及应用栈和队列程序设计——数据结构目录3.1栈的基本概念13.1.1栈的抽象数据类型定义13.1.2顺序栈23.1.3链栈33.2栈的应用33.2.1数制转换：将十进制数N转换成其他d进制数33.2.2括号匹配的检验43.2.3行输入处理程序43.2.4迷宫求解43.2.5表达式求值43.3栈与递归的实现53.4队列的基本概念63.4.1队列的抽象数据类型定义63.4.2链队列73.4.3循环队列73.5队列与栈的应用83.5.1离散事件模拟8完成时间张昱完成人文档编号第8页修改时间第8页基本概念及应用栈和队列程序设计——数据结构第3章栈和队列3
2、.1栈的基本概念3.1.1栈的抽象数据类型定义1、栈的逻辑特征1）限定在表尾进行插入或删除操作的线性表；2）栈顶——表尾端；栈底——表头端3）后进先出的线性表2、抽象数据类型的定义ADTStack{数据对象：D={ai
3、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R={R1},R1={
4、ai-1,ai∈D,i=2,3,…,n}基本操作：InitStack(&S)操作结果：构造一个空的栈SDestroyStack(&S)初始条件：栈S已存在操作结果：销毁栈SClearStack(&S)初始条件：栈S已存在操作结果：将栈S重置为空
5、栈StackEmpty(S)初始条件：栈S已存在操作结果：若S为空栈，则返回TRUE，否则返回FALSEStackLength(S)初始条件：栈S已存在操作结果：返回栈S中数据元素的个数GetTop(S,&e)初始条件：栈S已存在且非空操作结果：用e返回S中栈顶元素Push(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(&S,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值StackTraverse(S,visit())初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit(
6、)。一旦visit()失败，则操作失败}ADTStack思考：栈的取元素、插入、删除操作与线性表的相应操作有何区别，为什么？3.1.2顺序栈完成时间张昱完成人文档编号第8页修改时间第8页基本概念及应用栈和队列程序设计——数据结构1、增量式顺序栈的定义#defineSTACK_INIT_SIZE100/*存储空间的初始分配量*/#defineSTACKINCREMENT10/*存储空间的分配增量*/typedefstruct{ElemType*base;/*栈底指针*/ElemType*top;/*栈顶指针(栈顶元素的下一个位置)*/intstacksize;/
7、*当前分配的存储容量*/}SqStack;1）和顺序表一样采用增量式的空间分配；2）操作和栈顶相关：插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置；删除操作（出栈）：删除栈顶元素；取元素操作：取栈顶元素的值。各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取操作位置，故可设置专门的栈顶指针top。3）约定：top指向栈顶元素的下一个位置（便于表示空栈）。4）栈顶的初始化：S.top=S.base(在上述3)约定下的空栈形式)，5）栈空：S.base==S.top，栈满：S.top-S.base>=S.stacksize6）入
8、栈：*S.top++=e，出栈：e=*--S.top注意：4),5),6)步受3)制约。约定不同，相应的判定和处理也不一样。如假设top就指向栈顶元素，此时4),5),6)如何？2、取栈顶元素GetTop_Sq1)算法设计参数：顺序栈S、取得的栈顶元素&e分析：由于top指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是top-1；栈非空时，此操作有效。算法1StatusGetTop_Sq(SqStackS,ElemType&e){/*判断栈是否为空*/if(S.base==S.top)returnERROR;e=*(S.top-1);returnOK;}
9、3、入栈操作Push_Sq1)算法设计参数：顺序栈&S、插入元素e分析：插入位置为栈顶元素的下一个，无须判断位置的合法性；上溢即栈满的条件需要判断，由于是增量式分配，故栈满时需要重新申请空间;算法2StatusPush_Sq(SqStack&S,ElemTypee){/*判断栈是否为满*/if(S.top–S.base>=S.stacksize){/*栈满，追加空间*/S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(S.base==NULL)e
10、xit(OVERFLOW);完成时间张
