第三章栈的链式存储及其基本应用.pptVIP

第3章 栈和队列 ;温故知新环节：回顾上次课内容 习题实践环节：检查上次课内容 新语新知环节：栈的链式存储及其操作 重点难点： 栈的具体应用;3.1 栈 3.1.1 栈的定义 3.1.2 栈的顺序存储结构及其基本实现 ;顺序栈进栈和出栈示意图;1号题 ;; 设栈的输入序列是1，2，3，4，则 （）不可能是其出栈序列.(中科院计算所) A.1,2,4,3 B.2,1,3,4 C.1,4,3,2 D.4,3,1,2 E.3,2,1,4 ;输入序列为ABC,可以变为CBA，经过的栈操作为（）（中山大学） A.PUSH,POP,PUSH,POP,PUSH,POP B.PUSH,PUSH,PUSH,POP,POP,POP C.PUSH,PUSH,POP,POP,PUSH,POP D.PUSH,POP,PUSH,PUSH,POP,POP;若一个栈以向量V[1…n]存储，初始栈顶指针TOP,则下面X入栈的正确操作为（）（南京理工) A.TOP=TOP+1;V[TOP]=X B.V[TOP]=X;TOP=TOP+1 C.TOP=TOP-1;V[TOP]=X D.V[TOP]=X;TOP=TOP-1;设有一个空栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP，PUSH,PUSH之后，输出序列是（）。栈顶指针的值是（）。 设栈为顺序栈， 每个元素占4个字节。 （西安电子科技）;3.1 栈 3.1.1 栈的定义 3.1.2 栈的顺序存储结构及其基本实现 3.1.3 栈的链式存储结构及其基本实现 3.1.3 栈的应用 ;3.1.3 栈的链式存储结构及其基本运算的实现 采用链式存储的栈称为链栈,这里采用单链表实现。 链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、…、an。;链栈示意图;2个问题; 链栈中数据结点的类型LiStack定义如下: typedef struct linknode { ElemType data; /*数据域*/ struct linknode *next; /*指针域*/ } LiStack;;初始化栈InitStack( ): 进栈Push(s,e): 求栈的长度StackLength(s): 判断栈是否为空StackEmpty(s): 出栈Pop(s,e): 取栈顶元素GetTop(s,e): 显示栈中元素DispStack(s):; (1) 初始化栈initStack() 建立一个空栈s。实际上是创建链栈的头结点,并将其next域置为NULL。对应算法如下: LiStack * InitStack( void ) { LiStack * s; s=(LiStack *)malloc(sizeof(LiStack)); s-next=NULL; return s; }; (2) 进栈Push(s,e) 将新数据结点插入到头结点之后。对应算法如下: void Push(LiStack *s,ElemType e) { LiStack *p; p=(LiStack *)malloc(sizeof(LiStack)); p-data=e; p-next=s-next; /*插入*p结点作为第一个数据结点*/ s-next=p; }; (3) 求栈的长度StackLength(s) 从第一个数据结点开始扫描单链表,用i记录访问的数据结点个数,最后返回i值。对应算法如下: int StackLength(LiStack *s) { int 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); }; (5) 显示栈中元素DispStack(s) 从第一个数据结点开始扫描单链表,并输出当前访问结点的数