《栈和队列栈》ppt课件

《《栈和队列栈》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、带头结点的单链表为空的判定条件是（哈尔滨工业大学）A.H=NULLB.H->next=NULLC.H->next=HD.H!=NULL2、将图中S结点加到P所指结点之后，其语句是：(浙江大学)A.s->next=p+1p->next=sB.(*p).next=s(*s).next=(*p).nextC.s->next=p->nextp->next=s->nextD.s->next=p->nextp->next=sAPCBS3.下面关于线性表的叙述中，错误的是哪一个？（北方交通大学）线性表采用顺序储存，必须占用一片连续的存储单元线性表采用顺序储存，便于进行插入和删除操作线

2、性表采用链式储存，不必占用一片连续的储存单元线性表采用链式储存，便于插入和删除操作4.某线性表中最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，这样采用（）储存方式最节省时间。（哈尔滨工业大学）A顺序表B双向链表C单链表5.线性表的逻辑顺序和物理顺序总是一致的这种说法A正确B不正确6.线性表若是采用链式存储，要求内存中可用存储单元的地址A必须连续B部分地址必须连续C一定是不连续的D连续不连续都可以7.非空循环单链表L的尾结点P满足A.p->next=NULLB.p=NULLC.p->next=LD.p=L本章小结线性表的顺序表示与链式表示:从空间方面看：顺序

3、存储空间是静态分配的，程序运行之前必须明确规定存储元素得多少，过大造成空间的浪费，过小会溢出。链式存储的空间是动态分配的，利用率高，但是链表中每个结点都要由指针域，因此从存储密度来说是不经济的从时间方面看：顺序表是一种随机存储的结构，在数据的查找时时间复杂度为O(1)但是插入和删除时为O(n)链式存储在数据的查找时时间复杂度为O(n)但是插入和删除时为O(1)结论在线性表长度变化较大或难以估计其储存规模时采用动态链表，否则采用顺序存储对线性表的操作主要是查找而很少做插入和删除操作时，采用顺序存储，否则采用链式存储总之，两种情况各有优缺点，应看具体情况进行讨论。第3章栈和队列

4、3.1栈3.2队列本章小结栈和队列的逻辑结构和物理结构，以及他们之间的相互关系定义与之相适应的算法设计相应的算法分析算法的效率3.1栈3.1.1栈的定义3.1.2栈的顺序存储结构及其基本运算的实现3.1.3栈的链式存储结构及其基本运算的实现3.1.4栈的应用例子栈是一种操作受限的线性表。栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。3.1.1栈的定义栈顶栈底出栈进栈栈示意图栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。数据的插入操作通常称为进栈或入栈,数

5、据的删除操作通常称为退栈或出栈。栈顶top栈底botton出栈进栈栈示意图A1A2A3A4A5A6A7栈是一种限制存取点的线性结构，即只允许在栈顶进行出栈和入栈的操作。所以，栈还叫做“后进先出”表例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.2一

6、个栈的输入序列12345，则下列序列中不可能是栈的输出序列的是(南开大学，山东大学，北京理工大学)A23415B54132C23145D15432答案：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栈指针—代表的是物理位序data[MaxSize]

7、栈空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)显示栈中元素DispS