第3章栈和队列栈.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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,A,P,C,B,S,3.下面关于线性表的叙述中，错误的是哪一个？（北方交通大学）,线性表采用顺序储存，必须占用一片连续的存储单元,线性表采用顺序储存，便于进行插入和删除操作,线性表采用链式储存，不必占用一片连续的储存单元,线性表采用链式储存，便于插入和删除操作,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,本章小结,线性表的顺序表示与链式表示:,从空间方面看：顺序存储空间是静态分配的，程序运行之前必须明确规定存储元素得多少，过大造成空间的浪费，过小会溢出。链式存储的空间是动态分配的，利用率高，但是链表中每个结点都要由指针域，因此从存储密度来说是不经济的,从时间方面看：顺序表是一种随机存储的结构，在数据的查找时时间复杂度为O(1)但是插入和删除时为O(n)链式存储在数据的查找时时间复杂度为O(n)但是插入和删除时为O(1),3.1 栈,3.1.1 栈的定义,3.1.2 栈的顺序存储结构及其基本运算的实现,3.1.3 栈的链式存储结构及其基本运算的实现,3.1.4 栈的应用例子,栈是一种操作受限的线性表。,栈是一种只能,在一端,进行,插入或删除,操作的线性表。表中允许进行插入、删除操作的一端称为,栈顶,。,3.1.1 栈的定义,栈顶,栈底,出栈,进栈,栈示意图,栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。,当栈中没有数据元素时,称为,空栈,。,数据的插入操作通常称为,进栈,或,入栈,数据的删除操作通常称为,退栈,或,出栈,。,栈顶top,栈底,botton,出栈,进栈,栈示意图,A1,A2,A3,A4,A5,A6,A7,栈是一种限制存取点的线性结构，即只允许在栈顶进行出栈和入栈的操作。所以，栈还叫做“,后进先出,”表,例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一个栈的输入序列12345，则下列序列中不可能是栈的输出序列的是(南开大学，山东大学，北京理工大学),A 23415,B 54132,C 23145,D 15432,答案：B,例3.3 设n个元素进栈序列是1,2,3,n,其输出序列是p,1,p,2,p,n,若p,1,=3,则p,2,的值,。,(A)一定是2(B)一定是1,(C)不可能是1 (D)以上都不对,答:当p,1,=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p,2,可能是2,也可能是4,n,但一定不能是1。所以本题答案为C。,顺序栈进栈和出栈示意图,TOP 栈指针代表的是物理位序 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)显示栈中元素DispStack(s):从栈顶到栈底顺序显示栈中所有元素。,(8)销毁栈ClearStack(s):释放栈s占用的存储空间。,3.1.2 栈的顺序存储结构及其基本运算实现,假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack:,typedef struct,ElemType dataMaxSize；,int top；/*栈指针*/,SqStack；,在顺序栈中实现栈的基本运算算法:,(1)初始化栈initStack(),建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下:,SqStack*,InitStack(void),s=(SqStack*)malloc(sizeof(SqStack);,s-top=-1;,return s;,4,3,2,1,0,(a)初始化空栈,Top=-1,(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)元素a入栈,d,c,b,a,(c)元素b、c、d入栈,4,3,2,1,0,4,3,2,1,0,Top=3,A b c d e,(3)显示栈中元素DispStack(s),从栈顶到栈底顺序显示栈中所有元素。对应算法如下:,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)出栈Pop(s,&e),在栈不为空的条件下,先将栈顶元素赋给e,然后将栈指针减1。对应算法如下:,int Pop(SqStack*s,ElemType*e),if(s-top=-1)return 0;,/*栈为空的情况,即栈下溢出*/,*e=s-datas-top;,s-top-;,return 1;,(7)取栈顶元素GetTop(s,&e),在栈不为空的条件下,将栈顶元素赋给e。对应算法如下:,int GetTop(SqStack*s,ElemType&e),if(s-top=-1)return 0;,/*栈为空的情况,即栈下溢出*/,e=s-datas-top;,return 1;,(8)销毁栈ClearStack(&s),释放栈s占用的存储空间。对应算法如下:,void ClearStack(SqStack*&s),free(s);,编写一个程序exam3-1，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能,初始化栈,s;,判断栈,s,是否非空,;,依次进栈元素,a,b,c,d,e;,判断栈,s,是否非空,;,输出栈的长度,;,输出从栈顶到栈底元素,;,输出出栈序列,;,判断栈,s,是否为空,;,释放栈,.,3.1.3 栈的链式存储结构及其基本运算的实现,采用链式存储的栈称为链栈,这里采用单链表实现。,链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a,1,、a,2,、a,n,。,链栈示意图,链栈中数据结点的类型LiStack定义如下:,typedef struct linknode,ElemType data;/*数据域*/,struct linknode*next;/*指针域*/,LiStack;,在链栈中,栈的基本运算算法如下:,(1)初始化栈initStack(&s),建立一个空栈s。实际上是创建链栈的头结点,并将其next域置为NULL。对应算法如下:,LiStack*,InitStack(),LiStack*,s,;,s=(LiStack*)malloc(sizeof(LiStack);,s-next=NULL;,return s;,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);,s,(5)显示栈中元素DispStack(s),从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下:,void DispStack(LiStack*s),LiStack*p=s-next;,while(p!=NULL),printf(%c,p-data);,p=p-next;,printf(n);,(6)出栈Pop(&s,&e),在栈不为空的条件下,将头结点后继数据结点的数据域赋给e,然后将其删除。对应算法如下:,int Pop(LiStack*s,ElemType&e),LiStack*p;,if(s-next=NULL)return 0;/*栈空的情况*/,p=s-next;/*p指向第一个数据结点*/,e=p-data;,s-next=p-next;,free(p);,return 1;,(7)取栈顶元素GetTop(s),在栈不为空的条件下,将头结点后继数据结点的数据域赋给e。对应算法如下:,int GetTop(LiStack*s,ElemType&e),LiStack,*p;,if(s-next=NULL)return 0;/*栈空的情况*/,p=,s-next;,e=p-data;,return 1;,(8)销毁栈ClearStack(&s),释放栈s占用的全部存储空间。对应算法如下:,void ClearStack(LiStack*&s),LiStack*p=s-next;,while(p!=NULL),free(s);,s=p;,p=p-next;,编写一个程序exam3-2，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能,初始化链栈,s;,判断链栈,s,是否非空,;,依次进链栈元素,a,b,c,d,e;,判断链栈,s,是否非空,;,输出链栈的长度,;,输出从栈顶到栈底元素,;,输出出链栈序列,;,判断链栈,s,是否为空,;,释放链栈,.,exam3-3 假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。,解:设置一个括号栈,扫描表达式：遇到左括号(包括(、和)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。,若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。,int correct(LiStack*&Head,char exp,int length),int i,flag=1;,char e;,for(i=0;i=0&ch=0&ch(M-2,N-2)*/,int i,j,di,find,k;,top+;/*初始方块进栈*/,Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;,while(top-1)/*栈不空时循环*/,i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;,if(i=M-2&j=N-2)/*找到了出口,输出路径*/,printf(迷宫路径如下:n);,for(k=0;k=top;k+),printf(t(%d,%d),Stackk.i,Stackk.j);,if(k+1)%5=0)printf(n);,printf(n);,return;,find=0;,while(di4&find=0)/*找下一个可走方块*/,di+;,switch(di),case 0:i=Stacktop.i-1;j=Stacktop.j;break;,case 1:i=Stacktop.i;j=Stacktop.j+1;break;,case 2:i=Stacktop.i+1;j=Stacktop.j;break;,case 3:i=Stacktop.i,j=Stacktop.j-1;break;,if(mgij=0)find=1;,if(find=1)/*找到了下一个可走方块*/,Stacktop.di=di;/*修改原栈顶元素的di值*/,top+;/*下一个可走方块进栈*/,Stacktop.i=i;Stacktop.j=j;Stacktop.di=-1;,mgij=-1;/*避免重复走到该方块*/,else /*没有路径可走,则退栈*/,mgStacktop.iStacktop.j=0;,/*让该位置变为其他路径可走方块*/,top-;,printf(没有可走路径!n);,