资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,PPT,学习交流,*,Data,Structures: Chapter,3,中国水利水电出版社,*,Data,Structures: Chapter,3,单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,中国水利水电出版社,*,*,中国水利水电出版社,*,第,3,章 栈和队列,1,PPT,学习交流,通常称，栈和队列是限定,插入,和,删除,只能在表的“,端点,”进行的线性表。,栈和队列是两种常用的数据类型,2,PPT,学习交流,3.1 栈,栈是限定仅能在表尾一端进行插入、,删除操作的线性表,（,a,1,a,2, . ,a,i -1,a,i,a,i+1, ,a,n,）,插入,删除,3.1.1 栈的定义及基本运算,一、什么是栈,3,PPT,学习交流,栈的示意图,出栈,进栈,栈的特点,后进先出,(LIFO,表,),第,1,个进栈的元素在栈底，最后一个进栈的元素在栈顶，,第,1,个出栈的元素为栈顶元素，,最后一个出栈的元素为栈底元素,栈顶,栈底,a,n,a,2,a,1,二、栈的图示,4,PPT,学习交流,（1）初始化操作,InitStack(,&,S),功能：构造一个空栈,S；,（,2）,销毁栈操作,DestroyStack(,&,S),功能：销毁一个已存在的栈;,（3）置空栈操作,ClearStack(,&,S),功能：将栈,S,置为空栈;,（4）取栈顶元素操作,GetTop(S,&,e),功能：取栈顶元素，并用,e,返回;,三、栈的基本操作（,1,）,5,PPT,学习交流,（5）进栈操作,Push(,&,S, e),功能：元素,e,进栈;,（6）退栈操作,Pop(,&,S,&,e),功能：栈顶元素退栈，并用,e,返回;,（7）判空操作,StackEmpty(S),功能：若栈,S,为空，返回,True,，否则返回,False;,三、栈的基本操作 （,2,）,6,PPT,学习交流,栈的顺序存储结构，也是利用一组连续的内存单元依次存放自栈底到栈顶的,数据元素,，,栈顶元素的位置，,由一个称为,栈顶指针,的变量指示,。,栈的顺序存贮结构也称为,顺序栈。,一、栈的顺序存储结构及实现,3,.,1,.2,栈的顺序表示与实现,与线性表类似，栈也可以用顺序结构或链式结构存储。,7,PPT,学习交流,SqStack:,结构类型名；,SqStack,类型的变量是结构变量。,base：,称为栈底指针，始终指向栈底位置；,top：,称为栈顶指针，约定栈顶指针指向栈顶元素的下一个位置；,Stacksize：,用于存放当前已分配的栈的存储空间的大小；,#,define STACK_INIT_SIZE 100/,栈存储空间的初始分配量#,define STACKINCREMENT 10/,栈存储空间的分配增量,typedef struct, SElemType* base; /,栈空间基址便于判断栈是否为空,SElemType* top/,栈顶指针,intstacksize;/,当前分配的栈空间大小,/（以,sizeof(SElemType),为单位）,SqStack;,顺序栈的类型定义,8,PPT,学习交流,top,base,base,top,base,top,base,top,A,A,B,C,D,E,A,B,空栈,A,进栈,B C D E,进栈，栈满,E D C,出栈,顺序栈的操作示例,P.58,9,PPT,学习交流,顺序栈的图示,a,n,a,i,a,i-1,a,2,a,1,n,n-1,i-1,i-2,1,0,100,base top stacksize,S,10,PPT,学习交流,Status InitStack (SqStack &S) /,构造一个空栈,S ,S.base=(SElemType * )malloc (STACK_INIT_SIZE * sizeof(SElemType);,/,为顺序栈动态分配存储空间,if (! S. base) exit(OVERFLOW); /,存储分配失败,S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; / InitStack_Sq,（1）初始化操作,顺序栈的基本操作的实现,11,PPT,学习交流,Status DetroyStack ( SqStack &S) /,销毁一个已存在的栈, If (!S.base) return ERROR; /,若栈未建立（尚未分配栈空间）,free (S.base); /,回收栈空间,S.base = S.top = null; S.stacksize = 0; return OK; / DetroyStack_Sq,（,2）,销毁栈操作,12,PPT,学习交流,Status ClearStack ( SqStack &S) /,将栈,S,置为空栈, If (!S.base) return ERROR; /,若栈未建立,S.top = S.base ; return OK;, / ClearStack,（3,）,置空栈操作,13,PPT,学习交流,Status GetTop (SqStack S, SelemType &e), /,若栈不空，则用,e,返回,S,的栈顶元素，并返回,OK；,/,否则返回,ERROR,if (S.top= =S.base) return ERROR; /,若栈为空,e = * (S.top-1); /,取栈顶元素至,e,return OK; / GetTop_Sq,（,4,）,取栈顶元素操作,GetTop,14,PPT,学习交流,Status Push (SqStack &S, SElemType e), /,将元素,e,插入栈成为新的栈顶元素,if (S.top-S.base=S.stacksize) /,栈满，追加存储空间,S.base=,(SElemType * )realloc(S.base, (S.stacksize +STACKINCREMENT) * sizeof(ElemType);,if (! S. base) exit(OVERFLOW); /,存储分配失败,S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /,元素,e,插入栈顶，修改栈顶指针,return OK; / Push,（,5,）,进栈操作,Push,15,PPT,学习交流,Status Pop (SqStack &S, SElemType &e), /,若栈不空，则删除,S,的栈顶元素，用,e,返回其值，并返回,OK；,/,/,否则返回,ERROR if (S.top= = S.base) return ERROR; /,栈空,e = * -S.top; /,删除栈顶元素，并修改栈顶指针,return OK; ,（,6,）,出栈操作,Pop,16,PPT,学习交流,栈的链式存储结构，,也称链栈，,如右图所示：,Data next,S,栈顶,栈底,a,n-1,a,1,a,n,3,.,1,.,3栈,的链式表示及实现,17,PPT,学习交流,链式栈图示,说明：,1.,链栈可用线性链表表示；,2,.,链栈的栈顶指针就是链表的头指针；,3,.,进栈操作,(push),就是在该线性链表第一个元素结点之前插入一个新结点,.,4.,出栈操作,(pop),就是删除链表的第一个元素结点。,Data next,S,栈顶,栈底,a,n-1,a,1,a,n,18,PPT,学习交流,3.2 栈的应用举例,例1 数制转换,我们学习过各种数制的转换问题。,十,-,八进制转换,十,-,二进制转换等。,下面我们设计一程序,实现十,-,八进制数的自动转换。该程序功能为：,对于输入的任意一个非负十进制数，显示输出与其等值的八进制数。,19,PPT,学习交流,我们这里介绍的方法基于下列原理：,N = (Ndiv8),10,8+N mod 8,N：,十进制数，,div：,整除运算，,mod：,求余运算；,例：,(1348),10,= 2,8,3,+,5,8,2,+,0,8+4 = (2504),8,N N div 8 N mod 8,1348 168 4,168 21 0,21 2 5,2 0 2,20,PPT,学习交流,由上述求解过程可以看出，在计算过程中是从低位到高位顺序产生八进制数的各个数位。,而显示时按照我们的习惯是从高位在前，低位在后，即按从高位到低位的顺序输出。,即后计算出的（高）位数先输出，具有后进先出的特点。,因此可将计算过程中得到的八进制数顺序进栈，按出栈序列打印输出的数，就是对应的八进制数。,21,PPT,学习交流,例如：,（,1348),10,= (2504),8,其运算过程如下：,N N div 8 N mod 8,1348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,22,PPT,学习交流,void conversion( ) /,输入任意一个非负十进制整数，输出与其等值的八进制数,InitStack(S); /,建空栈,scanf(“%d”, /,输入一个,非负十进制整数,while(N) / N,不等于零,循环,Push(S, N % 8); /,余数,N%8,进栈,N=N / 8; /,辗转相除, while(! StackEmpty(S), /,输出存放在栈中的八制数位。,Pop(S, e); Printf(“%d”, e); ,23,PPT,学习交流,例,2,括号匹配的检验,假设在表达式中,（）或（ ）,等为,正确,的格式，,（ ）或（ ）或,( ),均为,不正确,的格式。,则 检验括号,是否匹配,的方法可用,“期待的急迫程度”这个概念来描述。,24,PPT,学习交流,分析可能出现的,不匹配,的情况,:,到来的右括弧非所“期待”的,;,例如：考虑下列括号序列：, ( ) ,1 2 3 4 5 6 7 8,到来的是“不速之客”,;,直到结束，也没有到来所“期待”的括弧,;,25,PPT,学习交流,算法的设计思想：,（,1,）凡出现,左括弧,，则,进栈,；,（,2,）凡出现,右括弧,，首先检查栈是否空,若,栈空,，则表明该,“,右括弧,”,多余,error,否则,和栈顶元素,比较，,若,相匹配,，则,“,左括弧出栈,”,否则表明,不匹配,error,（,3,）,表达式检验结束时,，,若,栈空,，则表明表达式中,匹配正确,否则表明,“,左括弧,”,有余,error,26,PPT,学习交流,Status matchpairs(SElemTypestr),SqStack *S;,int tag=1;char*ch,e;,/ e,存放出栈字符,/ tag=1,表示表达式中括号正确配对，,tag=0,表示不配对,InitStack( /,初始化构造一个空栈,S,ch=str;,while(*ch!=0)&(tag=1), switch(*ch),/,遇到,(,，,或,，将其入栈,case (:,case :,case : Push(S,*ch); break;,27,PPT,学习交流,/,遇到,),，, ,或,，弹出栈顶字符,case ): Pop(S,if (e!=() tag=0;break;,/,若栈顶不是对应的,(,，,或,，则置,tag,为,0,；, / end of switch,ch+; /,继续判断下一个字符,e=0; /,将,e,清空，以便存放下一次出栈的字符, / end of while,/,如果栈为空且,tag,为,1,，则配对成功,if (tag=1),else printf (not match!n);,28,PPT,学习交流,例,3,行编辑程序问题,如何实现？,是否每接受一个字符即存入存储器,?,29,PPT,学习交流,设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区,;,并假设“,#”,为退格符,“”,为退行符。,在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。,合理的作法是：,30,PPT,学习交流,假设从终端接受了这样两行字符：,whli#ilr#e,（,s#*,s),outputchar,(,*,s,=#+,);,则实际有效的是下列两行：,while,(,*,s),putchar,(,*,s,+,);,31,PPT,学习交流,while,(ch,!= EOF &,ch,!=,n),switch,(ch),case,#,:,Pop(S, c);,break;,case,:,ClearStack(S);,break; /,重置,S,为空栈,default,:,Push(S, ch);,break;,ch = getchar( );,/,从终端接收下一个字符,ClearStack(S);,/,重置,S,为空栈,if,(ch != EOF,),ch = getchar();,while,(ch,!= EOF,),/,EOF,为全文结束符,将从栈底到栈顶的字符传送至调用过程的数据区；,32,PPT,学习交流,(1),问题的提出,设计一个小计算器（程序），希望从键盘上输入一个算术表达式（由运算符操作数构成的字符串）后,在屏幕上显示表达式的求值结果。,例,4,表达式求值,33,PPT,学习交流,(2),表达式的构成,操作数+运算符+界符（如括号）,(3),表达式的求值：,例 5+6,(1+2)-4,按照四则运算法则，上述表达式的计算过程为：,5+6,(1+2)-4=5+6,3-4 = 5+18-4= 23-4=19,表达式中运算符的运算顺序为：,+ ，,，,+， -,如何确定运算符的运算顺序？,1,2,3,4,1,2,3,4,34,PPT,学习交流,+,2,1,-,*,/,(,),#,+ - * / ( ) #, , , , , , =,(4),算符间的优先关系表,注：,1,2,是相邻算符，,1,在左，,2,在右,1,2,表示,1,的优先权低于,2,P.52,35,PPT,学习交流,(,5,),算符优先算法,分析表达式5+4,(1+2)-6 计算过程：,从左向右扫描表达式：,遇操作数 进栈；,遇运算符号,j,与前面的刚扫描过的运算符,i,比较 若,i,j,则,j,进栈,（,已保存的运算符的优先关系为,1,2,3,j,则说明,i,是已扫描算符中优先级最高者，,j,出栈，进行运算； 若,i,=,j,若,i,为（，,j,为 ），,j,出栈，说明括号内的式子已计算完；,若,i,为,#,，出栈，栈空，表达式计算完毕。,5+4,(1+2)- 6,进行运算的算符,i,是当前扫描过的运算符中优先级最高者，可以利用两个栈分别保存扫描过程中遇到的操作数和运算符。,后面也许有优先级,更大的算符,36,PPT,学习交流,建立两个工作栈。,OPTR,栈保存运算符；,OPND,栈,-,保存操作数或运算结果。算法,3.3,operandType EvaluateExpression( ), /,算术表达式求值的算符优先算法。设,OPTR,和,OPND,/,分别为运算符栈和运算数栈，,OP,为运算符集合。,InitStack(OPTR); Push (OPTR, #);,InitStack(OPND); c=getchar( );,While(c!= # | GetTop(OPTR)!=#), if (! In (c, OP) / In(c, OP),是判断,c,是否为运算符的函数, Push(OPND, c);,c=getchar( ); /,不是运算符则进数据栈,OPND,else,37,PPT,学习交流,续,switch (Precede(GetTop(OPTR), c), case,: /,栈顶算符优先权高,出栈运算，并将运算结果入栈,OPND,Pop(OPTR, theta);,Pop(OPND, b); Pop(OPND, a);,Push(OPND, Operate(a, theta, b);,break;,/ switch,/while,return GetTop(OPND);,/EvaluateExpression,38,PPT,学习交流,3.3 栈与递归,1什么是递归,递归是一个很有用的工具，在数学和程序设计等许,多领域中都用到了递归。,递归概念：,一个用自己定义自己的定义,称为递归定义。,例,n!= 1*2*3*4*,*(n-1)* n,n!,递归定义,n!= 1,当,n=0,时,n!= n(n-1)!,当,n0,时,用(n-1)!,定义,n!,39,PPT,学习交流,例1 编写求解 阶乘,n!,的递归算法,n!,的递归定义：,基本项：,n!=1,当,n=1,递归项：,n!=n (n-1)!,当,n 1,递归算法：,int fact (int n),/ 算法功能是求解并返回,n,的阶乘,If（n=1） return（1）；,else,return（n*fact (n-1)）；,40,PPT,学习交流,例2 编写求解,Hanoi,塔问题的递归算法,有,3,个各为,X，Y，Z,的塔座，在,X,项上有,n,个大小不同，依小到大编号为1，2，,n,的圆盘。,现要求将,X,上的,n,个圆盘移至,Z,上，并仍以同样顺序叠放， 圆盘移动时必须遵守下列原则：,（1）每次移动,1,个盘子；,（2）圆盘可以放在,X，Y，Z,中的任一塔座上；,（3）任何时刻都不能将较大的圆盘压放在较小圆盘之上；,41,PPT,学习交流,a,b,c,3,2,1,1,1,2,1,3,1,2,1,例,: n=3,时圆盘移动的过程如下图所示,：,Y,X,Z,42,PPT,学习交流,求解,Hanoi,塔问题的递归描述（定义）,基本项：,n=1,时，将,n,号圆盘从,X,移至,Z；,递归项：,n1,时，,将,X,上 1,n-1,号圆盘移至,Y；,将,X,上的,n,号圆盘从,X,移至,Z;,将,Y,上 1,n-1,号圆盘从,Y,移至,Z;,将规模为,n,的问题的求解归结为规模为,n-1,的问题的求解,有了问题的递归定义，,很容易写出对应的递归算法：,43,PPT,学习交流,void hanoi (int n, char x, char y, char z),/,将塔座,x,上按直径由小到大，且自上而下编号为1至,n,的,n,个圆盘按规则搬到 / 塔座,z,上，,y,可用作辅助塔座。 / 搬动操作,move(x, n, z),可定义为(,c,是初值为0的全局变量，对搬动计数)： /,printf(“%d. Move disk %d from %c to %c n”, +c, n, x, z); if (n= =1) move(x,1,z); /,将编号为1的圆盘从,x,移动,z else ,hanoi(n-1, x, z, y); /,将,x,上编号为 1 至,n-1,的圆盘移到,y, z,作辅助塔,move(x, n, z); /,将编号为,n,的圆盘从,x,移到,z hanoi(n-1, y, x, z)； /,将,y,上编号为 1 至,n-1,的圆盘移到,z, x,作辅助塔 ,算法3.5,Hanoi,塔问题,44,PPT,学习交流,3,.4,队 列,3.4.1 队列的定义及基本运算,一 什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表。,（,a,1,a,2, . ,a,i -1,a,i,a,i+1, ,a,n,）,插入,删除,45,PPT,学习交流,说明：设（,a,1,a,2,a,3, . ,a,n,）,为一队列,(1),表尾称作队尾，表头称为队头；,(2),a,1,为队头元素，,a,n,为队尾元素；,(3),在表尾插入元素操作，称为入队操作；,在表头删除元素的操作，称为出队操作；,(4),元素按,a,1,a,2,a,3,. a,n,顺序入队，,第,1,个入队的元素为,a,1,，最后一个入队的元素是,a,n,；,第,1,个出队的元素为,a,1,最后一个出队的元素是,a,n,(5),队列具有先进先出的特点，所以又称为先进先出表（,FIFO,表）,46,PPT,学习交流,二队列的基本操作,（1）初始化操作,InitQueue( &Q),功能：构造一个空队列,Q；,（,2）,销毁操作,DestroyQueue( &Q),功能：销毁已存在队列,Q；,（,3）,置空操作,ClearQueue(&Q),功能：,将队列,Q,置为空队列；,（4）判空操作,QueueEmpty(Q),功能：若队列,Q,为空，则返回,True，,否则返回,False；,47,PPT,学习交流,（,5）,取队头元素操作,GetHead(Q,&e),功能：取队头元素，并用,e,返回；,（,6）,入队操作,EnQueue( &Q, e ),功能：将元素,e,插入,Q,的队尾；,（,7）出队操作,DeQueue( &Q, &e),功能：若队列不空，则删除,Q,的队头元素，用,e,返回其值，并返回,OK，,否则返回,ERROR；,48,PPT,学习交流,3.4.,2,队列的顺序表示和实现,一、 队列的顺序存贮结构,队列的,顺序存储,结构是用一组,地址连续,的存储单元依次存放队列中的各个元素，并用指针,front,指向队头，指针,rear,指向队尾 。,Q.rear,Q.front,J1,J2,J3,实际上，,front,指针始终指向队头元素，,rear,指针实际上并不是指向队尾元素，而是指向队尾元素的下一个位置。如图：,队列的顺序存贮结构图示,49,PPT,学习交流,#,define MAXSIZE 100/,最大队列长度,typedef struct, QElemType *base;/,初始化时动态分配,存储空间的基址,int,front;/,队头指针，指向队头元素,int rear;/,队尾指针，指向队尾元素的下一个位置,SqQueue;,二、顺序队列的类型定义,50,PPT,学习交流,顺序队列常常会出现“假溢出”现象，如图所示。虽然队列中还有一定的存储空间，但因为,front,指针与,rear,指针均向同一个方向移动，导致该队列不能再进行入队操作。,rear,front,E,D,C,51,PPT,学习交流,为了避免“假溢出”，可以这样规定，一旦,rear,指针（或,front,指针）指向了存储空间的末尾位置，如果此时再进行入队（或出队）操作，则将相应的指针平移到数组的起始位置，即是将队列假想为一个循环的环状空间，我们称之为,循环队列,。,52,PPT,学习交流,三、循环队列操作图示,front,rear,空队,front = rear,是队空标志,3,1,2,0,MAXSIZE = 4,A,rear,front,A,进队,B,进队,A,B,rear,front,C,进队,A,rear,front,B,C,53,PPT,学习交流,front,rear,空队,front = rear,是队空标志,B,C,rear,front,3,1,2,0,MAXSIZE = 4,A,出队,三、循环队列操作图示,队列中含有,3,个元素，,rear,已经指向存储空间的末端，不能再向上移动,A,rear,front,B,C,54,PPT,学习交流,front,rear,空队,front = rear,是队空标志,C,rear,front,rear,front,3,1,2,0,MAXSIZE = 4,B,C,B,出队,三、循环队列操作图示,队列中含有,2,个元素,55,PPT,学习交流,C,rear,front,D,MAXSIZE = 4,此刻,rear,已经指向存储空间的末端,若再有元素进队列，则执行语句：,rear=(rear+1)%,MAXSIZE,rear,front,C,三、循环队列操作图示,D,元素进队列，执行：,rear=(rear+1)%,MAXSIZE,经过计算，,rear,的值为,0,56,PPT,学习交流,front,rear,空队,front = rear,是队空标志,C,C,rear,front,rear,front,D,E,3,1,2,0,MAXSIZE = 4,D,E,进队,三、循环队列操作图示,Rear,重新指向存储空间的起始位置，此刻队列仍有存储空间，可以进行进队操作,57,PPT,学习交流,front,rear,空队,front = rear,是队空标志,C,C,rear,front,rear,front,D,E,F,3,1,2,0,MAXSIZE = 4,F,进队 ，队满,队满与队空,条件混淆,E,D,三、循环队列操作图示,58,PPT,学习交流,front,rear,空队,front = rear,是队空标志,C,rear,front,D,E,F,3,1,2,0,MAXSIZE = 4,为了区分队满与队空，规定,队满条件,为,：,( rear + 1) % MAXQSIZE = front,所以队列中最多能包含的元素个数比实际空间少一个,队满,三、循环队列操作图示,59,PPT,学习交流,出队时应先判,-,-,队是否空,?,队空,条件,：,Q.rear = Q.front,不空，则出队。,进队时应先判,-,队是否满,?,队满,条件,：,(,( Q.rear + 1) % MAXQSIZE ) = Q.front,不满，则进队,。,60,PPT,学习交流,(1),初始化循环队,Status InitQueue (SqQueue &Q ), Q.base = ( QElemType * ) malloc(MAXSIZE *,sizeof(QElemType);,if ( ! Q.base) exit( OVERFLOW ) ;,Q.front = Q.rear = 0;,return OK;,四、循环队列基本操作的实现,Q.base = new QElemType MAXSIXE;,61,PPT,学习交流,（,2,）,进队操作,Status EnSqQueue (SqQueue &Q, QElemType e ), if ( ( ( Q.rear + 1) % MAXQSIZE ) = Q. front ) return ERROR ;,/,队满,Q.base Q.rear = e; /,e,入队,Q.rear = ( ( Q.rear + 1) % MAXQSIZE ); /,修改尾指针,return OK;, / EnQueue ;,C,rear,front,D,E,3,1,2,0,C,rear,front,D,E,D,rear,front,再进队,满,（上溢）,再进队循环、满,再进队循环、不满,D,rear,front,S,S,进队,62,PPT,学习交流,（,3,）,出队操作,P.76,Status DeSqQueue (SqQueue &Q, QElemType &e ), if ( Q.rear = Q.front) return ERROR ; /,队空,e = Q.base Q.front ;,/,取队首元素,Q.front = ( Q.front + 1) % MAXQSIZE ;,/,出队,return OK;,C,rear,front,E,出队,不循环,rear,front,E,出队,不循环,rear,front,队,空,63,PPT,学习交流,3.4.,3,链队列,队列的链式存储结构和实现,一、定义,用链表表示的队列，称为链队列,Q.front,Q.rear,空链队列,J1,Q.front,Q.rear,J2,非空链队列,64,PPT,学习交流,二、链队列的类型定义,typedef struct QNode /,链队列结点的类型定义, QElemType data;,struct QNode,*,next;,QNode , *QueuePtr;,typedef struct /,链队列表头结点的类型定义, QueuePtr *front;/,队头指针，指向链表的头结点,QueuePtr,*,rear;/,队尾指针，指向队尾结点,LinkQueue;,65,PPT,学习交流,设,Q,为,LinkQueue,类型的变量，,Q,为链队列的表头结点，用于,存储队列队头指针和队尾指针。,链队列的,表头结点,链队列的,头结点,空链队列,J1,Q.front,Q.rear,J2,非空链队列,Q.front,Q.rear,66,PPT,学习交流,（,1）,初始化队操作：,InitQueue ( LinkQueue &Q ),Status InitQueue( LinkQueue &Q ), /,建,一个空队列,Q,Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);,/,为,链队列的头结点分配空间,if (!Q.front) exit(OVERFLOW);,Q.front-next=NULL;,return OK;,三、 链队列基本操作的算法,Q.front,Q.rear,空链队列,67,PPT,学习交流,销毁,队,操作,：,DestroyQueue( LinkQueue &Q ),Status DestroyQueue( LinkQueue &Q ),/,销毁队列,Q if (!Q.front) return ERROR; /,链队列不存在,while(Q.front) /,回收,链队列的所有元素结点空间,Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear,return OK;,Q.front,Q.rear,null,null,销毁后,68,PPT,学习交流,Q.front,J1,Q.rear,e,e,入队前,e,入队后,J1,Q.front,Q.rear,（3）入队操作,EnQueue(LinkQueue &Q, QElemType e),入队操作图示：,69,PPT,学习交流,Status EnQueue(LinkQueue &Q, QElemType e ),/,在链队列,Q,队尾，插入新的队尾结点,/,为新元素,p,分配结点空间,p=(QueuePtr) malloc (sizeof(QNode);,if (!p) exit (OVERFLOW); /,存储分配失败,p-date=e;p-next=NULL; Q.rear-next=p; /,插入新队尾结点,Q.rear=p; /,修改队尾指针,return OK;,Q.front,J1,Q.rear,e,J1,e,入队,P,70,PPT,学习交流,（,4,）出队操作：,Status DeQueue(LinkQueue &Q, QElemType &e) /,若队列不空，则删除,Q,的队头元素结点，用,e,返回其值,/,若队列空，返回,ERRORif (Q.front = =Q.rear) return ERROR;,p=Q.front-next;/ p,指向队头元素结点,e=p-data;Q.front-next=p-next; /,修改链队列头结点指针,/,对于链队列只有一个元素结点的情况，要同时修改,if (Q.rear= =p),Q.rear=Q.front;,/,队尾指针,free(p); return OK; ,71,PPT,学习交流,3.4.4,队列的应用举例,队列与栈一样，也是程序设计中经常使用的数据结构，其应用主要体现在以下,4,个方面：,（1）解决计算机主机与外设不匹配的问题（2）解决由于多用户引起的资源竞争问题,（3）离散事件的模拟,-模拟实际应用中的各种排队现象（4）用于处理程序中具有先进先出特征的过程,操作系统课程,72,PPT,学习交流,第,1,行,1,第,2,行,1 1,第,3,行,1 2 1,第,4,行,1 3 3 1,第,5,行,1 4 6 4 1,例,1.,二项式系数值（杨辉三角）,可以看出第,i,行除首尾元素之外，中间,i-2,个元素的值均可通过上一行的元素计算出来,73,PPT,学习交流,利用循环队列打印杨辉三角的过程：,设队列的最大容量为,5,，*表示已经出队列。,1,1,1,q.front,q.rear,1,1,1,*1,q.front,q.rear,*1,1,1,*1,2,q.front,q.rear,*1,*1,1,1,2,q.front,q.rear,1,*1,1,1,2,q.front,q.rear,1,3,*1,1,2,q.front,q.rear,74,PPT,学习交流,1,3,3,1,*2,q.front,q.rear,1,3,3,*1,1,q.front,q.rear,75,PPT,学习交流,此课件下载可自行编辑修改，供参考！,感谢您的支持，我们努力做得更好！,76,PPT,学习交流,
展开阅读全文