数据结构 3章栈和队.ppt

2010 7 21 数据结构 第三章栈和队列引言 对线性表L a1 a2 an 可在任意第i i 1 2 n n 1 个位置插入新元素 或删除任意第i i 1 2 n 个元素受限数据结构 插入和删除受限制的线性表 1 栈 stack 2 队列 queue 3 1栈 stack 3 1 1栈的定义和操作1 定义和术语 栈 限定在表尾作插入 删除操作的线性表 a1 a2 an 插入元素 进栈 删除元素 出栈 表头表尾 栈底 栈顶 栈顶 top 栈底 bottom 出栈 pop 进栈 push 进栈 插入一个元素到栈中 或 入栈 推入 压入 push 出栈 从栈删除一个元素 或 退栈 上托 弹出 pop 栈顶 表中允许插入 删除元素的一端 表尾 栈顶元素 处在栈顶位置的元素 栈底 表中不允许插入 删除元素的一端 空栈 不含元素的栈 栈的示意图 栈的元素的进出原则 后进先出 LastInFirstOut 栈的别名 后进先出 表 LIFO 表 反转存储器 地窖 2 栈的基本操作 1 Initstack s 置s为空栈 2 Push s e 元素e进栈s 若s已满 则发生溢出 若不能解决溢出 重新分配空间失败 则插入失败 3 Pop s e 删除栈s的顶元素 并送入e 若s为空栈 发生 下溢 underflow 为空栈时 表示某项任务未开始或已完成 4 Gettop s e 栈s的顶元素拷贝到e 若s为空栈 则结束拷贝 5 Empty s 判断s是否为空栈 若s为空栈 则Empty s 为true 否则为false 1 输入A B C 产生输出A B C的过程 B C 1 A进栈 B C 2 A出栈 C 3 B进栈 4 B出栈 5 C进栈 6 C出栈 C A B C A A B A B A 2 输入A B C 产生输出C B A的过程 B C 1 A进栈 C 2 B进栈 3 C进栈 4 C出栈 5 B出栈 6 A出栈 C B A C C B 3 输入A B C 产生输出B C A的过程 B C 1 A进栈 C 2 B进栈 C 3 B出栈 4 C进栈 5 C出栈 6 A出栈 B C A B B C B 当A B C依次进栈 C出栈后 由于栈顶元素是B 栈底元素是A 而A不能先于B出栈 所以不能在输出序列中 使A成为C的直接后继 即不可能由输入A B C产生输出C A B 一般地 输入序列 ai aj ak 到栈中 不能得到输出序列 ak ai aj 1 初始状态 2 A B C进栈 3 C出栈 C A B C 4 输入A B C 不能产生输出C A B 设依次输入元素A B C到栈中 可得哪几种输出 设依次输入元素C B A到栈中 可得哪几种输出 A B C 1 A B C 2 A C B 3 B A C 4 B C A 5 C A B 6 C B A C B A 1 A B C 2 A C B 3 B A C 4 B C A 5 C A B 6 C B A 讨论 假定输入元素A B C D到栈中 能得当哪几种输出 不能得到哪几种输出序列 1 A B C D 7 B A C D 13 C A B D 19 D B C A 2 A B D C 8 B A D C 14 C A D B 20 D B A C 3 A C B D 9 B C A D 15 C B A D 21 D C B A 4 A C D B 10 B C D A 16 C B D A 22 D C A B 5 A D B C 11 B D A C 17 C D A B 23 D A B C 6 A D C B 12 B D C A 18 C D B A 24 D A C B共5 5 3 1 14种输出序列 A B C D 输入 输出 5种 5种 3种 1种 顺序栈的基本操作及算法 顺序栈的类型定义如下所示 defineSackSize100typedefstruct Datatypedata SackSize inttop SeqStack定义一个指向顺序栈的指针 SeqStack s 3 1 2栈的存储表示和操作实现1 顺序栈 用顺序空间表示的栈 假设栈空间为data 0 SackSize 1 1 顶指针指向顶元素所在位置 top 栈顶指针 栈顶 栈底 SackSize 1n10 SackSize 110 1 自由区 自由区 a 非空栈 b 空栈 s top 1若删除元素 将发生 下溢 序号 top 序号 top 栈顶 栈底 SackSize 110 c 满栈 s top SackSize 1若插入元素 将发生 上溢 Overflow 2 操作实现 1 置空栈 首先建立栈空间 然后初始化栈顶指针 SeqStack InitStack SeqStack s s malloc sizeof SeqStack s top 1 returns 2 判空栈intStackEmpty SeqStack s returnS top 1 3 判满栈intStackFull SeqStack s returns top SackSize 1 4 入栈voidPush SeqStack s datatypex if StackFull s Error Stackoverflow 栈满不能入栈 s top s data s top x 5 出栈DataTypePop SeqStack s datatype x if StackEmpty s Error Stackunderflow 栈空不能出栈 returns data s top 返回 栈顶指针减1 6 取栈顶元素datatypeTop SeqStack SeqStack s if EmptyStack s Error Stackisempty 栈空 return s data s top 以下几点说明 1 对于顺序栈 入栈时 首先判断栈是否满了 栈满的条件为 s top StackSize 1 栈满时 不能入栈 否则出现空间溢出 引起错误 这种现象称为上溢 2 出栈和读栈顶元素操作 先判断栈是否为空 为空时不能操作 否则产生错误 通常栈空时常作为一种控制转移的条件 2 链式栈 使用不带表头结点的单链表 1 结点和指针的定义structnode ElemTypedata data为抽象元素类型structnode next next为指针类型 top NULL 初始化 置top为空栈 2 非空链式栈的一般形式 datanext top 栈顶 栈底 3 链式栈的进栈算法 压入元素e到top为顶指针的链式栈structnode push link structnode top Elemtypee structnode p intleng sizeof structnode 确定新结点空间的大小p structnode malloc leng 生成新结点p data e 装入元素ep next top 插入新结点top p top指向新结点returntop 返回指针top 栈底 top p X 栈底 top 栈顶 栈顶 1 插入e之前 2 插入e之后 3 1 3栈的应用举例栈的基本用途 保存暂时不用的数据或存储地址 数制转换问题例 给定十进制数N 1348 转换为八进制数R 25041 依次求余数 并送入栈中 1 r1 1348 8 4 求余n1 1348 8 168 整除 2 r2 168 8 0 求余n2 168 8 21 整除 3 r3 21 8 5 求余n3 21 8 2 整除 4 r4 2 8 2 求余n4 2 8 0 整除2 依次退栈 得R 2504 1 4进栈 2 0进栈 3 5进栈 4 2进栈 十进制数N转换为B进制数算法思想 N 0r N Br入栈N N B算法 typedefintDataType voidszzh intN intB inti SeqStacks InitStack printf d i y n 栈非空 出栈显示 3 2队列 排队 queue 3 2 1队列及其操作1 定义和术语 队列 只允许在表的一端删除元素 在另一端插入元素的线性表 空队列 不含元素的队列 队首 队列中只允许删除元素的一端 head front 队尾 队列中只允许插入元素的一端 rear tail 队首元素 处于队首的元素 队尾元素 处于队尾的元素 进队 插入一个元素到队列中 又称 入队 出队 从队列删除一个元素 2 元素的进出原则 先进先出 FirstInFirstOut 队列的别名 先进先出 表 FIFO 表 排队 queue 队列示意图 head front tail rear 队首队尾 进队 出队 3 队列的基本操作 1 InitQueue q 初始化 将q置为空队列 2 QueueEmpty q 判断q是否为空队列 3 EnQueue q e 将e插入队列q的尾端 4 DeQueue q e 取走队列q的首元素 送e 5 QetHead q e 读取队列q的首元素 送e 6 QueueClear q 置q为空队列 012345 012345 012345 A进队 fr B C D进队 f r f r 3 B C D进队后 3 2 2队列的顺序表示和实现 1 初始化后 2 A进队后 假设用一维数组Q 0 5 表示顺序队列1 顺序队列与 假溢出设f指向队头元素 r指向队尾元素 空队列 012345 012345 f r E F进队 f r G进队 假溢出 解决假溢出的办法之一 移动元素 6 D E F移到前端后 012345 f r G进队 4 A B C出队之后 5 E F依次进队之后 012345 f r 2 循环队列与解决假溢出的办法之二 7 G进队之后 解决方法 将存储队列元素的一维数组首尾相接 形成一个环状 将这种形式表示的队列称之为循环队列 5 中用循环队列表示 0 1 2 3 4 5 D E F G r f f f 1 QueueSiz r r 1 QueueSize QueueSize为数组单元数目 2 3 4 5 0 1 F G D E H I进队 2 3 4 5 0 1 F G D E I H H I进队之后 f r f r 满队列 将Q 0 5 解释为循环队列的示意图 D E F G H I出队 空队列 f r 0 1 2 3 4 5 当f r时 怎样判断队列是空还是满 当f r 判断队空和满的方法 a 设置一个布尔量以区别队空队满 b 少用一个元素的空间 约定入队前 测试尾指针在循环意义下加1后是否等于头指针 相等 队满 c 使用计数器记录队中元素的总数 下面以第三种方法定义循环队的类型 defineQueueSize100typedefcharDataType DataType类型依赖具体应用typedefstruct datatypedata QueueSize 数据的存储区 intfront rear intcount 计数器 记录队中元素的个数 CirQueue 循环队 循环队列的6种基本运算 队头队尾指针 非空时 队尾指针指向队尾元素下一个位置 1 置队空voidInitQueue CirQueue Q Q front Q rear 0 Q count 0 2 判队空intQueueEmpty CirQueue Q returnQ count 0 3 判队满intQueueFull CirQueue Q returnQ count QueueSize 4 入队voidEnQueue CirQueue Q DataTypex if QueueFull Q Error Queueoverflow 队满上溢Q count Q data Q rear x 新元素x入队尾Q rear Q rear 1 QueueSize 5 出队DataTypeDeQueue CirQueue Q DataTypetemp if QueueEmpty Q Error Queueundeflow 队空下溢temp Q data Q front Q count Q front Q front 1 QueueSize returntemp 6 取队头元素DataTypeQueueFront CirQueue Q if QueueEmpty Q Error Queueisempty returnQ data Q front 3 2 3链式队列 用不带表头结点的单链表表示队列1 一般形式 1 空队列 2 非空队列 其中 Q front 队头 首 指针 指向队头结点 Q rear 队尾指针 指向队尾结点 datanext 队头结点 队尾结点 Q frontQ rear Q Q frontQ rear Q 2 定义结点类型 1 存放元素的结点类型typedefstructqueuenode DataTypedata data为抽象元素类型structqueuenode next next为指针类型 QueueNode 结点类型 指针类型 2 由头 尾指针组成的结点类型typedefstruct QueueNode front 头指针QueueNode rear 尾指针 LinkQueue 链