3.ppt数据结构.ppt

3.1 栈 3.1.1 抽象数据类型栈的定义 1、栈(Stack)的定义 　栈是限定仅在表尾进行插入和删除操作的线性表。 术语 栈底(bottom) ——栈的表头 栈顶(top)——栈的表尾 空栈——没有元素的栈 入栈(push) ——向栈顶压入元素 出栈(pop) ——从栈顶弹出元素 3.1.1 抽象数据类型栈的定义 2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 3.1.1抽象数据类型栈的定义 2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ 3.1.1抽象数据类型栈的定义 2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ 3.1.1 抽象数据类型栈的定义 2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ 3.1.1 抽象数据类型栈的定义 2、栈的运算演示 (1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。 (2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ 请大家思考如下问题 结合书上图3.1（b）铁路调度站示意图，如果有编号分别为1，2，3，4的四列火车顺序开过来，如果你是调度，有多少种出站顺序？分别是什么？ 14种出站顺序 1234、1243、1324、1342、1432、 2134、2143、2314、2341、2431、 3214、3241、3421、4321 推广到一般情况： 例1：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹出一个即可。 例3（严题集3.1）一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？ 顺序栈——栈的顺序存储结构 顺序栈是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。 顺序栈——栈的顺序存储结构 顺序栈的基本操作 相应算法的基本思想 可设这个输入缓冲区为一个栈结构，每当从终端接受一个字符之后先作如下判别： （1）非#和@ 则压入栈 （2）# 删除栈顶元素 （3）@ 清空栈 作业(十一后交) 1简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 2描述以下三个概念的区别：头指针，头结点，首结点。 3试写一算法，实现顺序表的就地逆置，即利用原表的存储空间(a1,a2…an)将线性表逆置为(an…a2,a1) 。 4 编写实现将10进制 树转化为d进制的C语言程序 定 义 链队列：基本操作的实现 无队满问题(除非分配不出内存), 空间可扩充 引入头结点(一定需要吗？) 链队列讨论 循环队列 队列的顺序存储 约定与类型定义：Q.front和Q.rear的含义 删除：避免大量的移动-头指针增1 问题：假上溢?首尾相接的环（钟） 基本操作的实现 初始化空队：Q.front=Q.rear=0; 入队：判断是否队满；非队满时，Q.rear位置放新插入的元素, Q.rear++ 出队：判断是否队空，非队空时，Q.front位置为待删除的元素, Q.front++ 队空条件：Q.front == Q.rear 队满条件：Q.rear == MAXQSIZE 问题：假上溢() 实现：用一维数组实现sq[M] 存在问题: 设数组维数为M，则：队首固定，每次出队剩 余元素向下移动——浪费时间 解决方案: 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后, 若rear+1==M,则令rear=0; 假上溢的解决办法把顺序队列看成首尾相接的环(钟表)-循环队列 基本操作的实现 入队：Q.rear = ( Q.rear+1)%MAXQSIZE 出队：Q.front = ( Q.front+1)%MAXQSIZE 队空条件：Q.front == Q.rear 由于出队Q.front追上了Q.rear 队满条件：Q.front == Q.rear 由于入队Q.rear追上了Q