《程序设计初步》PPT课件.ppt

第3章堆栈和队列 主要知识点 堆栈堆栈应用队列优先级队列 3 1堆栈 1 堆栈的基本概念 1 定义 限定只能在固定一端进行插入和删除操作的线性表 特点 后进先出 2 允许进行插入和删除操作的一端称为栈顶 另一端称为栈底 2 堆栈抽象数据类型 数据集合 a0 a1 an 1 ai的数据类型为DataType 操作集合 1 Initiate S 初始化堆栈S 2 Push S x 入栈 3 Pop S d 出栈 4 GetTop S 取栈顶数据元素 5 NotEmpty S 堆栈S非空否 3 顺序堆栈类 1 顺序堆栈顺序存储结构的堆栈 2 顺序栈的存储结构它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 其结构如图所示 其中 a0 a1 a2 a3 a4表示顺序堆栈中已存储的数据元素 stack表示存放数据元素的数组 MaxStackSize 1表示最大存储单元个数 top表示当前栈顶存储下标 类的定义 classSeqStack private DataTypedata MaxStackSize 顺序堆栈数组inttop 栈顶位置指示器public SeqStack void top 0 构造函数 SeqStack void 析构函数voidPush constDataTypeitem 入栈DataTypePop void 出栈DataTypeGetTop void const 取栈顶数据元素intNotEmpty void const 堆栈非空否 return top 0 3 顺序栈类的操作实现 一 voidSeqStack Push constDataTypeitem 入栈 把元素item入栈 堆栈满时出错退出 if top MaxStackSize cout 堆栈已满 endl exit 0 data top item 先存储itemtop 然后top加1 二 DataTypeSeqStack Pop 出栈 出栈并返回栈顶元素 堆栈空时出错退出 if top 0 cout 堆栈已空 endl exit 0 top top先减1returndata top 然后取元素返回 三 DataTypeSeqStack GetTop void const 取栈顶数据元素 取当前栈顶数据元素并返回 if top 0 cout 堆栈空 endl exit 0 returndata top 1 返回当前栈顶元素 测试主程序如下 include includeconstintMaxStackSize 100 定义问题要求的元素数目的最大值typedefintDataType 定义具体问题元素的数据类型 voidmain voie SeqStackmyStack 构造函数无参数时 定义的对象后不带括号DataTypetest 1 3 5 7 9 intn 5 for inti 0 i n i myStack Push test i while myStack NotEmpty while myStack NotEmpty cout myStack Pop 程序运行输出结果为 97531 4 链式堆栈类 1 链式堆栈顺序存储结构的堆栈 2 链式栈的存储结构它是以头指针为栈顶 在头指针处插入或删除 其结构如图所示 链栈中每个结点由两个域构成 data域和next域 其结点类和类定义分别如下 templateclassLinStack 前视定义 否则友元无法定义 结点类template 模板类型为TclassStackNode friendclassLinStack 定义类LinStack为友元private Tdata 数据元素StackNode next 指针public 构造函数1 用语构造头结点StackNode StackNode ptrNext NULL next ptrNext 构造函数2 用于构造其他结点StackNode constT 链式堆栈类的定义templateclassLinStack private StackNode head 头指针intsize 数据元素个数public LinStack void 构造函数 LinStack void 析构函数voidPush constT 3 链式栈类的操作实现 一 templateLinStack LinStack 构造函数 head newStackNode 头指针指向头结点size 0 size的初值为0 二 templateLinStack LinStack void 析构函数 释放所有动态申请的结点空间 StackNode p q p head p指向头结点while p NULL 循环释放结点空间 q p p p next deleteq 三 templateintLinStack NotEmpty void const 堆栈非空否 if size 0 return1 elsereturn0 四 templatevoidLinStack Push constT 元素个数加1 五 templateTLinStack Pop void 出栈 if size 0 cout p head next p指向栈顶元素结点Tdata p data head next head next next 原栈顶元素结点脱链deletep 释放原栈顶结点空间size 结点个数减1returndata 返回原栈顶结点的data域值 六 templateTLinStack GetTop void const 取栈顶元素 returnhead next data 说明 1 在链栈中的头结点对操作的实现影响不大 栈顶 表头 操作频繁 可不设头结点链栈 2 一般不会出现栈满情况 除非没有空间导致malloc分配失败 3 链栈的入栈 出栈操作就是栈顶的插入与删除操作 修改指针即可完成 4 采用链栈存储方式的优点是 可使多个栈共享空间 当栈中元素个数变化较大 且存在多个栈的情况下 链栈是栈的首选存储方式 3 2堆栈应用 1 括号匹配问题 例 假设一个算法表达式中包含圆括号 方括号和花括号三种类型的括号 编写一个判别表达式中括号是否正确配对的函数 设计思路 用栈暂存左括号 voidExpIsCorrect charexp intn 判断有n个字符的字符串exp左右括号是否配对正确 SeqStackmyStack 定义顺序堆栈类对象myStackinti for i 0 i n i if exp i exp i exp i myStack Push exp i 人栈elseif exp i 出栈 elseif exp i elseif exp i elseif exp i exp i exp i 2 表达式计算问题 表达式计算是编译系统中的基本问题 其实现方法是堆栈的一个典型应用 在编译系统中 要把便于人理解的表达式翻译成能正确求值的机器指令序列 通常需要先把表达式变换成机器便于理解的形式 这就要变换表达式的表示序列 假设计算机高级语言中的一个算术表达式为A B C D E 这种表达式称为中缀表达式 写成满足四则运算规则的相应的后缀表达式即为ABCD E 中缀表达式变换为后缀表达式的算法步骤可以总结为 1 设置一个堆栈 初始时将栈顶元素置为 2 顺序读入中缀表达式 当读到的单词为操作数时就将其输出 并接着读下一个单词 3 令x1为当前栈顶运算符的变量 x2为当前扫描读到运算符的变量 当顺序从中缀表达式中读入的单词为运算符时就赋予x2 然后比较x1的优先级与x2的优先级 若x1的优先级高于x2的优先级 将x1退栈并作为后缀表达式的一个单词输出 然后接着比较新的栈顶运算符x1的优先级与x2的优先级 利用堆栈计算后缀表达式值的函数编写如下 voidPostExp LinStack x入栈 else x2 s Pop 退栈得操作数x1 s Pop 退栈得被操作数switch ch case x1 x2 break case x1 x2 break case x1 x2 break case if x2 0 0 cout 除数为0错 exit 0 else x1 x2 break s Push x1 运算结果入栈 cout 后缀表达式计算结果为 s Pop endl 3 3队列 1 队列的基本概念 1 定义 只能在表的一端进行插入操作 在表的另一端进行删除操作的线性表 一个队列的示意图如下 2 队列抽象数据类型 数据集合 a0 a1 an 1 ai的数据类型为DataType 操作集合 1 Initiate Q 初始化队列Q 2 Append Q x 入队列 3 Delete Q 出队列 4 GetFront Q 取队头数据元素 5 NotEmpty Q 队列Q非空否 队尾插入 队头删除 3 顺序队列 1 顺序队列顺序存储结构的队列 2 顺序队列的存储结构下图是一个有6个存储空间的顺序队列的动态示意图 3 顺序队列的 假溢出 问题 假溢出顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出 如何解决顺序队列的假溢出问题 可采取四种方法 1 采用循环队列 2 按最大可能的进队操作次数设置顺序队列的最大元素个数 3 修改出队算法 使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置 修改入队算法 增加判断条件 当假溢出时 把队列中的数据元素向对头移动 然后方完成入队操作 4 顺序循环队列的基本原理把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列 当rear和front达到MaxQueueSize 1后 再前进一个位置就自动到 5 顺序循环队列的队空和队满判断问题新问题 在循环队列中 空队特征是front rear 队满时也会有front rear 判决条件将出现二义性 解决方案有三 使用一个计数器记录队列中元素个数 即队列长度 判队满 count 0 rear front判队空 count 0 加设标志位 出队时置 入队时置 则可识别当前front rear属于何种情况判队满 tag 1 rear front判队空 tag 0 rear front 少用一个存储单元判队满 front rear 1 MaxQueueSize判队空 rear front 4 顺序循环队列类 采用设置计数器方法来判断队空状态和队满状态 类定义如下 classSeqQueue private DataTypedata MaxQueueSize 顺序队列数组intfront 队头指示器intrear 队尾指示器intcount 元素个数计数器public SeqQueue void 构造函数 front rear 0 count 0 SeqQueue void 析构函数voidAppend constDataType voidSeqQueue Append constDataType 计数器加1 DataTypeSeqQueue Delete void 出队列 把队头元素出队列 出队列元素由函数返回 if count 0 cout 队列已空 endl exit 0 DataTypetemp data front 保存原队头元素front front 1 返回原队头元素 DataTypeSeqQueue GetFront void const 取队头数据元素 取队头元素并由函数返回 if count 0 cout 队列已空 endl exit 0 returndata Front 返回队头元素 5 链式队列类 1 链式队列顺序存储结构的队列 2 链式队列的存储结构链式队列的队头指针指向队列的当前队头结点 队尾指针指在队列的当前队尾结点 下图是一个不带头结点的链式队列的结构 3 链式队列类的定义及实现 结点类的定义和实现如下 templateclassLinQueue 前视定义 否则友元无法定义templateclassQueueNode friendclassLinQueue 定义类LinQueue为友元private QueueNode next 指针Tdata 数据元素public 构造函数QueueNode const 为了方便设计 增加了一个count域用来计算当前的元素个数链式队列类的定义如下 templateclassLinQueue private QueueNode front 队头指针QueueNode rear 队尾指针intcount 计数器public LinQueue void 构造函数 LinQueue void 析构函数voidAppend constT 链式队列类的实现如下 templateLinQueue LinQueue 构造函数 front rear NULL 链式队列无头结点count 0 count的初值为0 templateLinQueue LinQueue void 析构函数 QueueNode p q p front p指向第一个结点while p NULL 循环直至全部结点空间释放 q p p p next deleteq count 0 置为初始化值0front rear NULL templatevoidLinQueue Append constT 计数器加1 templateTLinQueue Delete void 出队列 把队头结点删除并由函数返回 if count 0 cout p front next p指向新的队头结点Tdata front data 保存原队头结点的data域值deletefront 释放原队头结点空间front p front指向新的对头结点count 计数器减1returndata 返回原队头结点的data域值 templateTLinQueue GetFront void const 取队头数据元素 if count 0 coutdata 6 队列的应用 例 编写判断一个字符序列是否是回文的函数 编程思想 设字符数组str中存放了要判断的字符串 把字符数组中的字符逐个分别存入队列和堆栈 然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等 若全部相等则该字符序列是回文 否则就不是回文 设计函数如下 voidHuiWen charstr LinStackmyStack LinQueuemyQueue intn strlen str 求字符串长度for inti 0 i n i myQueue Append str i myStack Push str i while myQueue NotEmpty 3 4优先级队列 优先级队列带有优先级的队列 顺序优先级队列用顺序