三：栈和队列

第三章栈和队列 栈和队列是两种特殊的线性表 是操作受限的线性表 称限定性DS3 1栈 stack 栈的定义和特点定义 限定仅在表尾进行插入或删除操作的线性表 表尾 栈顶 表头 栈底 不含元素的空表称空栈特点 先进后出 FILO 或后进先出 LIFO 3 1 1顺序栈由于栈是运算受限的线性表 因此线性表的存储结构对栈也适应 栈的顺序存储结构简称为顺序栈 它是运算受限的线性表 因此 可用数组来实现顺序栈 因为栈底位置是固定不变的 所以可以将栈底位置设置在数组的两端的任何一个端点 栈顶位置是随着进栈和退栈操作而变化的 故需用一个整型变量top来表示当前栈顶的位置 通常称top为栈顶指针 因为数组是由下标0开始存放的 所以通常用top 1表示空栈 因此 顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可 顺序栈的类型定义如下 defineStackSize100typedefchardatatype typedefstruct datatypedata StackSize inttop SqStack top 6543210 1 A top B top C top 设S是SqStack类型的指针变量 若栈底位置在向量的低端 即s data 0 是栈底元素 那么栈顶指针s top是正向增加的 即进栈时需将s top加1 退栈时需将s top减1 因此 s top 1表示空栈 s top stacksize 1表示栈满 当栈满时再做进栈运算必定产生空间溢出 简称 上溢 当栈空时再做退栈运算也将产生溢出 简称 下溢 上溢是一种出错状态 应该设法避免之 下溢则可能是正常现象 因为栈在程序中使用时 其初态或终态都是空栈 所以下溢常常用来作为程序控制转移的条件 练习题 当用长度为n的数组顺序存储一个栈时 假定用top n表示栈空 则表示栈满的条件是 因为用一个长度为n的数组顺序储存一个栈 然而数组是从0 n 1 栈空为top n 那么栈满为top 0 1 置空栈voidinitstack seqstack s s top 1 2 判断栈空intstackempty seqstack s return s top 1 3 判断栈满intstackfull seqstack s return s top stacksize 1 4 进栈voidpush seqstack s datatypex if stackfull s error stackoverflow s data s top x 5 退栈datatypepop seqstack s if stackempty s error stackunderflow x s data top s top return x 6 取栈顶元素Datatypestacktop seqstack s if stackempty s error stackisenpty returns data s top Typedefstruct Elemtype base 栈底指针Elemtype top 栈顶指针intstacksize SqStack 判空条件 top base栈不存在 base NULL这样在非空栈中 栈顶指针始终在栈顶元素的一个位置上 出栈算法 在一个程序中同时使用两个栈 入栈算法 2 在作进栈运算时 应先判别栈是否 在作退栈运算时应先判别栈是否 当栈中元素为n个 作进栈运算时发生上溢 则说明该栈的最大容量为 为了增加内存空间的利用率和减少溢出的可能性 由两个栈共享一片连续的内存空间时 应将两栈的 分别设在这片内存空间的两端 这样 当 时 才产生上溢 A 空B 满C 上溢D 下溢 A n 1B nC n 1D n 2 A 长度B 深度C 栈顶D 栈底 A 两个栈的栈顶同时到达栈空间的中心点 B 其中一个栈的栈顶到达栈空间的中心点 C 两个栈的栈顶在栈空间的某一位置相遇 D 两个栈均不空 且一个栈的栈顶到达另一个栈的栈底 行编辑程序 遇到 则表示前一字符无效 遇到 表示整行无效 1 读入字符串2 判断该字符是否为 或者 3 如果不是 则压入栈4 如遇 则将栈顶元素出栈 如果为 则将栈清空 多进制输出 表达式求值 中缀表达式后缀表达式 RPN a b cab c a b cabc a b c d eabc d e 中缀表达式 操作数栈和运算符栈 例计算2 4 3 6 后缀表达式求值步骤 1 读入表达式一个字符2 若是操作数 压入栈 转43 若是运算符 从栈中弹出2个数 将运算结果再压入栈4 若表达式输入完毕 栈顶即表达式值 若表达式未输入完 转1 例计算4 3 5 后缀表达式 435 通常用的是 穷举求解 的方法 即从入口出发 顺某一方向向前探索 若能走通 则继续往前走 否则沿原路退回 换一个方向再继续探索 直至所有可能的通路都探索到为止如果所有可能的通路都试探过 还是不能走到终点 那就说明该迷宫不存在从起点到终点的通道 迷宫问题 所谓 下一位置 指的是 当前位置 四周四个方向 东 南 西 北 上相邻的方块 假设以栈S记录 当前路径 则栈顶中存放的是 当前路径上最后一个通道块 纳入路径 的操作即为 当前位置入栈 从当前路径上删除前一通道块 的操作即为 出栈 do 若当前位置可通 则 将当前位置插入栈顶 纳入路径若该位置是出口位置 则算法结束 此时栈中存放的是一条从入口位置到出口位置的路径否则切换当前位置的东邻方块为新的当前位置 否则 若栈不空且栈顶位置尚有其他方向未被探索 则设定新的当前位置为 沿顺时针方向旋转找到的栈顶位置的下一相邻块 若栈不空但栈顶位置的四周均不可通 则 删去栈顶位置 从路径中删去该通道块若栈不空 则重新测试新的栈顶位置 直至找到一个可通的相邻块或出栈至栈空 while 栈不空 栈的应用过程的嵌套调用 例递归的执行情况分析 递归过程及其实现递归 函数直接或间接的调用自身叫 实现 建立递归工作栈 voidprint intw inti if w 0 print w 1 for i 1 i w i printf 3d w printf n 运行结果 1 2 2 3 3 3 递归调用执行情况如下 3 2队列队列的定义及特点定义 队列是限定只能在表的一端进行插入 在表的另一端进行删除的线性表队尾 rear 允许插入的一端队头 front 允许删除的一端队列特点 先进先出 FIFO 双端队列 链队列结点定义 typedefstructQnode intdata structQnode next Qnode QueuePtr typedefstruct QueuePtrfront QueuePtrrear LinkQueue 设队首 队尾指针front和rear front指向头结点 rear指向队尾 StatusEnQueue LinkQueue 入队算法 StatusDeQueue LinkQueue if Q rear p Q rear Q front 出队算法 队列的顺序存储结构实现 用一维数组实现sq M 1 J1 J2 J3 设两个指针front rear 约定 rear指示队尾元素下一位置 front指示队头元素 初值front rear 0 空队列条件 front rear入队列 sq rear x 出队列 x sq front 实现 利用 取模 运算入队 sq rear x rear rear 1 M 出队 x sq front front front 1 M 队满 队空判定条件 存在问题设数组大小为M 则 当front 0 rear M时 再有元素入队发生溢出 真溢出当front 0 rear M时 再有元素入队发生溢出 假溢出解决方案 循环队列基本思想 把队列设想成环形 让sq 0 接在sq M 1 之后 若rear M 则令rear 0 队空 front rear队满 front rear 解决方案 1 另外设一个标志以区别队空 队满2 少用一个元素空间 队空 front rear队满 rear 1 M front defineMAXQSIZE100 最大队列长度typedefstruct QElemType base 动态分配存储空间intfront 头指针 若队列不空 指向队列头元素intrear 尾指针 若队列不空 指向 队列尾元素的下一个位置 SqQueue 循环队列的表示 StatusDeQueue SqQueue 循环队列出队 StatusEnQueue SqQueue 循环队列入队 练习 1 设一数列的顺序为1 2 3 4 5 6 通过队列操作可以得到 的输出序列 A 3 2 5 6 4 1B 1 2 3 4 5 6C 6 5 4 3 2 1D 4 5 3 2 6 12 若进栈序列为整数1 2 3 则通过进栈和出栈操作可能得到的整数的不同排列个数为 A 3B 4C 5D 6 B C 3 设一个栈的输入序列为1 2 3 4 则输出序列不可能是 A 1 2 3 4B 4 3 2 1C 1 3 2 4D 4 1 2 34 设循环队列中数组的下标范围是0 n 1 其头尾指针分别为f和r 则其元素个数为 A r fB r f 1C r f modn 1D r f n modn5 一个栈的进栈序列是a b c d e 则栈的不可能的输出序列是 A abcdeB edcbaC decbaD dceab D D D 第四章串 4 1串类型的定义4 2串的表示和实现4 2 1定长顺序存储表示4 2 2堆分配存储表示4 2 3串的块链存储表示 4 1串类型的定义一 串和基本概念串 String 是零个或多个字符组成的有限序列 一般记作S a1a2a3 an 其中S是串名 双引号括起来的字符序列是串值 ai 1 i n 可以是字母 数字或其它字符 串中所包含的字符个数称为该串的长度 长度为零的串称为空串 EmptyString 它不包含任何字符 通常将仅由一个或多个空格组成的串称为空白串 BlankString 注意 空串和空白串的不同 例如 和 分别表示长度为1的空白串和长度为0的空串 串中任意个连续字符组成的子序列称为该串的子串 包含子串的串相应地称为主串 通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号 定义为子串在主串中的序号 或位置 例如 设A和B分别为A Thisisastring B is 则B是A的子串 A为主串 B在A中出现了两次 其中首次出现所对应的主串位置是3 因此 称B在A中的序号 或位置 为3特别地 空串是任意串的子串 任意串是其自身的子串 通常在程序中使用的串可分为两种 串变量和串常量 串常量和整常数 实常数一样 在 程序中只能被引用但不能不能改变其值 即只能读不能写 通常串常量是由直接量来表示的 例如语句Error overflow 中 overflow 是直接量 但有的语言允许对串常量命名 以使程序易读 易写 如C 中 可定义constcharpath dir bin appl 这里path是一个串常量 对它只能读不能写 串变量和其它类型的变量一样 其取值是可以改变的 二 串的抽象数据定义串的抽象数据类型定义书P71 三 串的基本操作对于串的基本操作 许多高级语言均提供了相应的运算或标准库函数来实现 下面仅介绍几种在C语言中常用的串运算 定义下列几个变量 chars1 20 dirtreeformat s2 20 file mem chars3 30 p intresult 求串长 length intstrlen chars 求串的长度例如 printf d strlen s1 输出13 2 串复制 copy char strcopy charto charfrom 该函数将串from复制到串to中 并且返回一个指向串to的开始处的指针 例如 strcpy s3 s1 s3 dirtreeformat 3 联接 concatenation charstrcat charto charfrom 该函数将串from复制到串to的末尾 并且返回一个指向串to的开始处的指针 例如 strcat s3 strcat s3 s2 s3 dirtreeformat file mem 4 串比较 compare intstrcmp chars1 chars2 该函数比较串s1和串s2的大小 当返回值小于0 等于0或大于0时分别表示s1s2例如 result strcmp baker Baker result 0result strcmp 12 12 result 0result strcmp Joe Joseph result 0 上述串的操作是最基本的 串的其余操作可由这些基本操作组合而成 例1 求子串求子串的过程即为复制字符序列的过程 将串S中的第pos个字符开始长度为len的字符复制到串T中 voidsubstr stringsub strings intpos intlen if posstrlen s 1 len 0 error parametererror strncpy sub 例2 串的定位index s t pos 在主串中取从第pos个字符起 长度和串T相等的子串和T比较 若相等 则求得函数值为i 否则值增1直至S中不存在和串T相等的子串为止 4 2串的表现和实现因为串是特殊的线性表 故其存储结构与线性表的存储结构类似 只不过由于组成串的结点是单个字符 串有三种机内表示方法 下面分别介绍 4 2 1定长顺序存储表示定长顺序存储表示 也称为静态存储分配的顺应表 它是用一组连续的存储单元来存放串中的字符序列 所谓定长顺序存储结构 是直接使用定长的字符数组来定义 数组的上界预先给出 definemaxstrlen256typedefcharsstring maxstrlen sstrings s是一个可容纳255个字符的顺序串 一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束 例如 C语言中以字符 0 表示串值的终结 这就是为什么在上述定义中 串空间最大值maxstrlen为256 但最多只能存放255个字符的原因 因为必须留一个字节来存放 0 字符 若不设终结符 可用一个整数来表示串的长度 那么该长度减1的位置就是串值的最后一个字符的位置 此时顺序串的类型定义和顺