1、 程序设计数据结构 第 1 页栈和队列基本概念及应用文档编号完 成 人 张 昱完成时间修改时间 第 1 页目 录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 队列与栈的应用 .
2、83.5.1 离散事件模拟 .8程序设计数据结构 第 2 页栈和队列基本概念及应用文档编号完 成 人 张 昱完成时间修改时间 第 2 页第 3 章 栈和队列3.1 栈的基本概念3.1.1 栈的抽象数据类型定义1、栈的逻辑特征1） 限定在表尾进行插入或删除操作的线性表；2） 栈顶表尾端；栈底表头端3） 后进先出的线性表2、抽象数据类型的定义ADT Stack数据对象：D=a i |aiElemSet, i=1,2,n, n0数据关系：R=R1,R1=|ai-1,aiD, i=2,3,n 基本操作：InitStack( /* 栈底指针 */ElemType *top; /* 栈顶指针(栈顶元素的下
3、一个位置) */int stacksize; /* 当前分配的存储容量 */SqStack;1） 和顺序表一样采用增量式的空间分配；2） 操作和栈顶相关：插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置；删除操作（出栈）：删除栈顶元素；取元素操作：取栈顶元素的值。各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在 O(1)时间内能获取操作位置，故可设置专门的栈顶指针 top。3） 约定：top 指向栈顶元素的下一个位置 （便于表示空栈） 。4） 栈顶的初始化：S.top = S.base (在上述 3)约定下的空栈形式)，5） 栈空：S.base = S.top，栈满：S.top
4、 - S.base = S.stacksize6） 入栈：*S.top + = e，出栈：e = *-S.top注意：4), 5), 6)步受 3)制约。约定不同，相应的判定和处理也不一样。如假设 top 就指向栈顶元素，此时 4),5),6)如何？2、取栈顶元素 GetTop_Sq1) 算法设计参数：顺序栈 S、取得的栈顶元素e = *( S.top -1);return OK;3、入栈操作 Push_Sq1) 算法设计参数：顺序栈 算法 2Status Push_Sq( SqStack if ( S.base = NULL ) exit(OVERFLOW); S.top = S.base
5、+ S.stacksize; S.stacksize += STACKINCREMENT;*S.top+ = e;return OK; 2) 算法分析时间 T(n) = O(1)4、出栈操作 Pop_Sq1) 算法设计参数：顺序栈e = *( -S.top); /* 注意与 GetTop( )的区别 */return OK;2) 算法分析时间 T(n) = O(1)3.1.3 链栈与链表类似，只是链表的头指针即为栈顶指针。因其操作均在栈顶进行，故可以不引入头结点。思考：在链栈下的入栈、出栈以及取栈顶元素的操作的算法如何写？3.2 栈的应用3.2.1 数制转换：将十进制数 N 转换成其他 d 进
6、制数算法思想：N = ( N div d )d + N mod d1）将 N%d 的结果保存，2）N=N/d ，3）若 N=0 结束，否则继续 1） 。保存的余数从先到后依次表示转换后的 d 进制数的低位到高位，而输出是由高位到低位的，因此必须定义先进后出的线性表栈来保存；当全部的余数求出后，通过逐个出栈输出 d 进制数。3.2.2 括号匹配的检验算法思想：从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号匹配，则继续扫描；否则说明不匹配，结束。在上述操作中，若栈为空，或扫描结束后栈不为空，均说明不匹配。3.2.3 行输入处理程序处理规则：遇#退一格；遇退一行算法思想：引入栈
7、，保存终端输入的一行字符（逐行处理） ；程序设计数据结构 第 5 页栈和队列基本概念及应用文档编号完 成 人 张 昱完成时间修改时间 第 5 页遇#退一格出栈一次遇 退一行清栈步骤： 1）初始化栈 S2）读入字符 ch3）ch!=EOF3.1) ch!=EOF B. 从各方块出发已探索的方向，注意不能重复（可约定按东、南、西、北的方向顺次探索） ；C. 从当前方块无路可走时，将已走路径回退一个方块，继续探索其他未走的方向栈存储已走的通道块3.2.5 表达式求值1、问题描述只包含+, -, *, / 四个双目运算符，且算符本身不具有二义性；三个运算规则运算符优先关系（考虑算符本身的优先级和结合性
8、） ；只有 (=)，#=#；假设输入的是一个合法的表达式。2、算法思想引入 OPTR 和 OPND 两个栈初始：OPTR 有一个元素# ，OPND 为空读入一字符 cc=#： return(GetTop(OPND)c 非运算符：Push(OPND,c)c 运算符：t=GetTop(OPTR) ，比较 t 和 c 的优先关系tc：Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a);x=Operate(a, theta, b); Push(OPND, x);继续读入字符处理。 3.3 栈与递归的实现1、递归定义 开始结束形成了环程序设计数据结构 第 6 页栈和
9、队列基本概念及应用文档编号完 成 人 张 昱完成时间修改时间 第 6 页直接或间接地调用自身的函数，称为递归函数。如右图所示，递归表现为：在该函数的所有可能执行路径中，存在一条由于调用自身或其它函数所导致的环路路径；为确保函数最终在有限的时间内执行完毕，必须在环路中存在一个出口，即当某种条件成立时，不必执行环路，而直接执行一条通向结束的非环路线。2、递归应用1) 递归应用类型递归定义的数学问题具有递归特性的数据结构，其操作可以递归地表示其它一些问题2) 递归应用的特点对于一个问题，当问题规模很大时，往往难于直接求解，此时：将大问题分解成若干小问题考虑如何利用这些小问题的解构成大问题的解避免陷入
10、考虑如何求解小问题这种分解、合成的方法就是递归求解中的递归方法；另外，递归应用要注意避免陷入死循环，递归必须有出口，即要确立递归的结束条件，给出此时的直接求解方法。3) 递归应用举例Hanoi 塔问题3、递归的实现1) 系统的处理(1) 调用前现场保护，被调用函数的局部变量的空间分配，控制转移至被调用的函数入口。(2) 调用后保存计算结果，释放被调函数的数据区，控制转移回调用处。2) 实现栈“后调用先返回” 。系统利用递归工作栈记录各层调用的现场信息。3.4 队列的基本概念3.4.1 队列的抽象数据类型定义1、队列的逻辑特征1) 先进先出的线性表2) 队头：允许删除的一端；队尾：允许插入的一端
11、3) 应用举例：操作系统的作业排队2、队列的抽象数据类型定义 ADT QueueADT Queue数据对象：D=a i |aiElemSet, i=1,2,n, n0数据关系：R=R1,R1=|ai-1,aiD, i=2,3,n 基本操作：InitQueue(struct QNode *next;QNode, *QueuePtr;typedef struct QueuePtr front; /* 队头指针，指向头元素 */QueuePtr rear; /* 队尾指针，指向队尾元素 */LinkQueue;1）引入队头指针、队尾指针：在 O(1)时间内找到操作结点2）引入头结点：队尾插入时，使队
12、空和队不空的结点表示一致3）队空的判断：头、尾指针均指向头结点4）队满的判断转变成对申请空间是否成功的判断。2、类型说明程序设计数据结构 第 8 页栈和队列基本概念及应用文档编号完 成 人 张 昱完成时间修改时间 第 8 页操作实现：初始化、入队、出队注意：队空的判断、入队、出队依赖于队列的表示及其约定。进一步考虑：若无头结点，此时队列的初始化、入队、队空的条件、出队等如何表示与实现？3.4.3 循环队列1、循环队列的定义采用顺序表存储，约定 front 指向队列头元素，rear 指向队尾元素的下一位置。#define MAXQSIZE 100 /* 最大队列长度 */typedef stru
13、ctElemType *base; /* 存储空间 */int front; /* 头指针，指向队列的头元素 */int rear; /* 尾指针，指向队尾元素的下一个位置 */SqQueue; /* 非增量式的空间分配 */2、操作实现1）空队：Q.front=Q.rear=0;2）入队：判断是否队满，非队满时，Q.rear 位置放新插入的元素，Q.rear+3）出队：判断是否队空，非队空时，Q.front 位置为待删除的元素， Q.front+4）队空条件：Q.front = Q.rear5）队满条件：Q.rear = MAXQSIZE-1问题：存在假上溢(由于出队操作，队列空间的上部可能
14、存在空闲空间)3、假上溢的解决将队列假想为首尾相接的环，即循环队列。1）入队：，Q.rear = ( Q.rear+1)%MAXQSIZE2）出队：，Q.front = ( Q.front+1)%MAXQSIZE3）队空条件：Q.front = Q.rear，由于出队 Q.front 追上了 Q.rear4）队满条件：Q.front = Q.rear，由于入队 Q.rear 追上了 Q.front问题：队空和队满的判断条件一样4、如何区分队空和队满1） 设标志位：不足在于需要额外对标志位的判断及维护2） 在队列的结构中引入长度成员，在初始化队列、入队、出队操作中维护这个成员。3） 少用一个元素空间，即队满的条件如下(Q.rear+1)% MAXQSIZE = Q.front进一步思考：1）对比 4 中所列的 3 种方法在队列操作中处理的不同。2）若循环队列数组的下标起始为-3, 1 或 3 时，如何判断队空、队满，如何实现入队、出队？3.5 队列与栈的应用3.5.1 离散事件模拟
