《限定性线性表》PPT课件.ppt

《《限定性线性表》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《限定性线性表》PPT课件.ppt（107页珍藏版）》请在三一办公上搜索。

1、第3章 限定性线性表栈和队列,3.1 栈,3.2 队列,返回主目录,3.3 总结与提高,3.1 栈,3.1.1 栈的定义,3.1.2 栈的表示和实现,3.1.3 栈的应用举例,3.1.4 栈与递归的实现,返回主目录,栈的定义：,栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。,返回主目录,根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素

2、，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。如下图所示：,进栈、出栈图例,进栈,出栈,进栈,出栈,ana2a1,返回主目录,栈的抽象数据类型定义,关系：栈中数据元素之间是线性关系,数据元素：可以是任意类型的数据，但必须属于同一个数据对象。,基本操作：InitStack（S）2.ClearStack（S）3.IsEmpty（S）4.IsFull（S）5.Push（S，x）6.Pop（S，x）7.GetTop（S，x）,返回主目录,3.1.2 栈的表示和实现,栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈为顺序栈；链式存储的栈为链栈。,返回

3、主目录,1.顺序栈,顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。,返回主目录,栈的顺序存储结构定义如下：,#define Stack_Size 50typedef struct StackElementType elemStack_Size;/*用来存放栈中元素的一维数组*/int top;/*用来存放栈顶元素的下标，top为-1表示空栈*/SeqStack;,返回主目录,顺序栈中的进栈和出栈图例,top,top,t

4、op,top,返回主目录,顺序栈基本操作的实现,1）初始化,void InitStack(SeqStack*S)/*构造一个空栈S*/S-top=-1;,返回主目录,2）进栈,int Push(SeqStack*S,StackElementType x)if(S-top=Stack_Size)return(FALSE);/*栈已满*/S-top+;S-elemS-top=x;return(TRUE);,返回主目录,3）出栈,int Pop(SeqStack*S,StackElementType*x)if(S-top=-1)/*栈为空*/return(FALSE);else*x=S-elemS-

5、top;S-top-;/*修改栈顶指针*/return(TRUE);,返回主目录,4）取栈顶元素,int GetTop（SeqStack S,StackElementType*x）/*将栈S的栈顶元素弹出，放到x所指的存储空间中，但 栈顶指针保持不变*/if(S-top=-1)/*栈为空*/return(FALSE);else*x=S-elemS-top;return(TRUE);,返回主目录,在实现GetTop操作时，也可将参数说明SeqStack*S 改为SeqStack S，也就是将传地址改为传值方式。传值比传地址容易理解，但传地址比传值更节省时间、空间。,注意：,两栈共享技术（双端栈）

6、：,主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间SM，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。,共享栈的空间示意为：top0和top1分别为两个栈顶指示器。,top0,top1,Stack：0,M-1,返回主目录,两栈共享的数据结构定义,#define M 100typedef struct StackElementType StackM;int top2;/*top0和top1分别为两个栈顶指示器*/DqStack;,返回主目录,（1）两栈共享的初始化操作算法,void InitStack(DqStack*S)S-top0=-

7、1;S-top1=M;,返回主目录,（2）两栈共享的进栈操作算法,int Push(DqStack*S,StackElementType x,int i)/*把数据元素x压入i号堆栈*/if(S-top0+1=S-top1)/*栈已满*/return(FALSE);switch(i)case 0:S-top0+;S-StackS-top0=x;break;case 1:S-top1-;S-StackS-top1=x;break;default:return(FALSE)/*参数错误*/return(TRUE);,返回主目录,（3）两栈共享的出栈操作算法,int Pop(DqStack*S,St

8、ackElementType*x,int i)/*从i 号堆栈中弹出栈顶元素并送到x中*/switch(i)case 0:if(S-top0=-1)return(FALSE);*x=S-StackS-top0;S-top0-;break;case 1:if(S-top1=M)return(FALSE);*x=S-StackS-top1;S-top1+;break;default:return(FALSE);return(TRUE);,返回主目录,说明读栈顶与退栈顶的处理异同，并标明将已知的退栈顶算法改为读栈顶算法时应做哪些改动。,【思考题】,2.链栈,链栈是采用链表作为存储结构实现的栈。为便于

9、操作，采用带头结点的单链表实现栈。由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。,链栈的示意图为：,top,top为栈顶指针，始终指向当前栈顶元素前面的头结点。若top-next=NULL，则代表空栈。注意：链栈在使用完毕时，应该释放其空间。,返回主目录,链栈结构的用C语言定义,typedef struct node StackElementType data;struct node*next;LinkStackNode;typedef LinkStackNode*LinkStack;,返回主目录,链栈的进栈操作,int Push(LinkStack top,S

10、tackElementType x)/*将数据元素x压入栈top中*/LinkStackNode*temp;temp=(LinkStackNode*)malloc(sizeof(LinkStackNode);if(temp=NULL)return(FALSE);/*申请空间失败*/temp-data=x;temp-next=top-next;top-next=temp;/*修改当前栈顶指针*/return(TRUE);,返回主目录,链栈的出栈操作,int Pop(LinkStack top,StackElementType*x)/*将栈top的栈顶元素弹出，放到x所指的存储空间中*/LinkS

11、tackNode*temp;temp=top-next;if(temp=NULL)/*栈为空*/return(FALSE);top-next=temp-next;*x=temp-data;free(temp);/*释放存储空间*/return(TRUE);,返回主目录,如果将可利用的空闲结点空间组织成链栈来管理，则申请一个新结点（类似C语言中的malloc函数）相当于链栈的什么操作？归还一个无用结点（类似C语言中的free函数）相当于链栈的什么操作？试分别写出从链栈中申请一个新结点和归还一个空闲结点的算法。,【思考题】,（3）多栈运算,将多个链栈的栈顶指针放在一个一维指针数组中来统一管理，从而

12、实现同时管理和使用多个栈。,#define M 10/*M个链栈*/typedef struct node StackElementType data;struct node*next;LinkStackNode,*LinkStack;LinkStack topM;,用c语言定义,(1)第i号栈的进栈操作int pushi(LinkStack topM,int i,StackElementType x)/*将元素x进入第i号链栈*/LinkStackNode*temp;temp=(LinkStackNode*)malloc(sizeof(LinkStackNode);if(temp=NULL)

13、return(FALSE);/*申请空间失败*/temp-data=x;temp-next=topi-next;topi-next=temp;/*修改当前栈顶指针*/return(TRUE);,(2)第i号栈元素的出栈操作int Pop(LinkStack topM,int i,StackElementType*x)/*将栈top的栈顶元素弹出，放到x所指的存储空间中*/LinkStackNode*temp;temp=topi-next;if(temp=NULL)/*第i号栈为空栈*/return(FALSE);topi-next=temp-next;*x=temp-data;free(tem

14、p);/*释放存储空间*/return(TRUE);,1.数制转换 假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步，直到N等于零：X=N mod d(其中mod为求余运算)N=N div d(其中div为整除运算),3.1.3 栈的应用举例,数制转换算法void Conversion(int N)/*对于任意一个非负十进制数N，打印出与其等值的二进制数*/Stack S;int x;/*S为顺序栈或链栈*/InitStack(,2.括号匹配问题,思想：在检验算法中设置一个栈，若读入的是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，

15、则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时，说明所有括号完全匹配。,返回主目录,算法:,void BracketMatch(char*str)Stack S;int i;char ch;InitStack(else,GetTop(,返回主目录,3.表达式求值,1)无括号算术表达式求值,表达式运算及运算符优先级,3+4*5#+-*/*0 1 2 3,返回主目录,2)算术表达式处理规则,规定优先级表；(2)设置两个栈：OVS(运算数栈)和O

16、PTR(运算符栈)；(3)自左向右扫描，遇操作符则与OPTR栈顶优先级比较：当前操作符OPTR栈顶则进OPTR栈；当前操作符 OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T(i)，T(i)进OVS栈。,返回主目录,返回主目录,无括号算术表达式的处理过程如右图,例：实现A/BC+D*E#的运算过程时栈区变化情况,返回主目录,算法具体描述如下：,int ExpEvaluation()/*读入一个简单算术表达式并计算其值。OPTR和OVS分 别为运算符栈和运算数栈，OPSet为运算符集合*/InitStack(/*用ch逐个读入操作数的各位数码，并转化为十进制数a*/else,swit

17、ch(Compare(GetTop(operator),ch)case=:Pop(,3）带括号算术表达式 首先要了解算术四则运算的规则：从左算到右；先乘除，后加减；先括号内，后括号外。,其次,确定运算符的优先关系。运算符和界限符可统称为算符，它们构成的集合命名为OPS。任意两个前后相继出现的算符1和2之间的优先关系：12，1的优先权高于2。,算符之间的优先关系,实现算符优先算法时需要使用两个工作栈：一个称作运算符栈operator；另一个称作操作数栈operand。算法的基本过程如下：A.初始化操作数栈operand和运算符栈operator，并将表达式起始符“#”压入运算符栈；B.读入表达式

18、中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理：,返回主目录,(1)若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈；(2)若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行运算后，将运算结果作为中间结果推入operand栈；(3)若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。当operator栈的栈顶元素和当前读入的字符均为“#

19、”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求值完毕。,返回主目录,算法具体描述如下：,int ExpEvaluation()/*读入一个简单算术表达式并计算其值。operator和operand 分别为运算符栈和运算数栈，OPS为运算符集合*/InitStack(/*用ch逐个读入操作数的各位数码，并转化为十进制数a*/else,switch(Compare(GetTop(operator),ch)case:/退栈并将运算结果入栈 Pop(,利用算法EvaluateExpression_reduced对算术表达式3*(7-2)求值，操作过程如下所示。,3.1.4 栈与递归

20、的实现,递归:在定义自身的同时又出现了对自身的调用。直接递归函数:如果一个函数在其定义体内直接调用自己，则称直接递归函数。间接递归函数：如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间接递归函数。,返回主目录,1.具有递归特性的问题,1）递归定义的数学函数如二阶Fibonacci数列：,Ackerman函数：,Ackerman函数可用一个简单的C语言函数描述:,int ack(int m,int n)if(m=0)return n+1;else if(n=0)return ack(m-1,1);else return ack(m-1,ack(m,n-1);,我们在后续章节

21、将要学习的一些数据结构，如广义表、二叉树、树等结构其本身均具有固有的递归特性，因此可以自然地采用递归法进行处理。,2）递归数据结构的处理,主函数执行期间运行栈的状态,后调用先返回,3）递归求解方法,许多问题的求解过程可以用递归分解的方法描述，一个典型的例子是著名的汉诺塔问题（hanoi）问题。n阶Hanoi塔问题：假设有三个分别命名为X,Y和Z的塔座，在塔座X上插有n个直径大小各不相同、从小到大编号为1，2,.，n的圆盘。现要求将塔座X上的n个圆盘移至塔座Z上，并仍按同样顺序叠排。,（1）每次只能移动一个圆盘；（2）圆盘可以插在X,Y和Z中的任何一个塔座上；（3）任何时刻都不能将一个较大的圆盘

22、压在较小的圆盘之上。,圆盘移动时必须遵循下列规则：,算法思想：,当n=1时，问题比较简单，只要将编号为1的圆盘从座X直接移动到塔座Z上即可；当n1时，需利用塔座Y作辅助塔座，若能设法将压在编号为n的圆盘上的n-1个圆盘从塔座X(依照上述原则)移至塔座Y上，则可先将编号为n的圆盘从塔座X 移至塔座Z上，然后再将塔座Y上的n-1个圆盘(依照上述原则)移至塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座问题是一个和原问题具有相同特征属性的问题，只是问题的规模小于1，因此可以用同样方法求解。,求解n阶Hanoi塔问题的递归算法,void hanoi(int n,char x,char y,cha

23、r z)/*将塔座X上从上到下编号为1至n，且按直径由小到大叠放的n个圆盘，按规则搬到塔座Z上，Y用作辅助塔座。*/1 2 if(n=1)3 move(x,1,z);/*将编号为1的圆盘从x移动z*/4 else 5 hanoi(n-1,x,z,y);/*将X上编号为1至n-1的圆盘移到y,z作辅助塔*/6 move(x,n,z);/*将编号为n的圆盘从x移到z*/7 hanoi(n-1,y,x,z);/*将y上编号为1至n-1的圆盘移到z，x作辅助塔*/8 9,续,续,递归方法的优点：,对问题描述简洁,结构清晰,程序的正确性容易证明,设计递归算法的方法,递归算法就是在算法中直接或间接调用算法

24、本身的算法。,使用递归算法的前提有两个：,规模最小的子问题具有直接解。,原问题可以层层分解为类似的的子问题，且子问题比原问题的规模更小。,设计递归算法的方法,寻找分解方法,设计递归出口,将本层的参数和返回地址传递给被调用函数并保存；为被调用函数的局部变量分配存储区，给下层参数赋值；将程序转移到被调函数的入口。,2.递归过程的实现,递归退层（ii+1层）系统也应完成三件工作：,递归进层（ii+1层）系统需要做三件事：,保存被调函数的计算结果；释放被调函数的数据区，恢复上层参数；依照被调函数保存的返回地址，将控制转移回调用函数。,3.递归算法到非递归算法的转换,递归算法具有两个特性：,(1)递归算

25、法是一种分而治之、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析方法是有效的。,（2）递归算法的效率较低。,1）消除递归的原因：,第一：有利于提高算法时空性能,第二：无应用递归语句的语言设施环境条件,第三：递归算法是一次执行完,消除递归方法有两类,一类是简单递归问题的转换，对于尾递归和单向递归的算法，可用循环结构的算法替代。,另一类是基于栈的方式，即将递归中隐含的栈机制转化为由用户直接控制的明显的栈。,2)简单递归的消除,单向递归,单向递归是指递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，相互之间参数无关，并且这些递归调用语句处

26、于算法的最后。,例如计算斐波那契数列的递归算法,计算斐波那契数列的递归算法如下：Fib(int n)if（n=0|n=1）return n;/*递归出口*/else return Fib(n-1)+Fib(n-2);/*递归调用*/,Fib(5)递归调用过程示意,计算斐波那契数列的非递归算法(1)int Fib(int n):int x,y,z;if（n=0|n=1）return n;/*计算 Fib(0)或Fib(1)*/else x=0,y=1;/*x=Fib(0)y=Fib(1)*/for(i=2;i=n;i+)z=y;/*z=Fib(i-1)*/y=x+y;/*y=Fib(i-1)+F

27、ib(i-2)求Fib(i)*/x=z;/*x=Fib(i-1)*/return y;,计算斐波那契数列的非递归算法(2)main()long int f1,f2;int i;f1=1;f2=1;for(i=1;i=20;i+)printf(%12ld%12ld,f1,f2);if(i%2=0)printf(n);f1=f1+f2;f2=f2+f1;/*C程序设计 谭浩强*/,尾递归,尾递归是指递归调用语句只有一个，而且是处于算法的最后，尾递归是单向递归的特例。,求n!非递归算法：,long Fact(int n)int fac=1;for(int i=1;i=n;i+)/*依次计算f(1)f

28、(n)*/fac=fac*i;/*f(i)=f(i-1)*i*/return fac;,3.2 队列,3.2.1 队列的定义,队列的表示和实现,3.2.3 队列的应用举例,返回主目录,3.2.1 队列的定义,队列：是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出的特性。,在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。,队列的抽象数据类型定义：,ADT Queue数据元素：可以是任意类型的数据，但必须属于同一个数据 对象。关系：队列中数据元素之间是线性关系。,基本操作：,1)InitQueue(&Q)：初始化操作

29、,2)IsEmpty(Q)：判空操作,3)IsFull(Q)：判满操作,4)EnterQueue(&Q，x)：进队操作,5)DeleteQueue(&Q,&x)：出队操作,6)GetHead（Q,&x）：取队头元素操作,7)ClearQueue(&Q)：队列置空操作,8)DestroyQueue(&Q)：队列销毁操作,3.2.2 队列的表示和实现,队列的两种存储表示，顺序表示和链式表示。,1.链队列：用链表表示的队列简称为链队列。,空的链队列,非空的链队列,typedef struct Node QueueElementType data;/*数据域*/struct Node*next;/*指

30、针域*/LinkQueueNode;typedef struct LinkQueueNode*front;LinkQueueNode*rear;LinkQueue;,链队列可以定义如下：,链队列的基本操作：,(1)初始化操作,int InitQueue(LinkQueue*Q)/*将Q初始化为一个空的链队列*/Q-front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);if(Q-front!=NULL)Q-rear=Q-front;Q-front-next=NULL;return(TRUE);else return(FALSE);/*溢出！*/,(

31、2)入队操作,int EnterQueue(LinkQueue*Q,QueueElementType x)/*将数据元素x插入到队列Q中*/LinkQueueNode*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode);if(NewNode!=NULL)NewNode-data=x;NewNode-next=NULL;Q-rear-next=NewNode;Q-rear=NewNode;return(TRUE);else return(FALSE);/*溢出！*/,(3)出队操作,int DeleteQueue(LinkQu

32、eue*Q,QueueElementType*x)/*将队列Q的队头元素出队，并存放到x所指的存储空间中*/LinkQueueNode*p;if(Q-front=Q-rear)return(FALSE);p=Q-front-next;Q-front-next=p-next;/*队头元素p出队*/if(Q-rear=p)Q-rear=Q-front;/*如果队中只有一个元素p，则p出队后成为空队*/*x=p-data;free(p);/*释放存储空间*/return(TRUE);,2.循环队列 循环队列是队列的一种顺序表示和实现方法。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元

33、依次存放从队头到队尾的元素，如一维数组QueueMAXSIZE。队列中队头和队尾的位置都是动态变化的，需要附设两个指针front和rear，分别指示队头元素和队尾元素在数组中的位置。初始化队列时，令front=rear=0；入队时，直接将新元素送入尾指针rear所指的单元，然后尾指针增1；出队时，直接取出队头指针front所指的元素，然后头指针增1。,在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。当rear=MAXSIZE时，认为队满。但此时不一定是真的队满，因为随着部分元素的出队，数组前面会出现一些空单元，如图3.14(4)所示。由于只能在队尾入

34、队，使得上述空单元无法使用。我们把这种现象称为假溢出，真正队满的条件是rear-front=MAXSIZE,图3.14 队列的基本操作,解决假溢出现象方法：将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元，形象地称之为循环队列。假设队列数组为QueueMAXSIZE，当rear+1=MAXSIZE时，令rear=0，即可求得最后一个单元QueueMAXSIZE-1的后继：Queue0。通过数学中的取模（求余）运算来实现：rear=（rear+1）mod MAXSIZE，显然，当rear+1=MAXSIZE时，rear=0，同样可求得最后一个单元QueueMAXSIZE-

35、1的后继：Queue0。,借助于取模（求余）运算，可以自动实现队尾指针、队头指针的循环变化。进队操作时，队尾指针的变化是：rear=（rear+1）mod MAXSIZE；出队操作时，队头指针的变化是：front=（front+1）mod MAXSIZE。图3.15给出了循环队列的几种情况。,图3.15 循环队列,在非空循环队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。1.一般情况如图3.15(c)所示:队列头元素是e3，队列尾元素是e5 2.队列空间均被占满，如图3.15(b)所示，此时队尾指针追上队头指针，所以有：front=rear。3.空队列如图3.

36、15(a)所示，此时队头指针追上队尾指针，所以也存在关系式：front=rear。,只凭front=rear无法判别队列的状态是“空”还是“满”。对于这个问题，可有两种处理方法：一种方法是少用一个元素空间。当队尾指针所指向的空单元的后继单元是队头元素所在的单元时，则停止入队。这样一来，队尾指针永远追不上队头指针，所以队满时不会有front=rear。现在队列“满”的条件为（rear+1）mod MAXSIZE=front。判队空的条件不变，仍为rear=front。另一种是增设一个标志量的方法，以区别队列是“空”还是“满”。介绍损失一个存储空间以区分队列空与满的方法。,#define MAXS

37、IZE 50/*队列的最大长度*/typedef structQueueElementType elementMAXSIZE;/*队列的元素空间*/int front;/*头指针指示器*/int rear;/*尾指针指示器*/SeqQueue;,循环队列的类型定义：,循环队列的基本操作,(1)初始化操作,void InitQueue（SeqQueue*Q）/*将*Q初始化为一个空的循环队列*/Q-front=Q-rear=0;,(2)入队操作,int EnterQueue(SeqQueue*Q,QueueElementType x)/*将元素x入队*/if(Q-rear+1)%MAXSIZE=

38、Q-front)/*队列已经满了*/return(FALSE);Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE;/*重新设置队尾指针*/return(TRUE);/*操作成功*/,(3)出队操作,int DeleteQueue(SeqQueue*Q,QueueElementType*x)/*删除队列的队头元素，用x返回其值*/if（Q-front=Q-rear）/*队列为空*/return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE;/*重新设置队头指针*/return(TRUE);/*操

39、作成功*/,3.2.3 队列的应用举例,1.打印杨辉三角,图3.16 杨辉三角形,杨辉三角形的特点是两个腰上的数字都为1，其它位置上的数字是其上一行中与之相邻的两个整数之和。所以在打印过程中，第i行上的元素要由第i-1行中的元素来生成。可以利用循环队列实现打印杨辉三角形的过程。在循环队列中依次存放第i-1行上的元素，然后逐个出队并打印，同时生成第i行元素并入队。在整个过程中，杨辉三角形中元素的入队顺序如图3.17所示。,图3.17 杨辉三角形元素入队顺序,(1)第7行的第一个元素1入队。elementrear=1;rear=(rear+1)%MAXSIZE;(2)循环做以下操作，产生第7行的中

40、间5个元素并入队。elementrear=elementfront+element(front+1)%MAXSIZE；rear=(rear+1)%MAXSIZE;front=(front+1)%MAXSIZE;(3)第6行的最后一个元素1出队。front=(front+1)%MAXSIZE;(4)第7行的最后一个元素1入队。element elementrear=1;rear=(rear+1)%MAXSIZE;,打印杨辉三角形的前n行元素算法：void YangHuiTriangle()SeqQueue Q;InitQueue(/end of for,DeleteQueue(/*打印第n-1行

41、的最后一个元素*/EnterQueue(&Q,1)/*第n行的最后一个元素入队*/end of for/end of YangHuiTriangle,2.键盘输入循环缓冲区问题,问题描述：有两个进程同时存在于一个程序中。其中第一个进程在屏幕上连续显示字符“A”，与此同时，程序不断检测键盘是否有输入，如果有的话，就读入用户键入的字符并保存到输入缓冲区中。在用户输入时，键入的字符并不立即回显在屏幕上。当用户键入一个逗号（，）时，表示第一个进程结束，第二个进程从缓冲区中读取那些已键入的字符并显示在屏幕上。第二个进程结束后，程序又进入第一个进程，重新显示字符“A”，同时用户又可以继续键入字符，直到用户

42、输入一个分号（；），才结束第一个进程，同时也结束整个程序。,define MAXSIZE 16define QueueElementType chardefine TRUE 1define FALSE 0include stdio.hinclude conio.hinclude dos.hmain()/*模拟键盘输入循环缓冲区*/char ch1,ch2;SeqQueue Q;int f;InitQueue(),for(;)/*第一个进程*/printf(A);if(kbhit()ch1=bdos(7,0,0);/*通过DOS命令读入一个字符*/f=EnterQueue(/*循环队列满时，强制

43、中断第一个进程*/,if(ch1=;|ch1=,)break;/*第一个进程正常结束*/while(!IsEmpty(Q)/*第二个进程*/DeleteQueue(/*置空ch1，程序继续*/,3.3 总结与提高3.3.1 主要知识点(1)基本概念 两种特殊的抽象数据类型：堆栈和队列，它们都是特殊的线性表，是操作受限定的线性表，它们的共同点是操作的位置限制在表的端点。堆栈具有LIFO的特性，限定元素的运算位置只在表尾(栈顶)端进行。(Late In First Out,LIFO)队列具有FIFO的特性。限定元素的运算位置分别在表的两端进行。(First In First Out,FIFO),(

44、2)顺序和链式两种存储方式 对进栈操作来说，顺序栈受到事先开辟的栈区容量限制，以避免上溢。链栈方式下，只有当整个系统无法申请到可用空间时，才无法进栈。队列操作亦同。循环队列是一种顺序队列。通过模运算将其看成一个首尾相接的环。求队列的长度是模运算算式，为区分队列的空和满，有两种典型的解决方法：一种是损失一个空间的方法；另一种是设置标志位的方法o 链队列的操作实现与单链表的操作实现类似，而链队列除了头指针，还设一个尾指针，并且通常封装在一个结构体里。,(3)栈与队列的应用 利用栈可以保存暂时无法解决的问题，而将注意力转向最新出现的问题，当最新问题得到解决后，再次回到新问题上，利用最新问题的解，求得

45、次新问题的解。因此，凡是对元素的保存次序与使用顺序相反的，都可以使用栈。例如递归顺序、数制间转换。利用队列也可以控制解决问题的顺序，实际应用中，凡是对元素的保存次序与使用顺序相同的，都可以使用队。例如键盘缓冲区问题、排队就诊问题。,(4)递归实现机制 递归工作栈是实现递归的核心技术。需明确递归进层与递归退层的相关工作。递归的消除在简单情况下，可以将递归算法转化为线性操作序列，直接用循环实现。一般情况下，可以利用自定义栈模拟系统栈，将递归算法转换为非递归算法。,3.3.2 典型题例 例1 设m、n均为正整数，指出如下递归函数的功能，并将其改写，要求执行时间尽可能短。int fun(int m，i

46、nt n)int r；if(nm)return(fun(n，m)；else if(n=0)return(m)；else r=mn；return(fun(n，r)；,【程序功能分析】该算法要求第一个参数大于第二个参数，否则将换位。当m大于几时，首先求出m除以n的余数r，然后让n做第一个参数，让r做第二个参数，重复上述过程。这是辗转相除法的过程，该函数的功能是求m和凡的最大公约数。【改写思路】要对上述最大公约数的递归函数进行改写，使执行时间尽可能短，关键要将递归变为非递归，对求最大公约数的辗转相除法可以转化成迭代的直线型循环实现。,【算法描述】int fun(int m，int n)int r；do r=mn；m=n;n=r;while(r!=0);return(m);,