第3章栈和队列温故知新环节：回顾上次课内容习题实践环节：检查上次课内容新语新知环节：讲授第三章栈的概念重点难点：深刻理解栈是一种操作受限的线性表理解栈指针的含义并熟练使用线性表的顺序表示与链式表示:从空间方面看：顺序存储空间是静态分配的，程序运行之前必须明确规定存储元素得多少，过大造成空间的浪费，过小会溢出。链式存储的空间是动态分配的，利用率高，但是链表中每个结点都要由指针域，因此从存储密度来说是不经济的从时间方面看：顺序表是一种随机存储的结构，在数据的查找时时间复杂度为O(1)但是插入和删除时为O(n)链式存储在数据的查找时时间复杂度为O(n)但是插入和删除时为O(1)在线性表长度变化较大或难以估计其储存规模时采用动态链表，否则采用顺序存储对线性表的操作主要是查找而很少做插入和删除操作时，采用顺序存储，否则采用链式存储总之，两种情况各有优缺点，应看具体情况进行讨论。1、带头结点的单链表为空的判定条件是（哈尔滨工业大学）A.H=NULLB.H->next=NULLC.H->next=HD.H!=NULL5.线性表的逻辑顺序和物理顺序总是一致的这种说法A正确B不正确6.线性表若是采用链式存储，要求内存中可用存储单元的地址A必须连续B部分地址必须连续C一定是不连续的D连续不连续都可以7.非空单链表L的尾结点P满足A.p->next=NULLB.p=NULLC.p->next=LD.p=L(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(j<i-1&&p!=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;s->next=p->next;/*将*s插入到*p之后*/p->next=s;return1;}}3.1栈3.1.1栈的定义3.1.2栈的顺序存储结构及其基本运算的实现3.1.3栈的链式存储结构及其基本运算的实现栈是一种操作受限的线性表。栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。出栈例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例3.2一个栈的输入序列12345，则下列序列中不可能是栈的输出序列的是(南开大学，山东大学，北京理工大学)明白为什么说栈是操作受限的线性表吗？2个问题新语新知环节---3.1.2顺序栈的结构假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack:顺序栈进栈和出栈示意图初始化栈InitStack():进栈Push(s,e):求栈的长度StackLength(s):判断栈是否为空StackEmpty(s):(5)出栈Pop(s,&e):(6)取栈顶元素GetTop(s,&e):(7)显示栈中元素DispStack(s):(1)初始化栈initStack()建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下:SqStack*InitStack(void){SqStack*s；s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;returns;}(2)进栈Push(s,e)算法思想：若栈满返回0；在栈不满的条件下,先将栈指针增1,然后在该位置上插入元素e，返回1。intPush(SqStack*s,ElemTypee){if(s->top==MaxSize-1)return0;/*栈满的情况,即栈上溢出*/s->top++;s->data[s->top]=e;return1;}(3)显示栈中元素DispStack(s)从栈顶到栈底顺序显示栈中所有元素。对应算法如下:voidDispStack(SqStack*s){inti;for(i=s->top;i>=0;i-