《第3章栈和队列顺序栈.ppt》由会员分享，可在线阅读，更多相关《第3章栈和队列顺序栈.ppt（29页珍藏版）》请在三一文库上搜索。
1、第3章 栈和队列,3.1 栈,3.2 队列,本章小结,温故知新环节：回顾上次课内容 习题实践环节：检查上次课内容 新语新知环节：讲授第三章栈的概念 重点难点： 深刻理解栈是一种操作受限的线性表 理解栈指针的含义并熟练使用,本节课安排,线性表的顺序表示与链式表示: 从空间方面看：顺序存储空间是静态分配的，程序运行之前必须明确规定存储元素得多少，过大造成空间的浪费，过小会溢出。链式存储的空间是动态分配的，利用率高，但是链表中每个结点都要由指针域，因此从存储密度来说是不经济的 从时间方面看：顺序表是一种随机存储的结构，在数据的查找时时间复杂度为O(1) 但是插入和删除时为O(n) 链式存储在数据的查
2、找时时间复杂度为O(n) 但是插入和删除时为O(1),温故知新:线性表及两种存储方式顺序表、链表,在线性表长度变化较大或难以估计其储存规模时采用动态链表，否则采用顺序存储 对线性表的操作主要是查找而很少做插入和删除操作时，采用顺序存储，否则采用链式存储 总之，两种情况各有优缺点，应看具体情况进行讨论。,温故知新:线性表及两种存储方式顺序表、链表,1、带头结点的单链表为空的判定条件是 （哈尔滨工业大学） A.H=NULL B.H-next=NULL C.H-next=H D.H!=NULL,习题实践:线性表及两种存储方式顺序表、链表,2、将图中S结点加到P所指结点之后，其语句是：(浙江大学) A
3、. 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=s,习题实践:线性表及两种存储方式顺序表、链表,3.下面关于线性表的叙述中，错误的是哪一个？（北方交通大学） 线性表采用顺序储存，必须占用一片连续的存储单元 线性表采用顺序储存，便于进行插入和删除操作 线性表采用链式储存，不必占用一片连续的储存单元 线性表采用链式储存，便于插入和删除操作 4.某线性表中最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，这样采用（）储
4、存方式最节省时间。（哈尔滨工业大学） A 顺序表 B 单链表,习题实践:线性表及两种存储方式顺序表、链表,5.线性表的逻辑顺序和物理顺序总是一致的这种说法 A 正确 B 不正确 6.线性表若是采用链式存储，要求内存中可用存储单元的地址 A 必须连续 B 部分地址必须连续 C 一定是不连续的 D 连续不连续都可以 7.非空单链表L的尾结点P满足 A. p-next=NULL B. p=NULL C. p-next=L D. p=L,习题实践:线性表及两种存储方式顺序表、链表,(8) 插入数据元素ListInsert( ,if (p=NULL) return 0; /*未找到位序为i-1的结点*/
5、 else /*找到位序为i-1的结点*p*/ s=(LinkList *)malloc(sizeof(LinkList); /*创建新结点*s*/ s-data=e; s-next=p-next; /*将*s插入到*p之后*/ p-next=s; return 1; ,3.1 栈 3.1.1 栈的定义 3.1.2 栈的顺序存储结构及其基本运算的实现 3.1.3 栈的链式存储结构及其基本运算的实现,新语新知环节:,重点难点： 深刻理解栈是一种操作受限的线性表 理解栈指针的含义并熟练使用,栈是一种操作受限的线性表。 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称
6、为栈顶。,新语新知环节- 3.1.1 栈的定义,出栈,进栈,栈示意图,A1,A2,A3,栈是一种限制存取点的线性结构，即只允许在栈顶进行出栈和入栈的操作。所以，栈还叫做“后进先出”表,例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先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。,新语新知环节- 3
7、.1.1 栈的定义(习题实践),例3.2一个栈的输入序列12345，则下列序列中不可能是栈的输出序列的是(南开大学，山东大学，北京理工大学),A 23415 B 54132 C 23145 D 15432,答案：B,新语新知环节- 3.1.1 栈的定义(习题实践),明白为什么说栈是操作受限的线性表吗？,栈是一种逻辑结构有两种存储方式 顺序存储-顺序栈 链式存储-链栈,2个问题,如何构造顺序栈？,顺序栈上可进行什么基本操作？,新语新知环节- 3.1.2 顺序栈的结构,用大片连续单元存储，物理相邻并且逻辑相邻,顺序栈结构如下： 1、大片连续单元保存数据 2、栈指针记录栈顶位置,假设栈的元素个数最大
8、不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack:,新语新知环节- 3.1.2 顺序栈的数据类型,#define MaxSize 100 typedef char ElemType; typedef struct ElemType dataMaxSize； int top； /*栈指针*/ SqStack；,顺序栈进栈和出栈示意图,TOP 栈指针代表的是物理位序 栈空 TOP=-1 栈满 TOP=MaxSize -1 思考：如何表示栈顶元素?,新语新知环节- 3.1.2 顺序栈的基本操作,初始化栈InitStack( ): 进栈
9、Push(s,e): 求栈的长度StackLength(s): 判断栈是否为空StackEmpty(s): (5) 出栈Pop(s,&e): (6) 取栈顶元素GetTop(s,&e): (7) 显示栈中元素DispStack(s):,新语新知环节- 3.1.2 顺序栈的基本操作,(1) 初始化栈initStack( ) 建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下: SqStack * InitStack( void ) SqStack *s； s=(SqStack *)malloc(sizeof(SqStack); s-top=-1; return s; ,新语新知环节
10、- 3.1.2 顺序栈的基本操作,(2) 进栈Push(s,e) 算法思想：若栈满返回 0；在栈不满的条件下,先将栈指针增1,然后在该位置上插入元素e，返回1。 int Push(SqStack *s,ElemType e) if (s-top=MaxSize-1) return 0; /*栈满的情况,即栈上溢出*/ s-top+; s-datas-top=e; return 1; ,a b c d e,新语新知环节- 3.1.2 顺序栈的基本操作,(3) 显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中所有元素。对应算法如下: void DispStack(SqStack *s
11、) int i; for (i=s-top;i=0;i-) printf(“%c “,s-datai); 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-to
12、p=-1); ,新语新知环节- 3.1.2 顺序栈的基本操作,(6) 出栈Pop(s, ,新语新知环节- 3.1.2 顺序栈的基本操作,(7) 取栈顶元素GetTop(s, e) 在栈不为空的条件下,将栈顶元素赋给e。对应算法如下: int GetTop(SqStack *s,ElemType *e) if (s-top=-1) return 0; /*栈为空的情况,即栈下溢出*/ *e=s-datas-top; return 1; ,新语新知环节- 3.1.2 顺序栈的基本操作,编写一个程序exam3-1，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能,初始化栈s; 判断栈s是否非空; 依次进栈元素a,b,c,d,e; 判断栈s是否非空; 输出栈的长度; 输出从栈顶到栈底元素; 输出出栈序列; 判断栈s是否为空;,