数据结构严蔚敏课件第3章

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

第三章栈和队列【课前思考】1.什么是线性结构?简单地说,线性结构是一个数据元素的序列。2.你见过餐馆中一叠一叠的盘子吗?如果它们是按1,2,…,n的次序往上叠的,那么使用时候的次序应是什么样的?必然是依从上往下的次序,即n,…,2,1。它们遵循的是后进先出的规律,这正是本章要讨论的栈的结构特点。3.在日常生活中,为了维持正常的社会秩序而出现的常见现象是什么?是排队。在计算机程序中,模拟排队的数据结构是队列。【学习目标】1.掌握栈和队列这两种抽象数据类型的特点,并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。4.理解递归算法执行过程中栈的状态变化过程。栈和队列是在程序设计中被广泛使用的两种线性数据结构,因此本章的学习重点在于掌握这两种结构的特点,以便能在应用问题中正确使用。【知识点】顺序栈、链栈、循环队列、链队列【重点和难点】【学习指南】在这一章中,主要是学习如何在求解应用问题中适当地应用栈和队列,栈和队列在两种存储结构中的实现都不难,但应该对它们了如指掌,特别要注意它们的基本操作实现时的一些特殊情况,如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为:3.15,3.17,3.19,3.22,3.27,3.28,3.30,3.31,3.32。其中前4个主要是练习栈的应用,后4个主要是有关队列的实现方法的练习。通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型3.1栈3.2栈的应用举例3.4队列目录3.3栈与递归的实现3.1栈一、栈的定义栈(stack)作为一种限定性线性表,是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶(Top),因此栈顶的当前位置是动态变化的,它由一个称为栈顶指针的位置指示器指示。同时表的另一端为固定的一端,被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈,删除操作称为出栈或退栈。插入:最先放入栈中元素在栈底,最后放入的元素在栈顶;删除:最后放入的元素最先删除,最先放入的元素最后删除。栈是一种后进先出(LastInFirstOut)的线性表,简称为LIFO表。an…a2a1进栈出栈栈顶栈底进栈出栈(a)栈的示意图(b)铁路调序栈的表示图3.1栈an…a2a1进栈出栈栈顶栈底进栈出栈(a)栈的示意图(b)铁路调序栈的表示例:设一个栈的输入序列为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。二、栈的主要操作1.初始化栈:InitStack(&S)将栈S置为一个空栈(不含任何元素)。2.进栈:PUSH(&S,X)将元素X插入到栈S中,也称为“入栈”、“插入”、“压入”。3.出栈:POP(&S,&e)删除栈S中的栈顶元素,也称为”退栈”、“删除”、“弹出”。4.取栈顶元素:GETTOP(S,&e)取栈S中栈顶元素。5.判栈空:EMPTY(S)判断栈S是否为空,若为空,返回值为1,否则返回值为0。三、栈的抽象数据类型描述ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系:R1={ai-1,ai|ai-1,ai∈D,i=1,2,…,n}基本操作:InitStack(&S)操作前提:S为未初始化的栈。操作结果:将S初始化为空栈。ClearStack(&S)操作前提:栈S已经存在。操作结果:将栈S置成空栈。StackEmpty(S)操作前提:栈S已经存在。操作结果:若栈S为空,则返回TRUE,否则FALSE。StackLength(S)操作前提:栈S已经存在。操作结果:返回S的元素个数即栈的长度。IsFull(S)操作前提:栈S已经存在。操作结果:判栈满函数,若S栈已满,则函数值为TRUE,否则为FALSE。StackTraverse(S,visit())操作前提:栈S已经存在且非空。操作结果:从栈底到栈顶依次对S底每个元素调用函数visit()。一旦visit()失败,则操作失效。Push(&S,e)操作前提:栈S已经存在。操作结果:在S的顶部插入(亦称压入)元素e;若S栈未满,将e插入栈顶位置,若栈已满,则返回FALSE,表示操作失败,否则返回TRUE。Pop(&S,&e)操作前提:栈S已经存在。操作结果:删除(亦称弹出)栈S的顶部元素,并用e带回该值;若栈为空,返回值为FALSE,表示操作失败,否则返回TRUE。GetTop(S,&e)操作前提:栈S已经存在。操作结果:取栈S的顶部元素。与Pop(&S,&e)不同之处在于GetTop(S,&e)不改变栈顶的位置。}ADTStack1.顺序栈顺序栈是用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时由于栈的操作的特殊性,还必须附设一个位置指针top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置。通常以top=0或top=-1表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下:四、栈的表示和实现#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct{SElemType*base;//在栈构造前和销毁后base值为NULLSElemType*top;//栈顶指针intstacksize;}SqStack;//当前已分配存储空间或简单定义如下:#defineM100ints[M];inttop;图3.2顺序栈中的进栈和出栈Top指向栈顶元素初态:top=-1;空栈,栈中无元素,进栈:top=top+1;s[top]=x;退栈:取s[top];top=top-1;栈满:top=M-1;栈溢出(上溢),不能再进栈(错误状态)top=-1时不能退栈,下溢(正常状态,常作控制条件)(1)构造空顺序栈算法:初始化栈StatusInitStack(SqStack&S){//构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//为栈分配存储空间失败S.top=S.base;//令栈顶指针=栈底指针//设置栈的当前可使用的最大容量S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack2.顺序栈基本操作的实现如下:程序描述://Thisprogramistoinitializeastack#includemalloc.h#includeiostream.h#includeconio.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineERROR0typedefintSElemType;typedefstruct//definestructureSqStack(){SElemType*base;SElemType*top;intstacksize;}SqStack;intInitStack(SqStack&S)//InitStack()sub-function{S.base=(SElemType)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base){printf(“Allocatespacefailure!\n“);return(ERROR);}S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);}//InitStack()endvoidmain()//main()function{SqStackS;if(InitStack(S))printf(Success!Thestackhasbeencreated!\n“);printf(...OK!…\n“);getch();}(2)取顺序栈的栈顶元素StatusGetTop(SqStackS,SElemType&e){//如果栈S空,返回ERROR;如果栈S不空,用e返回栈S的栈顶元素,并返回OK。if(S.top==S.base)returnERROR;//如果栈S为空,则返回ERRORe=*(S.top-1);//将栈顶指针减1后所指向的单元内的值赋给ereturnOK;}//GetTop(3)将元素压入顺序栈算法(进栈)StatusPush(SqStack&S,SElemTypee){//将元素e插入到栈S中,成为新的栈顶元素if(S.top-S.baseS.stacksize){//如果栈满,则追加存储空间S.base=(SElemType*)realloc(S.base,(S.stacksixe+STACKINCREMENT*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//追加存储空间失败S.top=S.base+S.stacksize;//修改栈顶指针S.stacksize+=STACKINCREMENT;//修改当前栈的存储空间}//if结束*S.top++=e;//先将e送入栈顶,然后将栈顶指针加1returnOK;}//Push(4)将元素弹出顺序栈算法(退栈)StatusPop(SqStack&S,SElemType&e){//如果栈S空,返回ERROR;如果栈S不空,删除S栈顶元素,用e返回其值,并返回OK。if(S.top==S.base)returnERROR;//如果栈S为空,则返回ERRORe=*--S.top;//先令top减1,再将top所指单元值赋给ereturnOK;}//Pop(5)判栈空否IntEmpty(SqStackS){//如果栈S空,返回1;如果栈S不空,返回0。if(S.top==S.base)return1;//如果栈S为空,则返回1elsereturn0;//如果栈S为空,则返回0}//Emptyend3.栈的共享有时,一个程序设计中,需要使用多个同一类型的栈,这时候,可能会产生一个栈空间过小,容量发生溢出,而另一个栈空间过大,造成大量存储单元浪费的现象。为了充分利用各个栈的存储空间,这时可以采用多个栈共享存储单元,即给多个栈分配一个足够大的存储空间,让多个栈实现存储空间优势互补。栈1顶栈2顶栈1底栈2底图3-3两个栈共享存储单元示意图栈空:top1=0,top2=M-1;栈满:top1+1=top2两个栈共享存储单元可用如下C语句描述:#defineMAXSIZE100#defineDUSTACKSIZEMAXSIZEtypedefstructDuSqStack{SElemTypedata[MAXSIZE];inttop1;//top1isthepointerofDuSqStackS1inttop2;//top2isthepointerofDuSqStackS2intflag;}DuSqStack;//或:#defineMAXSIZE100Structduseqstack{elemtypedata[maxsize];inttop[2];//两个栈的栈顶指针intflag;}(1)两个栈共享存储单元的进栈算法StatusDuSqStackPush

1 / 109
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功