第三章 栈、队列和数组.ppt

1 第三章栈 队列和数组 栈和队列都是特殊的线性表 数组是线性表的变化形式 它们都是软件设计中常用的数据结构 2 主要内容 栈 队列数组栈的应用 递归 3 栈的定义 栈是只能在一端插入和删除的线性表 后进先出 4 栈的运算 初始化栈 init stack S 判断栈空 stack empty S 取栈顶元素 stack top S x 入栈 push stack S x 出栈 pop stack S 判断栈满 stack full S 5 顺序栈 存储结构 以顺序存储方式存储的栈叫做顺序栈 类型说明 typedefstruct elementtypedata maxsize inttop seqstack 6 顺序栈 运算 1 初始化栈 voidinit stack seqstack S s top 1 Top所指示元素下标比元素个数少1 即 0 判断栈S是否为空 BOOLstack empty seqstackS if S top 1 returnTRUE elsereturnFALSE 取栈顶元素Voidstack top seqstack S elementtype x if empty S error 栈为空 else x s data s top Top值是否为 1 栈不空 返回栈顶元素 否则出错 7 入栈 voidpush stack seqstack S elementtypex if S top maxsize 1 error 溢出 elseS data s top x 顺序栈 运算 2 出栈 voidpop stack seqstack S elementtype x if empty S error 栈空 不能删除 else x S data S top 判断栈是否为满 BOOLstack full seqstackS if S top maxsize 1 returnTRUE elsereturnFALSE 判断栈是否满了 否则不能插入 判断栈是否为空 否则不能删除 Top值是否为maxsize 1 8 链栈 用动态方式来存储栈可节省空间采用链表存储的栈为链栈 9 栈的应用 基本应用 1 voidread write stackS intn x cout n 输入元素个数init stack S 初始化栈for i 1 i x 读入一个数push stack S x 入栈 while stack empty S TRUE stack top S x 取出栈顶元素cout x 输出pop stack S 退栈 读入一个有限大小的整数n 并读入n个整数 然后按输入次序的相反次序输出各元素的值 10 栈的应用 基本应用 2 将单链表L就地逆置 即将链表中的各元素结点的后继指针倒置为指向其前驱结点 a1结点变成最后一个结点 an结点变成第一个结点 voidreverse node L node P NULL while L NULL node u L 操作 用指针u指示待分离的表头结点L L next 操作 从原表中分离出表头结点u next P 操作 新分离出的结点的后继指示新表表头结点P u 操作 新分离出的结点成为新表的表头结点 L P 原表头指针指示新的表头指针 11 栈的应用 表达式计算 编写程序以实现对任意输入的表达式的计算 例如表达式为12 5 2 3 6 2 4 12 1357 8所得的余数 1357 8所得的商 按此次序连接各位余数便得到最后的转换结果为2515 1357 栈的应用 数的进制转换 设计算法将十进制数转换为八进制形式 实例 voidDec to Ocx inta stackS init stack S 初始化栈while N 0 Mod N 8 求余数push stack S Mod 余数入栈N N 8 求商while stack empty S stack top S x 取出栈顶元素cout x 输出pop stack S 退栈 13 主要内容 栈 数组栈的应用 递归 队列 14 队列的定义 队列是只能在一端插入 另一端删除的线性表 15 队列的运算 初始化队列 init queue Q 判断队列是否为空 queue empty Q 取队头元素 queue front Q x 入队 enqueue Q x 出队 outqueue Q x 判断队列是否为满 queue full Q 16 顺序队列 存储结构 以顺序方式存储的队列叫做顺序队列 类型说明 typedefstruct elementtypedata maxsize 存放元素的数组intfront rear 头尾指针 seqqueue 17 循环队列 顺序队列会产生 假溢出 将数组元素data 0 看做是data maxsize 1 的下一个储存位置 就形成了循环队列 18 循环队列 运算 1 初始化队列 voidinit queue seqqueue Q Q front 0 Q rear 0 判断队列是否为空 BOOLqueue empty seqqueueQ if Q front Q rear returnTRUE elsereturnFALSE 判断队列是否为满 BOOLqueue full seqqueueQ if 1 Q rear maxsize Q front returnTRUE elsereturnFALSE 尾指针的下一个位置是头指针所指位置时为满 头尾指针相同 则肯定为空 19 入队voidEnqueue seqqueue Q elementtypex if full Q error 溢出 else Q rear 1 Q rear maxsize Q data Q rear x 循环队列 运算 2 取队头元素 elementtypequeue front seqqueueQ elementtype x if queue empty Q error 队空 else x Q data Q front 1 maxsize 队头元素在front指针所指位置的下一个位置 往后移动尾指针 填进待插入的元素 出队voidOutqueue seqqueue Q elementtype x if empty Q error 队空 不能出队 else Q front Q front 1 maxsize x Q data Q front 20 链队列 存储结构 头指针始终指向表头 尾指针始终指向表尾 采用带头节点的链表形式 类型说明typedefstruct node front rear 仅需要头尾指针即可 linkqueue 21 头结点之后的结点中的值为队头元素 链队列 运算 1 初始化队列 voidinit queue linkqueue Q Q front node malloc sizeof node Q rear Q front Q front next NULL 产生由头指针指示的头结点 尾指针也指向该头结点 尾结点的后继指针设置为空 取队头元素 voidqueue front linkqueue Q elementtypex if empty Q error 队空 不能取元素 elsex Q front next data 判断队为空 BOOLqueue empty linkqueueQ returnQ front Q rear 队头元素的值由x返回 首尾指针相等 22 链队列 运算 2 入队 voidEnqueue linkqueue Q elementtypex node P node malloc sizeof node P data x P next NULL Q rear next P Q rear P 出队 voidOutqueue linkqueue Q elementtype x if empty Q error 队空 不能出队 else x Q front next data node u Q front next Q front next u next free u if Q front next NULL Q rear Q front 新节点中填入数据 后继指针置空 连到表尾 尾指针指向新插入的节点 取队头元素的值 保存待删节点的指针 删除队头节点 释放所删除节点的存储空间 删除最后一个节点时 尾指针指向已被删除的节点 应做调整 23 队列的应用 杨辉三角 设计算法 用队列计算并打印杨辉三角的前8行的内容 即输出结果如下 111121133114641151010511615201561172135352171 解决方法 用队列保存上一行的内容 每当由上一行的两个数求出下一行的一个数时 删除前一个数 新求出的数入队 voidOut Number intn Init Queue Q 初始化队列cout 1 endl 输出第一行上的1En Queue Q s1 s2 所输出的当前行中的元素入队for i 2 i n i 计算并输出第i行上的数据 s1 0 存放前一个出队数for j 1 j i 1 j s2 Out Queue Q 取队头元素cout s1 s2 输出当前行中的一个元素En Queue Q s1 s2 所输出的当前行中的元素入队s1 s2 调整变量的值cout 1 endl 输出当前行中的最后一个元素1并换行En Queue Q s1 s2 本行最后的元素入队 24 主要内容 栈 数组 队列 栈的应用 递归 25 数组的定义 一维数组是有限个具有相同类型的变量组成的序列 若其中每个变量本身是一维数组 则构成二维数组 a1 a2 a3 an 26 数组的运算 对数组的运算 通常有如下两个 给定一组下标 存取相应的数组元素给定一组下标 修改相应的元素值由于这两个运算在内部实现时都需要计算出给定元素的实际存储地址 因此 计算数组元素地址这一运算就成了数组中最基本的运算 27 数组的顺序存储 行优先 逐行地顺序存储各元素 在PASCAL C COBOL PL 1等语言中均采用这种存储方式 列优先 逐列地顺序存储各元素 FORTRAN语言中采用的是这种方法 右边的下标比左边的下标变化快 左边的下标比右边的下标变化快 28 数组元素地址的计算 A i j 29 矩阵压缩存储 对称矩阵和三角矩阵 下三角元素 num i j 1 2 3 i 1 j i i 1 2 j上三角元素 num i j 1 2 3 j 1 i j j 1 2 i a11a12a13 a1na21a22a23 a2na31a32a33 a3n an1an2an3 ann 30 a11a12a21a22a23a32a33a34a43a44a45 ann 1ann 矩阵压缩存储 对角矩阵 num i j 3 i 1 1 j i 2 2i j 2 i j 1 31 矩阵压缩存储 稀疏矩阵 01200050006000500307001000000000009000000000 typedefstruct 三元组结构 inti j elementtypev tuplestruct 三元组表结构 intmu nu tu 行数 列数 非0元素个数tupledata maxnum spmatrix 32 主要内容 栈 数组 队列 栈的应用 递归 33 递归概述 如果一个函数直接调用自己或通过一系列调用间接调用自己 则称这一函数是递归定义的 几大难点 递归的理解问题递归程序的阅读递归程序的验证和编写递归程序的时间问题及其解决 34 递归程序的定义 一个实例 1 求解整数n的阶乘函数 调用函数本身 intFact intn if n 0 return 1 elsereturn n Fact n 1 35 递归程序的定义 一个实例 2 voidp intn if n 0 p n 1 cout n p n 2 36 递归程序的定义 一个实例 3 voidp1 intn if n 0 if n 2 1 p1 n 1 cout0 if n 3 0 cout n p1 n 1 else p2 n 1 cout n 两个函数之间互相调用 37 递归程序的一般形式 voidPname 参数表 if 数据为递归出口 简单操作 else 简单操作 Pname 实参表 简单操作 Pname 实参表 简单操作 可能有多次的调用 38 一般函数的内部实现 执行过程 在执行调用时 计算机内部至少执行如下操作 保存返回地址 即将返回地址入栈为被调子程序准备数据 计算实在参数的值 并赋给对应的形参转入子程序执行在执行返回操作时 计算机内部至少执行如下操作 从栈顶取出返回地址 并出栈按返回地址返回 39 一般函数的内部实现 局部变量 执行调用时 内部操作如下 返回地址入栈 同时在栈顶为被调过程的局部变量和形参开辟存储空间为被调子程序准备数据 计算实在参数的值 并赋给对应的形参 在栈顶 转入子程序执行在执行返回操作时 计算机内部至少执行如下操作 从栈顶取出返回地址 并出栈 同时撤消了被调过程的局部变量和形参 按返回地址返回 40 一般函数的内部实现 返回值 执行调用操作不变执行返回操作如下 若函数需要求值 将其值保存到回传变量中从栈顶取出返回地址 并退栈按返回地址返回在返回后自动执行以下操作 若函数需要求值 从回传变量中取出所保存的值并传送到相应的变量或位置上 41 递归调用的内部实现 可将递归调用理解为调用与自己有相同的代码和同名的局部变量的子程序 将递归调用当做是子程序调用的特殊情况 其特殊性在于所调用的乃是自身代码 若递归子程序中有局部变量 则其各复制件也应有自己的局部变量 它们是独立的 两个重点 内部实现不变 42 例题 根据递归程序的内部实现过程求解return 28 6 的执行结果 inthcf intM intN 1 if N 0 2 cout M returnM 3 elsereturnhcf N M N 4 点击显示执行过程 43 点击显示题目 44 阅读递归程序的方法 1 按次序写出程序当前调用层上实际执行的各语句 并用有向弧表示语句的执行次序 2 对程序中的每个调用语句或函数引用 写出其实际调用形式 带实参 然后在其右边或下边写出本次调用的子程序实际的执行语句 以区分调用主次和层次 另外 还要作如下操作 在被调层的前面标明各形参的值 从调用操作处画一有向弧指向被调子程序的入口 以表示调用路线 从被调子程序的末尾处画一有向弧指向调用操作的下面 表示返回路线 3 若为函数 在返回路线上标出调用所得的函数值 若有要返回修改值的参数 在返回路线上增加标注语句 实参 形参的值 45 对下面程序 求出调用AB的运行结果 voidA cout A voidB cout B A cout B voidAB cout AB A B cout AB 例题 1 AB Cout AB A Cout AB B 运行结果 ABABABAB 46 对下面的递归过程 写出调用P 4 的运行结果 voidP intW if W 0 P W 1 cout W P W 2 例题 2 运行结果 1231412 47 例题 3 函数F定义如下 用上述方法求出F 6 的值 intF intN if N 2 return1 return 2 F N 1 3 F N 2 运行结果 F 5 121 48 递归程序的逻辑正确性证明 数学归纳法证明在子程序的数据为递归出口时 功能正确假设在参数接近递归出口的某范围内 不妨设为 时子程序功能都正确 按程序描述 将这些正确的功能调用代入到子程序中 证明在参数远离递归出口 此处为 时子程序功能也正确 49 递归程序的正确性证明 逻辑正确性与实现正确性的关系 逻辑正确性 实现正确性 证明方法 先证明其逻辑正确性 然后再在限定条件下进行证明或讨论以得到其实现正确性 其中前面的证明是重点 在许多情况下仅考虑这一证明 50 例题 1 证明下面求累加和的函数S intn 的正确性 intS intn if n 0 return0 elsereturnn S n 1 证明 当n 0时 调用函数得值为0 符合函数定义 功能正确 设0 n k时 函数正确 即函数S n 等于1 2 3 n 则当n k 0时 由程序可知S n n S n 1 n 1 2 3 n 1 1 2 3 n 功能正确 综上所述 程序功能正确 51 例题 2 证明对下面的函数定义 调用P n 将按从大到小的次序依次输出n到1的各值 即输出n n 1 n 2 2 1 n 0 voidP intn if n 0 cout n P n 1 证明 当n 0时 由程序描述可知 不产生输出 符合命题 假设在0 n k时 命题正确 即调用P n 时 按从大到小的次序依次输出n到1的各值 即输出n n 1 n 2 2 1 则当 k时 由程序描述可知 要依次执行如下操作 cout n P n 1 其中第一个操作产生的输出为 由假设知后面的操作产生的输出为n 1 n 2 2 1 因此 整个输出为n n 1 n 2 2 1 符合命题 综上所述 程序功能正确 52 例题 3 证明对下面的函数 调用P n 所产生的输出项数为2n 1 n 0 voidP intn if n 0 cout n P n 1 P n 1 证明 当n 0时 由程序描述可知 不产生输出 即项数为0 符合命题 设0 n k时 命题正确 即调用P n 产生2n 1项输出 则当 k时 由程序描述可知 要依次执行如下操作 cout n P n 1 P n 1 其中第一个操作产生一个输出 由假设知后面两个操作分别产生2n 1 1项输出 因此总输出项数为2 2n 1 1 1 2n 1 符合命题 综上所述 程序功能正确 53 递归程序的编写 确定函数功能和变量含义 确定递归出口和描述 假设数据接近功能出口时 函数功能正常 适当调用这些功能实现本层函数功能 54 例题 fibnacci序列Fn定义如下 编写求解Fn的递归函数 F0 0F1 1Fn Fn 1 Fn 2n 2 设函数名为F 用参数n表示序号 即F n 表示序列中的Fn 讨论如下 1 递归出口有两个 即n 0和n 1 相应操作用语句实现如下 if n 0 return0 elseif n 1 return1 2 在数据为非递归出口 即n 2时 假设在n K时函数功能正确 即F n 为序列的第n项Fn 则在n k时 F n F n 1 F n 2 综上所述 得程序如下 intF intn if n 0 return0 elseif n 1 return1 elsereturnF n 1 F n 2 55 递归的模拟 必要性 程序设计语言对递归的支持方面的限制 程序运行的时间性能方面不如非递归程序 有时需要将递归程序转化为非递归程序 56 递归的模拟 转换规则 系统内部是借助一个栈来实现递归的 因此需要设置一个栈 不妨用 表示 并且开始时要将其置为空 在调用子程序的等价操作中有转入子程序入口的操作 这可用无条件转移语句来实现 因而需要在入口处设置一个标号 不妨设为 0 对程序中的每一递归调用 可用以下几个等价操作来替换 开辟栈顶存储空间 用于保存返回地址 不妨用 i i 1 2 3 和被调子程序中的形参和局部变量的值 为被调子程序准备数据 计算实在参数的值 并赋给对应的形参 在栈顶元素中 转入子程序执行 即执行gotoL0 在返回处设一个标号 i i 1 2 3 并根据需要设置以下语句 若函数需要返回值 从回传变量中取出所保存的值并传送到相应的位置 对返回语句 可用以下等价操作来替换 如果栈不空 则依次执行如下操作 否则结束本子程序 返回 若函数需要返回值 将其值保存到回传变量中 从栈顶取出返回地址 不妨保存到 中 并退栈 按返回地址返回 即执行goto 对其中的非递归调用和返回操作可照搬 但如前所述 由于所涉及到的参数和局部变量均用栈顶元素的分量来存储和表示 故须对此作相应的替换 57 递归的模拟 新的转换规则 设置一个栈 不妨用 表示 并且开始时将其置为空 在子程序入口处设置一个标号 不妨设为 0 对子程序中的每一递归调用 用以下几个等价操作来替换 保留现场 开辟栈顶存储空间 用于保存返回地址 不妨用 i i 1 2 3 和调用层中的形参和局部变量的值 最外层调用不必考虑 准备数据 为被调子程序准备数据 即计算实在参数的值 并赋给对应的形参 转入 子程序 执行 即执行gotoL0 在返回处设一个标号 i i 1 2 3 并根据需要设置以下语句 若函数需要返回值 从回传变量中取出所保存的值并传送到相应的位置 对返回语句 可用以下几个等价操作来替换 如果栈不空 则依次执行如下操作 否则结束本子程序 返回 回传数据 若函数需要返回值 将其值保存到回传变量中 恢复现场 从栈顶取出返回地址 不妨保存到 中 及各变量 形参的值 并退栈 返回 按返回地址返回 即执行goto 对其中的非递归调用和返回操作可照搬 58 例题 1 将下面递归程序转换为等价的非递归程序 voidP intW if W 0 P W 1 cout W voidP1 intW init stack S 规则1L0 规则2if W 0 规则5 push stack S W L1 规则3 aW W 1 规则3 bgotoL0 规则3 cL1 规则3 dcout W 规则5 if empty S 规则4 Pop stack S W X 规则4 bgotoX 规则4 c 59 简化规则1 如果递归程序中只有一处递归调用 则在转换时