第3章栈和队列栈.ppt
《第3章栈和队列栈.ppt》由会员分享,可在线阅读,更多相关《第3章栈和队列栈.ppt(65页珍藏版)》请在三一文库上搜索。
1、1、带头结点的单链表为空的判定条件是 (哈尔滨工业大学) A.H=NULL B.H-next=NULL C.H-next=H D.H!=NULL,2、将图中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=s,3.下面关于线性表的叙述中,错误的是哪一个?(北方交通大学) 线性表采用顺序储存,必须占用一片连续的存储单元 线性表采用顺序储存,便于进行插入和删除操作 线性表采用链式储
2、存,不必占用一片连续的储存单元 线性表采用链式储存,便于插入和删除操作 4.某线性表中最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,这样采用()储存方式最节省时间。(哈尔滨工业大学) A 顺序表 B 双向链表 C 单链表,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,本章小结 线性表的顺序表示与
3、链式表示: 从空间方面看:顺序存储空间是静态分配的,程序运行之前必须明确规定存储元素得多少,过大造成空间的浪费,过小会溢出。链式存储的空间是动态分配的,利用率高,但是链表中每个结点都要由指针域,因此从存储密度来说是不经济的 从时间方面看:顺序表是一种随机存储的结构,在数据的查找时时间复杂度为O(1) 但是插入和删除时为O(n) 链式存储在数据的查找时时间复杂度为O(n) 但是插入和删除时为O(1),结论,在线性表长度变化较大或难以估计其储存规模时采用动态链表,否则采用顺序存储 对线性表的操作主要是查找而很少做插入和删除操作时,采用顺序存储,否则采用链式存储 总之,两种情况各有优缺点,应看具体情
4、况进行讨论。,第3章 栈和队列,3.1 栈,3.2 队列,本章小结,栈和队列的逻辑结构和物理结构,以及他们之间的相互关系 定义与之相适应的算法 设计相应的算法 分析算法的效率,3.1 栈 3.1.1 栈的定义 3.1.2 栈的顺序存储结构及其基本运算的实现 3.1.3 栈的链式存储结构及其基本运算的实现 3.1.4 栈的应用例子,栈是一种操作受限的线性表。 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。,3.1.1 栈的定义,栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。 当栈中没有数据元素时,称为空栈。
5、 数据的插入操作通常称为进栈或入栈,数据的删除操作通常称为退栈或出栈。,栈顶top,栈底 botton,出栈,进栈,栈示意图,栈是一种限制存取点的线性结构,即只允许在栈顶进行出栈和入栈的操作。所以,栈还叫做“后进先出”表,例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。
6、所以本题答案为D。,例3.2一个栈的输入序列12345,则下列序列中不可能是栈的输出序列的是(南开大学,山东大学,北京理工大学),A 23415 B 54132 C 23145 D 15432,答案:B,例3.3 设n个元素进栈序列是1,2,3,n,其输出序列是p1,p2,pn,若p1=3,则p2的值 。 (A) 一定是2 (B) 一定是1 (C) 不可能是1 (D) 以上都不对,答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,n,但一定不能是1。所以本题答案为C。,顺序栈进栈和出栈示意图,TOP 栈指
7、针代表的是物理位序 dataMaxSize 栈空 TOP=-1 栈满 TOP=MaxSize -1 思考:如何表示栈顶元素?,栈的几种基本运算如下: 初始化栈InitStack( ):构造一个空栈s。 进栈Push(s,e):将元素e插入到栈s中作为栈顶元素 (3)求栈的长度StackLength(s):返回栈s中的元素个数。(4)判断栈是否为空StackEmpty(s):若栈s为空,则返回1;否则返回0。,(5) 出栈Pop(s,&e):从栈s中退出栈顶元素,并将其值赋给e。 (6) 取栈顶元素GetTop(s,&e):返回当前的栈顶元素,并将其值赋给e。 (7) 显示栈中元素DispSta
8、ck(s):从栈顶到栈底顺序显示栈中所有元素。 (8) 销毁栈ClearStack(s):释放栈s占用的存储空间。,3.1.2 栈的顺序存储结构及其基本运算实现 假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack: typedef struct ElemType dataMaxSize; int top; /*栈指针*/ SqStack;,在顺序栈中实现栈的基本运算算法: (1) 初始化栈initStack( ) 建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下: SqStack * InitS
9、tack( void ) s=(SqStack *)malloc(sizeof(SqStack); s-top=-1; return s; ,(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) 显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中所有元素。对应
10、算法如下: void DispStack(SqStack *s) int i; for (i=s-top;i=0;i-) printf(“%c “,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) 出栈P
11、op(s, ,(7) 取栈顶元素GetTop(s, ,(8) 销毁栈ClearStack( ,编写一个程序exam3-1,实现顺序栈的各种基本运算,并在此基础上设计一个主程序完成如下功能,初始化栈s; 判断栈s是否非空; 依次进栈元素a,b,c,d,e; 判断栈s是否非空; 输出栈的长度; 输出从栈顶到栈底元素; 输出出栈序列; 判断栈s是否为空; 释放栈.,3.1.3 栈的链式存储结构及其基本运算的实现 采用链式存储的栈称为链栈,这里采用单链表实现。 链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最
12、后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、an。,链栈示意图,链栈中数据结点的类型LiStack定义如下: typedef struct linknode ElemType data; /*数据域*/ struct linknode *next; /*指针域*/ LiStack;,在链栈中,栈的基本运算算法如下: (1) 初始化栈initStack( ,(2) 进栈Push( ,(3) 求栈的长度StackLength(s) 从第一个数据结点开始扫描单链表,用i记录访问的数据结点个数,最后返回i值。对应算法如下: int StackLength(LiStack *s) int
13、 i=0; LiStack *p; p=s-next; while (p!=NULL) i+;p=p-next; return(i); ,(4) 判断栈是否为空StackEmpty(s) 栈S为空的条件是s-next=NULL,即单链表中没有数据结点。对应算法如下: int StackEmpty(LiStack *s) return(s-next=NULL); ,s,(5) 显示栈中元素DispStack(s) 从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下: void DispStack(LiStack *s) LiStack *p=s-next; while (
14、p!=NULL) printf(“%c “,p-data); p=p-next; printf(“n“); ,(6) 出栈Pop( ,(7) 取栈顶元素GetTop(s) 在栈不为空的条件下,将头结点后继数据结点的数据域赋给e。对应算法如下: int GetTop(LiStack *s,ElemType ,(8) 销毁栈ClearStack( ,编写一个程序exam3-2 ,实现顺序栈的各种基本运算,并在此基础上设计一个主程序完成如下功能,初始化链栈s; 判断链栈s是否非空; 依次进链栈元素a,b,c,d,e; 判断链栈s是否非空; 输出链栈的长度; 输出从栈顶到栈底元素; 输出出链栈序列;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 队列
链接地址:https://www.31doc.com/p-2577417.html