栈和队列市公开课一等奖省赛课获奖课件

第三章栈和队列3.1栈3.2栈应用3.3栈与递归实现3.4队列

栈和队列第1页3.1栈栈和队列是特殊线性表，其基本操作是线性表操作子集，是操作受限线性表。3.1.1抽象数据结构类型栈定义栈（stack）是限定在表尾进行插入或删除操作线性表。插入元素叫入栈，删除元素叫出栈。表尾称为栈顶（top），表头称为栈底（bottom）。不含元素空表称为空栈。例：栈S=(a1,a2,….,an)，a1为栈底元素，an为栈顶元素。栈操作是后进先出（LIFO）。栈和队列第2页栈和队列第3页栈抽象类型定义栈和队列第4页3.1.2栈表示和实现栈存放表示两种方法：

1、次序栈（栈次序存放结构）：利用一组地址连续存放单元依次存放自栈底到栈顶数据元素。

Top=0表示空栈。

在初始化空栈时不应该限定栈最大空间，应该先为栈分配一个基本容量，然后在应用过程中，当栈空间不够使用时再逐段扩大。

两个常量：

STACK_INIT_SIZE:存放空间初始分配量；

STACKINCREMENT:存放空间分配增量。栈和队列第5页次序栈定义：说明：1）stacksize指示栈当前可使用最大容量。2）栈初始化操作为：按设定初始分配量进行第一次存放分配，base是栈底指针，一直指向栈底位置，若base=NULL，表明栈结构不存在。3）Top为栈顶指针，初始值指向栈底，即top=base表明空栈；插入元素top+1，删除元素top-1，非空栈中栈顶指针一直在栈顶元素下一个位置。top-base=stacksize表明栈满栈和队列第6页栈和队列第7页栈和队列第8页栈和队列第9页栈和队列第10页栈和队列第11页2、栈链式表示栈操作是线性表操作特例，故链栈操作易于实现栈和队列第12页3.2栈应用举例3.2.1数制转换十进制数N和其它d进制数转换N=(Ndivd)×d+Nmodd(其中：div为整除运算，mod为求余运算）比如：（1348)10=(2504)8，其运算过程以下：N

Ndiv8

Nmod81348

168

4

168

21

0

21

2

5

2

0

2栈和队列第13页voidconversion(intNum){//对于输入任意一个非负十进制整数，打印输出与其等值八进制数ElemTypee;SqStackS;InitStack(S);//结构空栈while(Num){Push(S,Num%8);Num=Num/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}printf("\n");}//conversion栈和队列第14页3.2.2括号匹配检验假设表示式中允许包含两种括号：圆括号和方括号，其嵌套次序随意，即（［］（））或［（［］［］）］等为正确格式，［（］）或（［（））或(()])均为不正确格式。检验括号是否匹配方法可用"期待紧迫程度"这个概念来描述。比如考虑以下括号序列：[([][])]12345678

分析可能出现不匹配情况:到来右括弧非是所“期待”;到来是“不速之客”;直到结束，也没有到来所“期待”。

栈和队列第15页statusmatching(string&exp){//检验表示式中所含括弧是否正确嵌套，是，返回OK，不然返回ERROR

intstate=1; while(i<=length(exp)&&state){ swithofexp[i]{ case左括弧:{Push(S,exp[i]);i++;break;} case右括弧: {if(NOTStackEmpty(S)&&GetTop(S)=左括号) {Pop(S,e);i++;}else{state=0} break; } ……} } if(state&&StackEmpty(S))returnOK elsereturnERROR;}栈和队列第16页3.2.3行编辑程序一个简单行编辑程序功效是：接收用户从终端输入程序或数据，并存入用户数据区。每接收一个字符即存入用户数据区”不恰当。很好做法是，设置一个输入缓冲区，用以接收用户输入一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发觉有误时能够及时更正。whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效是以下两行：while(*s)putchar(*s++);栈和队列第17页voidLineEdit(){//利用字符栈S，从终端接收一行并传送至调用过程数据区。charch,*temp;SqStackS;InitStack(S);//结构空栈Sprintf("请输入一行(#:退格；@:清行):\n");ch=getchar();//从终端接收第一个字符while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,ch);break;//仅当栈非空时退栈case'@':ClearStack(S);break;//重置S为空栈default:Push(S,ch);break;//有效字符进栈,未考虑栈满情形}

栈和队列第18页ch=getchar();//从终端接收下一个字符} temp=S.base;while(temp!=S.top){printf("%c",*temp); ++temp;} //将从栈底到栈顶栈内字符传送至调用过程数据区；ClearStack(S);//重置S为空栈printf("\n");if(ch!=EOF){printf("请输入一行(#:退格；@:清行):\n");ch=getchar();}}DestroyStack(S);}栈和队列第19页3.2.5表示式求值限于二元运算符表示式定义:表示式::=(操作数)+(运算符)+(操作数)操作数::=简单变量|表示式简单变量::=标识符|无符号整数在计算机中，表示式能够有三种不一样标识方法设Exp=S1+OP+S2则称OP+S1+S2为表示式前缀表示法称S1+OP+S2为表示式中缀表示法称S1+S2+OP为表示式后缀表示法可见，它以运算符所在不一样位置命名。栈和队列第20页栈和队列第21页3.3栈与递归实现栈递归调用：直接调用自己或经过一系列调用语句间接调用自己函数叫递归函数。经过栈能够实现非递归。递归调用数学函数：阶乘函数1n=0Fact(n)=n.Fact(n-1)n>0Fibonacci数列0n=0Fib(n)=1n=1Fib(n-1)+Fib(n-2)其它情况栈和队列第22页例：(n阶Hanoi塔问题)要求：将X轴上n个圆盘移动到Z上。

遵照标准：

1)每次只能移动一个圆盘；

2)圆盘能够插在X、Y、Z中任一塔座上；

3)任何时刻都不能将一个较大圆盘压在较小圆盘之上。栈和队列第23页分析：n=1时，将编号为1圆盘从X直接移动到Z上即可；n>1时，需要利用塔座Y作辅助塔座，若能设法将压在编号为n圆盘之上n-1个圆盘从塔座X移至塔座Y上，则可先将编号为n圆盘从塔座X移至塔座Z上，然后再将塔座Y上n-1个圆盘移至塔座Z上。栈和队列第24页调用函数和被调用函数之间链接及信息交换需经过栈来进行。当一个函数运行期间调用另一个函数，在运行被调用函数之前，系统需要完成3件事：

1)将全部实在参数、返回地址等信息传递给被调用函数保留；

2)为被调用函数局部变量分配存放区；

3)将控制转移到被调函数入口。被调用函数返回调用函数之前，系统应完成3件事：

1)保留被调函数计算结果；

2)释放被调函数数据区；

3)依照被调函数保留返回地址将控制转移到调用函数。栈和队列第25页为了确保递归函数正确执行，系统需要设置一个递归工作栈作为整个递归函数运行期间使用数据存放区。每一层递归所需信息组成一个工作统计，其中包含全部是在参数、全部局部变量以及上一层返回地址。每进入一层递归，就产生一个新工作统计压入栈顶。栈和队列第26页栈和队列第27页3.4队列3.4.1抽象数据类型队列定义队列是一个先进先出（FIFO）线性表。只允许在表一端（队尾rear）进行插入，在表另一端（对头front）删除元素。

设队列q=（a1,a2,……,an）,a1是对头，an是队尾。栈和队列第28页抽象数据类型队列定义：栈和队列第29页栈和队列第30页双端队列双端队列是限定插入和删除操作在表两端进行线性表。还有输出受限双端队列和输入受限双端队列。假如限定双端队列从某个端点插入元素只能从该端点删除，则该双端队列就变成两个栈底相邻栈了。栈和队列第31页3.4.2链队列---队列链式表示和实现链队列：用链表示队列。一个链队列需要指向队头和队尾2个指针才能唯一确定。为了操作方便，也给链队列加一个头结点。空链队列判定条件是头指针和尾指针均指向头结点。即Q.rear=Q.front栈和队列第32页栈和队列第33页栈和队列第34页栈和队列第35页栈和队列第36页3.4.3循环队列---队列次序表示和实现在队列次序存放结构中，用一组地址连续存放单元依次存放从队列头道队列尾元素，附设两个指针front和rear分别指示队列头元素和队列尾元素位置。初始化建空队列时，令front=rear=0，每当插入新队列尾元素，尾指针增1，每当删除队列头元素，头指针增1。在非空队列中，头指针一直指向队列头元素，尾指针一直指向队列尾元素下一个位置。图d即使有空间，不过不能插入新元素。栈和队列第37页（1）采取平移元素方法，当发生假溢出时，就把整个队列元素平移到存放区首部，然后再插入新元素。这种方法需移动大量元素，因而效率是很低。（2）将次序队列存放区假想为一个环状空间。当发生假溢出时，将新元素插入到第一个位置上，这么做，即使物理上队尾在队首之前，但逻辑上队首依然在前。入列和出列仍按“先进先出”标准进行，这就是循环队列。很显然，方法二中不需要移动元素，操作效率高，空间利用率也很高。处理方法：栈和队列第38页循环队列不能用队头指针和队尾指针相等来判断队列是否满。C语言不能用动态分配一维数组来实现循环队列，必须设定一个最大队列；若无法预计最大长度，宜用链队列。栈和队列第39页判断堆是空还是满有两种方法：1）另设一个标志位以区分对垒是空还是满；2）少用一个元素，约定以队列头指针在队列尾指针下一位置上作为队列呈满状态标志。队空条件：Q.rear=Q.front队满条件：(Q.rear+1)%MAXSIZE=Q.front栈和队列第40页栈和队列第41页栈和队列第42页作业：1、假设表示式中允许包含3种括号：圆括号、方括号和大括号。设计一个算法采取次序栈判断表示式中括号是否正确配对。81Intmatch(charexp[],intn){charst[Maxsize];inttop=-1;inti=0,tag=1;while(i<n&&ta