第三章 栈和队列(精品).ppt

第三章第三章第三章第三章栈和队列栈和队列栈和队列栈和队列两种特殊的线性表两种特殊的线性表两种特殊的线性表两种特殊的线性表1/26/20231栈和队列栈和队列3.1 栈栈3.2 栈的应用举例栈的应用举例3.3 栈与递归栈与递归3.4 队列队列1/26/202323.1 栈栈 栈栈是仅限定在表的一端操作是仅限定在表的一端操作的线性表。它的插入和删除都只的线性表。它的插入和删除都只能在表的一端进行。能在表的一端进行。定义定义1/26/20233 ADT Stack 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 约定an 端为栈顶，a1 端为栈底。基本操作：基本操作：ADT Stack3.1.1 栈的类型定义栈的类型定义1/26/20234InitStack(&S)/构造一个空栈构造一个空栈 S基本操作：基本操作：DestroyStack(&S)/销毁栈销毁栈 S GetTop(S,&e)/弹出弹出 S 栈顶元素。栈顶元素。Push(&S,e)/向栈内推入元素向栈内推入元素 e1/26/20235栈的表示和实现栈的表示和实现 顺序存储顺序存储 链表存储链表存储栈的存储方式栈的存储方式栈的性质栈的性质后进先出后进先出1/26/20236栈的顺序存储栈的顺序存储typedef struct char ST101 int top;stack;stack S;d4c3b2a1栈顶栈顶Top栈底栈底s stop1/26/20237栈的顺序存储栈的顺序存储#define Maxsize 100+1typedef struct elemtype STMaxsize int top;stack;stack S;d4c3b2a1栈顶栈顶top栈底栈底tops s1/26/20238栈的顺序存储栈的顺序存储1.栈空的条件：栈空的条件：S.top=04321栈顶栈顶Top1/26/202392.2.栈的压入操作栈的压入操作Push(&S,e)/栈栈 S 已存在，压入元素已存在，压入元素 e if(s.top=Maxsize-1)printf(栈满溢出栈满溢出);else S.top+;S.STtop=e;return OK;4321Top1/26/2023102.2.栈的压入操作栈的压入操作Push(&S,e)/栈栈 S 已存在，压入元素已存在，压入元素 e if(s.top=Maxsize-1)printf(栈满溢出栈满溢出);else S.top+;S.STs.top=e;return OK;4321Top23235050Top1/26/2023113.3.栈的弹出操作栈的弹出操作pop(&S,e)/栈栈 S 已存在，压入元素已存在，压入元素 e if(s.top=0)printf(栈栈空下溢空下溢);else e=S.STs.top;S.top-;return OK;432123235050TopTopTop1/26/202312例题例题一个栈的入栈序列是一个栈的入栈序列是12345，则栈的不可能，则栈的不可能的出栈序列是什么？的出栈序列是什么？判断一个顺序栈判断一个顺序栈st(最多元素为最多元素为maxsize)为为栈空栈空he栈满的条件分别是栈满的条件分别是 和和 A)st-top!=0 B)st-top=0 C)st-top!=maxsize-1 D)st-top=maxsize-1 B BD D1/26/202313栈的链式存储栈的链式存储head2118307542561.进栈进栈2.出栈出栈3.读栈顶元素读栈顶元素1/26/2023143.2 栈的应用举例栈的应用举例ClearStack(S)重置重置S为空栈为空栈empty(s)判断栈空判断栈空push(s，ch)将一个元素将一个元素e推入栈推入栈spop(s)将栈顶元素弹出，且返回其元素将栈顶元素弹出，且返回其元素gettop(s,e)取栈顶元素取栈顶元素1/26/202315 例例1 1 行编辑程序问题行编辑程序问题 假设假设“#”为退格符，表示前一个字为退格符，表示前一个字 符无效；符无效；“”为退行符，表示当前行无效；为退行符，表示当前行无效；设立一个设立一个栈栈（输入缓冲区），用以接（输入缓冲区），用以接受用户输入的一行字符，然后逐行存受用户输入的一行字符，然后逐行存入用户数据区。入用户数据区。1/26/202316假设从终端接受了这样两行字符：假设从终端接受了这样两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);则实际有效的是下列两行：while(*s)putchar(*s+);1/26/202317假设从终端接受了这样两行字符：假设从终端接受了这样两行字符：whli#ilr#eilhw当当#:Pop(S,e)/弹出当当:ClearStack(S)/清栈否则否则 入栈入栈1/26/202318假设从终端接受了这样两行字符：假设从终端接受了这样两行字符：whli#ilr#eilhw当当#:Pop(S,e)/弹出当当:ClearStack(S)/清栈否则否则 入栈入栈1/26/202319假设从终端接受了这样两行字符：假设从终端接受了这样两行字符：whli#ilr#eilhw当当#:Pop(S,e)/弹出当当:ClearStack(S)/清栈否则否则 入栈入栈1/26/202320 while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,e);break;case:ClearStack(S);break;/重置S为空栈 default:Push(S,ch);break;ch=getchar();/从终端接收下一个字符 ClearStack(S);/重置S为空栈if(ch!=EOF)ch=getchar();while(ch!=EOF)/EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；ilhw1/26/202321表达式表达式:=(操作数操作数 1)+(运算符运算符op)+(操作数操作数 2)操作数操作数:=简单变量简单变量|表达式表达式 简单变量简单变量:=标识符标识符|无符号整数无符号整数例例2 2 表达式求值表达式求值-利用算符优先级法则利用算符优先级法则1/26/202322算符间的优先级关系算符间的优先级关系 1 2+*/（）#+*/（=）#=1/26/202323例如例如:Exp=a b+(c d/e)f中缀式:#a b+c d/e f#使用两个栈：使用两个栈：栈栈OPTR寄存运算符寄存运算符OP （包括（）和#）栈栈OPND寄存操作数寄存操作数 1/26/202324例如例如:#4+2 3 10/5#OPTROPND#4+1/26/202325算符间的优先级关系算符间的优先级关系 1 2+*/（）#+*/（=）#=1/26/202326例如例如:#4+2 3 10/5#OPTROPND#4+2+1/26/202327算符间的优先级关系算符间的优先级关系 1 2+*/（）#+*/（=）#=1/26/202328例如例如:#4+2 3 10/5#OPTROPND#4+2 31/26/202329算符间的优先级关系算符间的优先级关系 1 2+*/（）#+*/（=）#=1/26/202330例如例如:#4+2 3 10/5#OPTROPND#4+2 3退栈退栈 322 2 3=63=66进栈进栈10/1/26/2023313.3 栈与递归的实现栈与递归的实现1.求求n!2.Hanoi塔问题塔问题1/26/202332 例例1 求求n!(用递归调用用递归调用)1 n=0fac=n(n-1)!n0int fac(int n)int f;if(n=0)fac=1;else f=fac(n-1)*n;return(f);main()int n=3;p=fac(n);printf(%d,p);1/26/202333 求求n!(用递归调用用递归调用)1 n=0fac=n(n-1)!n0int fac(int n)int f;if(n=0)fac=1;else f=fac(n-1)*n;return(f);main()int n=3;p=fac(n);printf(%d,p);将所有的将所有的实参实参、返回地址返回地址等信息传递给等信息传递给被调用函数被调用函数保存保存；为被调用函数的局部变量为被调用函数的局部变量分配存储区分配存储区；将将控制转移控制转移到被调用函数的入口。到被调用函数的入口。1/26/202334 求求n!(用递归调用用递归调用)1 n=0,1fac=n(n-1)!n0int fac(int n)int f;if(n=0)fac=1;else f=fac(n-1)*n;return(f);main()int n=3;p=fac(n);printf(%d,p);保存保存被调函数的被调函数的计算结果计算结果；释放释放被调函数的被调函数的数据区数据区；依照被调函数保存的返回地址将依照被调函数保存的返回地址将控制转移控制转移到调用函数。到调用函数。1/26/202335递归的要点：递归的要点：1.由由系统提供一个信息栈，保留函数调用时系统提供一个信息栈，保留函数调用时的相关信息（调用时的信息、返回地址、的相关信息（调用时的信息、返回地址、局部变量）；局部变量）；2.每执行递归调用语句时，将有关信息送入每执行递归调用语句时，将有关信息送入栈，转入函数入口；栈，转入函数入口；3.每当执行到返回语句时，保存每当执行到返回语句时，保存计算结果计算结果，释放被调函数的数据区，弹出释放被调函数的数据区，弹出返回地址返回地址返返回。回。1/26/202336多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回！例如：void main()void a()void b()a();b();/main /a /bMain的数据区函数a的数据区函数b的数据区 1/26/202337n=3;p=fac(n);printf(p);main()f=fac(n-1)*3;return(f);fac(3)f=fac(n-1)*2;return(f);fac(2)f=fac(n-1)*1;return(f);fac(1)f=1;return(f);fac(0)1/26/202338n=3;p=fac(n);main()f=fac(n-1)*3;fac(3)f=fac(n-1)*2;fac(2)f=fac(n-1)*1;fac(1)f=1;return(f);fac(0)fac(3)fac(2)fac(1)fac(0)RETRETRETRETn 地址地址3 L3 L3 L3 L3 L3 L3 Ln 地址地址3 L13 L13 L13 L13 L1n 地址地址2 L22 L22 L2n 地址地址1 L31/26/202339例例2 Hanoi 塔问题塔问题abc1/26/202340例例2 Hanoi 塔问题塔问题abc1/26/202341例例2 Hanoi 塔问题塔问题abc1/26/202342例例2 Hanoi 塔问题塔问题abc1/26/202343void hanoi(int n,char x,char y,char z)/将塔座x上按直径由小到大且至上而下编号为1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if(n=1)2 move(x,1,z);/将编号为的圆盘从x移到z3 else 4 hanoi(n-1,x,z,y);/将x上编号为至n-1的 /圆盘移到y,z作辅助塔5 move(x,n,z);/将编号为n的圆盘从x移到z6 hanoi(n-1,y,x,z);/将y上编号为至n-1的 /圆盘移到z,x作辅助塔7 8 1/26/202344void hanoi(int n,char x,char y,char z)12 if(n=1)3 move(x,1,z);4 else 5 hanoi(n-1,x,z,y);6 move(x,n,z);7 hanoi(n-1,y,x,z);8 9 0 3 a b c返址 n x y z6 2 a c b6 1 a b c8 1 c a b 1/26/2023453.4 队列队列1/26/2023463.4.1 抽象数据类型队列的定义抽象数据类型队列的定义队列：是一种队列：是一种先进先出先进先出的线性表，它的操的线性表，它的操作只能在表的两端进行。作只能在表的两端进行。队尾队尾队尾队尾队首队首队首队首a1 a2 a3 an-1 an1/26/202347 ADT Queue 数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,ai D,i=2,.,n 约定其中a1 端为队列头队列头，an 端为队列尾队列尾基本操作：基本操作：ADT Queue 队列的抽象数据类型队列的抽象数据类型1/26/202348队列的基本操作：队列的基本操作：1、InitQueue(&Q)/创建空队列创建空队列Q2、DestroyQueue(&Q)/销毁队列销毁队列Q7、QueueLength(Q)/求队列长度求队列长度5、GetHead(Q,&e)/取队首元素取队首元素6、ClearQueue(&Q)/队列置空队列置空3、DelQueue(&Q,&e)/出队出队4、EnQueue(&Q,e)/入队入队1/26/202349QueueEmpty(Q)初始条件：队列队列Q已存在。已存在。操作结果：若若Q为空队列，则返回为空队列，则返回TRUE，否则返回否则返回FALSE。1/26/202350QueueLength(Q)初始条件：队列队列Q已存在。已存在。操作结果：返回返回Q的元素个数，即队的元素个数，即队列的长度。列的长度。1/26/202351 GetHead(Q,&e)初始条件：Q为非空队列。为非空队列。操作结果：用用e返回返回Q的队头元素。的队头元素。a1a2an 1/26/202352 ClearQueue(&Q)初始条件：队列队列Q已存在。已存在。操作结果：将将Q清为空队列。清为空队列。1/26/202353 EnQueue(&Q,e)初始条件：队列队列Q已存在。已存在。操作结果：插入元素插入元素e为为Q的新的的新的队尾元素。队尾元素。a1a2ane 1/26/202354 DeQueue(&Q,&e)初始条件：Q为非空队列。为非空队列。操作结果：删除删除Q的队头元素，并的队头元素，并用用e返回其值。返回其值。a1a2an 1/26/202355队列的表示队列的表示 链式表示链式表示链队列链队列 顺序表示顺序表示循环队列循环队列1/26/2023563.4.2 链队的表示和实现链队的表示和实现链队链队用链表表示的存储结构的队列用链表表示的存储结构的队列rearfrontfrontrear链队列1/26/202357 typedef struct QNode/结点类型结点类型 QElemType data;struct QNode *next;QNode,*QPtr;链队链队de结点结构结点结构1/26/202358 QPtr front;/队头指针队头指针 QPtr rear;/队尾指针队尾指针a1anfrontfront空队列空队列rearrearrearfront=rear表示表示表示表示1 11/26/202359typedef struct /链队列类型链队列类型 QPtr front;/队头指针队头指针 QPtr rear;/队尾指针队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列表示表示表示表示2 21/26/202360 Status InitQueue(LinkQueue&Q)/构造一个空队列Q Q.front=Q.rear=(QPtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存储分配失败 Q.front-next=NULL;return OK;1/26/202361 Status EnQueue(LinkQueue&Q,QElemType e)/插入元素e为Q的新的队尾元素 p=(QPtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败 p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;1/26/202362 Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除Q的队头元素，/用 e 返回其值，并返回OK；否则返回ERROR 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;1/26/202363rearfrontfrontrear链队列1/26/2023643.4.3 队列的顺序存储结构队列的顺序存储结构1.顺序队列顺序队列数组表示数组表示 队列的顺序存储结构称为顺序队列。队列的顺序存储结构称为顺序队列。5432J31J20J1rearfront队首队首队尾队尾1/26/2023651.顺序队列顺序队列数组表示数组表示初始化建空队列时令初始化建空队列时令543210rearfrontfront=rear=01/26/2023661.顺序队列顺序队列数组表示数组表示入队时入队时:加入结点加入结点;rear+1;543210rearfrontJ1rearrear1/26/202367rear1.顺序队列顺序队列数组表示数组表示入队：入队：加加入结点入结点;头指针头指针rear+1;543210rearfrontJ1rearJ2rearrearJ31/26/2023681.顺序队列顺序队列数组表示数组表示出队出队：删除结点删除结点;队头指针队头指针front+1;543210frontJ1J2rearJ3J1frontfront在非空队列中，在非空队列中，头指针头指针front总是总是指向队头元素，指向队头元素，而尾指针而尾指针rear总是总是指向队尾元素的指向队尾元素的下一个位置下一个位置1/26/202369（1）入队操作入队操作 enqueue(Q,x)if(rear+1=MAX-1)printf(队满溢出队满溢出)else Qrear=x;rear+;return OK;2顺序队列的基本运算顺序队列的基本运算543J42J31J20J1rearfront1/26/202370（2）出队操作出队操作 Dequeue(Q,e)if(front=rear)return ERROR/队队空空 else e=Qfront;front+;return OK;543J42J31J20rearfront1/26/20237154J53J4210rearfront3.循环队列循环队列if(rear+1=MAX-1)队满溢出队满溢出 在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，此时若有元素入列，就会发生“溢出”。在图中，虽然队尾指针已经指向最后一个位置，但事实上队列中还有空位置。也就是说，队列的存储空间并没有满，但队列却发生了溢出，我们称这种现象为假溢出。1/26/202372解决的方法解决的方法:将队列看成是循环表将队列看成是循环表：MAXNUM-101rearfront循环队列示意54J53J4210frontrear1/26/202373但但当队满时当队满时rear=front：5J64J53J42J31J20J1frontrear1/26/202374但但当队满时当队满时rear=front当队空时当队空时rear=front：543210frontrear无法判断！无法判断！无法判断！无法判断！1/26/202375解决的方法解决的方法:少用一的单元少用一的单元：5 4J53J42J31J20J1frontrear队满条件队满条件(rear+1)mod max=front1/26/202376解决的方法解决的方法:少用一的单元少用一的单元：5 43210frontrear队满条件队满条件(rear+1)mod max=front队空条件队空条件 front=rear1/26/202377入队入队Enqueue(Q,x)if(front=(rear+1)%max)exit(over)else Qrear=x;rear=(rear+1)%max;return OK 1/26/202378出队出队Delqueue(Q,e)if(front=rear)exit(over)else e=Qfront;front=(front+1)%max;return OK 1/26/202379#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base;/动态分配存储空间 int front;/头指针，若队列不空，/指向队列头元素 int rear;/尾指针，若队列不空，指向 /队列尾元素 的下一个位置 SqQueue;循环队列结构循环队列结构21/26/202380 Status InitQueue(SqQueue&Q)/构造一个空队列Q Q.base=(ElemType*)malloc (MAXQSIZE*sizeof(ElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败 Q.front=Q.rear=0;return OK;1/26/202381Status EnQueue(SqQueue&Q,ElemType e)/插入元素e为Q的新的队尾元素 if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/队列满 Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;1/26/202382 Status DeQueue(SqQueue&Q,ElemType&e)/若队列不空，则删除Q的队头元素，/用e返回其值，并返回OK;否则返回ERROR if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;1/26/2023831/26/202384 1.掌掌握握栈栈和和队队列列类类型型的的特特点点，并并能能在在相相应应的应用问题中正确选用它们。的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法，特别应熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3.熟练掌握循环队列和链队列的基本操作实熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。现算法，特别注意队满和队空的描述方法。4.理解递归算法执行过程中栈的状态变化过理解递归算法执行过程中栈的状态变化过程。程。本章学习要点本章学习要点1/26/202385