c语言课件：栈和队列.ppt

栈和队列 栈抽象数据类型栈的定义栈的表示和实现栈的应用举例数制转换表达式求解队列 是限制仅在线性表的一端进行插入和删除运算的线性表 栈顶 TOP 允许插入和删除的一端 栈底 bottom 不允许插入和删除的一端 空栈表中没有元素 栈 Stack 进栈最先插入的元素放在栈的底部 退栈最后插入的元素最先退栈 栈的基本概念 栈 又称为后进先出的线性表 LIFO表 LastInFirstOut 一叠书或一叠盘子 栈与子程序调用 调用子程序时 计算机将子程序要用到的参数及返回地址等信息存放在栈里子程序返回时 从栈顶取回返回地址 转回主调程序继续运行 处理递归调用 顺序栈 用数组定义 类似于顺序表 将栈底位置设置在向量两端的任意一个端点 用top 整型量 栈顶指针 来指示栈当前栈顶位置 定义 typedef type Element 栈元素的数据类型 definemaxsize100 栈初始的容量 typedefstructstack Elementdata maxsize inttop Stack 顺序栈类型定义 Stack s s是顺序栈类型指针 3210 Top 1空栈 顺序栈 栈顶指针与栈中元素间的关系 顺序栈 栈底位置固定在数组的低端 即 S data 0 表示栈底元素 进栈 S TOP加1 正向增长 退栈 S TOP减1 空栈 S TOPTOP maxsize 1上溢 栈满时再做进栈运算 一种出错状态 应设法避免 顺序栈的几种基本运算 置空栈判栈空进栈退栈取栈顶元素 顺序栈的几种基本运算 置空栈 Create Stack S voidCreate Stack S 将顺序栈S置为空 S top 1 顺序栈的几种基本运算 判栈空 BoolEmpty Stack Empty voidPush Stack Push 顺序栈的几种基本运算 进栈 若栈S非空 取出栈顶元素删除 voidPop Element 退栈 Pop S 顺序栈的几种基本运算 取顺序栈S的栈顶 ElementTop Stack 取栈顶 Top S 顺序栈的几种基本运算 链栈 栈的链式存储结构 当顺序栈的最大容量事先无法估计时 可采用链栈结构 TOP e1next 栈顶 链栈的定义 typedefstructcell Position typedefstructcell Elemente1 Positionnext Cell typedefstructstack Position top Stack 链栈的特点 插入和删除 进栈 退栈 仅能在表头位置上 栈顶 进行 链栈中的结点是动态产生的 可不考虑上溢问题 不需附加头结点 栈顶指针就是链表 即链栈 的头指针 voidPush Elemente Stack 栈底 x s top 链栈进栈运算 链栈退栈运算 voidPop Element 栈小结 顺序栈有发生上溢的可能 而链栈通常不会发生栈满 除非整个空间均被占满 只要满足LIFO原则 均可采用栈结构 栈的应用实例 递归调用 栈的应用举例一数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题 其解决方法很多 其中一个简单算法基于下列原理 N ndivd d nmodd 185 10 8 185 10 271 8 栈的应用举例一数制转换 voidconversion conversion Initstack S scanf d 栈的应用举例一数制转换 栈的应用举例一算术表达式 建立2个栈 操作数栈及运算符栈 初始为空从左到右读取表达式 如果读到操作数则置入操作数栈中 若读到运算符时则置入运算符栈 当读到的运算符优先级比栈中的运算符高 则存入栈当读到的运算符优先级比堆栈中的运算符低或相等 则取出该运算符并从操作数栈取出相应的操作数运算 并将结果存回操作数栈 同时新运算符入栈 堆栈非空从运算符栈中取出一个运算符从操作数栈中取出所需操作数计算其值后将结果存回操作数栈 例计算2 4 3 6 例计算2 4 3 6 栈的应用举例一算术表达式 队列 只允许在表的一端进行插入 而在表的另一端进行删除 是一种先入先出的线性表 FIFO 队列的基本概念 队头 head 允许删除 出队 的一端队尾 tail 允许插入的一端空队列 队列中没有元素进队 队的插入运算 即插入新的队尾元素出队 队的删除运算 删除队首元素 队列的基本运算 入队出队取队头元素置空队列判队列是否为空 顺序队列 队列的顺序存储结构 用一组连续的存储单元依次存放队列中的元素顺序队列的类型说明 typedefstruct datatypedata m inthead tail 队首 队尾 queue queue sq BA DC 3210 sq headsq tail sq head sq tail sq headsq tail sq tail sq head 空队列 A B相继入队 A B相继出队 C D相继入队 顺序队列运算时的头 尾指针变化 顺序队列的约定和主要运算 队头指针 head总是指向当前队头元素队尾指针 tail指向当前队尾元素的下一个位置 初始状态 head tail 0入队运算 sq tail 尾指针加1 sq data sq tail x x入队 出队运算 sq head 头指针加1 顺序队列的约定和主要运算 队列长度 sq tail sq head 队空 sq tail sq head 下溢 队空时再作出队操作 队满 sq tail sq head m上溢 队满时再作入队操作 顺序队列的上溢 队上溢 真上溢 r f m 队列真正满时再入队 假上溢 r已指向数组尾端 但队列前端仍有空位置 解决假上溢的方法 方法一 每次删除队头一个元素后 把整个队列往前移一个位置 造成时间浪费 方法二 循环队列 Setnull queue sq sq head 0 sq tail 0 顺序队列置队空 BoolEmpty queue sq if sq tail sq head return True elsereturn False 顺序队列判队空 datatypeFront queue sq datatypetemp if Empty sq printf queueisempty n returnNULL else temp sq data sq head returntemp 顺序队列取队头元素 BoolEnqueue queue sq datatypex if sq head sq tail 1 m printf queueisfull n returnNULL else sq tail sq tail 1 sq data sq tail x return True 顺序队列入队 datetypeDequeue queue sq if Empty sq printf queueisempty n returnNULL else sq head sq head 1 return sq data sq head 顺序队列出队 循环队列 CircularQueue 当队尾指针tail等于MaxSize时 无论有否空间 都无法再将数据存于队列中将所用的数组sq data m 设想为首尾相接的循环数组 即 data 0 连在data m 1 之后 tail head 循环队列的进队和出队 空队列 循环队列 CircularQueue 队列入队 若尾指针r等于向量的上界 再入队 令尾指针等于向量的下界 即 在循环意义下的尾指针的加1操作可描述为 if sq tail 1 m sq tail 0 elsesq tail 循环队列 CircularQueue 存储队列的数组被当作首尾相接的表处理 队头 队尾指针加1时从maxSize 1直接进到0 可用语言的取模 余数 运算实现 队头指针进1 head head 1 maxSize 队尾指针进1 tail tail 1 maxSize 队列初始化 head tail 0 队空条件 head tail 队满条件 tail 1 maxSize head Q head datanext 队头 Q tail 队尾 队列的链接表示 链式队列 队头在链头 队尾在链尾 链式队列在进队时无队满问题 但有队空问题 队空条件为head NULL 队列的链接表示 链式队列 typedefstruct linklist head tail linkqueue 链队列结点类型定义 Setnull linkqueue q q head malloc sizeof linklist q head next NULL q tail q head 链队列置队空 intEmpty linkqueue q if q head q tail return True elsereturn False 链队列判队空 datatypeFront linkqueue q if Empty q printf queueisempty n returnNULL elsereturn q head next data 链队列取队头结点 Enqueue linkqueue q datatypex p malloc sizeof linklist p data x p next null q tail next p q tail p 链队列入队 datatypeDequeue linkqueue q datatypee linklist p if Empty q printf queueisempty n returnNULL else p q head next e p data q head next p nextfree p return p 链队列出队 栈和队列作业1 用栈实现以下功能 1 实现任意十进制数转换为二进制数 并测试 2 实现表达式计算 并测试 2 用循环队列模拟舞伴配对问题 在舞会上 男 女各自排成一队 舞会开始时 依次从男队和女队的队头各出一人配成舞伴 如果两队初始人数不等 则较长的那一队中未配对者等待下一轮舞曲 假设初始男 女人数及性别已经固定 舞会的轮数从键盘输入 试模拟解决上述舞伴配对问题 要求 从屏幕输出每一轮舞伴配对名单 如果在该轮有未配对的 能够从屏幕显示下一轮第一个出场的未配对者的姓名