《第3章栈和队列.ppt》由会员分享，可在线阅读，更多相关《第3章栈和队列.ppt（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3.1 栈的类型定义栈的类型定义3.2 栈类型的实现栈类型的实现3.3 栈的应用举例栈的应用举例3.4 队列的类型定义队列的类型定义3.5 队列类型的实现队列类型的实现3.1 栈的类型定义一、栈的定义一、栈的定义 栈栈(stack)(stack)作为一种限定性线性表，是将线性表的插插入入和删删除除运算限制为仅在表的一端仅在表的一端进行。栈顶栈顶(Top):(Top):表中允许进行插入、删除操作的一端表中允许进行插入、删除操作的一端栈底栈底(Bottom):(Bottom):同时表的另一端为固定的一端同时表的另一端为固定的一端空栈空栈:栈中没有元素。栈的插入操作被称为进栈、入栈或压入进栈、入栈或
2、压入栈的删除操作被称为出栈、退栈或弹出出栈、退栈或弹出。栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。例例：设设一一个个栈栈的的输输入入序序列列为为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二、栈的抽象数据类型定义二、栈的抽象数据类型定义 ADT Stack 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 约定an 端为栈
3、顶，a1 端为栈底。基本操作：基本操作：ADT Stack置空栈setnull(s)：将栈S设置成空栈，即不管栈的原来状态如何一律置为空栈；判栈空empty(s)：返回一个布尔值，当栈S为空时返回1，否则返回0；push(s,x)把元素x压入栈s中，成为新的栈顶元素a1a2anx pop(s，e)从栈顶弹出栈顶元素并返回1（成功），当栈S为空时返回0（不成功）a1a2anan-1 gettop(s,e)栈不空时读取栈s的栈顶元素，并返回1（成功），当栈s为空时返回0（不成功）a1a2an 3.2 栈类型的实现顺序栈顺序栈链栈链栈/-栈的顺序存储表示栈的顺序存储表示-#define MAXSIZ
4、E 100typedef struct elemtype dataMAXSIZE;int top;seqstack;seqstack*s;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。栈顶指针top与数据元素之间的关系v通常把0下标端设为栈底，栈空条件：栈顶指针top=-1栈满条件：栈顶指针top=MAXSIZE-1；v入栈时：s-top+，然后数据元素进栈；v出栈时在读出栈顶数据元素后，s-top-。v在栈满时做入栈操作会产生空间不足的情况，简称上溢（overflow）；v而在栈空时做出栈操作会产生无元素可出的情况，简称下溢（underflow）。v上溢和下溢两种情况均应该避免
5、，而栈空在应用中通常作为算法（或程序）的控制转移条件。顺序栈的基本运算空栈操作置空栈算法 void setnull(seqstack*s)/*不不论论栈栈S状状态态如如何何，都置都置top为为-1*/s-top=-1;判栈空算法 int empty(seqstack*s)/*依依top值值，在在空空栈栈时返回时返回1，否则返回，否则返回0*/if(s-top=-1)return 1;else return 0;顺序栈的基本运算进栈int push(seqstack*s,elemtype x)/*把把元元素素x压压入入栈栈s中中*/if(s-top=MAXSIZE-1)return 0;/*栈上
6、溢进栈不成功返回栈上溢进栈不成功返回0标志标志*/else s-top+;/*栈顶指针加栈顶指针加1*/s-datas-top=x;/*元素元素x进栈进栈*/return 1;/*进栈成功返回进栈成功返回1标志标志*/顺序栈的基本运算出栈int pop(seqstack*s,elemtype&e)if(s-top=-1)return 0;/栈栈空返回空返回0 else s-top-;/*栈顶指针减栈顶指针减1*/e=s-datas-top+1;/*原原栈栈顶顶元元素素的的值值赋赋给给e*/return 1;顺序栈的基本运算读栈顶元素int gettop(seqstack*s,elemtype&
7、e)/*读栈顶元素读栈顶元素*/if(s-top=-1)return 0;/*栈空无元素返回栈空无元素返回0*/else e=s-datas-top;/*栈顶元素值赋给栈顶元素值赋给e*/return 1;栈的共享栈的共享为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。两个栈共享的类型定义：两个栈共享的类型定义：typedef struct elemtype stackm;/*m为数组长度，依具体问为数组长度，依具体问题题 而定而定*/int top2;/*top0和和top1分别为两栈的栈顶指分别为两栈的栈顶指针
8、针*/sharedstack;栈空：栈空：s-top0=-1;s-top1=m;栈满：栈满：s-top0+1=s-top1栈空与栈满条件？栈空与栈满条件？两栈共享的基本运算置空栈void setnull(sharedstack*s)s-top0=-1;/*0号栈空为号栈空为-1*/s-top1=m;/*1号栈空为号栈空为m*/两栈共享的基本运算进栈int push(sharedstack*s,int i,elemtype x)/*i=0,1为两栈的编号，算法把元素为两栈的编号，算法把元素x压入栈压入栈si 中中*/if(i1|s-top0+1=s-top1)return 0;else if(i
9、=0)s-stack+s-top0=x;else s-stack-s-top1=x;return 1;两栈共享的基本运算出栈int pop(sharedstack*s,int i,elemtype&e)/*弹出弹出i号栈的栈顶元素号栈的栈顶元素*/if(i1)return 0;/*参数出错无法弹出参数出错无法弹出*/else if(i=0)if(s-top0=-1)return 0;/*0号栈无法弹出号栈无法弹出*/else e=s-stacks-top0-;return 1;else if(s-top1=m)return 0;/*1号栈无法弹出号栈无法弹出*/else e=s-stacks-
10、top1+;return 1;链栈v链式存储结构实现的栈链栈（link stack）。v由于在链头运算，所以不用像单链表那样附加头结点，更方便运算链栈的类型定义typedef struct node elemtype data;struct node*next;linkstack;linkstack*top;/*栈顶指针，即链头指针栈顶指针，即链头指针*/链栈的基本运算空栈操作置空栈算法void setnull(linkstack*top)top=NULL;/*只要置只要置top为空即可为空即可*/判栈空算法int empty(linkstack*top)/*栈空返回栈空返回1否则返回否则返回
11、0*/if(top=NULL)return 1;else return 0;链栈的基本运算进栈void push(linkstack*top,elemtype x)/*注意：链栈不会发生上溢！注意：链栈不会发生上溢！*/linkstack*p;p=(linkstack*)malloc(sizeof(linkstack);p-data=x;p-next=top;top=p;链栈的基本运算出栈int pop(linkstack*top,elemtype&x)linkstack*p;if(top=NULL)return 0;/*栈为空无元素弹出栈为空无元素弹出*/else p=top;/*保存栈顶指
12、针于保存栈顶指针于P中中*/x=top-data;top=top-next;free(p);return 1;链栈的基本运算读栈顶元素int gettop(linkstack*top,elemtype&x)if(top=NULL)return 0;/*若栈为空返回若栈为空返回0*/else x=top-data;return 1;/*否则返回否则返回1*/3.3 栈的应用举例例一、例一、数制转换数制转换例二、例二、表达式求值表达式求值例三、例三、实现递归实现递归 例一、例一、数制转换数制转换 算法基于原理：N=(N div d)d+N mod d 例如：例如：（1348)10=(2504)8，
13、其运算过程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计计算算顺顺序序输输出出顺顺序序void conversion()setnull(s)；/将栈s初始化为一个空栈 scanf(%d,N);while(N!=0)push(s,N%8);N=N/8;while(!empty(s)pop(s,e);printf(%d,e);/conversion一、表达式表达式由操作数、运算符和界限符组成其中：操作数operand：常数或变量 运算符operator：算术运算符（+，-，*，/等等）关系运算符（=!=等等）逻辑运算符：AND，OR，NO
14、T界限符delimiter：左右括号，表达式结束符#等例二、例二、表达式求值表达式求值二、算符优先关系表v先乘除，后加减：*+v先括号内，后括号外：(一切算符v同级按左结合律：+v不允许的：)(，(#，#)v三、算术表达式求值的算符优先算法1、使用DS算符栈OPTR：有效算符操作数栈OPND：有效操作数、运算结果v2、算法思想初始化：OPND置为空栈，将#放入OPTR栈底依次读入表达式中的每个字符，若是操作数，则入OPND栈；若是算符，则和OPTR栈顶算符进行优先级比较a.“”：若栈顶算符优先，则执行相应运算，结果存入OPND栈重复，直到表达式求值完毕OperandType EvaluateE
15、xpression()/算术表达式求值的算符优先算法。设OPTR/OPND分别为运算符栈和操作数栈，OP为/运算符集合setnull(OPTR);push(OPTR,#);setnull(OPND);c=getchar();while(c!=#|gettop(OPTR)!=#)/whilereturn gettop(OPND);/EvaluateExpression if(!In(c,OP)push(OPND,c);c=getchar();else switch(Precede(gettop(OPTR),c)case:/退栈并将运算结果入栈pop(OPTR,theta);pop(OPND,b)
16、;pop(OPND,a);push(OPND,Operate(a theta b);break;/switch 1 1、什么是递归、什么是递归 在定义一个过程或函数时出现调用本过程或在定义一个过程或函数时出现调用本过程或本函数的成分本函数的成分,称之为称之为递归递归。直接递归：直接递归：调用自身。调用自身。间接递归：间接递归：过程或函数过程或函数p p调用过程或函数调用过程或函数q,q,而而q q又又调用调用p p。尾递归：尾递归：一个递归过程或递归函数中递归调用语一个递归过程或递归函数中递归调用语句是最后一条执行语句。句是最后一条执行语句。例三、例三、栈与递归的实现栈与递归的实现例例 以下是
17、求以下是求n!(n为正整数为正整数)的递归函数。的递归函数。int fun(int n)int x;if(n=1)/*语句语句1*/x=1;/*语句语句2*/else/*语句语句3*/x=fun(n-1)*n;/*语句语句4*/return(x);/*语句语句5*/2 2、何时使用递归、何时使用递归 在以下三种情况下在以下三种情况下,常常要用到递归的方法。常常要用到递归的方法。1)定义是递归的定义是递归的 有许多数学公式、数列等的定义是递归的。例如有许多数学公式、数列等的定义是递归的。例如,求求n!和和Fibonacci数列等。这些问题的求解过程可以将数列等。这些问题的求解过程可以将其递归定义
18、直接转化为对应的递归算法。其递归定义直接转化为对应的递归算法。v这个数列从第三项开始，每一项都等于前两项之和。v如果设F(n)为该数列的第n项(nN+)。那么这句话可以写成如下形式：vF(0)=0，n=0v F(1)=1，n=1v F(n)=F(n-1)+F(n-2)(n3)2)数据结构是递归的数据结构是递归的 例如：链表例如：链表 其结点类型定义如下：其结点类型定义如下：typedef struct node ElemType data;struct node*next;LinkList;该定义中该定义中,结构体结构体node的定义中用到了它自身的定义中用到了它自身,即即指针域指针域next
19、是一种指向自身类型的指针是一种指向自身类型的指针,所以它是一种所以它是一种递归数据结构。递归数据结构。对对于于递递归归数数据据结结构构,采采用用递递归归的的方方法法编编写写算算法法既既方方便又有效。便又有效。例例如如,求求一一个个不不带带头头结结点点的的单单链链表表head的的所所有有data域域(假设为假设为int型型)之和的递归算法如下：之和的递归算法如下：int Sum(LinkList*head)if(head=NULL)return 0;else return(head-data+Sum(head-next);3)问题的求解方法是递归的问题的求解方法是递归的 有有些些问问题题的的解解
20、法法是是递递归归的的,典典型型的的有有Hanoi问问题题求求解解函数的嵌套调用时栈变化过程3 3、递归函数的实现、递归函数的实现v将所有的实在参数、返回地址等信息传递给被调用函数保存；v为被调用函数的局部变量分配存储区；v将控制转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：v保存被调函数的计算结果；v释放被调函数的数据区；v依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回返回调用函数之前之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回！例如：void
21、main()void a()void b()a();b();/main /a /bMain的数据区函数a的数据区函数b的数据区 递归函数的执行过程v递归函数的执行过程类似于嵌套调用时的情况v如阶乘函数：vint fact(int n)v if(n=0)v return 1;v elsev return n*fact(n-1);v v由于被调用函数与调用函数是同一个函数，其返回地址应为同一语句位置设为r。递归调用fact(4)的工作栈变量情况Hanoi问题问问题题描描述述：设设有有3个个分分别别命命名名为为X,Y和和Z的的塔塔座座,在在塔塔座座X上上有有n个个直直径径各各不不相相同同,从从小小到
22、到大大依依次次编编号号为为1,2,n的的盘盘片片,现现要要求求将将X塔塔座座上上的的n个盘片移到塔座个盘片移到塔座Z上并仍按同样顺序叠放上并仍按同样顺序叠放v盘片移动规则盘片移动规则：v1、每次只能移动一个盘片；、每次只能移动一个盘片；v2、盘片可以插在、盘片可以插在X,Y和和Z中任一塔座；中任一塔座；v3、任何时候都不能将一个较大的盘片放在较、任何时候都不能将一个较大的盘片放在较小的盘片上。小的盘片上。v设设Hanoi(n,x,y,z)表示将表示将n个盘片从个盘片从x通过通过y移移动到动到z上上,递归分解的过程是：递归分解的过程是：vhanoi(n-1,x,z,y);v /将x上编号为至n-
23、1的圆盘移到y,z作辅助塔vmove(x,n,z);/将编号为n的圆盘从x移到zvhanoi(n-1,y,x,z);v/将y上编号为至n-1的圆盘移到z,x作辅助塔n-1n原柱原柱 A 辅助柱辅助柱 B 目标柱目标柱 C void hanoi(int n,char x,char y,char z)1/将塔座x上按直径由小到大且至上而下编号为1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。2if(n=1)3 move(x,1,z);/将编号为的圆盘从x移到z4 else 5 hanoi(n-1,x,z,y);/将x上编号为至n-1的 /圆盘移到y,z作辅助塔6 move(x,n,z);/
24、将编号为n的圆盘从x移到z7 hanoi(n-1,y,x,z);/将y上编号为至n-1的 /圆盘移到z,x作辅助塔8 9 Hanoi(n,a,b,c)Hanoi(n-1,a,c,b)；move(n,a,c):将第将第n个圆盘从个圆盘从a移到移到c；Hanoi(n-1,b,a,c)图 Hanoi塔的递归函数运行示意图 4 4、递归模型递归模型 递递归归模模型型是是递递归归算算法法的的抽抽象象,它它反反映映一一个个递递归归问问题题的的递递归归结结构构,例例如如,前前面面的的递递归归算算法法对对应应的的递递归归模模型型如如下：下：fun(1)=1 (1)fun(n)=n*fun(n-1)n1 (2)
25、其中其中,第一个式子给出了递归的终止条件第一个式子给出了递归的终止条件递归出口递归出口 第第二二个个式式子子给给出出了了fun(n)的的值值与与fun(n-1)的的值值之之间间的关系的关系递归体递归体。5 5、递归算法的设计递归算法的设计v分而治之v回溯法把一个不能或不好直接求解的把一个不能或不好直接求解的“大问题大问题”转化成一个转化成一个或几个或几个“小问题小问题”来解决来解决,再把这些再把这些“小问题小问题”进一步进一步分解成分解成更小的更小的“小问题小问题”来解决来解决,如此分解如此分解,直至每个直至每个“小问题小问题”都可以直接解决都可以直接解决(此时分解到递归出口此时分解到递归出口
26、)。但递归分解不是随意的分解但递归分解不是随意的分解,递归分解要保证递归分解要保证“大问题大问题”与与“小问题小问题”相似相似,即即求解过程与环境都相似求解过程与环境都相似。分而治之算法：回溯法回溯法(探索与回溯法探索与回溯法)是一种选优搜索法，按选优条是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为回溯条件的某个状态
27、的点称为“回溯点回溯点”。回溯法：求解求解fun(5)的过程如下：的过程如下：5!6 6、递归问题的优点递归问题的优点 递归既是强有力的数学方法，也是程序设计中一个很有用的工具。其特点是对递归问题描述简捷，结构清晰，程序的正确性容易证明。v7、消除递归的原因、消除递归的原因 v 其一：有利于提高算法时空性能v 其二：有些计算机语言不支持递归功能v 其三：递归算法是一次执行完，这在处理有些问题时不合适，也存在一个把递归算法转化为非递归算法的需求。8 8、递归算法到非递归算法的转换、递归算法到非递归算法的转换 递递归归算算法法有有两两个个基基本本特特性性：一一是是递递归归算算法法是是一一种种分分而
28、而治治之之的的、把把复复杂杂问问题题分分解解为为简简单单问问题题的的求求解解问问题题方方法法,对对求求解解某某些些复复杂杂问问题题,递递归归算算法法分分析析问问题题的的方方法法是是十十分分有有效效的的；二二是是递递归归算算法法的的时时间间/空空间间效效率率通通常常比比较较差差。因因此此,对对求求解解某某些些问问题题时时,我我们们希希望望用用递递归归算算法法分分析析问问题题,用用非非递递归归算算法法具具体体求求解解问问题题。这这就就需需要要把把递递归归算算法转换为非递归算法。法转换为非递归算法。把递归算法转化为非递归算法有如下三种基本方法：把递归算法转化为非递归算法有如下三种基本方法：(1)通通
29、过过分分析析，跳跳过过分分解解过过程程，直直接接用用循循环环结结构构的的算算法实现法实现求值过程求值过程。(2)自自己己用用栈栈模模拟拟系系统统的的运运行行时时栈栈,通通过过分分析析只只保保存存必须保存的信息必须保存的信息,从而用非递归算法替代递归算法。从而用非递归算法替代递归算法。(3)利利用用栈栈保保存存参参数数,由由于于栈栈的的后后进进先先出出特特性性吻吻合合递递归归算算法法的的执执行行过过程程,因因而而可可以以用用非非递递归归算算法法替替代代递递归归算算法。法。1 1）利用循环跳过分解过程从而消除递归）利用循环跳过分解过程从而消除递归 采采用用循循环环结结构构消消除除递递归归。求求解解
30、Fibonacci数数列列的的算算法法如下：如下：int Fib(int n)int i,f1,f2,f3;if(n=1|n=2)return(n);f1=1;f2=2;for(i=3;i=n;i+)f3=f1+f2;f1=f2;f2=f3;return(f3);2 2）模拟系统的运行时栈消除递归模拟系统的运行时栈消除递归直直接接使使用用栈栈保保存存中中间间结结果果,从从而而将将递递归归算算法法转转化化为为非非递归算法的过程。递归算法的过程。例：汉诺塔的递归算法转换为非递归算法（查阅）例：汉诺塔的递归算法转换为非递归算法（查阅）9、设计举例、设计举例1 1）一般递归算法设计举例一般递归算法设计
31、举例 设计一个输出如下形式数值的递归算法。设计一个输出如下形式数值的递归算法。n n n .nn n n .n.3 3 3 3 3 3 2 22 21 1问问题题分分析析：该该问问题题可可以以看看成成由由两两部部分分组组成成：一一部部分分是是输输出出一一行行值值为为n的的数数值值；另另一一部部分分是是原原问问题题的的子子问问题题，其其参参数数为为n-1。当当参参数数减减到到0时时不不再再输输出出任任何何数数据据值值，因因此此递递归归的的出出口口是是当当参参数数n0时空语句返回。时空语句返回。请自行写出递归算法！拓展：将递归算法转换为非递归算法2）设设计计求求解解委委员员会会问问题题的的算算法法
32、。委委员员会会问问题题是是：从从一一个个有有n个个人人的的团团体体中中抽抽出出k(kn)个个人人组组成成一一个个委委员员会会，计计算算共共有有多少种构成方法。多少种构成方法。问问题题分分析析：从从n个个人人中中抽抽出出k(kn)个个人人的的问问题题是是一一个个组组合合问问题题。即即求求组组合合数数公公式式C(n,k)。由由于于要要所所用用递递归归算算法法,大大家家容容易想到公式易想到公式:C(n,k)=C(n-1,k-1)+C(n-1,k),当当n=k或或k=0时，该问题可直接求解，数值均为时，该问题可直接求解，数值均为1，这是，这是算法的递归出口。因此，委员会问题的算法的递归出口。因此，委员
33、会问题的递推定义式递推定义式为：为：请自行写出递归算法！请自行写出递归算法！3）求两个正整数求两个正整数n和和m最大公约数的递推定义式为：最大公约数的递推定义式为：要求：要求：（1）编写求解该问题的递归算法；）编写求解该问题的递归算法；（2）分分析析当当调调用用语语句句为为Gcd(30,4)时时算算法法的的执执行行过过程程和和执行结果；执行结果；（3）分分析析当当调调用用语语句句为为Gcd(5,97)时时算算法法的的执执行行过过程程和和执行结果；执行结果；（4）编写求解该问题的循环结构算法。）编写求解该问题的循环结构算法。解：解：（1）请自行写出）请自行写出递归算法！递归算法！（2）调用语句为
34、）调用语句为Gcd(30,4)时，因时，因mn，递归调，递归调用用Gcd(4,2)；因；因mn，递归调，递归调用用Gcd(97,5)；因；因mn，递归调用，递归调用Gcd(5,2)；因；因mn，递归调用，递归调用Gcd(2,1)；因；因mn，递归调用，递归调用Gcd(1,0)；因因m=0，到达递归出口，函数最终返回值为，到达递归出口，函数最终返回值为n=1，即，即5和和97的最大公约数为的最大公约数为1。（4）请自行写出请自行写出循环结构算法！循环结构算法！3.5 队列类型的定义队列类型的定义 队列：一种运算受限的线性表队列：一种运算受限的线性表,其限制仅允许在其限制仅允许在表的一端进行插入表
35、的一端进行插入,而在表的另一端进行删除。而在表的另一端进行删除。进行插入的一端称做进行插入的一端称做队尾队尾(rear),进行删除的一端进行删除的一端称做称做队首队首(front)。进队进队或或入队入队出队出队或或离队离队 ADT Queue 数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,ai D,i=2,.,n 约定其中a1 端为队列头队列头，an 端为队列尾队列尾基本操作：基本操作：ADT Queue队列的基本操作：队列的基本操作：InitQueue(q)Empty(q)GetHead(q,x)OutQueue(q,x)Add
36、Queue(q,x)InitQueue(q)操作结果：操作结果：构造一个空队列q。AddQueue(q)初始条件：初始条件：队列q已存在。操作结果：操作结果：插入元素x为Q的新的队尾元素。a1a2anx OutQueue(q,x)初始条件：初始条件：Q为非空队列。操作结果：操作结果：删除Q的队头元素。a1a2an GetHead(q,x)初始条件：初始条件：Q为非空队列。操作结果：操作结果：用e返回Q的队头元素。a1a2an Empty(q)初始条件：初始条件：队列Q已存在。操作结果：操作结果：若Q为空队列，则返回1，否则返回0。链队列链队列链式映象顺序队列，循环队列顺序队列，循环队列顺序映象
37、3.5 队列类型的实现顺序队列v队列的顺序存储结构实现称作顺序队列。v顺序队列的类型定义如下：typedef struct elemtype queueMAXSIZE;int front,rear;/*队队头头指指针针（当当前前队队头头实实际际位位置置的的前前一一个个，队队尾尾指指针针（当当前前队队尾尾的的实实际际位位置置）*/sequeue;sequeue*q;顺序队列的几种状态循环队列循环队列顺序映象a1a2a3a4a5a6a7要入队列？013452a1a2a3a4a5a6a7a8产生的问题？队空与队满的判定条件相同q-rear=q-front解决途径：1、在队列中预留一个空位2、设定一个
38、标志3、设置一个数字计数器4、让front与rear等于一个不可能等于的值循环队列的基本运算初始化v初始化算法：构造一个空队列v只要将队头和队尾指针同时指向0到MAXSIZE-1的任一位置即可。void iniqueue(sequeue*q)q-front=0;q-rear=0;循环队列的基本运算入队int AddQueue(sequeue*q,elemtype x)if(q-rear+1)%MAXSIZE=q-front)return 0;/*队列已满无法插入返回队列已满无法插入返回0*/else q-rear=(q-rear+1)%MAXSIZE;q-queueq-rear=x;retur
39、n 1;/*返回插入成功标志返回插入成功标志1*/循环队列的基本运算出队int OutQueue(sequeue*q,elemtype&x)if(q-rear=q-front)return 0;/*队队列已空无法列已空无法删删除元素返回除元素返回0*/else q-front=(q-front+1)%MAXSIZE;e=q-queueq-front;return 1;/*返回返回删删除成功除成功标标志志1*/循环队列的基本运算读队头元素int GetHead(sequeue*q，elemtype&x)if(q-rear=q-front)return 0;/*队队列已空无法列已空无法读读取取队头
40、队头元素元素*/else x=q-queue(q-front+1)%MAXSIZE;return 1;/*返回返回读读取成功取成功标标志志1*/循环队列的基本运算判队列空int empty(sequeue*q)if(q-rear=q-front)return 1;else return 0;队列的链式存储结构实现称作链队列。注意front所指的是头结点而不是第一个元素（队头）结点。a1anQ.frontQ.rearQ.frontQ.rear空队列空队列链队列链队列链式映象typedef struct node elemtype data;struct node*next;linknode;/*
41、定义链队列中的结点类型*/typedef struct linknode*front,*rear;linkqueue;/*定义将头尾指针封装在一起的链队列类型*/linkqueue*q;链队列链队列链式映象链队列的基本运算初始化void iniqueue(linkqueue*q)q-front=(linknode*)malloc(sizeof(linknode);q-rear=q-front;/*让尾指针也指向头结点让尾指针也指向头结点*/q-front-next=NULL;/*填填头头结结点点的的next域域为为 NULL*/链队列的基本运算入队void addqueue(linkqueue
42、*q,elemtype x)linknode*p;p=(linknode*)malloc(sizeof(linknode);p-data=x;/*填入元素值填入元素值*/p-next=NULL;/*指针域填指针域填NULL值值*/q-rear-next=p;/*新结点插入队尾新结点插入队尾*/q-rear=p;/*修改队尾指针修改队尾指针*/链队列的基本运算出队v队空的处理？v队列非空（至少两个结点的情况）v队列非空（只有一个结点的情况）算法中删除的是头结点而不是第一个元素结点，让第一个元素结点作为删除后的头结点int OutQueue(linkqueue*q,elemtype&x)linkn
43、ode*p;if(q-rear=q-front)return 0;/*队列为空时返回队列为空时返回0*/else p=q-front;/*p指向头结点指向头结点*/q-front=q-front-next;free(p);x=q-front-data;return 1;/*返回返回删删除成功除成功标标志志1*/链队列的基本运算读队头元素int GetHead(linkqueue*q,elemtype x)if(q-rear=q-front)return 0;else x=q-front-next-data;return 1;/*返回返回读读取成功取成功标标志志1*/链队列的基本运算判队列空in
44、t empty(sequeue*q)/*当当队队列列q为为空空时时返返回回1否否则则返回返回0*/if(q-rear=q-front)return 1;else return 0;1.掌掌握握栈栈和和队队列列类类型型的的特特点点，并并能能在在相相应应的应用问题中正确选用它们。的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过理解递归算法执行过程中栈的状态变化过程。程。本章学习要点本章学习要点