第3章栈和队列顺序栈ppt课件

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=s B.(*p).next=s (*s).next=(*p).next C.s-next=p-next p-next=s-next D.s-next=p-next p-next=sAPCBS3.下面关于线性表的表达中，错误的选项是哪一个？下面关于线性表的表达中，错误的选项是哪一个？北方交通大学北方交通大学线性表采用顺序储存，必需占用一片延续的存储单线性表采用顺序储存，必需占用一片延续的存储单元元线性表采用顺序储存，便于进展插入和删除操作线性表采用顺序储

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

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的结点的结点*s插入到其后。插入到其后

7、。假设位序不合法：前往假设位序不合法：前往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-next; /*将*s插入到*p之后*/ p-next=s;

8、return 1;3.1 栈栈3.1.1 栈的定义栈的定义3.1.2 栈的顺序存储构造及其根本运算的实现栈的顺序存储构造及其根本运算的实现3.1.3 栈的链式存储构造及其根本运算的实现栈的链式存储构造及其根本运算的实现重点难点：重点难点：深化了解栈是一种操作受限的线性表深化了解栈是一种操作受限的线性表了解栈指针的含义并熟练运用了解栈指针的含义并熟练运用 栈是一种操作受限的线性表。栈是一种操作受限的线性表。栈是一种只能在一端进展插入或删除操作的线栈是一种只能在一端进展插入或删除操作的线性表。表中允许进展插入、删除操作的一端称性表。表中允许进展插入、删除操作的一端称为栈顶。为栈顶。 出栈出栈进栈进

9、栈栈表示图栈表示图A1A2A3栈顶栈顶top=-1栈是一种限制存取点栈是一种限制存取点的线性构造，即只允的线性构造，即只允许在栈顶进展出栈和许在栈顶进展出栈和入栈的操作。所以，入栈的操作。所以，栈还叫做栈还叫做“后进先出后进先出表表栈顶栈顶top=0栈顶栈顶top=1栈顶栈顶top=2 例3.1 设一个栈的输入序列为A,B,C,D,那么借助一个栈所得到的输出序列不能够是 。北京航天航空大学(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C 答答:可以简单地推算可以简单地推算,得容易得出得容易得出D,A,B,C是是不能够的不能够的,由于由于D先出来先出来,

10、阐明阐明A,B,C,D均在栈中均在栈中,按照入栈顺序按照入栈顺序,在栈中顺序应为在栈中顺序应为D,C,B,A,出栈的出栈的顺序只能是顺序只能是D,C,B,A。所以此题答案为。所以此题答案为D。 A 23415 B 54132 C 23145 D 15432答案：答案：B明白为什么说栈是操作受限的线性表吗？栈是一种逻辑构造有两种存储方式顺序存储-顺序栈链式存储-链栈2个问题个问题如何构造顺序栈？如何构造顺序栈？顺序栈上可进展什么根本操作？顺序栈上可进展什么根本操作？用大片延续单元存储，物理相邻并且逻辑相邻用大片延续单元存储，物理相邻并且逻辑相邻 d c b a 4 3 2 1 0 MaxSize

11、=5 Top=3 顺序栈构造如下：顺序栈构造如下：1、大片延续单元保管数据、大片延续单元保管数据2、栈指针记录栈顶位置、栈指针记录栈顶位置假设栈的元素个数最大不超越正整数假设栈的元素个数最大不超越正整数MaxSize,一一切的元素都具有同一数据类型切的元素都具有同一数据类型ElemType,那么那么可用以下方式来定义栈类型可用以下方式来定义栈类型SqStack:#define MaxSize 100typedef char ElemType;typedef struct ElemType dataMaxSize； int top；/*栈指针栈指针*/ SqStack；顺序栈进栈和出栈表示图顺序

12、栈进栈和出栈表示图TOP 栈指针栈指针代表的是物理位序代表的是物理位序栈空栈空 TOP=-1栈满栈满 TOP=MaxSize -1 思索：如何表示栈顶元素思索：如何表示栈顶元素? 初始化栈初始化栈InitStack( ): 进栈进栈Push(s,e): 求栈的长度求栈的长度StackLength(s): 判别栈能否为空判别栈能否为空StackEmpty(s): (5) 出栈出栈Pop(s,&e): (6) 取栈顶元素取栈顶元素GetTop(s,&e): (7) 显示栈中元素显示栈中元素DispStack(s): (1) 初始化栈初始化栈initStack( ) 建立一个新的空栈

13、建立一个新的空栈s,实践上是将栈顶指针指向实践上是将栈顶指针指向-1即可。对应算法如下即可。对应算法如下: SqStack * InitStack( void ) SqStack *s；s=(SqStack *)malloc(sizeof(SqStack); s-top=-1;return s; 43210(a)初始化空栈初始化空栈Top=-1 (2) 进栈进栈Push(s,e) 算法思想：假设栈满前往算法思想：假设栈满前往 0；在栈不满的条件下；在栈不满的条件下,先将栈指针增先将栈指针增1,然后在该位置上插入元素然后在该位置上插入元素e，前往，前往1。 int Push(SqStack *s

14、,ElemType e) if (s-top=MaxSize-1) return 0;/*栈满的情况栈满的情况,即栈上溢出即栈上溢出*/s-top+; s-datas-top=e;return 1; a(b)元素元素a入栈入栈dcba(c)元素元素b、c、d入栈入栈4321043210Top=3a b c d e (3) 显示栈中元素显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中一切元素。对应算从栈顶到栈底顺序显示栈中一切元素。对应算法如下法如下: void DispStack(SqStack *s) int i;for (i=s-top;i=0;i-) printf(%c ,

15、s-datai);printf(n); (4) 求栈的长度求栈的长度StackLength(s) 前往栈前往栈s中的元素个数中的元素个数,即栈指针加即栈指针加1的结果。对应的结果。对应算法如下算法如下: int StackLength(SqStack *s) return(s-top+1); (5) 判别栈能否为空判别栈能否为空StackEmpty(s) 栈栈S为空的条件是为空的条件是s-top=-1。对应算法如下。对应算法如下: int StackEmpty(SqStack *s) return(s-top=-1); (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; (7) 取栈顶元素取栈顶元素GetTop(s,