第3章栈和队列顺序栈.ppt
《第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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 队列 顺序
链接地址:https://www.31doc.com/p-2596713.html