北大数据结构课讲义7

1第四章栈和队列4.1栈4.2栈的顺序存储结构和操作实现4.3栈的链接存储结构和操作实现4.4栈的简单应用举例4.5算术表达式的计算4.6栈与递归4.7队列退出24.1栈栈的定义栈（stack）又称堆栈，是限定只在表尾进行插入或删除操作的线性表。栈S=(a1,a2,…，an)是按a1,a2,…，an次序进栈的，a1为栈底元素，an为栈顶元素。3栈与递归递归可使问题及求解步骤的描述变得简洁而清晰。特别是对于复杂问题，用递归方法分析描述，比较自然，利于理解。递归包括递归步骤和终止出口。递归问题转化为非递归往往要用栈来实现,把在递归中用到的变量入栈出栈,如书上【习题4-4】之9,1044.7队列队列是一种先进先出（FIFO）线性表。只允许在其一端删除元素，即队头（front），只允许在其另一端插入元素，即队尾（rear）。5图4-10顺序队列的插入和删除操作6……01234……M-2M-101234M-1M-2::循环队列把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为循环队列。入队时需先修改入队指针（队尾指针）rear==(rear+1)%QueueMaxSize出队时需要修改队头指针front==(front+1)%QueueMaxSize7初始时,队列为空,有front=0rear=0测试队列为空的条件是front=rear1Mabcdfrontrearad约定rear指出实际队尾元素所在的位置,front指出实际队头元素所在位置的前一个位置.8队列的静态数组一般是循环使用的。为了判别队列满和队列空的指针状况，令front指向队首元素的前一个位置。入队时需先修改入队指针（队尾指针）rear==(rear+1)%QueueMaxSize然后判断队列满的条件(rear+1)%QueueMaxSize==front最后将元素入队。出队时先判断队列空的条件front==rear然后修改队头指针front==(front+1)%QueueMaxSize最后将元素出队。910在顺序队列中插入和删除，不需要比较和移动任何元素，只需修改队尾和队首指针，并向队尾写入元素或从队首取出元素时间复杂度为：O(1)若存储队列的数组的长度为N，则队列长度（即所含元素个数）为:(N+rear-front)%N11（2）队列的链式存储结构structLinkQueue{LNode*front;LNode*rear;};structLNode{ElmeTypedata;LNode*next;};structLNode{ElemTypedata;//数据域Lnode*next;//指针域};1213在链队中插入和删除，不需要比较和移动任何元素，只需修改个别相关指针和进行结点的动态分配或回收操作时间复杂度为：O(1)144.4.4队列运算的实现1.队列运算在顺序存储结构上的实现（1）初始化队列voidInitQueue(Queue&Q){Q.MaxSize=10;Q.queue=newElemType[Q.MaxSiize];Q.front=Q.rear=0;}15（2）将队列清空,并释放动态存储空间voidClearQueue(Queue&Q){if(Q.queue!=NULL)delete[]Q.queue;Q.front=Q.rear=0;Q.queue=NULL;Q.MaxSize=0;}16（3）检查队列是否为空intQueueEmpty(Queue&Q){returnQ.front==Q.rear;}（4）读取队头元素//让front指针不是指向队首元素，而是指向它的前一个位置即：队首元素是队首指针front的下一个位置中的元素ElemTypePeekQueue(Queue&Q){if(Q.front==Q.rear){cerrQueueisEmpty.endl;exit(1);}returnQ.queue[(Q.front+1)%QueueMaxSize];}17（5）向队列插入新元素-1voidEnQueue(Queue&Q,constElemType&item){intk=(Q.rear+1)%QueueMaxSize;//队尾的下一位置if(k==Q.front){cerrQueueisoverflow.endl;exit(1);}Q.rear=k;Q.queue[k]=item;}入队时需先修改入队指针（队尾指针）rear==(rear+1)%QueueMaxSize然后判断队列满的条件(rear+1)%QueueMaxSize==front最后将元素入队。18（5）向队列插入新元素-2voidEnQueue(queue&Q,constElemType&item){if((Q.rear+1)%QueueMaxSize==Q.front){//扩大2倍的存储空间intk=sizeof(ElemType);Q.queue=(ElemType*)realloc(Q.queue,2*Q.MaxSize*k);//把原队列尾部内容后移MaxSize个位置if(Q.rear!=Q.MaxSize-1)19{for(inti=0;i=q.rear;i++)Q.queur[i+Q.MaxSize]=Q.queur[i];Q.rear+=Q.MaxSize;}Q.MaxSize=2*Q.MaxSize;}//求出队尾的下一个位置Q.rear=(Q.rear+1)%Q.MaxSize;//把item的值赋给新的队尾位置Q.queue[Q.rear]=item;}入队时需先修改入队指针（队尾指针）rear==(rear+1)%QueueMaxSize然后判断队列满的条件(rear+1)%QueueMaxSize==front最后将元素入队。20（6）从队列中删除元素ElemTypeOutQueue(Queue&Q){if(Q.front==Q.rear){cerrQueueisempty.endl;exit(1);}Q.front=(Q.front+1)%QueueMaxSize;//队头指向下一位置returnQ.queue[Q.front];}（7）检查队列是否已满intQueueFull(Queue&Q){return(Q.rear+1)%QueueMaxSize==Q.front;}出队时先判断队列空的条件front==rear然后修改队头指针front==(front+1)%QueueMaxSize最后将元素出队。212.队列运算在链接存储结构上的实现（1）初始化链队voidInitQueue(LinkQueue&HQ){HQ.front=HQ.rear=NULL;}（2）清空链队voidClearQueue(LinkQueue&HQ){LNode*p=HQ.front;while(p!=NULL){HQ.front=HQ.front-next;deletep;p=HQ.front;}HQ.rear=NULL;}structLNode{ElemTypedata;//数据域Lnode*next;//指针域};22（3）判断链队是否为空intQueueEmpty(LinkQueue&HQ){returnHQ.front==NULL;}（4）读取队首元素ElemTypePeekQueue(LinkQueue&HQ){if(HQ.front==NULL){cerr“Linkedqueueisempty.endl;exit(1);}returnHQ.front-data;}23（5）向链队中插入一个元素voidEnQueue(LinkQueue&HQ,constElemType&item){LNode*newptr=newLNode;if(newptr==NULL){cerr“Memoryalocationfailure.endl;exit(1);}newptr-data=item;newptr-next=NULL;if(HQ.rear==NULL)HQ.front=HQ.rear=newptr;elseHQ.rear=HQ.rear-next=newptr;}//不妨与书上P78的算法9(ppt4,算法9)：向单链表的末尾插入一个元素“相对照学习//思考与书上P137的算法2(ppt6,算法5)：向链栈中插入一个元素“的不同24（6）从队列中删除一个元素ElemTypeOutQueue(LinkQueue&HQ){if(HQ.front==NULL){cerr“Linkedqueueisempty.endl;exit(1);}ElemTypetemp=HQ.front-data;Lnode*p=HQ.front;HQ.front=p-next;if(HQ.front==NULL)HQ.rear=NULL;deletep;returntemp;}//不妨与书上P79的算法10(ppt4,算法12)：从单链表中删除表头元素“相对照学习//也可对照书上P137的算法3(ppt6,算法6)：从链栈中删除一个元素”254.4.6队列应用简介第一：解决主机与外设之间速度不匹配的问题如：打印输出。设置一个打印数据缓冲区，用队列存储待输出的数据，解决主机与外设速度不匹配的问题。第二：解决多用户引起的资源竞争问题如：多用户CPU资源竞争。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列261.熟悉栈的含义，掌握基本概念、存储结构和运算的实现。2.熟悉队列的含义，掌握基本概念、存储结构和运算的实现。本章学习要点27本章习题(第173－177页)(!!)4.1.1~4.1.4请独立完成该题4个问题(!!)4.2请独立完成该题(#)4.3课外思考该题(!)4.4.1~2,7能在书上程序的基础上编写程序实现(#)4.4.3~6,8~11有兴趣者课外思考28书面回答,请以纸面形式上交课代表,要求整洁清楚，时间期限:5月10日[格式提头:学号/序号/姓名/第四章]1、对于一个栈，如果输入项序列由A，B，C组成，给出全部可能和不可能的输出序列。2、设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a6,a7,a5,a8,a4,a2,a1，则栈S的容量至少应该是多少？（即至少应该容纳多少个元素？）3、设有算术表达式x+a*(y-b)-c/d，将其转换为后缀表达式。4、有字符串序列为3*-y-a/y↑2,试利用栈给出将次序改变为3y-*ay2↑/-的操作步骤。（用X代表扫描字符串函数中顺序取一字符进栈的操作，S代表从栈中取出一个字符加入到新字符串尾的出栈操作。）例如，ABC变为BCA，则操作步骤为XXSXSS。5、假设Q[0..10]是一个线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。（要求明确标出各元素在队列中的位置序号，头、尾指针）(a)d,e,b,g,h入队(b)d,e出队(c)i,j,k,l,m入队(d)b出队(e)n,o,p入队课后作业第四章29约定:进栈X,出栈S4个元素依次进栈,任何时候都可以出栈,请写出所有可能的出栈序列1.XXXXSSSS2.XXXSXSSS3.XXXSSXSS4.XXXSSSXS5.XXSXXSSS6.XXSXSXSS7.XXSXSSXS8.XXSSXSXS9.XXSSXXSS10.XSXSXSXS11.XSXXXSSS12.XSXXSXSS13.XSXXSSXS14.XSXSXXSS方法提示30第五章树5.1树的概念5.2二叉树5.3二叉树的遍历5.4二叉树的其他运算5.5树的存储结构和运算退出31校长一系二系三系六系教务处科研处总务处601602教务科603ABCD…………张三李四王五…例1…工厂32(根目录)\f