栈和队列的详细讲解PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,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,栈的概念及运算,栈,限制仅在一端进行,插入和删除运算的线性,表,栈顶,进行插入、删除的,一端,栈底,栈顶,栈底,进栈,退栈,a,2,a,1,a,n,.,栈是后进先出表（,LIFO,表）,4,（,1,）置空栈,createEmptyStack(void)空栈；,（,2,）判栈空,isEmptytack,（,st,）,：这是一个布尔函数。,若,st,为空栈，则函数值为,“,真,”,否则为,“,假,”,。,（,3,）进栈,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,*PSeqStack;,PSeqStack pastack;/*,指向顺序栈的指针变量*,/,6,注意,:,t,是,int,型简单变量,指向栈顶元素在栈中的位置,(,序号,),约定,:,1,、栈空时，,t=,-1,2,、栈满时，,t=,MAXNUM-1,3,、栈顶元素：,St,4,、若,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,）,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.,进栈（算法,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_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,顶,让多个栈共享存储空间，可以相互调节余缺，,节约存储空间，降低发生上溢的概率。,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 /*,单链表结点结构*,/,DataType info;,pNode link;,;,struct LinkStack/*,链接栈类型定义*,/,pNode top;/*,指向栈顶结点*,/,;,typedef struct LinkStack *PLinkStack;,3.1.3,链栈,pLinkstack plstack;/*,变量声明*/,plstack,top,info,link,栈的链接表示,20,21,3.1.3,链栈,相当于链表在,top,结点前插入,出栈,相当于链表在将,top,结点删除,进栈,22,void push_link(PLinkStack plstack,DataType x),/*,在栈中压入一元素,x*/PNode p;,p=(PNode)malloc(sizeof(struct Node);,if(p=NULL ),printf(Out of space!n);,else,p-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);,else,p=plstack-top;,plstack-top=plstack-top-link;,free(p);,退栈算法（算法,4.9,）,24,3.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=createEmptyStack();,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,例,3.2,栈与递归,递归函数的特点,：在函数内部可以直接或间接地,调用函数自身。如阶乘函数：,n!=,1 ,n=0,n*(n-1)!,n0,阶乘的递归计算（算法,4.11,）,int fact(int n),if(n=0),return 1;,else,return(n*,fact(n-1),);,;,r2,main(),int n;,scanf(“%dn”,printf(“%8d%8dn”,n,fact(n),);,r1,3,3,r1,2,r2,1,r2,0,r2,1,1,2,6,29,30,调用前：,（,1,）为被调用函数的局部变量分配存储区；,（活动记录，数据区）,（,2,）将所有的实参、返回地址传递给被调用函数；,实参和形参的结合，传值。,（,3,）将控制转移到被调用函数入口。,调用后返回：,（,1,）保存被调用函数的计算结果；,（,2,）释放被调用函数的存储区；,（,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:,31,int main(),int m,n;,.,int i;,int x,y;,3:,2:,1:,first,main,second,函数嵌套结构,32,算法,4.12,阶乘的非递归计算,程序员自己管理一个栈，并模拟函数调用的执行过程。,int nfact(int n);,int res;,pSeqStack st;,st=createEmptyStack-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),);,;,33,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,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(,“,%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,括号匹配的检验,假设表达式中允许三种括号：,（）,、,和,，,其嵌套的顺序随意。,检验括号是否匹配的方法可用,“,期待的急迫程度,”,这个概念来描述。,在算法中设置一个,栈,，每读入一个括号，,若是右括,号，则或者使置于栈顶的最急迫的期待得以消解，或者,是不合法的情况；,若是左括号，则作为一个新的更急迫,的期待压入栈中，自然使原有的在栈中的所有未消解的,期待的急迫性都降了一级。,（,）,1 2 3 4 5 6 7 8,39,Judgement(),/*,判断表达式是否配对，表达式以,#,结束*,/,PSeqStack sta;,char ch,chpop;,int valid;,SETNULL(,PUSH(&sta,#,);,/*,把,#,放在栈底*/,ch=getchar();,valid=TRUE;,/*valid,为,FALSE,表示括号配对失败*,/,例,3.4,括号匹配的检验,40,例,3.4,括号匹配的检验,while(ch!=,#,),/*,当读入字符为左括号时进栈*/,if (,(ch=,(,)|,(ch=,)|,(ch=,),),PUSH,（,&sta,ch,）；,/*,当读入字符为右括号时出栈*/,else if (,(ch=,),)|,(ch=,)|,(ch=,),),chpop=POP(,if(chpop=,#,),/*,右括号多于左括号*/,valid=FALSE;,break;,41,例,3.4,括号匹配的检验,if (,!,(,(ch=,),)&(chpop=,(,),|,(ch=,)&(chpop=,),|,(ch=,)&(chpop=,),),valid=FALSE;,break;,/*else*/,ch=getchar);,/*,读入下一字符*/,/*while*/,42,if(POP(&sta)!=,#,）,valid=FALSE;,/*,左括号多于右括号*,/,if(valid),printf(,“,括号配对成功,“,）；,else,printf(,“,括号,配对不成功,”,）；,例,3.4,括号匹配的检验,43,表达式求值是程序设计语言编译中的一个最基本,问题。它的实现是栈应用的一个典型例子。下面我们,介绍一种简单直观、广为使用的算法，通常称为,“,算,符优先法,”,。,例,3.5,表达式求值,要把一个表达式翻译成正确求值的机器指令序列，,或者直接对表达式求值，首先要能够正确解释表达式。,算符优先法就是根据算符优先关系的规定来实现对表达,式的编译或解释执行的。,44,任何一个表达式都是由,操作数,（,operand,）、,运算,符,（,operator,）和,界限符,组成的，我们称它们为,单词,。,我们仅讨论简单表达式的求值问题，这种表达式,只含加、减、乘、除、乘方、括号等运算。,例,3.5,表达式求值,我们把,运算符,和,界限符,统称为,算符,。,45,对于两个相继出现的算符,Q1,和,Q2,，其优先关系：,例,3.5,表达式求值,1,2,+-*/()#,+,-,*,/,(,#=,46,界限符,#,优先级别最低,设置两个工作栈：,运算符栈,OPTR,操作数栈,OPND,算法的基本思想1,）首先置操作数栈为空栈，表达式起始符,#,为运算符,栈的栈底元素。,2,）依次读入表达式中每个字符，若是操作数则进,OPND,栈，若是运算符则和,OPTR,栈的栈顶运算符比较优先权,后作相应操作，直至整个表达式求值完毕。,例,3.5,表达式求值,输入：,3,*,（,7,+,3,*,6,/,2,-,5,#,),操作数栈,运算符栈,3,#,*,(,7,+,3,*,6,18,/,2,9,16,-,5,11,33,47,48,例,3.5,表达式求值,datatype evaluate(),PSeqStack optr,opnd;,char ch;,SETNULL(,PUSH(&optr,#,);SETNULL(,ch=getchar();,while(ch!=,#,|TOP(&optr)!=,#,),if(!In(ch,OP),/*,不是运算符则进栈*,/,PUSH(,ch=getchar();,49,else,switch(Precede(TOP(&optr),ch),case-1:,/*,:,退栈并将运算结果入栈*,/,theta=POP(,b=POP(,a=POP(,PUSH(,break;,/*switch*/,/*while*/,return TOP(,/*evalate*/,51,若进栈序列为,3,，,5,，,7,，,9,，进栈过程中可以出栈，则不可能的一个出栈次序是（a)7,5,3,9,(b)9,7,5,3,(c)7,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,队列,只允许在表的一端进行插入，而在另一端,进行删除。,队头,允许删除的一端,队尾,允许插入的一端,队列的概念,出队,入队,队头队尾,a,1,a,2,a,n,.,队列是先进先出表,56,队列的基本运算：,创建一个空队列,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,顺序队列,队列的顺序存储结构简称为顺序队列。顺序队,列实际上是运算受限的顺序表。,由于队列的队头和队尾的位置均是变化的，因,而要设置两个指针，分别指示当前队头元素和队尾,元素在向量空间中的位置。,59,#define MAXNUM 100,struct SeqQueue,datatype qMAXNUM;,int f,r;,;,typedef struct SeqQueue*PSeqQueue;,PSeqQueue sq;,顺序队列的定义,4.5.1,顺序队列,f,r,7,6,5,4,3,2,1,0,k,1,k,2,k,3,f,r,r,f,k,8,k,7,队列空,队列数组越界,顺序队列,约定,队列满,k,1,k,2,k,3,fk,8,r,k,4,k,5,k,6,k,7,60,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,，则队列长度,为,0,，即空队列。再出队会,“,下溢,”,若,(sq-r)-(sq-f)=MAXNUM,，则队满。,队满时再入队会,“,上溢,”,4.5.1,顺序队列,7,6,5,4,3,2,1,0,f,r,k,1,k,2,k,3,f,r,r,f,k,6,k,5,队列空,队列数组越界,顺序队列,63,64,4.5.1,顺序队列,假上溢,：当前队列并不满，但不能入队。,每次出队时向前移一位置。,大量移动元素,循环队列,原因,:,被删除元素的空间没有再被使用,解决,:,65,采用循环队列克服“假上溢”,。,。,。,sq-r,sq-f,MAXNUM-1,0,1,指针移动方向,66,入队,：,if (sq-r+1=MAXNUM),sq-r=0;,else sq-r+;,利用模运算,sq-r=(sq-r+1)%MAXNUM,出队,：,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,sq.rear,sq.front,k,1,k,2,k,7,k,6,k,5,k,4,k,3,sq.front,sq.rear,图,(a),空队列,图,(b),队列满,图,4.9,循环队列,69,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-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),printf(Empty Queue.n);,else,sq-f=(sq-f+1)%MAXNUM;,76,4.5.2,链队列,队列的链式存储结构简称为链队列，它是限制仅在,表头删除和表尾插入的单链表。,显然仅有单链表的头指针不便于在表尾做插入操作，,为此再增加一个尾指针，指向链表上的最后一个结点。,于是，一个链队列由一个头指针和一个尾指针唯一地确,定。,k,0,k,1,k,2,k,n-1,.,图,4.10,队列的链接表示,plqu,f,r,77,78,struct Node;,typedef struct Node *pNode;,struct Node,DataType info;,pNodelink;,;,struct LinkQueue,PNodef;,PNoder;,;,typedef struct LinkQueue,*PLinkQueue;,队列的链接表示,79,*plqu,头结点,plqu-f,plqu-r,头结点,队头结点,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=NULL;,plqu-r=NULL;,else,printf(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;,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,农夫过河问题,:,一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。显然，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开。好在狼属于食肉动物，它不吃白菜。请问农夫该采取什么方案才能将所有的东西运过河,?,4.6,队列的应用,农夫过河问题*,87,用计算机实现上述求解的搜索过程可以采用两种不同的策略：,一种是,广度优先,(breadth_first),搜索，,另一种是,深度优先,(depth_first),。,实现这两种策略所依赖的数据结构正好是前面介绍的,队列,和,栈,。,本节讨论队列的应用，所以下面重点介绍,广度优先,的策略。,4.6,队列的应用,农夫过河问题*,模拟农夫过河问题：用四位二进制数分别顺序表示农,夫、狼、白菜和羊的位置。,0,表示在南岸，,1,表示在北岸,Path,：,15,，,6,，,14,，,2,，,11,，,1,，,9,，,0,从初始状态,0,到最终状态,15,的动作序列为：,88,89,队列的应用 医院门诊部病人管理系统,工作过程：当一病人进入门诊室时，负责挂号的义务人员就根据观察和简短询问发给他一个从,0,（病危）到,4,（一般）变化的优先数，让他到相应优先数队列中去排队等待。当一医生空闲时，就根据优先数和等待时间，通知某候诊病人就诊。,原则：优先级高的先考虑，同一优先级中，则先来先考虑。,90,队列的应用 医院门诊部病人管理系统,组织数据的方式数据结构,分析：,系统中的数据：病人的姓名，优先数，到达时间,91,队列的应用 医院门诊部病人管理系统,组织方式一：若病人以其到达门诊部的先后次序组织到一个队列，则具体到达时间可不考虑。,到达次序,优先数,姓名,1,2,3,4,5,6,7,2,3,0,3,0,2,1,林文,郑江,鲁明,陈真,李军,王红,张兵,这样的单队列对按就诊原则来确定下一就诊病人是很不方便的，还将破坏队列的操作原则。,92,队列的应用 医院门诊部病人管理系统,组织方式二：多个队列（队列数组）：队列数组的第,i,个元素是优先级为,i,的队列。优先数隐含在队列的编号中。,鲁明,0,1,2,3,4,李军,张兵,林文,王红,郑江,陈真,93,队列的应用 医院门诊部病人管理系统,就病人管理系统来说，功能菜单中至少有以下两个功能：（,1,）病人登记,AddPatient(),提示并读入病人优先数,i,；,提示并读入病人名,调用链队列的入队算法,EnQueue(),（,2,）确定下一个就诊病人,GetPatient(),按就诊原则确定和显示下一个就诊病人名,即：若优先数,0,的队列非空，则下一就诊病人为队首元素，否则，考虑优先数,1,的队列；依次类推。,94,线,性,表,存储结构,运 算,队列,链 表,顺序表,栈,顺序栈,链 栈,顺序队列,链队列,线性表小结,95,顺序表,typedef int datatype;,#define MAXNUM 1024,typedef struct,datatype dataMAXNUM;,int last;,sequenlist;,96,链 表,typedef int datatype;,typedef struct node,datatype data;,struct node *next;,linklist;,linklist *head,*p;,97,顺序栈,typedef int datatype;,#define MAXNUM 64,typedef struct,datatype dataMAXNUM;,int top;,PSeqStack;,PSeqStack *s;,98,链 栈,typedef int datatype;,typedef struct node,datatype data;,struct node *next;,linkstack;,linkstack *top;,99,顺序队列,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,后移*,/,/*,将当前结点链到表头*,/,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);rb-next=rb;,rc=malloc(sizeof(linklist);rc-next=ra;,103,while(p),s=p;p=p-next;,if(s-data=0)&(s-datanext=ra-next;ra-next=s;,ra=s;,/*,将数字字符结点链接到,A,表,*/,else if(s-data=a)&(s-datadata=A)&(s-datanext=rb-next;rb-next=s;,rb=s;,/*,将字母字符结点链接到,B,表,*/,else,s-next=rc-next;rc-next=s;,rc=s;,/*,将其它字符结点链接到,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(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&!EMPTY(s),if (p-data!POP(s),break;,else p=p-next;,if (!p&EMPTY(s),return 1;,else return 0;,/*Judgement*/,107,3.4,设计算法判断一个算术表达式的圆括号是否正确配对,Judgement2(),/*,判断表达式是否配对，表达式以,#,结束*,/,PSeqStack sta;,char ch,chpop;,int valid;,SETNULL(,PUSH(&sta,#,);,/*,把,#,放在栈底*/,ch=getchar();,valid=TRUE;,/*valid,为,FALSE,表示括号配对失败*,/,108,while(ch!=,#,),if,(ch=,(,),/*,读入字符为左括号时进栈*/,PUSH,（,&sta,ch,）；,else if,(ch=,),),/*,读入字符为右括号时出栈*/,chpop=POP(,if(chpop=,#,),/*,右括号多于左括号*/,valid=FALSE;break;,/*else*/,ch=getchar();,/*,读入下一字符*/,/*while*/,3.4,设计算法判断一个算术表达式的圆括号是否正确配对,109,if(POP(&sta)!=,#,）,valid=FALSE;,/*,左括号多于右括号*,/,if(valid),printf(,“,括号配对成功,“,else,printf(,“,括号,配对不成功,”,）；,/*,Judgement2*/,3.4,设计算法判断一个算术表达式的圆括号是否正确配对,110,3.8,对于循环向量中的循环队列，写出求队列长度的公式,0,MAXNUM,-1,r,f,q-rear,q-f:,length=q-r-q-f;,0,MAXNUM,-1,r,f,q-rf:,length=,MAXNUM,-(sq-f-sq-r);,111,3.9,假设以数组,sequm,存放循环队列的元素，同时设变量,rear,和,quelen,分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判断,此循环队列的队满条件，并写出相应