《《数据结构线性表》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构线性表》PPT课件.ppt（70页珍藏版）》请在三一办公上搜索。
1、第三章 栈和队列,3.1 栈,3.1.1 栈的概念一、什么是栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（a1,a2,.,ai-1,ai,ai+1,an）,插入,删除,能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。,3.1 栈,栈的特点后进先出,第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素最后一个出栈的元素为栈底元素,3.1 栈,二、栈的基本操作1）初始化操作 InitStack(&S)功能：构造一个空栈S。2）销毁栈操作 DestroyStack(&S)功能：销毁一个已存在的栈。3）置空栈操
2、作 ClearStack(&S)功能：将栈S置为空栈。4）取栈顶元素操作 GetTop(S,&e)功能：取栈顶元素，并用e 返回。,3.1 栈,二、栈的基本操作5）进栈操作 Push(&S,e)功能：元素e进栈。6）退栈操作 Pop(&S,&e)功能：栈顶元素退栈，并用e返回。7）判空操作 StackEmpty(S)功能：若栈S为空，则返回True，否则，栈不空返回False。,3.1 栈,3.1.2 栈的顺序存储和实现,一、栈的顺序存储结构,#define STACK_INIT_SIZE 100/栈存储空间的初始分配量#define STACKINCREMENT 10/空间的分配增量type
3、def struct ElemType*base;/栈空间基址 ElemType*top;/栈顶指针 int stacksize;/当前分配的栈空间大小SqStack;,3.1 栈,3.1.2 栈的顺序存储和实现,顺序栈的图示,S.stacksizeS.topS.base,100,约定栈顶指针指向栈顶元素的下一个位置,3.1 栈,3.1.2 栈的顺序存储和实现,top,base,空栈,B C D E进栈,E D C出栈,称为：栈满,空栈 top=base 栈满 top-base=stacksize(无可分配空间),3.1 栈,不可扩充栈的操作,栈空,栈顶指针top，指向实际栈顶后的空位置，初值
4、为 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
5、,栈空，此时出栈，则下溢(underflow),base,栈空,top,3.1 栈,二、顺序栈基本操作的算法1）初始化操作 InitStack(SqStack&S)参数：S是存放栈的结构变量功能：建一个空栈S,100,3.1 栈,初始化操作算法Status InitStack(SqStack/InitStack,2）销毁栈操作 DestroyStack(SqStack&S)功能：销毁一个已存在的栈,100,3.1 栈,Status DetroyStack(SqStack/DetroyStack,销毁操作算法,3.1 栈,3）置空栈操作ClearStack(SqStack&S)功能：将栈S置为空
6、栈,3.1 栈,Status ClearStack(SqStack/ClearStack,置空操作算法,3.1 栈,an,4）取栈顶元素操作GetTop(SqStack S,ElemType&e)功能：取栈顶元素，并用e返回,3.1 栈,Status GetTop(SqStack S,ElemType/GetTop,取栈顶元素操作算法,3.1 栈,5）进栈操作 Push(SqStack&S,ElemType e)功能：元素 e 进栈。,3.1 栈,进栈操作算法Status Push(SqStack/Push,3.1 栈,6）出栈操作 Pop(SqStack&S,ElemType&e)功能：栈顶
7、元素退栈，并用 e 返回。,3.1 栈,Status Pop(SqStack/Pop,出栈操作算法,3.1 栈,栈的链式存储结构，也称链栈。,栈顶,栈底,在前面学习了线性链表的插入、删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法。,3.1.3 栈的链式存储和实现,3.1 栈,小 结1、栈是限定仅能在表尾一端进行插入、删除操作的线性表2、栈的元素具有后进先出的特点3、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改栈顶指针,3.1 栈,1）问题的提出从键盘一次性输入一串算术表达式，给出计算结果。,栈的应用举例表达式求值,3.2 栈的应用举例,2）表达式的构成 操作数
8、+运算符+界符,1,2,3,4,常数,+、-、*、/,()、#,3.2 栈的应用举例,3）表达式的求值：例：5+6(1+2)-4 按照四则运算法则，上述表达式的计算过程为：5+6(1+2)-4=5+63-4=5+18-4=23-4=19,4）算符优先关系表 表达式中任何相邻运算符 1、2 的优先关系有：1 2：1的优先级 高于 2,注：1、2是相邻算符，1在左，2在右,3.2 栈的应用举例,5）算符优先算法,从左向右扫描表达式：遇操作数保存；遇运算符号j与前面的刚扫描过的运算符i比较：若ij 则说明i是已扫描的运算符中优先级最高者，可进行运算 若i=j 则说明括号内的式子已计算完，需要消去括号
9、,5+4(1+2)-6,后面也许有优先级更高的算符,+,+,(,后保存的算符优先级高,用两个栈分别保存扫描过程中遇到的操作数和运算符,3.2 栈的应用举例,在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符；一个是OPND栈，用以保存操作数或运算结果。算法的基本思想是：1、首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素。2、依次读入表达式中每个字符，若是操作数，则进OPND栈；若是运算符，则与OPTR栈的栈顶运算符比较优先级后作相应操作。直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。,3.2 栈的应用举例,表达式求值示意：5+6(1
10、+2)-4,#,5,+,6,(,1,+,2,3,18,23,-,4,19,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18=23,23-4=19,3.2 栈的应用举例,算法描述operandType EvaluateExpression()/算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符、界限符集合。InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)/In(c
11、,OP)判断c是否为运算符 Push(OPND,c);c=getchar();/不是运算符则进栈 else,3.2 栈的应用举例,switch(Precede(GetTop(OPTR),c)/判定OPTR的栈顶运算符1与读入的运算符2间的优先关系 case:/新输入的算符c优先级低，即栈顶算符优先权高/出栈并将运算结果入栈OPND Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);/进行二元运算a b break;/switch/while return GetTop(OPND);/EvaluateExpr
12、ession,3.2 栈的应用举例,递归是很有用的工具，在数学和程序设计等许多领域中都会用到。递归定义：简单说，一个用自己定义自己的概念，称为递归定义。任何一个递归程序都可以通过非递归程序实现。,3.3 栈与递归,3.4.1 队列的概念一、什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表。,（a1,a2,.,ai-1,ai,ai+1,an）,插入,删除,能进行插入的一端称为队尾，能进行删除的一端称为队头。称插入操作为入队，删除操作为出队。,3.4 队列,a1 a2 a3 an,队头,队尾,出队列,队列的示意图,队列的特点先进先出,第一个入队的元素在队头最后一个入队的元素在队尾第一
13、个出队的元素为队头元素最后一个出队的元素为队尾元素,出队列,3.4 队列,二、队列的基本操作1）初始化操作 InitQueue(&Q)功能：构造一个空队列Q。2）销毁操作 DestroyQueue(&Q)功能：销毁已存在队列Q。3）置空操作 ClearQueue(&Q)功能：将队列Q置为空队列。4）出队操作 DeQueue(&Q,&e)功能：删除Q的队头元素。5）取队头元素操作 GetHead(Q,&e)功能：取队头元素，并用e返回。,3.4 队列,二、队列的基本操作6）入队操作 EnQueue(&Q,e)功能：将元素e插入Q的队尾。7）判空操作 QueueEmpty(Q)功能：若队列Q为空，
14、则返回True，否则返回False。,3.4 队列,3.4.2 循环队列队列的顺序存储和实现一、队列的顺序存贮结构,#define MAXSIZE 100/最大队列长度typedef struct ElemType*base;/初始化时分配存储空间的基址 int front;/队头指针，指向队头元素 int rear;/队尾指针，指向队尾元素的下一个位置SqQueue;,队头,队尾指针是用整型实现的,3.4 队列,(a)空队列,(b)J1,J2和J3相继入队列,(c)J1和J2相继出队,(d)J4,J5和J6相继入队之后,J3出队,Q.front,Q.rear均为整数用箭头指示只是为了直观,3
15、.4 队列,3.4 队列,队列基本操作,队空,J1,J2,J3,J4,J5,J6入队,设两个指针：front,rear。rear指向队尾元素的下一个位置；front指向队头元素。初值 front=rear=0,队空条件：front=rear 入队列：Q.base rear+=e;出队列：e=Q.base front+;,Q.base,3.4 队列,存在问题设数组大小为M，则：当front=0，rear=M 时，再入队发生溢出真溢出当front0，rear=M 时，再入队发生溢出假溢出解决方案队首固定，每次出队后将剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让 Q.baseM-1
16、 接在 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,少用一个元素空间
17、：队空：front=rear 队满：(rear+1)%M=front,队空：front=rear,J7,J8,1）初始化操作 InitQueue_Sq(SqQueue/InitQueue_Sq,二、循环队列的基本操作算法,3.4 队列,2）入队操作 EnQueue_Sq(SqQueue&Q,ElemType e)功能：将元素 e 插入队尾,元素e入队前,元素e入队后,3.4 队列,入队操作算法：Status EnQueue_Sq(SqQueue/EnQueue_Sq,3.4 队列,3)出队操作 DeQueue_Sq(SqQueue&Q,QElemType&e)功能：删除队头元素，用e返回其值,
18、出队操作前,出队操作后,3.4 队列,出队操作算法：Status DeQueue_Sq(SqQueue/EnQueue_Sq,3.4 队列,3.4.3 链队列队列的链式存储结构和实现一、链队列,3.4 队列,二、链队列的类型定义,typedef struct QNode/链队列结点的类型定义 ElemType data;struct QNode*next;QNode,*QueuePtr;,3.4 队列,typedef struct/链队列的表头结点的的类型定义 QueuePtr front;/队头指针，指向链表的头结点 QueuePtr rear;/队尾指针，指向队尾结点LinkQueue;,
19、front指向头结点，rear指向队尾,3.4 队列,链式队列的基本操作,判断队空的条件：front=rear,三、队列的应用,1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；,3）离散事件的模拟模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程。,3.4 队列,小 结1、队列是限定仅能在表尾一端进行插入，表头一端进行删除的线性表；2、队列中的元素具有先进先出的特点；3、队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示；4、入队操作要修改队尾指针，出队操作要修改队头指针。,3.4 队列,栈和队列练习,1、已知一堆栈的进栈序列为：1234
20、，则下列哪个序列为不可能的出栈序列：A）1234 B）4321 C）2143 D）4123答案：D2、若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear和 front 的值分别为多少？A）1和5 B）2和4 C）4和2 D）5和1答案：B,栈和队列,3、写出循环队列队空、队满的判断方法及条件（一种）。答案：方法：少用一个存储单元判满条件(Q.rear+1)%Q.queuesize=Q.front判空条件 Q.rear=Q.front,栈和队列,4、若将一个双端队列顺序表示在一维数组 Vm 中，两
21、个端点设为 end1 和 end2，并组织成一个循环队列。试写出双端队列所用指针 end1 和 end2 的初始化条件及队空与队满条件。,答案：双端队列实际上就是一个双端的栈。假设：end1端顺时针进栈，end2端逆时针进栈初始化条件：end1=end2=0;队空条件：end1=end2;队满条件：(end1+1)%m=end2;,end1,end2,栈和队列,问题：编程判断一个字符序列是否是回文（回文是指一个字符序列以中间字符为基准两边字符完全相同）。算法设计 程序从键盘接受一个字符序列存入字符串str中，字符串长度80，输入字符序列以回车符为结束标记，字符串str中不包括回车换行符。将字符
22、串中字符逐个分别存入队列和栈，然后逐个出队和退栈，比较出队的元素和退栈的元素是否相等，若全部相等则该字符序列是回文，否则就不是回文。,栈和队列,#include stdio.h#define MAX 100#define OK 1#define ERROR 0typedef int Status;/*返回值状态*/typedef struct char*base;char*top;int stacksize;SqStack;/*栈*/SqStack s;,栈和队列,Status InitStack(SqStack*s)s-base=(char*)malloc(MAX*sizeof(char);
23、s-top=s-base;s-stacksize=MAX;return OK;Status Push(SqStack*s,char e)*s-top+=e;Status Pop(SqStack*s,char*e)*e=*-s-top;Status StackEmpty(SqStack s)return(s.top=s.base);,栈和队列,typedef struct char*base;int front,rear;SqQueue;/*队列*/SqQueue q;,栈和队列,Status InitQueue(SqQueue*q)q-base=(char*)malloc(MAX*sizeof
24、(char);q-front=q-rear=0;return OK;Status QueueEmpty(SqQueue q)return q.front=q.rear;Status EnQueue(SqQueue*q,char e)q-baseq-rear+=e;Status DeQueue(SqQueue*q,char*e)*e=q-baseq-front+;,栈和队列,main()char c,e;InitStack(,队列应用,提出问题 某运动会设立 N 个比赛项目，每个运动员可以参加13个项目。试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一单位时间进行，又可使总的竞赛日程
25、最短。问题抽象 若将此问题抽象成数学模型，则归属于“划分子集”问题。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,
26、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），使同一子集中的元素均无冲突关系，并要求划分的子集数目尽可能地少。对前述例子而言，问题即为：同一子集中的项目为可以同时进行的项目，显然希望运动会的日程尽可能短。,栈和队列,算法设计 可利用“过筛”的方法来解决划分子集问题。从第一个元素考虑起，凡不与第一个元素发生冲突的元素都可以和它分在同一子集中，然后再“过筛”出一批互不冲突的元素
27、为第二个子集。依次类推，直至所有元素都进入某个子集为止。,栈和队列,0 1 0 0 0 1 0 0 0,0 1 0 0 0 2 1 0 0,0 1 0 0 1 2 1 0 1,0 2 0 0 1 2 1 0 1,71,栈和队列,为了减少重复察看 R 数组的时间，可另设一个数组clashn，记录和当前已入组元素发生冲突的元素的信息。每次新开辟一组时，令 clash 数组各分量的值均为“0”，当序号为“i”的元素入组时，将和该元素发生冲突的信息记入clash 数组。,栈和队列,pre(前一个出队列的元素序号)=n;组号=0;全体元素入队列;while(队列不空)队头元素 i 出队列;if(i pre)/开辟新的组 组号+;clash 数组初始化;if(i 能入组)i 入组，记下序号为 i 的元素所属组号;修改 clash 数组;else i 重新入队列;pre=i;,结果：(0,2,3,7)，(1,6)，(4,5)，(8),
