数据结构资料ppt课件.ppt

1 第3章栈和队列 2 通常称 栈和队列是限定插入和删除只能在表的 端点 进行的线性表 线性表栈队列Insert L i x Insert S n 1 x Insert Q n 1 x 1 i n 1Delete L i Delete S n Delete Q 1 1 i n 栈和队列是两种常用的数据类型 3 3 1栈 3 1 1抽象数据类型栈的定义3 1 2栈的表示和实现 3 2栈的应用举例 3 4队列 3 4 1抽象数据类型队列的定义3 4 2链队列 队列的链式表示和实现3 3 3循环队列 队列的顺序表示和实现 4 3 1栈3 1 1抽象数据类型栈的定义 1 栈 Stack 的定义栈是限定仅在表尾进行插入和删除操作的线性表 术语栈底 bottom 栈的表头栈顶 top 栈的表尾空栈 没有元素的栈入栈 push 向栈顶压入元素出栈 pop 从栈顶弹出元素 栈的特点栈的修改是按后进先出的原则进行的 因此 栈称为后进先出的线性表 LIFO 5 3 1 1抽象数据类型栈的定义 2 栈的运算演示 1 A B C D四个元素依次进入一个栈 再依次出栈 得到一个输出序列DCBA DCBA 6 3 1 1抽象数据类型栈的定义 2 栈的运算演示 1 A B C D四个元素依次进入一个栈 再依次出栈 得到一个输出序列DCBA 2 能否由入栈序列A B C D E得到出栈序列CBDAE ABCDE 操作序列 出栈序列 元素A入栈 A A 元素B入栈 B B 元素C入栈 C C 7 3 1 1抽象数据类型栈的定义 2 栈的运算演示 1 A B C D四个元素依次进入一个栈 再依次出栈 得到一个输出序列DCBA 2 能否由入栈序列A B C D E得到出栈序列CBDAE DE 操作序列 出栈序列 元素A入栈 A 元素B入栈 B 元素C入栈 元素C出栈 C C 元素B出栈 B 8 3 1 1抽象数据类型栈的定义 2 栈的运算演示 1 A B C D四个元素依次进入一个栈 再依次出栈 得到一个输出序列DCBA 2 能否由入栈序列A B C D E得到出栈序列CBDAE DE 操作序列 出栈序列 元素A入栈 A 元素B入栈 元素C入栈 元素C出栈 C 元素B出栈 B 元素D入栈 D D 元素D出栈 D 元素A出栈 A 9 3 1 1抽象数据类型栈的定义 2 栈的运算演示 1 A B C D四个元素依次进入一个栈 再依次出栈 得到一个输出序列DCBA 2 能否由入栈序列A B C D E得到出栈序列CBDAE E 操作序列 出栈序列 元素A入栈 元素B入栈 元素C入栈 元素C出栈 C 元素B出栈 B 元素D入栈 元素D出栈 D 元素A出栈 A 元素E入栈 E E 元素E出栈 E 10 请大家思考如下问题 结合书上图3 1 b 铁路调度站示意图 如果有编号分别为1 2 3 4的四列火车顺序开过来 如果你是调度 有多少种出站顺序 分别是什么 14种出站顺序1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321推广到一般情况 11 例1 一个栈的输入序列是12345 若在入栈的过程中允许出栈 则栈的输出序列43512可能实现吗 12345的输出呢 43512不可能实现 主要是其中的12顺序不能实现 12345的输出可以实现 只需压入一个立即弹出一个即可 435612中到了12顺序不能实现 135426可以实现 例2 如果一个栈的输入序列为123456 能否得到435612和135426的出栈序列 答 答 12 例3 严题集3 1 一个栈的输入序列为123 若在入栈的过程中允许出栈 则可能得到的出栈序列是什么 答 可以通过穷举所有可能性来求解 1入1出 2入2出 3入3出 即123 1入1出 2 3入3 2出 即132 1 2入 2出 3入3出 即231 1 2入 2 1出 3入3出 即213 1 2 3入 3 2 1出 即321 合计有5种可能性 13 3 1 1抽象数据类型栈的定义3 栈的抽象数据类型定义 ADTStack 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定an端为栈顶 a1端为栈底 基本操作 ADTStack 14 InitStack S DestroyStack S ClearStack S StackEmpty S StackLength S GetTop S e Push S e Pop S e StackTraverse S visit 15 InitStack S 操作结果 构造一个空栈S DestroyStack S 初始条件 栈S已存在 操作结果 栈S被销毁 16 StackEmpty S 初始条件 栈S已存在 操作结果 若栈S为空栈 则返回TRUE 否则FALE 17 StackLength S 初始条件 栈S已存在 操作结果 返回S的元素个数 即栈的长度 18 GetTop S e 初始条件 栈S已存在且非空 操作结果 用e返回S的栈顶元素 a1 a2 an 19 ClearStack S 初始条件 栈S已存在 操作结果 将S清为空栈 20 Push S e 初始条件 栈S已存在 操作结果 插入元素e为新的栈顶元素 a1 a2 an e 21 Pop S e 初始条件 栈S已存在且非空 操作结果 删除S的栈顶元素 并用e返回其值 a1 a2 an an 1 22 3 1 2栈的表示和实现 顺序栈 链栈 23 顺序栈 栈的顺序存储结构 顺序栈是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 同时附设指针top指示栈顶元素在顺序栈中的位置 栈 栈的顺序存储映象 24 顺序栈的基本操作 栈的顺序存储映象 顺序栈基本操作的实现StackEmpty top basePush e top ePop e e topGetTop e top 1 思考 为何不用top指向栈顶元素 顺序栈 栈的顺序存储结构 25 栈的顺序存储表示 defineSTACK INIT SIZE100 defineSTACKINCREMENT10 typedefstruct SElemType base SElemType top intstacksize SqStack 顺序栈的C语言描述 26 StatusInitStack SqStack 27 StatusGetTop SqStackS SElemType 28 StatusPush SqStack 29 StatusPop SqStack 30 栈顶指针 链栈 a1 an 注意 链栈中指针的方向 an 1 栈底元素 31 3 2栈的应用举例 3 2 1数制转换 3 2 2括号匹配的检验 3 2 3行编辑程序 3 2 4迷宫求解 3 2 5表达式求值 32 3 2 1数制转换算法基于原理 除d取余N Ndivd d Nmodd 33 例如 1348 10 2504 8 其运算过程如下 NNdiv8Nmod8134816841682102125202 计算顺序 输出顺序 34 voidconversion InitStack S scanf d N while N Push S N 8 N N 8 while StackEmpty S Pop S e printf d e conversion 35 3 2 2括号匹配的检验假设在表达式中 或 等为正确的格式 或 或 均为不正确的格式 则检验括号是否匹配的方法可用 期待的急迫程度 这个概念来描述 36 分析可能出现的不匹配的情况 到来的右括弧不是所 期待 的 例如 考虑下列括号序列 12345678 到来的是 不速之客 直到结束 也没有到来所 期待 的括弧 37 算法的设计思想 1 凡出现左括弧 则进栈 2 凡出现右括弧 首先检查栈是否空若栈空 则表明该 右括弧 多余否则和栈顶元素比较 若相匹配 则 左括弧出栈 否则表明不匹配 3 表达式检验结束时 若栈空 则表明表达式中匹配正确否则表明 左括弧 有余 38 Statusmatching string 39 3 2 3行编辑程序 如何实现 每接受一个字符即存入存储器 并不恰当 40 设立一个输入缓冲区 用以接受用户输入的一行字符 然后逐行存入用户数据区 并假设 为退格符 为退行符 在用户输入一行的过程中 允许用户输入出差错 并在发现有误时可以及时更正 合理的作法是 41 假设从终端接受了这样两行字符 whli ilr e s s outcha putchar s 则实际有效的是下列两行 while s putchar s 42 相应算法的基本思想 可设这个输入缓冲区为一个栈结构 每当从终端接受一个字符之后先作如下判别 1 非 和 则压入栈 2 删除栈顶元素 3 清空栈 VoidLineEdit InitStack S ch getchar DestroyStack S LineEdit 43 while ch EOF 从终端接收下一个字符 ClearStack S 重置S为空栈if ch EOF ch getchar while ch EOF EOF为全文结束符 将从栈底到栈顶的字符传送至调用过程的数据区 44 3 2 4迷宫求解 通常用的是 穷举求解 的方法 45 求迷宫路径算法的基本思想是 若当前位置 可通 则纳入路径 继续前进 若当前位置 不可通 则后退 换方向继续探索 若四周 均无通路 则将当前位置从路径中删除出去 46 设定当前位置的初值为入口位置 do 若当前位置可通 则 将当前位置插入栈顶 若该位置是出口位置 则算法结束 否则切换当前位置的东邻方块为新的当前位置 否则 while 栈不空 求迷宫中一条从入口到出口的路径的算法 47 若栈不空且栈顶位置尚有其他方向未被探索 则设定新的当前位置为 沿顺时针方向旋转找到的栈顶位置的下一相邻块 若栈不空但栈顶位置的四周均不可通 则 删去栈顶位置 从路径中删去该通道块若栈不空 则重新测试新的栈顶位置 直至找到一个可通的相邻块或出栈至栈空 若栈空 则表明迷宫没有通路 48 typedefstruct intord 在路径上的序号inti j 坐标intdir 当前位置下一方向 SElemType ordijdir1 1 1 12 1 2 23 2 2 24 3 2 15 3 3 16 3 4 47 2 4 18 2 5 19 2 6 410 1 6 311 1 5 3 1 4 X 3 1 214 4 1 2 5 3 3 16 3 4 47 2 4 18 2 5 19 2 6 410 1 6 311 1 5 312 1 4 X 4 3 2 3 49 一 算符优先法 1 问题的提出2 正确解释表达式是解决这个问题的关键 如何给计算机解释表达式 例如 4 2 3 10 53 正确解释的实质在于算符的优先级别4 表达式包括操作数 operand 运算符 operator 和界限符 delimiter 5 任意两个相继出现算符 1和 2的关系 3 2 5表达式求值 50 书上表3 1所示优先关系说明 1 算符相同 左遇到右时 2 由规则三 运算符遇到 和 3 是表达式的结束符 左边也虚设一个 4 表示当左右括号相遇时 括号内运算已经完成 5 表示 6 和 相遇 或 和 相遇 语法错 51 二 算符优先法的实现 注 算法中两个函数 Precede 1 2 和Operate a theta b 算法思想设定两栈 操作符栈OPTR 操作数栈OPND栈初始化 设操作数栈OPND为空 操作符栈OPTR的栈底元素为表达式起始符 依次读入字符 是操作数则入OPND栈 是操作符则要判断 if操作符栈顶元素 压入OPTR栈 52 表达式求值示意图 5 6 1 2 4 5 读入表达式过程 6 1 2 4 19 1 2 3 6 3 18 5 18 23 23 4 19 6 1 2 3 18 4 5 23 19 表达式求值 53 表达式求值示例 例3 1 54 StatusEvaluateExpression OperandType EvaluateExpression 此函数在哪里 55 作业 十一后交 1简述下列术语 数据 数据元素 数据对象 数据结构 存储结构 数据类型和抽象数据类型 2描述以下三个概念的区别 头指针 头结点 首结点 3试写一算法 实现顺序表的就地逆置 即利用原表的存储空间 a1 a2 an 将线性表逆置为 an a2 a1 4编写实现将10进制树转化为d进制的C语言程序 56 3 3队列 Queue 定义队列是只允许在一端删除 在另一端插入的顺序表 允许删除的一端叫做队头 front 允许插入的一端叫做队尾 rear 特性先进先出 FIFO FirstInFirstOut 常用操作初始化空队 入队 出队 判断队空 判断队满 取队头 a0a1a2an 1 front rear 队头 入队 出队 队尾 队列的抽象数据类型定义见教材队列的存储结构为链队或顺序队 常用循环顺序队 插入元素称为入队 删除元素称为出队 57 定义 3 3 1队列的结构特点和操作 与同线性表相同 仍为一对一关系 顺序队或链队 以循环顺序队更常见 只能在队首和队尾运算 且访问结点时依照先进先出 FIFO 的原则 关键是掌握入队和出队操作 具体实现依顺序队或链队的不同而不同 基本操作有入队或出队 建空队列 判队空或队满等操作 只能在表的一端进行插入运算 在表的另一端进行删除运算的线性表 头删尾插 例如 队列Q a1 a2 a3 an 1 an 队头 队尾 58 队列的进队和出队原则 进队时队尾指针先进一rear rear 1 再将新元素按rear指示位置加入 出队时队头指针先进一front front 1 再将下标为front的元素取出 队满时再进队将溢出出错 队空时再出队将队空处理 解决办法之一 将队列元素存放数组首尾相接 形成循环 环形 队列 59 队列的进队和出队示例 front rear 空队列 front rear A进队 A front rear B进队 AB front rear C D进队 ABCD front rear A退队 BCD front rear B退队 CD front rear E F G进队 CDEFG CDEFG front rear H进队 溢出 60 队列的基本操作 InitQueue Q 操作结果 构造一个空队列Q DestroyQueue Q 初始条件 队列Q已存在 操作结果 队列Q被销毁 不再存在 QueueEmpty Q 初始条件 队列Q已存在 操作结果 若Q为空队列 则返回TRUE 否则返回FALSE QueueLength Q 初始条件 队列Q已存在 操作结果 返回Q的元素个数 即队列的长度 ClearQueue Q 初始条件 队列Q已存在 操作结果 将Q清为空队列 61 a1 a2 an GetHead Q e 初始条件 Q为非空队列 操作结果 用e返回Q的队头元素 EnQueue Q e 初始条件 队列Q已存在 操作结果 插入元素e为Q的新的队尾元素 a1 a2 an e DeQueue Q e 初始条件 Q为非空队列 操作结果 删除Q的队头元素 并用e返回其值 a1 a2 an 62 链队列 基本操作的实现无队满问题 除非分配不出内存 空间可扩充引入头结点 一定需要吗 a1 a2 an Q front Q rear 链式栈无栈满问题 空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作 队头在链头 队尾在链尾 链式队列在进队时无队满问题 但有队空问题 队空条件为 front NULL 3 3 2队列的表示和操作实现 63 Q front Q rear 空队列 Q front Q rear Q front Q rear Q front Q rear X Y X Y X 元素X入队列 元素Y入队列 元素X出队列 64 链队列讨论 讨论 空队列的特征 队尾 队首 front rear p 怎样实现入队和出队操作 入队 尾部插入 rear next S rear S 出队 头部删除 front next p next 队列会满吗 front rear 一般不会 因为删除时有free动作 除非内存不足 65 TypedefLinkListQuencePtr typedefstruct 链队列类型QueuePtrfront 队头指针QueuePtrrear 队尾指针 LinkQueue 空队列 队列 链队列的表示与实现 66 voidInitQueue L LinkQueue voidDestroyQuence L LinkQueue voidEnQueue L LinkQueue 67 boolDeQueue L LinkQueue if Q rear p Q rear Q front null q q rear x null q front p 存储池 68 循环队列队列的顺序存储约定与类型定义 Q front和Q rear的含义删除 避免大量的移动 头指针增1问题 假上溢 首尾相接的环 钟 队头Q front 入队 出队 a1 a2 a3 an Q rear 队尾 2 循环队列 69 基本操作的实现初始化空队 Q front Q rear 0 入队 判断是否队满 非队满时 Q rear位置放新插入的元素 Q rear 出队 判断是否队空 非队空时 Q front位置为待删除的元素 Q front 队空条件 Q front Q rear队满条件 Q rear MAXQSIZE问题 假上溢 Q front 入队 出队 a1 a2 a3 an Q rear 队尾 循环队列 70 实现 用一维数组实现sq M J1 J2 J3 设两个指针front rear 约定 rear指示队尾元素 front指示队头元素前一位置初值front rear 1 空队列条件 front rear入队列 sq rear x 出队列 x sq front 循环队列 71 当J6入队后 队尾指针Q rear越界 不可能再插入新的队尾元素 但是另一方面 队列的实际可用空间并未占满 一个巧妙的办法是 将顺序队列设想为首尾相连的环状空间 当Q rear值超出队列空间的最大位置时 令Q rear 0 使队列空间能 循环 使用 这种循环使用空间的队列称为循环队列 循环队列图示 72 存在问题 设数组维数为M 则 队首固定 每次出队剩余元素向下移动 浪费时间解决方案 循环队列基本思想 把队列设想成环形 让sq 0 接在sq M 1 之后 若rear 1 M 则令rear 0 实现 利用 模 运算入队 rear rear 1 M sq rear x 出队 front front 1 M x sq front 队满 队空判定条件 循环队列 73 假上溢的解决办法把顺序队列看成首尾相接的环 钟表 循环队列基本操作的实现入队 Q rear Q rear 1 MAXQSIZE出队 Q front Q front 1 MAXQSIZE队空条件 Q front Q rear由于出队Q front追上了Q rear队满条件 Q front Q rear由于入队Q rear追上了Q front问题 队空和队满的判断条件一样 循环队列 74 队空 front rear队满 front rear 解决方案 1 另外设一个标志以区别队空 队满2 少用一个元素空间 队空 front rear队满 rear 1 M front 新问题 在循环队列中 空队特征是front rear 队满时也会有front rear 判决条件将出现二义性 解决方案有三 加设标志位 让删除动作使其为1 插入动作使其为0 则可识别当前front rear 使用一个计数器记录队列中元素个数 即队列长度 人为浪费一个单元 令队满特征为front rear 1 N 75 循环队列讨论 队列会满吗 很可能会 因为数组前端空间无法释放 因此数组应当有长度限制 空队列的特征 约定 front rear 入队 尾部插入 v rear e rear 出队 头部删除 x v front front 讨论 假溢出 有缺陷 怎样实现入队和出队操作 问2 在具有n个单元的循环队列中 队满时共有多少个元素 n 1个 6 问1 上图中队列长度L 76 队列存放数组被当作首尾相接的表处理 队头 队尾指针加1时从maxSize 1直接进到0 可用语言的取模 余数 运算实现 队头指针出 front front 1 maxSize 队尾指针进 rear rear 1 maxSize 队列初始化 front rear 0 队空条件 front rear 队满条件 rear 1 maxSize front 4 循环队列 CircularQueue 队空 Q front Q rear队满 Q front Q rear 1 maxSize入队 Q rear Q rear 1 maxSize出队 Q front front 1 maxSize 求队长 Q rear Q front maxSize maxSize 77 defineMAXQSIZE100 最大队列长度constQUENCE INIT SIZE 100 ConstQUENCEINCREMENTSIZE 10 typedefstruct QElemType elem 动态分配存储空间intfront 头指针 若队列不空 指向队列头元