第3章和队列顺序栈

1、第第3 3章章 栈和队列栈和队列 3.1 3.1 栈栈 3.2 3.2 队列队列 本章小结本章小结 温故知新环节：温故知新环节：回顾上次课内容回顾上次课内容习题实践环节：习题实践环节：检查上次课内容检查上次课内容新语新知环节：新语新知环节：讲授第三章栈的概念讲授第三章栈的概念重点难点：重点难点：深刻理解栈是一种操作受限的线性表深刻理解栈是一种操作受限的线性表理解栈指针的含义并熟练使用理解栈指针的含义并熟练使用线性表的顺序表示与链式表示线性表的顺序表示与链式表示:从空间方面看：顺序存储空间是静态分配的，程序从空间方面看：顺序存储空间是静态分配的，程序运行之前必须明确规定存储元素得多少，过大造成运

2、行之前必须明确规定存储元素得多少，过大造成空间的浪费，过小会溢出。链式存储的空间是动态空间的浪费，过小会溢出。链式存储的空间是动态分配的，利用率高，但是链表中每个结点都要由指分配的，利用率高，但是链表中每个结点都要由指针域，因此从存储密度来说是不经济的针域，因此从存储密度来说是不经济的从时间方面看：顺序表是一种随机存储的结构，在从时间方面看：顺序表是一种随机存储的结构，在数据的查找时时间复杂度为数据的查找时时间复杂度为o(1) 但是插入和删除时但是插入和删除时为为o(n) 链式存储在数据的查找时时间复杂度为链式存储在数据的查找时时间复杂度为o(n) 但是插入和删除时为但是插入和删除时为o(1)

3、 在线性表长度变化较大或难以估计其储存在线性表长度变化较大或难以估计其储存规模时采用动态链表，否则采用顺序存储规模时采用动态链表，否则采用顺序存储 对线性表的操作主要是查找而很少做插入对线性表的操作主要是查找而很少做插入和删除操作时，采用顺序存储，否则采用和删除操作时，采用顺序存储，否则采用链式存储链式存储 总之，两种情况各有优缺点，应看具体情总之，两种情况各有优缺点，应看具体情况进行讨论。况进行讨论。1、带头结点的单链表为空的判定条件是、带头结点的单链表为空的判定条件是（哈尔滨工业大学）（哈尔滨工业大学）a.h=nullb.h-next=nullc.h-next=hd.h!=null 2、将

4、图中、将图中s结点加到结点加到p所指结点之后，其语句是：所指结点之后，其语句是：(浙江大学浙江大学)a. s-next=p+1 p-next=sb.(*p).next=s (*s).next=(*p).nextc.s-next=p-next p-next=s-nextd.s-next=p-next p-next=sapcbs3.下面关于线性表的叙述中，错误的是哪一个？下面关于线性表的叙述中，错误的是哪一个？（北方交通大学）（北方交通大学）a) 线性表采用顺序储存，必须占用一片连续的存储线性表采用顺序储存，必须占用一片连续的存储单元单元b) 线性表采用顺序储存，便于进行插入和删除操作线性表采用顺

5、序储存，便于进行插入和删除操作c) 线性表采用链式储存，不必占用一片连续的储存线性表采用链式储存，不必占用一片连续的储存单元单元d) 线性表采用链式储存，便于插入和删除操作线性表采用链式储存，便于插入和删除操作4.某线性表中最常用的操作是存取任一指定序号的某线性表中最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，这样采用（）元素和在最后进行插入和删除运算，这样采用（）储存方式最节省时间。（哈尔滨工业大学）储存方式最节省时间。（哈尔滨工业大学）a 顺序表顺序表b 单链表单链表5.线性表的逻辑顺序和物理顺序总是一致的这种说线性表的逻辑顺序和物理顺序总是一致的这种说法法a 正确正确

6、b 不正确不正确6.线性表若是采用链式存储，要求内存中可用存储线性表若是采用链式存储，要求内存中可用存储单元的地址单元的地址a 必须连续必须连续 b 部分地址必须连续部分地址必须连续c 一定是不连续的一定是不连续的 d 连续不连续都可以连续不连续都可以7.非空单链表非空单链表l的尾结点的尾结点p满足满足a. p-next=nullb. p=nullc. p-next=ld. p=l (8) 插入数据元素插入数据元素listinsert(&l,i,e) 思路：先在单链表思路：先在单链表l中找到第中找到第i-1个结点个结点*p,若存在这若存在这样的结点样的结点,将值为将值为e的结点的结点*

7、s插入到其后。插入到其后。若位序不合法：返回若位序不合法：返回0，否则返回，否则返回1表示插入表示插入 int listinsert(linklist *l,int i,elemtype e) int j=0; linklist *p=l-next,*s; while (jnext; j+; if (p=null) return 0; /*未找到位序为未找到位序为i-1的结点的结点*/else/*找到位序为找到位序为i-1的结点的结点*p*/ s=(linklist *)malloc(sizeof(linklist);/*创建新结点创建新结点*s*/ s-data=e; s-next=p-ne

8、xt; /*将将*s插入到插入到*p之后之后*/ p-next=s; return 1;3.1 栈栈3.1.1 栈的定义栈的定义3.1.2 栈的顺序存储结构及其基本运算的实现栈的顺序存储结构及其基本运算的实现3.1.3 栈的链式存储结构及其基本运算的实现栈的链式存储结构及其基本运算的实现重点难点：重点难点：深刻理解栈是一种操作受限的线性表深刻理解栈是一种操作受限的线性表理解栈指针的含义并熟练使用理解栈指针的含义并熟练使用 栈是一种操作受限的线性表。栈是一种操作受限的线性表。栈是一种只能栈是一种只能在一端在一端进行进行插入或删除插入或删除操作的线性表。操作的线性表。表中允许进行插入、删除操作的一

9、端称为表中允许进行插入、删除操作的一端称为栈顶栈顶。 3.1.1 栈的定义栈的定义出栈出栈进栈进栈栈示意图栈示意图a1a2a3栈顶栈顶top=-1栈是一种限制存取点栈是一种限制存取点的线性结构，即只允的线性结构，即只允许在栈顶进行出栈和许在栈顶进行出栈和入栈的操作。所以，入栈的操作。所以，栈还叫做栈还叫做“后进先出后进先出”表表栈顶栈顶top=0栈顶栈顶top=1栈顶栈顶top=2 例例3.1 设一个栈的输入序列为设一个栈的输入序列为a,b,c,d,则借助则借助一个栈所得到的输出序列不可能是一个栈所得到的输出序列不可能是 。（北京航天。（北京航天航空大学）航空大学）(a) a,b,c,d(b)

10、 d,c,b,a (c) a,c,d,b(d) d,a,b,c 答答:可以简单地推算可以简单地推算,得容易得出得容易得出d,a,b,c是是不可能的不可能的,因为因为d先出来先出来,说明说明a,b,c,d均在栈中均在栈中,按照入栈顺序按照入栈顺序,在栈中顺序应为在栈中顺序应为d,c,b,a,出栈的出栈的顺序只能是顺序只能是d,c,b,a。所以本题答案为。所以本题答案为d。 3.1.1 栈的定义栈的定义(习题实践习题实践) a 23415 b 54132 c 23145 d 15432答案：答案：b3.1.1 栈的定义栈的定义(习题实践习题实践)明白为什么说栈是操作受限的线性表吗？栈是一种逻辑结构

11、有两种存储方式顺序存储顺序存储-顺序栈顺序栈链式存储链式存储-链栈链栈2个问题个问题如何构造顺序栈？如何构造顺序栈？顺序栈上可进行什么基本操作？顺序栈上可进行什么基本操作？3.1.2 顺序栈的结构顺序栈的结构用大片连续单元存储，物理相邻并且逻辑相邻用大片连续单元存储，物理相邻并且逻辑相邻 d c b a 4 3 2 1 0 maxsize=5 top=3 顺序栈结构如下：顺序栈结构如下：1、大片连续单元保存数据、大片连续单元保存数据2、栈指针记录栈顶位置、栈指针记录栈顶位置假设栈的元素个数最大不超过正整数假设栈的元素个数最大不超过正整数maxsize,所所有的元素都具有同一数据类型有的元素都具

12、有同一数据类型elemtype,则可则可用下列方式来定义栈类型用下列方式来定义栈类型sqstack:3.1.2 顺序栈的数据类型顺序栈的数据类型#define maxsize 100typedef char elemtype;typedef struct elemtype datamaxsize； int top；/*栈指针栈指针*/ sqstack；顺序栈进栈和出栈示意图顺序栈进栈和出栈示意图top 栈指针栈指针代表的是物理位序代表的是物理位序栈空栈空 top=-1栈满栈满 top=maxsize -1 思考：如何表示栈顶元素思考：如何表示栈顶元素?3.1.2 顺序栈的基本操作顺序栈的基本操

13、作(1)初始化栈初始化栈initstack( ):(2)进栈进栈push(s,e): (3)求栈的长度求栈的长度stacklength(s): (4)判断栈是否为空判断栈是否为空stackempty(s):(5) 出栈出栈pop(s,&e): (6) 取栈顶元素取栈顶元素gettop(s,&e): (7) 显示栈中元素显示栈中元素dispstack(s):3.1.2 顺序栈的基本操作顺序栈的基本操作 (1) 初始化栈初始化栈initstack( ) 建立一个新的空栈建立一个新的空栈s,s,实际上是将栈顶指针指向实际上是将栈顶指针指向-1-1即可。对应算法如下即可。对应算法如下:

14、 : sqstack * initstack( void ) sqstack *s；s=(sqstack *)malloc(sizeof(sqstack); s-top=-1;return s; 43210(a)初始化空栈初始化空栈top=-13.1.2 顺序栈的基本操作顺序栈的基本操作 (2) 进栈进栈push(s,e) 算法思想：若栈满返回算法思想：若栈满返回 0；在栈不满的条件下；在栈不满的条件下,先先将栈指针增将栈指针增1,然后在该位置上插入元素然后在该位置上插入元素e，返回，返回1。 int push(sqstack *s,elemtype e) if (s-top=maxsize-

15、1) return 0;/*栈满的情况栈满的情况,即栈上溢出即栈上溢出*/s-top+; s-datas-top=e;return 1; a(b)元素元素a入栈入栈dcba(c)元素元素b、c、d入栈入栈4321043210top=3a b c d e3.1.2 顺序栈的基本操作顺序栈的基本操作 (3) 显示栈中元素显示栈中元素dispstack(s) 从栈顶到栈底顺序显示栈中所有元素。对应算从栈顶到栈底顺序显示栈中所有元素。对应算法如下法如下: void dispstack(sqstack *s) int i;for (i=s-top;i=0;i-) printf(%c ,s-datai);

16、printf(n); 3.1.2 顺序栈的基本操作顺序栈的基本操作 (4) 求栈的长度求栈的长度stacklength(s) 返回栈返回栈s中的元素个数中的元素个数,即栈指针加即栈指针加1的结果。对应的结果。对应算法如下算法如下: int stacklength(sqstack *s) return(s-top+1); 3.1.2 顺序栈的基本操作顺序栈的基本操作 (5) 判断栈是否为空判断栈是否为空stackempty(s) 栈栈s为空的条件是为空的条件是s-top=-1。对应算法如下。对应算法如下: int stackempty(sqstack *s) return(s-top=-1); 3.1.2 顺序栈的基本操作顺序栈的基本操作 (6) 出栈出栈pop(s,&e) 在栈不为空的条件下在栈不为空的条件下,先将栈顶元素赋给先将栈顶元素赋给e,然后将然后将栈指针减栈指针减1。对应算法如下。对应算法如下: int pop(sqstack *s,elemtype *e) if (s-top=-1) return 0; /*栈为空的情况栈为空的情况,即栈下溢出即栈下溢出*/*e=s-datas-top;s-top-;return 1; 3.1.2 顺序栈的基本操作顺序栈的基本操作 (7) 取栈顶元素取栈顶元素gettop(s, e) 在栈不为空的条件下在栈不为空