第3章 栈和队列(学生)

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,北京林业大学信息学院,data structure,2024年10月2日,陈正铭,数据结构,2024年10月2日,3.1,栈,3.2,栈,的应用,3.3,栈与递归,3.4,队列,3.5,队列的应用,教学内容,2024年10月2日,第,3,章,栈和队列,掌握栈和队列的,特点,，并能在相应的应用问题中正确选用,熟练掌握栈的,两种存储结构,的基本操作实现算法，特别应注意,栈满和栈空,的条件,熟练掌握,循环队列和链队列,的基本操作实现算法，特别注意,队满和队空,的,条件,理解,递归算法,执行过程中栈的状态变化过程,教学目标,2024年10月2日,3.1,栈,1.,定义,用,顺序栈,或,链栈,存储均可，但以顺序栈更常见,3.,存储结构,与线性表相同，仍为,一对一,关系,2.,逻辑结构,只能在,表的一端,（,栈顶,）进行插入和删除运算的,线性表,2024年10月2日,只能在,栈顶,运算，且访问结点时依照,后进先出,（,LIFO,）,或,先进后出,（,FILO,）,的原则,4.,运算规则,关键是编写,入栈,和,出栈,函数，具体实现依顺序栈或链栈的不同而不同,基本操作有,入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空,等,5.,实现方式,2024年10月2日,栈是一种特殊的线性表，它只能在表的一端（栈顶）进行插入和删除运算,栈与一般线性表的区别：仅在于,运算规则,不同,“,进,”,压入,=PUSH,（,),“,出,”,弹出,=POP( ),一般线性表,逻辑结构：一对一,存储结构：顺序表、链表,运算规则：随机,、,顺序存取,栈,逻辑结构：一对一,存储结构：顺序,栈,、链,栈,运算规则：,后进先出,栈与一般线性表的区别,2024年10月2日,“,进,”,压入,=PUSH,（,),“,出,”,弹出,=POP( ),2024年10月2日,a,1,a,2,a,n,顺序栈,S,a,i,表头,表尾,栈底,base,栈顶,top,低地址,高地址,写入：,vi,=,a,i,读出：,x=,vi,压入：,PUSH (,a,n+1,),弹出：,POP (x),前提：一定要预设栈顶指针,top,！,低地址,高地址,vi,a,1,a,2,a,i,a,n,顺序表,Vn,a,n+1,顺序栈与顺序表,2024年10月2日,顺序栈的表示,空栈,base = top,是栈空标志,stacksize,= 4,top,A,base,base,top,A,B,A,B,C,top,base,top,base,A,B,C,D,base,top,3,1,2,0,top,指示真正的,栈顶元素之上,的下标地址,栈满时的处理方法：,1、,报错,返回操作系统。,2、,分配更大的空间,，作为栈的存储空间,将原栈的内容移入新栈。,2024年10月2日,#define MAXSIZE 100,typedef,struct,SElemType,*base;,SElemType,*top;,int,stacksize,;,SqStack,;,顺序栈的表示,2024年10月2日,构造一个空栈,步骤：,(1),分配空间并检查空间是否分配失败，若失败则返回错误,顺序栈初始化,base,stacksize,top,s,(2),设置栈底和栈顶指针,S.top,=,S.base,;,(3),设置栈大小,2024年10月2日,Status,InitStack,(,SqStack,&S ),S.base,=new,SElemTypeMAXSIZE,；,if( !,S.base,) return OVERFLOW;,S.top,=,S.base,;,S.stackSize,= MAXSIZE;,return OK;,顺序栈初始化,2024年10月2日,判断顺序栈是否为空,bool,StackEmpty,(,SqStack,S ),if(,S.top,=,S.base,) return true;,else return false;,base,top,3,1,2,0,求顺序栈的长度,int,StackLength,(,SqStack,S ),return,S.top,S.base,;,base,top,A,B,2024年10月2日,Status,ClearStack,(,SqStack,S ),if(,S.base,),S.top,=,S.base,;,return OK;,清空顺序栈,base,top,3,1,2,0,2024年10月2日,Status,DestroyStack,(,SqStack,&S ),if(,S.base,),delete,S.base,;,S.stacksize,= 0;,S.base,=,S.top,= NULL;,return OK;,销毁顺序栈,2024年10月2日,(1),判断是否栈满，若满则出错,(2),元素,e,压入栈顶,(3),栈顶指针加,1,顺序栈进栈,Status Push(,SqStack,&S,SElemType,e),if(,S.top,-,S.base,=,S.stacksize,) /,栈满,return ERROR;,*,S.top,+=e;,return OK;,*,S.top,=e;,S.,top,+;,A,B,C,top,base,2024年10月2日,(1),判断是否栈空，若空则出错,(2),获取栈顶元素,e,(3),栈顶指针减,1,顺序栈出栈,Status Pop(,SqStack,&S,SElemType,&e),if(,S.top,=,S.base,) /,栈空,return ERROR;,e, *,-,S.top,;,return OK;,-,S.,top,;,e=*,S.top,;,A,B,C,top,base,2024年10月2日,判断是否空栈，若空则返回错误,否则通过栈顶指针获取栈顶元素,取顺序栈栈顶元素,Status,GetTop,(,SqStack,S,SElemType,&e),if(,S.top,=,S.base,) return ERROR; /,栈空,e = *(,S.top, 1 );,return OK;,e = *(,S.top,- ); ?,A,B,C,top,base,2024年10月2日,435612,中到了,12,顺序不能实现；,135426,可以实现。,1.,如果一个栈的输入序列为,123456,，能否得到,435612,和,135426,的出栈序列？,练习,(,经验值,200),2024年10月2日,b,0,t,0,t,1,b,1,0 m-1,V,双栈共享一个栈空间,优点：互相调剂，灵活性强，减少溢出机会,具体参考,P71,算法设计题（,1,）,2024年10月2日,链栈的表示,运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针,typedef,struct,StackNode,SElemType,data;,struct,StackNode,*next;,StackNode, *,LinkStack,;,LinkStack,S;,data next,栈顶,栈底,S,2024年10月2日,链栈的初始化,void,InitStack(,LinkStack,&S ),S=NULL;,NULL,S,判断链栈是否为空,Status,StackEmpty(,LinkStack,S) if (S,=NULL,) return TRUE; else return,FALSE;,2024年10月2日,链栈进栈,p,S,e,S,Status,Push(,LinkStack,&S,SElemType,e),p=new,StackNode,; /,生成新结点,p,if (!p),exit(OVERFLOW,);,p-data=e; p-next=S; S=p;,return OK;,2024年10月2日,链栈出栈,S,A,e = A,p,S,2024年10月2日,链栈出栈,Status Pop (,LinkStack,&,S,SElemType,&,e),if (S=NULL) return,ERROR;,e = S- data; p = S; S = S- next;,delete p; return OK; ,e = A,S,2024年10月2日,取链栈栈顶元素,SElemType,GetTop(LinkStack,S),if (,S=NULL),exit(ERROR,),；,else,return Sdata,;,2024年10月2日,3.2,栈的应用,例,1,：数制转换（十转,N,）,用栈暂存低位值,例,2,：,括号匹配的检验,用栈暂存左括号,例,3,：,表达式求值（自学）,用栈暂存运算符,简化了程序设计的问题,例,1,、 数制转换,算法基于原理：,N = (N div d)d + N mod d,例如：（,1348),10,= (2504),8,，其运算过程如下：,N N div 8 N mod 8,1348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,void conversion () ,InitStack(S,);,cin,N;,while (N),Push(S, N % 8);,N = N/8; ,while (!,StackEmpty(S,),),Pop(S,e);,cout,x,=,x,x,表,3.1,算符间的优先关系,2024年10月2日,【,算法思想,】,（,1,）初始化,OPTR,栈和,OPND,栈，将 “,#”,压入,OPTR,（,2,）依次读入字符,ch,，循环执行（,3,）至（,5,）,（,3,）取出,OPTR,的栈顶元素，当,OPTR,的栈顶元素和,ch,均为“,#”,时，表达式求值完毕，,OPND,栈顶元素为表达式的值,设定两栈 ：,OPND-,操作数或运算结果,OPTR-,运算符,（,4,）,if (,ch,是操作数,),则,ch,进,OPND,，读入下一字符,ch,（,5,）,else,比较,OPTR,栈顶元素和,ch,的优先级,case :,运算符,ch,进,OPTR,，读入下一字符,ch,case=:,脱括号（弹出左括号），读入下一字符,ch,case :,栈顶运算符退栈、计算，结果进,OPND,2024年10月2日,北京林业大学信息学院,OperandType,EvaluateExpression,( ) ,InitStack,(OPND);,ch,=,getchar,( );,while (,ch,!= # |,GetTop(OPTR,)! = #) ,if (!,In(ch,OP)Push(OPND,ch,);,ch,=,getchar,(); /,ch,不是运算符则进栈,else,switch (,Precede(GetTop(OPTR),ch,) /,比较优先权,case : /,弹出,OPTR,栈顶的运算符运算，并将运算结果入栈,Pop(OPTR, theta);,Pop(OPND, b);,Pop(OPND, a);,Push(OPND,Operate(a, theta, b); break;,case = : /,脱括号并接收下一字符,Pop(OPTR,x,);,ch,=,getchar,();,break;, / switch, / while,return,GetTop(OPND,); /,EvaluateExpression,2024年10月2日,OPTR,OPND,INPUT,OPERATE,3*(7-2)#,Push(opnd,3),#,*(7-2)#,3,#,Push(optr,*),#,*,3,(7-2)#,Push(optr,(),#,*,(,3,7-2)#,Push(opnd,7),#,*,(,3,7,-2)#,Push(optr,-),#,*,(,3,7,2)#,Push(opnd,2),#,*,(,3,7,2,)#,Operate(7-2),#,*,(,3,5,)#,Pop(optr,),#,*,3,5,#,Operate(3*5),#,15,#,GetTop(opnd,),2024年10月2日,3.3,栈与递归,递归的定义,若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程,直接地或间接地调用自己,则称这个过程是递归的过程。,2024年10月2日,当多个函数构成嵌套调用时,遵循,后调用先返回,栈,递归与栈的关系,2024年10月2日,以下三种情况常常用到递归方法,递归定义的数学函数,具有递归特性的数据结构,可递归求解的问题,2024年10月2日,1.,递归定义的数学函数,:,阶乘函数,:,2,阶,Fibonaci,数列,:,2024年10月2日,树,2.,具有递归特性的数据结构,:,Root,Lchild,Rchild,广义表,A=(,a,A,),3.,可递归求解的问题,:,迷宫问题,Hanoi,塔问题,2024年10月2日,分治法：,对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解,1,、能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的,2,、可以通过上述转化而使问题简化,3,、必须有一个明确的递归出口，或称递归的边界,用分治法求解递归问题,必备的三个条件,2024年10月2日,分治法求解递归问题算法的一般形式：,void p (,参数表,) ,if,（递归结束条件）可直接求解步骤；,-,基本项,else p,（较小的参数）；,-,归纳项,long,Fact (,long,n ),if,( n,=,0),return,1,;,/,基本项,else return,n * Fact (n,-,1),;,/,归纳项,2024年10月2日,在印度圣庙里，一块黄铜板上插着三根宝石针。,主神梵天在创造世界时，在其中一根针上穿好了由大到小的,64,片金片，这就是汉诺塔。,僧侣不停移动这些金片，一次只移动一片，小片必在大片上面。,当所有的金片都移到另外一个针上时，世界将会灭亡。,汉诺塔,2024年10月2日,规则,:,(1),每次只能移动一个圆盘,(2),圆盘可以插在,A,B,和,C,中的任一塔座上,(3),任何时刻不可将较大圆盘压在较小圆盘之上,Hanoi,塔问题,A,B,C,2024年10月2日,Hanoi,塔问题,n = 1,，则直接从,A,移到,C,。否则,(1),用,C,柱做过渡，将,A,的,(n-1),个移到,B,(2),将,A,最后一个直接移到,C,(3),用,A,做过渡，将,B,的,(n-1),个移到,C,2024年10月2日,#include,int,c=0;,void,move(char,x,int,n,char,z),cout,+c,n,x,zc,2024年10月2日,调用前,系统完成,:,(1),将,实参,返回地址,等传递给被调用函数,(2),为被调用函数的,局部变量,分配存储区,(3),将控制转移到被调用函数的,入口,调用后,系统完成,:,(1),保存被调用函数的计算,结果,(2),释放被调用函数的,数据区,(3),依照被调用函数保存的,返回地址,将控制转移到调用函数,函数调用过程,2024年10月2日,空间效率,时间效率,O(,2,n,),与递归树的结点数成正比,与递归树的深度成正比,O(n,),递归算法的效率分析,2024年10月2日,1 2 3 4,f(1)=1 f(1)+1+f(1)=3 f(2)+1+f(2)=7 f(3)+1+f(3)=15,f(n,) = 2f(n-1)+1,f(n-1) = 2f(n-2)+1,f(n-2) = 2f(n-3)+1,.,f(3) = 2f(2)+1,f(2) = 2f(1)+1,2,0,f(n) = 2,1,f(n-1)+2,0,2,1,f(n-1) = 2,2,f(n-2)+2,1,2,2,f(n-2) = 2,3,f(n-3)+2,2,.,2,n-3,f(3) = 2,n-2,f(2)+ 2,n-3,2,n-2,f(2) = 2,n-1,f(1)+ 2,n-2,f(n,) = 2,0,+2,1,+2,n-2,+ 2,n-1,f(1) = 2,n,-1,递归算法的效率分析,2024年10月2日,64,片金片移动次数：,2,64,-1=18446744073709551615,假如每秒钟一次，共需多长时间呢？,一年大约有,31536926,秒，移完这些金片需要,多亿年,世界、梵塔、庙宇和众生都已经灰飞烟灭,!,2024年10月2日,优点：,结构清晰，程序易读,缺点：,每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。,递归的优缺点,2024年10月2日,3.4,队列,队列是一种先进先出,(FIFO),的线性表,.,它只允许在表的一端进行插入,而在另一端删除元素,a,1,a,2,a,3,a,n,.,入队列,队头,队尾,2024年10月2日,设栈,S,和队列,Q,的初始状态为空，元素,e1,、,e2,、,e3,、,e4,、,e5,和,e6,依次通过,S,，一个元素出栈后即进入,Q,，若,6,个元素出队的序列是,e2,、,e4,、,e3,、,e6,、,e5,和,e1,，则栈,S,的容量至少应该是（）。,（,A,）,2,（,B,）,3,（,C,）,4,（,D,）,6,课堂任务（经验值,200,）,2024年10月2日,数据对象,:,数据关系,:,基本操作,:,(1),InitQueue,(&Q) /,构造空队列,(2),DestroyQueue,(&Q) /,销毁队列,(3),ClearQueue,(&S) /,清空队列,(4),QueueEmpty(S,) /,判空,.,空,-TRUE,ADT Queue ,队列的抽象数据类型,2024年10月2日,(5),QueueLength(Q,) /,取队列长度,(6),GetHead,(,Q,&e,) /,取队头元素,(7),EnQueue,(&,Q,e,) /,入队列,(8),DeQueue,(&,Q,&e,) /,出队列,(9),QueueTraverse(Q,visit,() /,遍历,ADT Queue,队列的抽象数据类型,2024年10月2日,#define M 100 /,最大队列长度,Typedef,struct,QElemType,*base; /,初始化的动态分配存储空间,int,front; /,头指针,int,rear; /,尾指针,SqQueue,;,队列的顺序表示,用一维数组,baseM,2024年10月2日,队列的顺序表示用一维数组,baseM,Q.front,0,1,2,3,4,5,Q.rear,Q.front,Q.rear,J,1,J,2,J,3,Q.front,Q.rear,J,3,Q.front,Q.rear,J,5,J,6,front=rear=0,空队标志：,front= =rear,入队：,baserear,+=x;,出队：,x=,basefront,+;,2024年10月2日,Q.front,Q.rear,J5,J6,Q.front,0,1,2,3,4,5,Q.rear,J5,J6,J1,J2,J3,J4,存在的问题,设数组大小为,M,front=0,rear=M,时,再入队,真溢出,front,0,rear=M,时,再入队,假溢出,2024年10月2日,解决的方法循环队列,1,0,Q.rear,Q.front,.,.,base0,接在,baseM-1,之,后,若,rear+1=M,则令,rear=0;,实现：利用“模”运算,入队：,baserear,=x;,rear=(rear+1)%M;,出队：,x=,basefront,;,front=(front+1)%M;,2024年10月2日,北京林业大学信息学院,J4,J5,J6,0,1,2,3,4,5,rear,front,J9,J8,J7,J7,J8,J9,入队,队空：,front=rear,队满：,front=rear,解决方案：,1.,另外,设一个标志,以区别队空、队满,2,.,少用一个元素空间,：,队空：,front=rear,队满：(,rear+1)%M=front,J4,J5,J6,0,1,2,3,4,5,rear,front,0,1,2,3,4,5,front,J4,J5,J6,出队,rear,2024年10月2日,循环队列,#define MAXQSIZE 100 /,最大队列长度,Typedef,struct,QElemType,*base; /,初始化的动态分配存储空间,int,front; /,头指针,int,rear; /,尾指针,SqQueue,;,2024年10月2日,Status,InitQueue,(,SqQueue,&Q),Q.base,=new,QElemTypeMAXQSIZE,if(!Q.base,),exit(OVERFLOW,);,Q.front,=,Q.rear,=0;,return OK;,循环队列初始化,2024年10月2日,求循环队列的长度,int,QueueLength,(,SqQueue,Q),return (,Q.rear-Q.front+MAXQSIZE)%MAXQSIZE,;,2024年10月2日,Status,EnQueue(SqQueue,&,Q,QElemType,e),if(Q.rear+1)%MAXQSIZE=,Q.front,) return ERROR;,Q.baseQ.rear,=e;,Q.rear,=(Q.rear+1)%MAXQSIZE;,return OK;,循环队列入队,2024年10月2日,Status,DeQueue,(,LinkQueue,&,Q,QElemType,&e),if(Q.front,=,Q.rear,) return ERROR;,e=,Q.baseQ.front,;,Q.front,=(Q.front+1)%MAXQSIZE;,return OK;,循环队列出队,2024年10月2日,.,.,.,data,next,队头,队尾,Q.front,Q.rear,链队列,2024年10月2日,typedef,struct,QNode, /,链队列结点定义,QElemType,data;,struct,Qnode,*next;,Qnode, *,QueuePtr,;,typedef,struct, /,链队列定义,QueuePtr,front; /,队,头指针,QueuePtr,rear; /,队尾指针,LinkQueue,;,链队列,2024年10月2日,(a),空队列,(b),元素,x,入,队列,(d),元素,x,出,队列,(c),元素,y,入,队列,链队列,2024年10月2日,Status,InitQueue,(,LinkQueue,&Q),Q.front,=,Q.rear,=new,QNode,;,if(!Q.front,),exit(OVERFLOW,);,Q.front,-next=NULL;,return OK;,链队列初始化,2024年10月2日,Status,DestroyQueue,(,LinkQueue,&Q),while(Q.front,),Q.rear,=,Q.front,-next;,free(Q.front,);,Q.front,=,Q.rear,;,return OK;,销毁链队列,2024年10月2日,Status,QueueEmpty,(,LinkQueue,Q),return (,Q.front,=,Q.rear,);,判断链队列是否为空,求链队列的队头元素,Status,GetHead,(,LinkQueue,Q,QElemType,&e),if(Q.front,=,Q.rear,) return ERROR;,e=,Q.front,-next-data,;,return OK;,2024年10月2日,Status,EnQueue(LinkQueue,&,Q,QElemType,e),p=new,QNode,;,if(!p,),exit(OVERFLOW,);,p-data=e; p-next=NULL;,Q.rear,-next=p;,Q.rear,=p;,return OK;,链队列入队,p,2024年10月2日,Status,DeQueue,(,LinkQueue,&,Q,QElemType,&e),if(Q.front,=,Q.rear,) return ERROR;,p=,Q.front,-next;,e=p-data;,Q.front,-next=p-next;,if(Q.rear,=p),Q.rear,=,Q.front,;,free(p,);,return OK;,链队列出队,p,2024年10月2日,【,例,】,模拟打印机缓冲区,在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。,3.5,队列的应用,2024年10月2日,【,例,】CPU,分时系统,在一个带有多个终端的计算机系统中，同时有多个用户需要使用,CPU,运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用,CPU,的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把,CPU,分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将,CPU,分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使,CPU,正常工作。,2024年10月2日,【,例,】,打印杨辉三角形,任务：请同学们写出该算法,3.20,的,c,语言程序实现，并在实验课验证之（经验值,200,）,2024年10月2日,1.,掌握栈和队列的,特点,，并能在相应的应用问题中正确选用,2.,熟练掌握栈的,顺序栈,和链栈的进栈出栈算法，特别应注意,栈满和栈空,的条件,3.,熟练掌握,循环队列,和链队列的进队出队算法，特别注意,队满和队空,的条件,4.,理解,递归算法,执行过程中栈的状态变化过程,小结,进阶任务,2,（完成每任务加经验值,100,）,请把下面名词术语翻译成英文，并大声读与拼写出来：,栈 栈顶 栈底,后进先出 顺序栈,链栈 递归,分治法 汉诺塔,队列 队头 队尾,先进先出 顺序队列,循环队列 链队列,进阶任务,2,（完成每任务加经验值,100,）,教材,P69,页，,1,选择题,（,1,）若让元素,1,，,2,，,3,，,4,，,5,依次进栈，则出栈次序不可能出现在（ ）种情况。,A,5,，,4,，,3,，,2,，,1 B,2,，,1,，,5,，,4,，,3,C,4,，,3,，,1,，,2,，,5 D,2,，,3,，,5,，,4,，,1,（,2,）若已知一个栈的入栈序列是,1,，,2,，,3,，,，,n,，其输出序列为,p1,，,p2,，,p3,，,，,pn,，若,p1=n,，则,pi,为（ ）。,A,i B,n-i,C,n-i+1 D,不确定,（,3,）数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素个数的公式为（ ）。,A,r-f,B,(,n+f-r)%n,C,n+r-f,D,（,n+r-f)%n,进阶任务,2,（完成每任务加经验值,100,）,（,4,）链式栈结点为：,(,data,link,),，,top,指向栈顶,.,若想摘除栈顶结点，并将删除结点的值保存到,x,中,则应执行操作（ ）。,A,x=top-,data;top,=top-link,；,B,top=,top,-,link;x,=top-link,；,C,x=,top;top,=top-link,；,D,x=top-link,；,（,5,）设有一个递归算法如下,int,fact(int,n) /n,大于等于,0,if(n,=0) return 1;,else return n*fact(n-1); ,则计算,fact(n,),需要调用该函数的次数为（ ）。,A,n+1 B,n-1 C,n D,n+2,（,6,）栈在 （ ）中有所应用。,A,递归调用,B,函数调用,C,表达式求值,D,前三个选项都有,进阶任务,2,（完成每任务加经验值,100,）,（,7,）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。,A,队列,B,栈,C, 线性表,D,有序表,（,8,）设栈,S,和队列,Q,的初始状态为空，元素,e1,、,e2,、,e3,、,e4,、,e5,和,e6,依次进入栈,S,，一个元素出栈后即进入,Q,，若,6,个元素出队的序列是,e2,、,e4,、,e3,、,e6,、,e5,和,e1,，则栈,S,的容量至少应该是（）。,A,2 B,3 C,4 D,6,（,9,）在一个具有,n,个单元的顺序栈中，假设以地址高端作为栈底，以,top,作为栈顶指针，则当作进栈处理时，,top,的变化为（）。,A,top,不变,B,top=0 C,top- D,top+,进阶任务,2,（完成每任务加经验值,100,）,（,10,）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。,A,线性表的顺序存储结构,B,队列,C.,线性表的链式存储结构,D.,栈,（,11,）用链接方式存储的队列，在进行删除运算时（）。,A.,仅修改头指针,B.,仅修改尾指针,C.,头、尾指针都要修改,D.,头、尾指针可能都要修改,（,12,）循环队列存储在数组,A0.m,中，则入队时的操作为（）,A. rear=rear+1 B. rear=(rear+1)%(m-1),C. rear=(rear+1)%m D. rear=(rear+1)%(m+1),进阶任务,2,（完成每任务加经验值,100,）,（,13,）最大容量为,n,的循环队列，队尾指针是,rear,，队头是,front,，则队空的条件是（）。,A. (rear+1)%n=front B. rear=front,C,rear+1=front D. (rear-,l)%n,=front,（,14,）栈和队列的共同点是（）。,A.,都是先进先出,B.,都是先进后出,C.,只允许在端点处插入和删除元素,D.,没有共同点,（,15,）一个递归算法必须包括（）。,A.,递归部分,B.,终止条件和递归部分,C.,迭代部分,D.,终止条件和迭代部分,2024年10月2日,（,2,）回文是指正读反读均相同的字符序列，如“,abba,”,和“,abdba,”,均是回文，但“,good”,不是回文。试写一个算法判定给定的字符向量是否为回文。,(,提示：将一半字符入栈,),算法设计题,进阶任务,2,（完成每任务加经验值,200,）,2024年10月2日,int,IsHuiwen,( char *t),/判断t字符向量是否为回文，若是，返回1，否则返回0,SeqStack,s;int,i ,len;char,temp;,InitStack,( ,len,=,strlen(t,); /,求向量长度,for ( i=0; ilen/2;,i+)/将一半字符入栈,Push( &s,ti,);,while( !,EmptyStack,( &s),/,每弹出一个字符与相应字符比较,temp=Pop (,if( temp!=,Si,) return 0 ;/ 不等则返回0,else i+;,return 1 ; /,比较完毕均相等则返回,1,任务：请同学们把本题用,c,语言程序实现，并在实验课验证之（经验值,200,）,2024年10月2日,（,10,）已知,f,为单链表的表头指针,链表中存储的都是整型数据，试写出实现下列运算的,递归,算法：, 求链表中的最大整数；, 求链表的结点个数；, 求所有整数的,平均值,。,算法设计题,进阶任务,2,（完成每子任务加经验值,200,）,2024年10月2日,void main( ),LinkList,L;,CreatList(L,);,cout,链表中的最大整数为：,next)next)return p-data;,else,int,max=,GetMax(p,-next);,return p-data=max ? p-,data:max,;,提示,2024年10月2日,int,Num,(,ListNode,*f,) /,递归算法,:,求链表中结点个数,if (,f = NULL,) return 0;/,空表,返回,0,return 1+,Num,(,f,-,link,); /,否则,返回后继链表结点个数加,1,float,Avg,(,ListNode,*f,int,&,n,) /,递归算法,:,求链表中所有元素的平均值,if (,f,-,link = NULL,) /,链表中只有一个结点,递归结束条件,n,= 1; return ( float ) (,f,-,data,); ,else ,float,Sum =,Avg,(,f,-,link,n,) *,n,;,n,+;,return (,f,-,data,+,Sum,) /,n,;,提示,任务：请同学们把本题用,c,语言程序实现，并在实验课验证之（经验值,200,）,进阶任务,2,（经验值,200,）,1.,串与线性表之间有什么相似之处？,2.,子串的定义是什么？,3.,串有哪几种机内表示方法（存储方法）？这些方法各有什么特点？,进阶任务,2,（经验值,200,）,在,Google,或百度搜索关于,D.E.Knuth,教授及其相关信息，并与课堂用,3,分钟向全体同学介绍。介绍得生动有趣的额外再加,100,经验值。,