数据结构C语言描述第章栈和队列.ppt

第3章栈和队列 学习重点 栈和队列的概念及特点栈的顺序存储和链式存储及在不同存储结构上操作的实现算法队列的顺序存储和链式存储及在不同存储结构上操作的实现算法 第3章栈和队列 3 1实例 药店药品柜的管理3 2逻辑结构及特征3 3栈的存储结构3 4队列的存储结构3 5应用举例 3 1实例 药店药品柜的管理 3 1 1问题描述在药店管理过程中 当购进一批药品时 需要按类别将药品放入不同的药品柜中 而在销售药品时 则应该按照药品生产日期先后顺序进行销售 3 1 2问题的分析存放药品时 放入药柜的同一类药品总是从底层开始摆放 在取药时 总是从最上一层开始拿 也就是说药品的摆放顺序和药品取出顺序是相反的 不论是放入药柜的药品 还是销售出的药品 它们都存在着时间上的先后的关系 是一种一一对应的关系 若把放入药柜的药品和销售出的药品看作是两个线性表A1和A2 则A1这种线性表称之为栈 A2这种线性表称为队列 3 2逻辑结构及特征 3 2 1栈的基本概念3 2 2队列的基本概念 3 2 1栈的基本概念 栈 Stack 是仅允许在表的一端进行插入或删除操作的线性表 允许进行插入和删除的一端称为栈顶 另一端称为栈底 栈顶的第一个元素被称为栈顶元素 不含任何数据元素的栈称为空栈 在栈顶进行插入运算 被称为入栈或进栈 在栈顶进行删除运算 被称为出栈或退栈 根据栈进行插入和删除操作的特点 栈又称为后进先出表 图3 1栈的示意图 下面给出常见的栈的操作 Initstack S 初始化操作 Clearstack S 把栈S置为空栈 Push S elem 入栈操作 Pop S w 出栈函数 Gettop S 取栈顶元素函数 Empty S 判断空函数 3 2 2队列的基本概念 队列 Queue 简称队 插入限定在表的一端进行 删除限定在表的另一端进行 允许插入的一端叫做队尾 rear 允许删除的一端称为队头或队首 front 向队列中插入新元素称为进队或入队 从队列中删除元素称为出队或离队 根据插入和删除操作的特点 又称为先进先出线性表 图3 2队列的示意图 下面给出队列的常见的操作 Iniqueue Q 初始化操作 Clearqueue Q 清空队列Q Empty Q 判队列Q是否为空 Enqueue Q elem 入队操作 Dlqueue Q 出队操作 Gethead Q 取队头元素函数 3 3栈的存储结构 3 3 1栈的顺序存储3 3 2栈的链式存储 3 3 1栈的顺序存储 顺序存储实现 用一个一维数组存放栈元素 栈底为数组下标小的那端 又用一个变量指示栈顶位置 栈顶指针 栈顺序存储数据类型定义 structStack Elemtypestack StackMaxSize StackMaxSize确定栈的最大深度inttop 栈顶指针 取值范围为0 StackMaxSize 1 注意 top 1表示栈空 top StackMaxSize 1表示栈满 顺序栈的各种基本操作的实现 操作一 Initstack S 初始化 操作二 Clearstack S 清空栈操作三 Push S elem 进栈操作四 Pop S 出栈操作五 Gettop S 读取栈顶元素操作六 Empty S 判断是否为空栈 操作一 Initstack S 初始化 分析 初始化就是建立一个空栈 栈中不含任何元素 此时栈顶指针top为 1 表示栈空 实现算法 略 操作二 Clearstack S 分析 清空栈 就是把一个栈置成空栈 即不论数组中是否存有数据 只要将栈顶指针top 1 就表示栈空 实现算法 略 操作三 Push S elem 分析 进栈需要判断是否会出现 溢出 若栈不满 则元素进栈时 栈顶指针做加一操作 元素进栈 实现算法 voidPush Stack S Elemtypeelem if S top StackMaxSize 1 printf 栈上溢出 n exit 1 else S top 栈顶指针加1S stack S top elem 将elem赋给新的栈顶 栈满条件 操作四 Pop S 分析 如果顺序栈不为空 此时执行出栈操作 栈顶指针做减一操作 指向原栈顶的后继元素 如果对空栈执行出栈操作 应提示错误信息并终止程序运行 实现算法 voidPop Stack S Elemtype 操作五 Gettop S 分析 栈顶指针直接指向栈顶元素 需要注意空栈的情况 实现算法 略 操作六 Empty S 分析 通过判断栈顶指针来判断栈是否为空 栈顶指针top为 1 表示栈为空 返回1 否则返回0 实现算法 略 结论 顺序栈的入栈和出栈操作 实际上对应的是顺序表的表尾插入和表尾删除操作 所以入栈和出栈操作的时间复杂度都为O 1 空栈不存在栈顶元素 3 3 2栈的链式存储 栈的链式存储通常用单链表实现 此时链表的头指针为栈顶指针 定义为top 链表第一个结点为栈顶结点 当头指针为NULL时 表示当前栈为空栈 链栈示意图 图3 4链栈示意图 链栈的各种基本操作的实现 操作一 Initstack S 初始化 操作二 Clearstack S 清空栈操作三 Push S elem 进栈操作四 Pop S 出栈操作五 Gettop S 读取栈顶元素操作六 Empty S 判断是否为空栈 操作一 Initstack S 初始化分析 链式存储时 空栈即为空单链表 其栈顶指针值为NULL 实现算法 voidInitstack Lnode 注意 空单链表是带表头结点的空单链表 操作二 Clearstack S 分析 清空链栈 要释放链表中的所有结点 实现算法 voidClearstack Lnode 操作三 Push S elem 分析 链栈的入栈操作就是单链表的表头插入 实现算法 略 操作四 Pop S 分析 如果是空栈 提示出错信息并退出 否则 栈顶元素出栈 即删除单链表的第一个结点 实现算法 略 操作五 Gettop S 分析 如果是空栈 提示出错信息并退出 否则 返回单链表的第一个结点的值 实现算法 略 操作六 Empty S 分析 通过判断top的值来判断链栈的状态实现算法 略 3 4队列的存储结构 3 4 1队列的顺序存储3 4 2队列的链式存储 3 4 1队列的顺序存储 顺序存储实现 顺序队由一个一维数组及两个分别指示队头和队尾的指针变量组成 这两个变量分别称为 队头指针 和 队尾指针 顺序存储类型定义为 structQueue ElemTypequeue QueueMaxSize QueueMaxSize表示队列的最大长度intfront rear 注意 当前队列的长度与数组所占用的单元数量无关 由队头指针和队尾指针决定 所以会出现 假溢出 现象 循环队列 将数组的前端和后端连接起来通过语句rear rear 1 QueueMaxSize 使顺序队列的整个数组空间变为首尾相接的队列 当rear指向最后一个存储单元QueueMaxSize 1时 下一个所求的位置自动为数组的开始位置 即下标为0的位置 队头指针的变化方法同队尾指针相同 删除元素时队头指针front front 1 QueueMaxSize 注意 判断队满的条件 rear 1 QueueMaxSize front判断队空的条件 rear frontfront指针不是指向队头元素的位置 而是指向队头元素的前一个位置 队列的操作在顺序存储结构上的实现 操作一 Iniqueue Q 初始化分析 队列为空时 队头指针和队尾指针的值相同 通常将队头指针和队尾指针指向0号单元 实现算法 略 操作二 Clearqueue Q 分析 置队列为空时 只需让队首指针和队尾指针指向同一单元即可 实现算法 略 操作三 Empty Q 分析 判断队列为空的条件是队首指针和队尾指针值相同 若相等返回1 否则返回0 实现算法 略 操作四 Enqueue Q elem 分析 如队列没满 将元素elem插入到队尾 否则提示出错信息并退出程序 实现算法 略 操作五 Dlqueue Q 分析 如队列非空 进行删除操作 否则提示出错 实现算法 略 操作六 Gethead Q 略 3 4 2队列的链式存储 链队常用单链表来表示 队头指针front指向单链表的表头结点 队尾指针rear指向单链表的最后一个结点 链队的插入和删除操作 对应的是单链表的表尾插入和表头删除 链队的类型定义如下 structLinkqueue Lnode front Lnode rear 队列基本操作在链式存储结构上的实现 操作一 Iniqueue Q 初始化 分析 把队首和队尾指针置为空 则队列为空 实现算法 略 操作二 Clearqueue Q 分析 清除链队中所有结点 使之成为空队 实现算法 略 操作三 Empty Q 分析 队首指针和队尾指针指向同一个结点时队为空 实现算法 略 操作四 Enqueue Q elem 分析 将新元素插入到队尾 修改队尾指针 实现算法 略 操作五 Dlqueue Q 分析 删除队首元素 如果队中只有一个元素 队尾指针也要修改 实现算法 略 操作六 Gethead Q 分析 读取队首元素 不修改指针 实现算法 略 3 5应用举例 3 5 1表达式中的括号匹配的检验3 5 2递归3 5 3栈和队列的各种操作的综合实践 3 5 1表达式中括号匹配的检验 分析 检验时 应从左向右扫描左括号 找离它最近的没有匹配的同一类型的右括号 在扫描过程中 可能会连续出现几个左括号 这时应先从后扫描的左括号开始进行匹配 再对前面的括号进行匹配 也就是说后扫描的括号需要先进行匹配 这与栈的特点一致 所以可以用栈来实现括号匹配的检验 实现方法 当扫描到一个花 中 圆的左括号时 令其进栈 当扫描到一个花 中 圆的右括号时 则检查栈顶是否为相匹配的左括号 若是则作退栈处理 如果不是则表明括号不匹配 当扫描到表达式结尾时 栈为空表明括号是配对的 否则表明式中肯定存在不配对的括号 3 5 2递归 递归 子程序或函数重复调用自己 并传入不同的变量来执行的一种程序设计方法 可以直接调用自己或间接地调用自己 递归的执行过程 每当一个函数在运行期间调用另一个函数时 执行函数要将所有的实参 返回地址等信息进行保存 当有多个函数构成嵌套调用时 按照 后调用先返回 的原则 即每次进行函数调用时 都把相应的值压入栈 每次调用结束时 都按照当前栈顶的返回地址返回到指定位置 并且自动作一次退栈操作 3 5 3栈和队列的综合实践 栈的应用举例 数制转换问题描述 十进制整数转换为2至9之间的任一进制数输出 问题分析 转换方法为逐次除基数r取余法 以十进制整数x除以基数r 得到的余数是r进制数y的最低位 接着以r的商作为被除数 用它除以r得到的整余数是y的次最低位 依次类推 直到商为0时得到的整余数是y的最高位 这m 1位余数ym y1y0 就得到转换后的结果 先得到的余数需要最后输出 最后得到的余数需要最先输出 所以在转换的时候 使用一个栈来保存得到的余数 直到商为0时 再将栈中的结果依次出栈 实现算法 略 队列的应用举例 奇 偶数配对输出问题描述 用两个链队q1和q2 分别存储由计算机随机产生的20个100以内的奇数和偶数 然后每行输出q1和q2中的一个值 即奇数和偶数配对输出 直到任一队列为空时止 问题分析 计算机产生的随机数 如果是奇数 用q1存放 如果是偶数