964栈与队列.ppt

《964栈与队列.ppt》由会员分享，可在线阅读，更多相关《964栈与队列.ppt（113页珍藏版）》请在三一办公上搜索。

1、1,4.1 栈4.2 栈的实现4.3 栈的应用4.4 队列4.5 队列的实现 4.6 队列的应用,栈和队列是运算受限的线性表。,第四章 栈与队列,2,3.1 栈,3.1.1 栈的概念及运算3.1.2 顺序栈3.1.3 链栈,3,3.1.1 栈的概念及运算,栈,限制仅在一端进行插入和删除运算的线性表,栈顶,进行插入、删除的一端,栈底,栈顶,栈底,进栈,退栈,a2,a1,an,.,栈是后进先出表（LIFO 表）,4,（1）置空栈 createEmptyStack(void)：空栈；（2）判栈空 isEmptytack（st）：这是一个布尔函数。若st为空栈，则函数值为“真”,否则为“假”。（3）进

2、栈 push（st，x）：在st的顶部插入(亦称压入）元素 x。（4）退栈 pop（st）：删除（亦称弹出）栈st的顶部元素。（5）取栈顶 top（st）：取栈st的顶部元素。,栈的五种基本运算,3.1.1 栈的概念及运算,5,3.1.2 顺序栈,栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。,#define MAXNUM 100/*栈中能达到的最大容量*/typedef int DataType;/*定义栈元素的数据类型*/struct SeqStack/*顺序栈类型定义*/DataType sMAXNUM;int t;/*栈顶*/；typedef struct SeqStack,*P

3、SeqStack;PSeqStack pastack;/*指向顺序栈的指针变量*/,6,注意:,t是 int型简单变量,指向栈顶元素在栈中的位置(序号),约定:,1、栈空时，t=-12、栈满时，t=MAXNUM-13、栈顶元素：St4、若t=-1时，执行pop,产生“下溢”5、若t=MAXNUM-1时，执行push,产生“上溢”,7,6 5 4 3 2 1 0-1,A,B,C,D,进栈和退栈,3.1.2 顺序栈,8,3.1.2 顺序栈,（1）置空栈（2）判栈空（3）进栈（4）退栈（5）取栈顶,在顺序栈下实现栈的五种基本运算,当程序中同时使用两个栈时，可共享存储空间。,9,1.置空栈（算法4.1

4、）,PSeqStack createEmptyStack_seq(void)PSeqStack pastack;pastack=malloc(sizeof(struct SeqStack);if(pastack=NULL)printf(“out of space!n”);else pastack-t=-1;return pastack;/*SETNULL*/,10,2.判栈空（算法4.2）,int isEmptyStack_seq(pastack)PSeqStack pastack;if(pastack-t=0)return FALSE;else return TRUE;,11,3.进栈（算法

5、4.3）,先修改 t 值，再放入数据,t+,st=x,(*pastack).t+,(*pastack).s(*pastack).t=x,push_seq(pastack,x),12,push_seq(pastack,x)PSeqStack pastack;datatype x;if(pastack-t=MAXNUM-1)print(“overflow”);else pastack-t+;pastack-spastack-t=x;/*push_seq*/,3.进栈（算法4.3）,13,4.退栈（算法4.4）,pop_seq(pastack),修改 t 值,t-,pastack-t-,14,pop

6、_seq(pastack)PSeqStack pastack;if(pastack-t=-1)print(“underflow”);else pastack-t-;/*pop_seq*/,4.退栈（算法4.4）,15,5.取栈顶元素（算法4.5）,datatype top_seq(pastack)PSeqStack pastack;if(pastack-t=-1)print(“stack is empty”);return NULL;else return(pastack-spastack-t;/*top_seq*/,16,多个栈共享存储空间,.,栈1,栈2,栈1底,栈1顶,栈2底,栈2顶,让

7、多个栈共享存储空间，可以相互调节余缺，节约存储空间，降低发生上溢的概率。,17,多个栈共享存储空间,多栈共享：采用链栈,Typedef struct datatype sMAXNUM;int top1,top2;DStack;Push(x,i)Pop(i),18,3.1.3 链栈,栈的链式存储结构称为链栈。它是运算受限的单链表。,由于只能在链表头部进行操作，故链栈没有必要象单链表那样需附加头结点。栈顶指针top就是链表的头指针head。,19,typedef int DataType;struct Node;typedef struct Node*pNode;struct Node/*单链表结

8、点结构*/DataType info;pNode link;struct LinkStack/*链接栈类型定义*/pNode top;/*指向栈顶结点*/;typedef struct LinkStack*PLinkStack;,3.1.3 链栈,pLinkstack plstack;/*变量声明*/,plstack,top,info,link,栈的链接表示,21,3.1.3 链栈,相当于链表在 top 结点前插入,出栈,相当于链表在将top 结点删除,进栈,22,void push_link(PLinkStack plstack,DataType x)/*在栈中压入一元素x*/PNode p

9、;p=(PNode)malloc(sizeof(struct Node);if(p=NULL)printf(Out of space!n);elsep-info=x;p-link=plstack-top;plstack-top=p;,进栈算法（算法4.8）,23,void pop_link(PLinkStack plstack)PNode p;if(isEmptyStack_link(plstack)printf(Empty stack pop.n);elsep=plstack-top;plstack-top=plstack-top-link;free(p);,退栈算法（算法4.9）,24,3

10、.2 栈的应用,栈的应用非常之广，只要问题满足LIFO 原则，均可使用栈做数据结构。我们先看几个例子。例3.1 文字编辑器 例3.2 栈与递归 例3.3 数制转换 例3.4 括号匹配的检验 例3.5 表达式求值,25,例3.1 设计一个简单的文字编辑器，使其具有删除打 错字符的功能。,#删除前面一个字符 删除前面所有字符*输入结束,“abc#defg*”,我们用栈来实现这种功能的文字编辑器,每读入一个字符,退栈,置空栈,编辑结束,26,PSeqStack str;/*顺序栈 str 是全程变量*/EDIT()/*编辑好的字符串在 str 中*/char c;str=createEmptySta

11、ck();c=getchar();while(c!=*)/*字符*为编辑结束符*/if(c=#)POP(str);else if(c=)str=createEmptyStack();else PUSH(str,c);c=getchar()；/*EDIT*/,例3.1 设计一个简单的文字编辑器，使其具有删除打 错字符的功能。,27,如果一个对象部分的由自己组成，或者是按它自己定义的，则称为递归的。一个递归定义必须一步比一步简单，最后是有终结的，决不能无限循环下去。在n阶乘的定义中，当n为0时定义为1，它不再用递归来定义，称为递归定义的出口，简称为递归出口。,例3.2 栈与递归,递归的定义,28,

12、例3.2 栈与递归,递归函数的特点：在函数内部可以直接或间接地调用函数自身。如阶乘函数：,阶乘的递归计算（算法4.11）int fact(int n)if(n=0)return 1;else return(n*fact(n-1);r2main()int n;scanf(“%dn”,r1,3,3,r1,2,r2,1,r2,0,r2,1,1,2,6,30,调用前：（1）为被调用函数的局部变量分配存储区；（活动记录，数据区）（2）将所有的实参、返回地址传递给被调用函数；实参和形参的结合，传值。（3）将控制转移到被调用函数入口。调用后返回：（1）保存被调用函数的计算结果；（2）释放被调用函数的存储区；

13、（3）依照被调用函数保存的返回地址将控制转 移到调用函数。,递归函数到非递归函数的转换,函数嵌套调用时，按照“后调用先返回”的原则进行。,int main()int m,n;.first(m,n);1:,int first(int s,int t)int i;second(i);2:,int second(int d)intx,y;3:,int main()int m,n;.int i;int x,y;3:2:1:,函数嵌套结构,算法4.12 阶乘的非递归计算程序员自己管理一个栈，并模拟函数调用的执行过程。int nfact(int n);int res;pSeqStack st;st=cre

14、ateEmptyStack-seq();while(n0)while(!isEmptyStack-seq(st)push-seq(st,n);res=res*top-seq(st);n=n-1;pop-seq(st);res=1;free(st);return(res);,阶乘递归算法：int fact(int n)if(n=0)return 1;else return(n*fact(n-1);,34,例3.3 数制转换,十进制数N和其它d进制数的转换基于下列原理：N=(N div d)x d+N mod d,N N div 8 mod 8,1348 168 4,168 21 0,21 2 5

15、,2 0 2,4,0,5,2,35,程序要求：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。,由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好与计算过程相反。,例3.3 数制转换,因此，若将计算过程中得到的八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。,36,PSeqStack str;void CONVERSION()str=createEmptyStack();scanf(“%d”,X);while(X)PUSH(str,X%8);X=X/8;while(!EMPTY(str)printf(“%

16、d”,TOP(str);POP(str);/*CONVERSION*/,例3.3 数制转换,37,例3.3 数制转换,void CONVERSION(int X)If(X/8!=0)conversion(X/8);Printf(“%d”,X%8);,用递归函数实现：,用递归编程时，不需要用户自行定义栈。它是由编译程序加以设立和处理的。,38,例3.4 括号匹配的检验,假设表达式中允许三种括号：（）、和，其嵌套的顺序随意。,检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是

17、左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。,（）1 2 3 4 5 6 7 8,39,Judgement()/*判断表达式是否配对，表达式以#结束*/PSeqStack sta;char ch,chpop;int valid;SETNULL(/*valid为FALSE表示括号配对失败*/,例3.4 括号匹配的检验,40,例3.4 括号匹配的检验,while(ch!=#)/*当读入字符为左括号时进栈*/if(ch=()|(ch=)|(ch=)PUSH（,41,例3.4 括号匹配的检验,if(!(ch=)/*读入下一字符*/*while*/

18、,42,if(POP(/*左括号多于右括号*/if(valid)printf(“括号配对成功“）；else printf(“括号配对不成功”）；,例3.4 括号匹配的检验,43,表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的一个典型例子。下面我们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。,例3.5 表达式求值,要把一个表达式翻译成正确求值的机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。算符优先法就是根据算符优先关系的规定来实现对表达式的编译或解释执行的。,44,任何一个表达式都是由操作数（operand）、运算符（operator）和界限符组

19、成的，我们称它们为单词。,我们仅讨论简单表达式的求值问题，这种表达式只含加、减、乘、除、乘方、括号等运算。,例3.5 表达式求值,我们把运算符和界限符统称为算符。,45,对于两个相继出现的算符Q1和Q2，其优先关系：,例3.5 表达式求值,46,界限符#优先级别最低,设置两个工作栈：运算符栈OPTR 操作数栈OPND,算法的基本思想,1）首先置操作数栈为空栈，表达式起始符#为运算符栈的栈底元素。,2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和 OPTR 栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。,例3.5 表达式求值,输入：,3,*,（,7,+,3,

20、*,6,/,2,-,5,#,),操作数栈,运算符栈,3,#,*,(,7,+,3,*,6,18,/,2,9,16,-,5,11,33,48,例3.5 表达式求值,datatype evaluate()PSeqStack optr,opnd;char ch;SETNULL(,49,else switch(Precede(TOP(,例3.5 表达式求值,50,例3.5 表达式求值,case 1:/*:退栈并将运算结果入栈*/theta=POP(/*evalate*/,51,若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的一个出栈次序是（）。(a)7,5,3,9(b)9,7,5,3(c)7,

21、5,9,3(d)9,5,7,3,d,练习题,52,用一维数组设计栈，初态是栈空，top=0。现有输入序列是 a、b、c、d，经过 push、push、pop、push、pop、push操作后，输出序列是（），栈顶指针是（）,b、c,2,练习题,53,对于下面的程序调用过程，请问入栈序列是（），出栈次序是（）。,BCD,CBD,练习题,54,4.4 队列,队列的概念及运算(逻辑结构),55,队列,只允许在表的一端进行插入，而在另一端进行删除。,队头,允许删除的一端,队尾,允许插入的一端,队列的概念,出队,入队,队头,队尾,a1,a2,an,.,队列是先进先出表,56,队列的基本运算：创建一个空队

22、列Queue createEmptyQueue(void)判队列是否为空队列int isEmptyQueue(Queue qu)往队列中插入一个元素void enQueue(Queue qu,DataType x)从队列中删除一个元素void deQueue(Queue qu)求队列头部元素的值DataType frontQueue(Queue qu),队列的运算,57,4.5 队列的实现,4.5.1.顺序队列4.5.2.链队列,58,4.5.1 顺序队列,队列的顺序存储结构简称为顺序队列。顺序队列实际上是运算受限的顺序表。,由于队列的队头和队尾的位置均是变化的，因而要设置两个指针，分别指示当

23、前队头元素和队尾元素在向量空间中的位置。,59,#define MAXNUM 100struct SeqQueue datatype qMAXNUM;int f,r;typedef struct SeqQueue*PSeqQueue;PSeqQueue sq;,顺序队列的定义,4.5.1 顺序队列,队列空,队列数组越界,顺序队列,约定,队列满,61,开始：sq-f=0;sq-r=0;,入队：sq-datasq-r=x;sq-r+;,出队：sq-f+;,顺序队列的入队和出队,4.5.1 顺序队列,62,元素个数（队列长度）:（sq-r)-(sq-f),若（sq-r)-(sq-f)=0，则队列长度

24、为0，即空队列。再出队会“下溢”,若(sq-r)-(sq-f)=MAXNUM，则队满。队满时再入队会“上溢”,4.5.1 顺序队列,7,6,5,4,3,2,1,0,fr,k1,k2,k3,k6,k5,队列空,队列数组越界,顺序队列,64,4.5.1 顺序队列,假上溢：当前队列并不满，但不能入队。,每次出队时向前移一位置。,大量移动元素,循环队列,原因:,被删除元素的空间没有再被使用,解决:,65,采用循环队列克服“假上溢”,。,sq-r,sq-f,指针移动方向,66,入队：if(sq-r+1=MAXNUM)sq-r=0;else sq-r+;,利用模运算 sq-r=(sq-r+1)%MAXNU

25、M,出队：sq-f=(sq-f+1)%MAXNUM,采用循环队列克服“假上溢”,4.5.1 顺序队列,67,某一元素出队后，若头指针已从后面追上尾指针，则当前队列为空：sq-f=sq-r,某一元素入队后，若尾指针已从后面追上头指针，则当前队列为满：sq-f=sq-r,因此，仅凭 sq-f=sq-r 是无法区别队列空还是队列满。,判断队空和队满,4.5.1 顺序队列,68,解决办法,标志变量,测试尾指针在循环意义下是否等于头指针,判别队列满的条件：(sq-r+1)%MAXNUM=sq-f,使 sq-f=sq-r 成为判断队列空的条件,4.5.1 顺序队列,元素个数是MAXNUM-1,图(a)空队

26、列,图(b)队列满,图4.9 循环队列,70,4.5.1 顺序队列,在循环队列上实现五种基本运算：1.置空队 2.判队空 3.取队头元素 4.入队 5.出队,71,1.置空队,PSeqQueue createEmptyQueue_seq(void)PSeqQueue sq;sq=(PSeqQueue)malloc(sizeof(struct SeqQueue);if(sq=NULL)printf(Out of space!n);else sq-f=0;sq-r=0;return(sq);,72,2.判队空,int isEmptyQueue_seq(PSeqQueue sq)return(sq-

27、f=sq-r);,73,3.取队头元素,DataType frontQueue_seq(PSeqQueue sq)/*对非空队列,求队列头部元素*/return(sq-qsq-f);,74,4.入队,void enQueue_seq(PSeqQueue sq,DataType x)/*在队列中插入一元素x*/if(sq-r+1)%MAXNUM=sq-f)printf(Full queue.n);else sq-qsq-r=x;sq-r=(sq-r+1)%MAXNUM;,75,5.出队,void deQueue_seq(PSeqQueue sq)/*删除队列头部元素*/if(sq-f=sq-r)

28、printf(Empty Queue.n);elsesq-f=(sq-f+1)%MAXNUM;,76,4.5.2 链队列,队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。,显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一地确定。,k0,k1,k2,kn-1,.,图4.10 队列的链接表示,plqu,f,r,78,struct Node;typedef struct Node*pNode;struct Node DataType info;pNodelink;struct LinkQ

29、ueue PNodef;PNoder;typedef struct LinkQueue,*PLinkQueue;,队列的链接表示,79,头结点 队头结点,plqu-f,plqu-r,空和非空的链队列,80,4.5.2 链队列,在链队列上实现的五种基本运算如下：1.置空队 2.判队空 3.取队头结点数据 4.入队 5.出队,81,1.置空队（算法4.21）,PLinkQueue createEmptyQueue_link()PLinkQueue plqu;plqu=(PLinkQueue)malloc(sizeof(struct LinkQueue);if(plqu!=NULL)plqu-f=N

30、ULL;plqu-r=NULL;elseprintf(Out of space!n);return(plqu);,82,2.判队空（算法4.22）,int isEmptyQueue_link(PLinkQueue plqu)return(plqu-f=NULL);,83,3.取队头结点数据（算法4.25）,DataType frontQueue_link(PLinkQueue plqu)/*在非空队列中求队头元素*/return(plqu-f-info);,84,4.入队（算法4.23）,void enQueue_link(PLinkQueue plqu,DataType x)PNode p;

31、p=(PNode)malloc(sizeof(struct Node);if(p=NULL)printf(Out of space!);else p-info=x;p-link=NULL;if(plqu-f=NULL)plqu-f=p;plqu-r=p;else plqu-r-link=p;plqu-r=p;,85,5.出队（算法4.24）,void deQueue_link(PLinkQueue plqu)PNode p;if(plqu-f=NULL)printf(Empty queue.n);else p=plqu-f;plqu-f=plqu-f-link;free(p);,86,农夫过河

32、问题:一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。显然，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。好在狼属于食肉动物，它不吃白菜。请问农夫该采取什么方案才能将所有的东西运过河?,4.6 队列的应用农夫过河问题*,87,用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first)搜索，另一种是深度优先(depth_first)。实现这两种策略所依赖的数据结构正好是前面介绍的队列和栈。本节讨论队列的应用，所

33、以下面重点介绍广度优先的策略。,4.6 队列的应用农夫过河问题*,模拟农夫过河问题：用四位二进制数分别顺序表示农 夫、狼、白菜和羊的位置。0表示在南岸，1表示在北岸Path：15，6，14，2，11，1，9，0从初始状态0到最终状态15的动作序列为：,89,队列的应用 医院门诊部病人管理系统,工作过程：当一病人进入门诊室时，负责挂号的义务人员就根据观察和简短询问发给他一个从0（病危）到4（一般）变化的优先数，让他到相应优先数队列中去排队等待。当一医生空闲时，就根据优先数和等待时间，通知某候诊病人就诊。原则：优先级高的先考虑，同一优先级中，则先来先考虑。,90,队列的应用 医院门诊部病人管理系统

34、,组织数据的方式数据结构,分析：系统中的数据：病人的姓名，优先数，到达时间,91,队列的应用 医院门诊部病人管理系统,组织方式一：若病人以其到达门诊部的先后次序组织到一个队列，则具体到达时间可不考虑。,这样的单队列对按就诊原则来确定下一就诊病人是很不方便的，还将破坏队列的操作原则。,92,队列的应用 医院门诊部病人管理系统,组织方式二：多个队列（队列数组）：队列数组的第i个元素是优先级为i的队列。优先数隐含在队列的编号中。,01234,93,队列的应用 医院门诊部病人管理系统,就病人管理系统来说，功能菜单中至少有以下两个功能：（1）病人登记AddPatient()提示并读入病人优先数i；提示并

35、读入病人名 调用链队列的入队算法EnQueue()（2）确定下一个就诊病人 GetPatient()按就诊原则确定和显示下一个就诊病人名 即：若优先数0的队列非空，则下一就诊病人为队首元素，否则，考虑优先数1的队列；依次类推。,94,线性表,存储结构,运 算,队列,链 表,顺序表,栈,顺序栈,链 栈,顺序队列,链队列,线性表小结,95,顺序表,typedef int datatype;,#define MAXNUM 1024,typedef struct,datatype dataMAXNUM;,int last;,sequenlist;,96,链 表,typedef int datatype

36、;,typedef struct node,datatype data;,struct node*next;,linklist;,linklist*head,*p;,97,顺序栈,typedef int datatype;#define MAXNUM 64typedef struct datatype dataMAXNUM;int top;PSeqStack;PSeqStack*s;,98,链 栈,typedef int datatype;typedef struct node datatype data;struct node*next;linkstack;linkstack*top;,99

37、,顺序队列,typedef struct datatype dataMAXNUM;int f,r;sequeue;sequeue*sq;,100,链队列,typedef struct linklist*f,*r;linkqueue;linkqueue*q;,101,2.6 设计一算法，逆置带头结点的动态单链表 L。,void reverse(linklist*L)/*假设链表带有头结点*/linklist*p,*s;p=L-next;/*用p指向当前结点*/L-next=NULL;while(p)s=p;/*用s保存当前结点地址*/p=p-next;/*链表指针p后移*/*将当前结点链到表头*

38、/s-next=L-next;L-next=s;/*reverse*/,102,2.10 已知，由单链表表示的线性表中，含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。,linklist*ra,*rb,*rc;void sort(linklist*head)linklist*s,*p=head;/*建立三个空的循环链表*/ra=malloc(sizeof(linklist);ra-next=ra;rb=malloc(sizeof(linklist);

39、rb-next=rb;rc=malloc(sizeof(linklist);rc-next=ra;,103,while(p)s=p;p=p-next;if(s-data=0)/*将其它字符结点链接到C表*/*while*/*sort*/,104,3.3 设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。,int Judgement1(linklist*head)/*若对称返回 1，否则返回 0*/PSeqStack*s;linklist*p;int i,n=0;/*n为计数器，记录链表的长度*/p=head;/*先用循环求出链表的长度*/while

40、(p)n+;p=p-next;,105,3.3 设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。,SETNULL(s);/*设置空栈 s*/p=head;/*先将一半字符进栈*for(i=1;idata);p=p-next;/*若字符个数为基数，则跳过中间的字符*if(n%2)p=p-next;,106,3.3 设单链表中存放着n个字符，试编写算法，判断该字符串是否有中心对称关系。要求用尽可能少的时间完成。,/*当字符串未扫描完毕且栈非空时进行匹配*/while(p/*Judgement*/,107,3.4 设计算法判断一个算术表达式的圆括号是否

41、正确配对,Judgement2()/*判断表达式是否配对，表达式以#结束*/PSeqStack sta;char ch,chpop;int valid;SETNULL(/*valid为FALSE表示括号配对失败*/,108,while(ch!=#)if(ch=()/*读入字符为左括号时进栈*/PUSH（/*读入下一字符*/*while*/,3.4 设计算法判断一个算术表达式的圆括号是否正确配对,109,if(POP(/*左括号多于右括号*/if(valid)printf(“括号配对成功“）；else printf(“括号配对不成功”）；/*Judgement2*/,3.4 设计算法判断一个算术

42、表达式的圆括号是否正确配对,110,3.8 对于循环向量中的循环队列，写出求队列长度的公式,q-rearq-f:length=q-r-q-f;,q-rf:length=MAXNUM-(sq-f-sq-r);,111,3.9 假设以数组sequm存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判断 此循环队列的队满条件，并写出相应的入队列和出队列的算法。,根据题意，定义顺序队列的结构：typedef struct datatype dataMAXNUM;int f,r,seqlen;sequeue;,这样，循环队列满的条件为：seql

43、en=MAXNUM;,112,3.9 假设以数组sequm存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判断 此循环队列的队满条件，并写出相应的入队列和出队列的算法。,int ENQUEUD(sq,x)/*将新元素x插入到队列的队尾*/sequeue*sq;datatype x;if sq-quelen=MAXNUM/*队满上溢*/printf(“queue is full”);return NULL;else sq-r=(sq-r+1)%MAXNUM;sq-datasq-r=x;return TURE;/*ENQUEUE;*/,

44、113,3.9 假设以数组sequm存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判断 此循环队列的队满条件，并写出相应的入队列和出队列的算法。,datatype DEQUEUD(sq)/*删除队头元素并返回*/sequeue*sq;datatype x;int f;if(EMPTY(sq)/*队空下溢*/printf(“queue is empty”);return NULL;else sq-seqlen-;f=(MAXNUM+sq-r-seq-seqlen)%MAXNUM;return(sq-dataf);/*ENQUEUE;*/,