《数据结构线性表》PPT课件

第三章栈和队列,3.1栈,3.1.1栈的概念一、什么是栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（a1,a2,.,ai-1,ai,ai+1,an）,插入,删除,能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。,3.1栈,栈的特点后进先出,第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元素,3.1栈,二、栈的基本操作1）初始化操作InitStack(/栈空间基址ElemType*top;/栈顶指针intstacksize;/当前分配的栈空间大小SqStack;,3.1栈,3.1.2栈的顺序存储和实现,顺序栈的图示,S.stacksizeS.topS.base,100,约定栈顶指针指向栈顶元素的下一个位置,3.1栈,3.1.2栈的顺序存储和实现,top,base,空栈,BCDE进栈,EDC出栈,称为：栈满,空栈top=base栈满top-base=stacksize(无可分配空间),3.1栈,不可扩充栈的操作,栈空,栈顶指针top，指向实际栈顶后的空位置，初值为base,进栈,A,栈满,B,C,D,E,设数组大小为Mtop=M，栈满，此时入栈，则上溢(overflow),栈空,top=base，栈空，此时出栈，则下溢(underflow),出栈,3.1栈,可扩充栈的操作,栈顶指针top，指向实际栈顶后的下一个位置，初值为top=base,进栈,A,出栈,栈当前空间不足，需扩充,B,C,D,E,设栈的初始分配量为Stacksize=STACK_INIT_SIZE。若top=Stacksize，栈满，此时入栈，则需扩充栈空间，每次扩充STACK_INCREMENT；若无可利用的存储空间，则上溢(overflow)。,栈空,若top=base,栈空，此时出栈，则下溢(underflow),base,栈空,top,3.1栈,二、顺序栈基本操作的算法1）初始化操作InitStack(SqStackPush(OPTR,#);InitStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)/In(c,OP)判断c是否为运算符Push(OPND,c);c=getchar();/不是运算符则进栈else,3.2栈的应用举例,switch(Precede(GetTop(OPTR),c)/判定OPTR的栈顶运算符1与读入的运算符2间的优先关系case:/新输入的算符c优先级低，即栈顶算符优先权高/出栈并将运算结果入栈OPNDPop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);/进行二元运算abbreak;/switch/whilereturnGetTop(OPND);/EvaluateExpression,3.2栈的应用举例,递归是很有用的工具，在数学和程序设计等许多领域中都会用到。递归定义：简单说，一个用自己定义自己的概念，称为递归定义。任何一个递归程序都可以通过非递归程序实现。,3.3栈与递归,3.4.1队列的概念一、什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表。,（a1,a2,.,ai-1,ai,ai+1,an）,插入,删除,能进行插入的一端称为队尾，能进行删除的一端称为队头。称插入操作为入队，删除操作为出队。,3.4队列,a1a2a3an,队头,队尾,出队列,队列的示意图,队列的特点先进先出,第一个入队的元素在队头最后一个入队的元素在队尾第一个出队的元素为队头元素最后一个出队的元素为队尾元素,出队列,3.4队列,二、队列的基本操作1）初始化操作InitQueue(/初始化时分配存储空间的基址intfront;/队头指针，指向队头元素intrear;/队尾指针，指向队尾元素的下一个位置SqQueue;,队头,队尾指针是用整型实现的,3.4队列,(a)空队列,(b)J1,J2和J3相继入队列,(c)J1和J2相继出队,(d)J4,J5和J6相继入队之后,J3出队,Q.front,Q.rear均为整数用箭头指示只是为了直观,3.4队列,3.4队列,队列基本操作,队空,J1,J2,J3,J4,J5,J6入队,设两个指针：front,rear。rear指向队尾元素的下一个位置；front指向队头元素。初值front=rear=0,队空条件：front=rear入队列：Q.baserear+=e;出队列：e=Q.basefront+;,Q.base,3.4队列,存在问题设数组大小为M，则：当front=0，rear=M时，再入队发生溢出真溢出当front0，rear=M时，再入队发生溢出假溢出解决方案队首固定，每次出队后将剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让Q.baseM-1接在Q.base0之后，若rear+1=M，则令rear=0;,rear,J4,J5,J6入队,J4,J5,J6,front,3.4队列,实现：利用“模”运算入队：Q.baserear=e;rear=(rear+1)%M;出队：e=Q.basefront;front=(front+1)%M;队满、队空判定条件?,J7,J9,J8,队空：front=rear,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear队满：(rear+1)%M=front,队满：front=rear,3.4队列,队满：front=(rear+1)%M,少用一个元素空间：队空：front=rear队满：(rear+1)%M=front,队空：front=rear,J7,J8,1）初始化操作InitQueue_Sq(SqQueue/InitQueue_Sq,二、循环队列的基本操作算法,3.4队列,2）入队操作EnQueue_Sq(SqQueuestructQNode*next;QNode,*QueuePtr;,3.4队列,typedefstruct/链队列的表头结点的的类型定义QueuePtrfront;/队头指针，指向链表的头结点QueuePtrrear;/队尾指针，指向队尾结点LinkQueue;,front指向头结点，rear指向队尾,3.4队列,链式队列的基本操作,判断队空的条件：front=rear,三、队列的应用,1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；,3）离散事件的模拟模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程。,3.4队列,小结1、队列是限定仅能在表尾一端进行插入，表头一端进行删除的线性表；2、队列中的元素具有先进先出的特点；3、队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示；4、入队操作要修改队尾指针，出队操作要修改队头指针。,3.4队列,栈和队列练习,1、已知一堆栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列：A）1234B）4321C）2143D）4123答案：D2、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？A）1和5B）2和4C）4和2D）5和1答案：B,栈和队列,3、写出循环队列队空、队满的判断方法及条件（一种）。答案：方法：少用一个存储单元判满条件(Q.rear+1)%Q.queuesize=Q.front判空条件Q.rear=Q.front,栈和队列,4、若将一个双端队列顺序表示在一维数组Vm中，两个端点设为end1和end2，并组织成一个循环队列。试写出双端队列所用指针end1和end2的初始化条件及队空与队满条件。,答案：双端队列实际上就是一个双端的栈。假设：end1端顺时针进栈，end2端逆时针进栈初始化条件：end1=end2=0;队空条件：end1=end2;队满条件：(end1+1)%m=end2;,end1,end2,栈和队列,问题：编程判断一个字符序列是否是回文（回文是指一个字符序列以中间字符为基准两边字符完全相同）。算法设计程序从键盘接受一个字符序列存入字符串str中，字符串长度80，输入字符序列以回车符为结束标记，字符串str中不包括回车换行符。将字符串中字符逐个分别存入队列和栈，然后逐个出队和退栈，比较出队的元素和退栈的元素是否相等，若全部相等则该字符序列是回文，否则就不是回文。,栈和队列,#includestdio.h#defineMAX100#defineOK1#defineERROR0typedefintStatus;/*返回值状态*/typedefstructchar*base;char*top;intstacksize;SqStack;/*栈*/SqStacks;,栈和队列,StatusInitStack(SqStack*s)s-base=(char*)malloc(MAX*sizeof(char);s-top=s-base;s-stacksize=MAX;returnOK;StatusPush(SqStack*s,chare)*s-top+=e;StatusPop(SqStack*s,char*e)*e=*-s-top;StatusStackEmpty(SqStacks)return(s.top=s.base);,栈和队列,typedefstructchar*base;intfront,rear;SqQueue;/*队列*/SqQueueq;,栈和队列,StatusInitQueue(SqQueue*q)q-base=(char*)malloc(MAX*sizeof(char);q-front=q-rear=0;returnOK;StatusQueueEmpty(SqQueueq)returnq.front=q.rear;StatusEnQueue(SqQueue*q,chare)q-baseq-rear+=e;StatusDeQueue(SqQueue*q,char*e)*e=q-baseq-front+;,栈和队列,main()charc,e;InitStack(,队列应用,提出问题某运动会设立N个比赛项目，每个运动员可以参加13个项目。试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一单位时间进行，又可使总的竞赛日程最短。问题抽象若将此问题抽象成数学模型，则归属于“划分子集”问题。N个比赛项目构成一个大小为n的集合，有同一运动员参加的项目则抽象为“冲突”关系。,栈和队列,例如：某运动会设有9个项目：A=0，1，2，3，4，5，6，7，8，七名运动员报名参加的项目分别为：（1,4,8）、（1,7）、（8,3）、（1,0,5）、（3,4）、（5,6,2）、（6,4）它们之间的冲突关系为：R=(1,4),(4,8),(1,8),(1,7),(8,3),(1,0),(0,5),(1,5),(3,4),(5,6),(5,2),(6,2),(6,4)构造99的“冲突”矩阵,栈和队列,数据表示R=(1,4),(4,8),(1,8),(1,7),(8,3),(1,0),(0,5),(1,5),(3,4),(5,6),(5,2),(6,2),(6,4)对称冲突矩阵,栈和队列,问题分析“划分子集”问题即为：将集合A划分成k个互不相交的子集：A1，A2，Ak（kn），使同一子集中的元素均无冲突关系，并要求划分的子集数目尽可能地少。对前述例子而言，问题即为：同一子集中的项目为可以同时进行的项目，显然希望运动会的日程尽可能短。,栈和队列,算法设计可利用“过筛”的方法来解决划分子集问题。从第一个元素考虑起，凡不与第一个元素发生冲突的元素都可以和它分在同一子集中，然后再“过筛”出一批互不冲突的元素为第二个子集。依次类推，直至所有元素都进入某个子集为止。,栈和队列,010001000,010002100,010012101,020012101,71,栈和队列,为了减少重复察看R数组的时间，可另设