第3章--栈和队列(顺序栈).ppt

温故知新环节：回顾上次课内容习题实践环节：检查上次课内容新语新知环节：讲授第三章栈的概念重点难点：深刻理解栈是一种操作受限的线性表理解栈指针的含义并熟练使用在线性表长度变化较大或难以估计其储存规模时采用动态链表，否则采用顺序存储对线性表的操作主要是查找而很少做插入和删除操作时，采用顺序存储，否则采用链式存储总之，两种情况各有优缺点，应看具体情况进行讨论。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=s3.下面关于线性表的叙述中，错误的是哪一个？（北方交通大学）线性表采用顺序储存，必须占用一片连续的存储单元线性表采用顺序储存，便于进行插入和删除操作线性表采用链式储存，不必占用一片连续的储存单元线性表采用链式储存，便于插入和删除操作4.某线性表中最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，这样采用（）储存方式最节省时间。（哈尔滨工业大学）A顺序表B单链表5.线性表的逻辑顺序和物理顺序总是一致的这种说法A正确B不正确6.线性表若是采用链式存储，要求内存中可用存储单元的地址A必须连续B部分地址必须连续C一定是不连续的D连续不连续都可以7.非空单链表L的尾结点P满足A.p-next=NULLB.p=NULLC.p-next=LD.p=L3.1栈3.1.1栈的定义3.1.2栈的顺序存储结构及其基本运算的实现3.1.3栈的链式存储结构及其基本运算的实现例3.2一个栈的输入序列12345，则下列序列中不可能是栈的输出序列的是(南开大学，山东大学，北京理工大学)A23415B54132C23145D15432明白为什么说栈是操作受限的线性表吗？假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack:编写一个程序exam3-1，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能初始化栈s;判断栈s是否非空;依次进栈元素a,b,c,d,e;判断栈s是否非空;输出栈的长度;输出从栈顶到栈底元素;输出出栈序列;判断栈s是否为空;**第3章栈和队列3.1栈3.2队列本章小结本节课安排线性表的顺序表示与链式表示:从空间方面看：顺序存储空间是静态分配的，程序运行之前必须明确规定存储元素得多少，过大造成空间的浪费，过小会溢出。链式存储的空间是动态分配的，利用率高，但是链表中每个结点都要由指针域，因此从存储密度来说是不经济的从时间方面看：顺序表是一种随机存储的结构，在数据的查找时时间复杂度为O(1)但是插入和删除时为O(n)链式存储在数据的查找时时间复杂度为O(n)但是插入和删除时为O(1)温故知新:线性表及两种存储方式顺序表、链表温故知新:线性表及两种存储方式顺序表、链表习题实践:线性表及两种存储方式顺序表、链表APCBS习题实践:线性表及两种存储方式顺序表、链表习题实践:线性表及两种存储方式顺序表、链表习题实践:线性表及两种存储方式顺序表、链表(8)插入数据元素ListInsert(L,i,e)思路：先在单链表L中找到第i-1个结点*p,若存在这样的结点,将值为e的结点*s插入到其后。若位序不合法：返回0，否则返回1表示插入intListInsert(LinkList*L,inti,ElemTypee){intj=0;LinkList*p=L-next,*s;while(ji-1p!=NULL)/*查找第i-1个结点*/{ p=p-next;j++;} if(p==NULL)return0;/*未找到位序为i-1的结点*/ else /*找到位序为i-1的结点*p*/ {s=(LinkList*)malloc(sizeof(LinkList)); /*创建新结点*s*/ s-data=e;