第3章栈和队列2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,实验一,线性表的插入与删除,1、以福彩和体彩选号器为设计实例，重点掌握循环链表的插入和删除操作。,2、设计程序能够完成线形表的生成、插入和删除元素。,3、集合的并、交和差运算（参见严习题,P80）。,4、,一元稀疏多项式计算器（参见教材,P39,和严习题,P81）。,实验内容,：（任选一题）,1,上堂课遗留问题讨论,教材,P43,中,case1：,DelFirst,(,hb,qb,)；,InsFirst,(ha,qb,)；,是先删除后插入，有无风险？这两条语句能否颠倒？,2.,教材,P53,表3.1中，,1,和,2,哪个对应栈顶元素，哪个对应键盘输入字符？,答：,根据,P53,Precede(),函数可知，1对应栈顶元素。因此：,答：,无风险，因为删除语句中没有,free(p),操作，且链表的合并无需删除结点，只需重链指针。,可以颠倒次序，但会繁琐些，因为,InsFirst,的入口参数,qb,还得作为输出参数被送出来。,若,栈顶元素 操作符,，则退栈、计算，结果压入,OPND,栈；,栈顶元素=操作符且不为#,，脱括号（弹出左括号）；,栈顶元素next=S;rear=S;,出队（头部删除）：,front-next=p-next;,完整动作设计参见教材,P61-62,队列会满吗？,front=rear,一般不会，因为删除时有,free,动作。除非内存不足！,6,顺序队示意图,Q,(队尾),(队首),front,a,1,a,2,a,3,data,a,4,0,.,.,.,.,.,.,.,99,rear,队列会满吗？,很可能会，因为数组前端空间无法释放,。,因此,数组应当有长度限制。,空队列的特征？,约定：,front=rear,队尾后地址,入队(尾部插入)：,vrear=e;rear+;,出队(头部删除)：,x=vfront;front+;,讨论：,假溢出,有缺陷,怎样实现入队和出队操作？,3.2 队列,7,问：什么叫“假溢出”？如何解决？,答：,在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。,3.2 队列,解决假溢出的途径,采用循环队列,8,a3,a2,a1,0,1,2,3,N-1,rear,front,循环队列（臆造）,顺序队列,a3,a2,a1,front,rear,0,1,2,3,.,.,N-1,新问题：,在循环队列中，空队特征是,front=rear；,队满时也会有,front=rear；,判决条件将出现二义性！,解决方案有三：,加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前,front=rear,使用一个计数器记录队列中元素个数（即队列长度）；,人为浪费一个单元，令,队满特征为,front=(rear+1)%N；,9,队空条件,:,front=rear,(,初始化时：,front=rear),队满条件,：,front=(rear+1)%N,(N=,maxsize,),队列长度：,L=（Nrearfront）%N,J2 J3,J1 J4,J5,front,rear,选用,空闲单元法：,即,front,和,rear,之一指向实元素，另一指向空闲元素。,问2：,在具有,n,个单元的循环队列中，队满时共有多少个元素？,n-1个,6,问1：,左图中队列长度,L=？,10,J6 J5,J7,J8 J9,例1：,一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,J2 J3,J1 J4,J5,front,rear,解：,由图可知，队头和队尾指针的初态分别为,front=1,和,rear=6。,front,rear,删除4个元素后,front=5；,再插入4个元素后，,r=(6+4),%,6=4,front,front,front,front,front,11,例2：,数组,n,用来表示一个循环队列，,f,为当前队列头元素的,前一,位置，,r,为队尾元素的位置。假定队列中元素的个数小于,n，,计算队列中元素的公式为:,（）,rf,（,）（,nfr）%n,（,）,nrf,（,）（,nrf）%n,4,种公式哪种合理？,当,r f,时（,A）,合理；,当,r f,时（,C）,合理；,分析：,综合2种情况，以（,D）,的表达最为合理,例3：,在一个循环队列中，若约定队首指针指向队首元素的,前一个,位置。那么，从循环队列中删除一个元素时，其操作是 先,，后,。,移动队首指针,取出元素,12,问：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序）；,操作系统中多道作业的处理（一个,CPU,执行多个作业）；,3.,简化程序设计。,答：,循环队列的操作实现,见教材,P64,13,循环队列的操作实现,1）,初始化一空队列,算法要求：生成一空队列,算法操作：为队列分配基本容量空间,设置队列为,空队列，,即,front=rear=0（,也可为任意单元，如 2，或 4）;,14,算法：,Status,InitQueue,(,SqQueue,&q),/,初始化空循环队列,q,q.base=(,QElemType,*),malloc,(,sizeof,(,QElemType,）,*QUEUE_MAXSIZE,),;,/,分配空间,if(,!q.base,)exit(OVERFLOW);/,失败，退出程序,q.front=q.rear=0;/,置空队列,return OK;,/,InitQueue,;,新开单元的地址为0则表示内存不足,15,算法说明：向循环队列的队尾插入一个元素,分 析,：,(1),插入前应当先判断队列是否满,if(,(,q.rear+1,),%,QUEUE_MAXSIZE,)=q.front),return ERROR;,(2）,插入动作,q.base q.rear=e;,q.rear=(q.rear+1)%,QUEUE_MAXSIZE,;,2）入队操作,16,Status,EnQueue,(,SqQueue,&q,QElemType,e),/,向循环队列,q,的队尾加入一个元素,e,if(q.rear+1)%,QUEUE_MAXSIZE,=q.front ),return ERROR;,q.base q.rear =e;/,存储,q.rear=(q.rear+1)%,QUEUE_MAXSIZE,;/,指针后移,return OK;,/,EnQueue,;,2）入队操作（完整函数）,17,3）出队操作,算法说明：删除队头元素，返回其值,e,分 析：,（1）,在删除前应当判断队列是否空；,if(q.front=q.rear)return ERROR;,（2）,插入动作分析；,因为队头指针,front,指向队头元素的位置，所以：,e=q.base q.front ;,q.front=(q.front+1)%,QUEUE_MAXSIZE,;,18,Status,DeQueue,(,SqQueue,&q,QElemType,&e),/,若队列不空，删除循环队列,q,的队头元素，,/由,e,返回其值，并返回,OK,if(q.front=q.rear)return ERROR;/,队列空,e=q.base q.front ;,q.front=(q.front+1)%,QUEUE_MAXSIZE,;,return OK;,/,DeQueue,算法：,19,讨论（代本,章,小结）,线性表、栈与队的异同点,相同点：,逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即,受限的线性表,（只是对插入、删除运算加以限制）。,不同点：,运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表,LIFO；,队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表,FIFO。,用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。,20,注：下次课（月 日）,前,请完成,第2章自测卷,全部内容，有关算法设计题，建议上机验证。,21,