数据结构-基于C++语言（微课版） 课件 第3章和第4章 队列

线性结构—栈学习内容：栈的存储实现及运算实现（顺序、链式）栈的定义与运算栈的应用举例—进制转换、迷宫问题、括弧匹配、表达式求值等应用栈的定义本节内容：线性结构—栈自古华山一条道假设道路一次只能允许一个人通过1）上山：游客只能顺着石路一个接着一个上山，先登山的游客先到达目的地。满足“先进先出”的原则----队列2）下山：如果在登山的过程中，由于某种原因，需要折返沿原路下山，依照后上山的游客先下山，先上山的游客后下山的原则返回。满足“后进先出”的原则----栈数据结构课程内容可表示为：（a1,a2,……,an）线性结构的定义：

栈和队列是两种应用非常广泛的数据结构，它们都来自线性表数据结构，都是“操作受限”的线性表。线性结构—栈

一叠盘子，一串糖葫芦、待处理的一批作业等，处理的次序与其叠放的次序正好相反。日常模型：线性结构—栈机器模型：

括号匹配问题是编译程序时经常遇到的问题，用以检测语法是否有错，即检查各种括号是否匹配。编号0123456789括号{{{}[]}()}栈的定义

定义：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO(LastInFirstOut)或先进后出FILO(FirstInLastOut)线性表。栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。

用栈顶指针(top)来指示栈顶元素。栈底(Bottom)：是固定端，不允许插入和删除，又称为表头。空栈：当表中没有元素时称为空栈。topBottom表头表尾栈的定义例：一个存储整型元素的栈，依次压栈：{1,2,3｝在压栈的过程中，栈顶的位置一直在“向上”移动，而栈底是固定不变的。栈的定义在弹栈的过程中，栈顶位置一直在“向下”移动，而栈底一直保持不变。栈的定义例：栈中的元素弹出栈中的元素弹出栈的定义本节内容：线性结构—栈小结：理解栈的先进后出模型掌握栈的栈顶、栈底的定义理解入栈和出栈操作过程栈的基本运算本节内容：线性结构—栈⑴栈初始化：InitSeqStack(s)初始条件：栈s不存在。操作结果：构造了一个空栈。⑵判栈空：EmptySeqStack(s)初始条件：栈s已存在。操作结果：若s为空栈返回为1，否则返回为0。栈的基本运算⑶入栈：

PushSeqStack(s，x)初始条件：栈s已存在。

操作结果：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。栈发生变化。⑷出栈：PopSeqStack(s)初始条件：栈s存在且非空。操作结果：将栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。栈的基本运算⑸读栈顶元素：TopSeqStack(s)初始条件：栈s存在且非空。操作结果：栈顶元素作为结果返回，栈不变化。栈的基本运算栈的基本运算问题：一个栈的输入序列为A,B,C，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？CBA

?问题：一个栈的输入序列为A,B,C，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？分析：1、只有一个字符出入栈时，只有一种可能，即A入栈也只有A出栈。

AA

A

2、有两个字符AB出入栈时，如果进栈顺序为AB，那么出栈的系列AB、BA都有可能：即可以A进栈、A出栈、B进栈、B出栈，产生输出序列AB；

A

B

A

A

B

B

分析：B

A

BABA

AB

2、有两个字符AB出入栈时，如果进栈顺序为AB，那么出栈的系列AB、BA都有可能：

也可以A进栈、B进栈、B出栈、A出栈，产生输出序列BA。分析：3、分析：三个字符ABC出入栈时，可以通过穷举所有可能性来求解：①A入A出，B入B出，C入C出，即A、B、C；②A入A出，B、C入，C、B出，即A、C、B；③A、B入，B出，C入C出，即B、C、A；④A、B入，B、A出，C入C出，即B、A、C；⑤A、B、C入，C、B、A出，即C、B、A；合计有5种可能性。C、A、B有可能吗？

拓展：四个字符出栈的所有可能序列有几种？（14种）如果有四个字符ABCD出入栈时，排列有4!=24种可能。不是所有排列都有可能是出栈的序列，像CABD这样的序列产生不了。栈的基本运算本节内容：线性结构—栈小结：掌握栈的五个基本操作的定义进一步理解栈的出栈序列和入栈序列顺序栈的结构体类型定义本节内容：线性结构—栈顺序栈的结构体类型定义栈的顺序存储结构简称为顺序栈，和线性表相类似，用静态一维数组来实现顺序栈。

栈底固定不变的，而栈顶则随着进栈和出栈操作变化。◆用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。◆用top=-1，表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。◆

结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。◆结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。

top=-1top=2top=1空栈(b)三个元素(c)2个元素

图栈顶指针top与栈中数据元素的关系顺序栈的结构体类型定义toptop说明：

用栈顶指针top=-1表示空栈;

入栈时，栈顶指针加１，即s->top++;出栈时，栈顶指针减１，即s->top--。

top=-1top=2top=1空栈(b)三个元素(c)2个元素

图栈顶指针top与栈中数据元素的关系顺序栈的结构体类型定义toptop#typedefintElemType;#defineMAXSIZE100;/*栈向量大小*/structSeqStack{ElemTypedata[MAXSIZE];inttop;//栈顶指针}定义一个顺序栈SSeqStack*s;顺序栈的结构体类型定义：顺序栈的结构体类型定义顺序栈的结构体类型定义本节内容：线性结构—栈小结：掌握顺序栈的类型定义理解栈空、栈满状态表示理解栈的进栈和出栈过程中top的变化顺序栈的初始化及入栈本节内容：线性结构—栈顺序栈的初始化及入栈本节内容：线性结构—栈小结：掌握顺序栈的类型定义理解栈空、栈满状态表示理解栈的进栈和出栈过程中top的变化顺序栈的初始化及入栈SeqStack*InitSeqStack(void){SeqStack*S;S=new(SeqStack);

S—>top=-1;/*栈空时,栈顶和栈底指针相同*/returnS;/*返回一个空的栈*/}1、栈的初始化topdatasintEmptySeqStack(SeqStack*s){if(s->top==-1)return1;elsereturn0;}2、判断栈空如果栈，空返回1，否则返回0。顺序栈的初始化及入栈intPushSeqStack(SeqStack*s,ElemType

e){if(s->top==MAXSIZE-1)return0;/*栈满不能入栈*/else{

s->top++;/*栈顶指针加1*/s->data[s->top]=e;/*e成为新的栈顶*/return1;

/*入栈成功*/}}3、入栈(元素进栈)将指定的数据元素e入栈s中。顺序栈的初始化及入栈302010topdatas顺序栈的初始化及入栈本节内容：线性结构—栈小结：掌握顺序栈的类型定义理解栈空、栈满状态表示理解栈的进栈和出栈过程中top的变化顺序栈的出栈及取元素本节内容：线性结构—栈顺序栈的出栈及取元素intPopSeqStack(SeqStack*s,ElemType*e){if(EmptySeqStack(s))return0;/*栈空不能出栈*/else{

*e=s->data[s->top];

s->top--;

return1;/*栈顶元素存入*e，返回成功*/}}4、出栈(元素出栈)将栈s的栈顶元素出栈，栈顶元素的值赋值给参数e。xe302010topdatasintGetSeqStack(SeqStack*s,

ElemType*e){if(EmptySeqStack(s))return0;/*栈空*/else

{*e=s->data[s->top];return1;/*栈顶元素存入*e，返回成功*/}/*栈不变*/}5、取栈顶元素返回栈顶元素的值，栈不变。xe顺序栈的出栈及取元素302010topdatas线性结构—栈小结：理解顺序栈的出栈及取元素的函数定义掌握将顺序栈的出栈及取元素操作步骤转换为语句实现顺序栈的出栈及取元素本节内容：链栈的结构体类型定义本节内容：线性结构—栈链栈的结构体类型定义

栈的链式存储结构称为链栈，是运算受限的单链表，其插入和删除操作只能在表头位置上进行。

说明：链栈不需要附加头结点，栈顶指针top就是链表的头指针。

下面是栈的链式存储表示形式，分别是空栈和非空栈的情况。空栈top⋀非空栈top

a3

a2

a0⋀

a1图

链栈存储形式以链表为数据结构时，以链表头作为栈顶较为合适，这样方便节点的插入与删除。压栈产生的新节点将一直出现在链表的头部。#typedefintElemType;structStackNode{ElemTypedata;structStackNode*next;}*LinkStack;创建一个新结点的语句如下：LinkStacks;s=newLinkStack;s->data=100;s-next=null;链栈的结点类型构造：data

next

^100链栈的结构体类型定义S链栈的结构体类型定义本节内容：线性结构—栈小结：掌握链栈的类型定义理解空栈、非空栈状态表示理解链栈的进栈和出栈过程中表头的变化链栈的初始化及入栈出栈操作本节内容：线性结构—栈LinkStackInitLinkStack(void){

StackNode*top;top=new(StackNode）;top->next=NULL;

returntop;}1、链栈的初始化空栈top⋀链栈的初始化及入栈出栈操作intPushLinkStack（LinkStacktop,inte）{StackNode*p;p=new(StackNode）;if(!p)return0;/*申请新结点失败，返回错误标志*/p->data=e;

p->next=top;

top=p;

/*修改栈顶指针*/return1;}2、入栈(元素进栈)将变量e所在的结点入栈。非空栈toptop

e

a2

a0⋀

a1p×链栈的初始化及入栈出栈操作LinkStackPopLinkStack(LinkStacktop,int*e){StackNode*p;if（top==NULL）returnNULL;/*栈空不能出栈*/else{*e=top->data;/*栈顶元素存入*e*/p=top;top=top->next;/*修改栈顶指针*/

deletep;returntop;/*返回新链栈*/}}/*将栈顶元素出栈*/从栈中弹出一个结点，并将该结点的值赋值给参数e3、出栈(元素出栈)非空栈toptopa3

a2

a0⋀

a1pe×链栈的初始化及入栈出栈操作链栈的初始化及入栈出栈操作本节内容：线性结构—栈小结：掌握链栈的初始化过程理解链表结点的新增与删除过程理解链栈的进栈和出栈过程中链头指针top的变化栈的应用——进制转换本节内容：线性结构—栈栈的应用——进制转换由于栈的“先进后出”特点，栈成为程序设计中常用的工具和数据结构。在很多实际问题中，利用栈做一个辅助的数据结构来进行求解。下面介绍栈在数制转换中的应用。例如：栈在数制转换、括号匹配问题、迷宫求解、表达式求值等方面的应用。十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。数制转换的原理为：

N=(Ndivd)×d+Nmodd其中：div为整除运算,mod为求余运算栈的应用——进制转换例如：（35)10

转换成八进制(43)8

的运算过程如下：

（35)10=4*8+3=(43)8

（122)10

转换成八进制(172)8

的运算过程如下：（122)10=

1*82+7*8+2=(172)8例如：（1348)10

转换成八进制(2504)8

的运算过程如下：

NNdiv8（整除）Nmod8余数计算顺序输出顺序1348168

4

16821

0

2125

2

02栈的应用——进制转换算法思想如下：当N>0时，重复1，2；（1）若N≠0，则将N%r压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束；（2）用N/r代替N。栈的应用——进制转换voidconversion(intN,intr){//显示和输入十进制数对应的八进制数值

SeqStack*S;

intk;

S=InitSeqStack();while(N){

k=N%r;

PushSeqStack(S,k);N=N/r;}/*

求出所有的余数，进栈*/while(!EmptySeqStack(S)){

PopSeqStack(S,e);cout<<e;}/*栈不空时出栈，输出*/}//conversion

采用静态顺序栈方式实现

栈的应用——进制转换#defineL10voidconversion(intN，intr){//将N转换为r进制

ints[L],top;/*定义一个顺序栈*/

inte;top=-1;/*初始化栈,栈为空*/while(N){s[++top]=N%r;/*余数入栈*/N=N/r;/*商作为被除数继续*/}while(top!=-1){e=s[top--];

cout<<e;}}栈的应用——进制转换

采用一维数组直接实现

栈的应用——进制转换本节内容：线性结构—栈小结：理解十进制整数进制转换的计算规律能够由计算规律总结算法思想掌握进制转换的程序设计栈的应用——括号匹配问题本节内容：线性结构—栈栈的应用——括号匹配问题由于栈的“先进后出”特点，栈成为程序设计中常用的工具和数据结构。在很多实际问题中，利用栈做一个辅助的数据结构来进行求解。下面主要介绍栈括号匹配问题中的应用。栈存储结构还可以检测代码中的括号匹配问题。多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。3.4.2括号匹配问题

当栈满时，做进栈运算必定产生空间溢出，简称“上溢”。上溢是一种出错状态，应设法避免。当栈空时，做退栈运算也将产生溢出，简称“下溢”。下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。教学目标第3章栈和队列1.理解栈的逻辑结构定义及在两种存储结构(顺序存储和链式存储)上如何实现栈的基本运算。2.了解队列的逻辑结构定义及在两种存储结构(顺序存储和链式存储)上如何实现队列的基本运算。3.了解栈的经典应用如进制转换、括弧匹配、表达式计算、迷宫求解等。

教学内容3.1栈的定义与运算3.2栈的存储实现及运算实现（顺序、链式）3.3栈的应用举例3.4队列的定义与运算3.5队列的存储实现及运算实现（顺序、链式）3.6队列的应用举例

第3章栈和队列3.1栈的定义与运算

设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素，如图3-1所示。栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。图3-1顺序栈示意图a1a2aian⋯⋯⋯⋯bottomtop进栈（push）出栈(pop)3.4.2括号匹配问题如表达式中

（［］（））或［（［］［］）］等为正确的匹配，

［（］）或（［（）]或[()])均为不正确的匹配。检验括弧匹配的方法可用“按期待的急迫程度进行处理”描述之。[例如考虑下列括号序列:([][())]]可见，括弧匹配也遵循“后进先出”的规律。。如何表示下列“不匹配”的情况？到来的右括弧非是所“期待”的;来了一个“不速之客”;直到结束，也没有等到“期待”的匹配;算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空？若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余。3.4.2括号匹配问题intmatching(charexp[],intn){//检测长度为n的字符序列exp中的括弧是否匹配inti=0;match=true;InitStack(S);while(i<n&&match){switch(exp[i]){case

(

:{Push(S,exp[i]);i++;break;}case

)

:{if(!StackEmpty(S)&&GetTop(S)==

(

){Pop(S,e);i++;}else{match=false;}break;}//case)……returnmatch;算法的实现：表达式求值是程序设计语言编译中一个最基本的问题，它的实现也是需要栈的加入。栈的应用——表达式计算表达式是由运算对象、运算符、括号组成的有意义的式子。运算符从运算对象的个数上分，有单目运算符和双目运算符；从运算类型上分，有算术运算、关系运算、逻辑运算。在此仅限于讨论只含二目运算符的算术表达式。表达式：3*2^（4+2*2-１*3）-53.4.3表达式求值第一步：中缀表达式转换为后缀表达式(1)初态：设置两个栈，首先置操作数栈为空；将“#”作为运算符栈的栈底元素。(2)依次读入表达式中的每个字符，

若当前字符是操作数，则进操作数栈OPTR栈;

若当前字符是运算符，则和OPTR栈的栈顶元素比较优先级：

若当前运算符的优先级高于栈顶运算符，则进OPTR栈;否则，退出栈顶运算符，作相应运算，中间运算结果入OPND栈；(3)重复步骤（2），直到整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）。表达式求值规律：第一步：中缀表达式转换为后缀表达式表达式4+9/3-5S2:操作符栈S1:操作数栈运算级别1、中缀--->后缀表达式S2:操作符栈S1:操作数栈表达式：4+9/3-5#运算级别求值栈2、后缀表达式求值493/+5-设

Exp=S1+OP+S2则称

OP+S1+S2

为前缀表示法

S1+OP+S2

为中缀表示法

S1+S2+OP

为后缀表示法

表达式的三种标识方法：3.4.3表达式求值例如:Exp=a

b

+

(c

d/e)

f前缀式:+

ab

c/def中缀式:

a

b

+

c

d/e

f后缀式:

ab

cde/

f

+结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息，致使运算的次序被改变;4)前缀式的运算规则为:

连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;5)后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式;后缀式的优点是什么?表达式不需要使用括号计算时不需要考虑操作符的优先级,操作符在后缀式中出现的顺序恰为表达式的运算顺序Why?3.4.3表达式求值中缀表示——>转后缀表示先对中缀表达式按运算优先次序加上括号，再把操作符后移到右括号的后面并以就近移动为原则，最后将所有括号消去。如中缀表示(A+B)*D-E/(F+A*D)+C，其转换为后缀表达式的过程如下：

(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)后缀表示

AB+D*EFAD*+/-C+如何从后缀式求值？先找运算符，再找操作数例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

f如何从后缀式求值？12

342/

6

+12123243224322321161161从左到右扫描表达式：1.碰到操作数，则入栈；2.碰到运算符，则从栈中弹出两个操作数加以计算，计算结果入栈。分析“原表达式”和“后缀式”中的运算:a+b#>a+b+c# =>a*b*c# =>a*b+c#>>a+b*c#<>a+b+c*d#=<>a+b*c*d#<=>以‘#’为结束字符。如何从原表达式求得后缀式？从原表达式求得后缀式的规律为：1)设立暂存运算符的栈;2)设表达式的结束符为“#”,

予设运算符栈的栈底为“#”3)若当前字符是操作数，则直接发送给后缀式;4)若当前运算符的优先数高于栈顶运算符，则进栈;5)否则，退出栈顶运算符发送给后缀式;

6)“(”对它之后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：利用栈将中缀表示转换为后缀表示使用栈可将表达式的中缀表示转换成它的前缀表示和后缀表示。为了实现这种转换， 需要考虑各操作符 的优先级。

优先级

操作符

1 单目-、！

2 *、/、% 3 +、-

4 <、<=、>、>=5==、!= 6 && 7 || 各个算术操作符的优先级isp叫做栈内(instackpriority)优先数icp叫做栈外(incomingpriority)优先数。操作符优先数相等的情况只出现在括号配对或栈底的“#”号与输入流最后的“#”号配对时。中缀表达式转换为后缀表达式的算法：1、操作符栈初始化，将结束符‘#’进栈。然后读入中缀表达式字符流的首字符ch。2、重复执行以下步骤，直到ch=‘#’，同时栈顶的操作符也是‘#’，停止循环。（1）若ch是操作数直接输出，读入下一个字符ch。（2）若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp：（3）若icp(ch)>isp(op)，令ch进栈，读入下一个字符ch。（4）若icp(ch)<isp(op)，退栈并输出。（5）若icp(ch)==isp(op)，退栈但不输出(退出的是左括号或#号，所以不输出)，若退出的是“(”号读入下一个字符ch。算法结束，输出序列即为所需的后缀表达式。中缀表达式转换为后缀表达式的算法：//由中缀表达式转后缀表达式/*Prefixexpressionsuffix*///pre=8-2*3+(9-6/2)-5\0voidInToSuf(char*pre,char*&suf){SeqStack<char>*s; s=newSeqStack<char>;SetNULL(s);//s空栈intk=0;

while(*pre){//操作数直接存储在数组suf中if(*pre>='0'&&*pre<='9'){suf[k]=*pre;k++;}else//操作符，依据优先级，决定入栈或存入suf中 { if(EmptyStack(s)){//空栈，直接入栈Push(s,*pre);}elseif(*pre=='('){//直接入栈Push(s,*pre);}elseif(*pre==')'){//（前的全部出栈while(GetTop(s)!='('){suf[k]=Pop(s);k++;}Pop(s);//弹出( }

3.4.3表达式求值

else{while(prio(*pre)<=prio(GetTop(s))){//外面的运算符级别比栈中低suf[k]=Pop(s);k++;if(EmptyStack(s))break; } Push(s,*pre);//该运算符进栈 }}pre++;}while(!EmptyStack(s)){//留在s栈中的运算符全部存到结果字符串suf中suf[k]=Pop(s);k++;

}//suf为后缀表达式suf[k]='\0';}3.4.3表达式求值//由中缀表达式转后缀表达式a(b(c+d/e)-f)##a

(b

(c+d

/e//++

-f-

#//由中缀表达式转后缀表达式演示另一个例子：A+B*(C-D)-E/F另一个例子：A+B*(C-D)-E/F//计算后缀表达式的结果typedefcharElemType;doublecalcul_exp(char*A){/*本函数返回由后缀表达式A表示的表达式运算结果*/

SeqStacks;ch=*A++;//后缀表达式A

InitSeqStack(&s);while(ch!=’#’){if(ch!=运算符)PushSeqStack(&s,ch);//数字，入栈else{

PopSeqStack(s,&a);

PopSeqStack(s,&b);/*取出两个运算量*/

3.4.3表达式求值switch(ch){casech==’+’：c=a+b;break;casech==’-’：c=a-b;break;casech==’*’：c=a*b;break;casech==’/’：c=a/b;break;casech==’%’：c=a%b;break;}

PushSeqStack(&s,c);//中间结果入栈}ch=*A++;//读下一个字符}/*while*/

PopSeqStack(s,result);//结果数据出栈returnresult;}3.4.3表达式求值##################Q#######回溯法：求解思想：回溯算法实际上是一个类似枚举的搜索尝试过程。

1．从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北的方向，依着某个走得通的方向继续往前直到出口为止；2．如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通。

深度优先搜索（DepthFirstSearch）迷宫问题（八个方向）EntranceExitMaze[m][p]迷宫问题（四周加墙）ExitMaze[m+2][p+2]

top—>5,8,

2

5,7,

0

5,6,

0

4,5,

1top—>3,6,

03,6,

3

3,5,

03,5,

03,4,

03,4,

03,3,

03,3,

02,2,

12,2,

11,1,

11,1,

1当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向。图3.5所示

迷宫依次入栈顺序

4、入栈01234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111

intmaze[m+2][n+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,1,0,1,1,1,1,1},

{1,0,1,0,0,0,0,0,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,0,1,1,0,0,0,1},

{1,0,1,1,0,0,1,1,0,1},

{1,1,1,1,1,1,1,1,1,1}

};//8*10入口：（1,1）,出口（6，8）01234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111

top—>5,8,

2

5,7,

0

5,6,

0

4,5,

1top—>3,6,

03,6,

3

3,5,

03,5,

03,4,

03,4,

03,3,

03,3,

02,2,

12,2,

11,1,

11,1,

1栈的应用——迷宫问题本节内容：线性结构—栈

在实验心理学中有一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，如图所示，迷宫中设置很多隔离墙，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解从入口到出口的所经过的路径。

栈的应用——迷宫问题

3.4.

计算机解迷宫时，通常用的是“穷举求解”的方法。即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；

否则，沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。

栈的应用——迷宫问题#################Q#######移动方向(八个方向)X[i][j][i+1][j][i][j+1][i][j-1][i+1][j-1][i+1][j+1][i-1][j+1][i-1][j][i-1][j-1]NESWNESESWNW(i，j)图3.6与点(i，j)相邻的8个点及坐标0(i，j+1)4(i，j-1)2(i+1，j)6(i-1，j)7(i-1，j+1)5(i-1，j-1)3(i+1，j-1)1(i+1，j+1)2、八个方向坐标变换的值为：00111121031-140-15-1-16-107-11图3.7增量数组movemove数组定义如下：structitem

{intx，y};itemmove[8];按某一方向v(0<=v<=7)到达的新点（i，j）的坐标：i=i+move[v].x;j=j+move[v].y;012345678901111111111110111011112110101111131010000011410111011115110011000161011001101711111111110123456789011111111111101111111211111111311114111111115111116111110171111111111

top—>

top—>

迷宫问题1、迷宫数据结构：maze[m][n]二维数组来表示一个迷宫;

maze[i][j]=0或1;其中：0表示通路，1表示不通，是墙。

-1表示已经走过。从点maze[i][j]可试探的方向有8个方向。为了算法方便，在迷宫外围加了一道围墙。使用另外一个maze[m+2][p+2]

维度的数组，来表示迷宫，使得每个点的试探方向全部为8。

迷宫问题3、路径表示

通常解决迷宫问题时，常用堆栈来储存已走过之路径的方向和坐标。structpoint/*横纵坐标及方向*/{ intx,y;//迷宫中某点

intdir;//到达该点的行走放向0-7，

//初始为-1}栈的定义为：SeqStacks;迷宫问题4、如何防止重复到达某点，以避免发生死循环?当到达某点（i,j）后使maze[i][j]置-1，以便区别未到达过的点，同样也能起到防止走重复点的目的。求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。思路分析：

我们使用一个二维数组模拟迷宫，并新建一个栈来保存从入口通往出口的路径。然后以入口节点为基准节点，依次向八个方向探测，如果探测到新的活节点，就将新探测到的活节点压入栈中，并以此新节点为基准节点继续向八个方向探测，直到找出迷宫出口。如果某基准节点八个方向不存在活节点，则认为此基准节点为死节点，将其从栈中弹出，返回上次基准节点继续探测(为避免重复探测，探测过的基准节点要加上标记)。迷宫求解路径算法的基本思想：1．栈初始化;2．将入口点坐标及到达该点的方向（设为－1）入栈3．while(栈不空){

栈顶元素＝＞（x,y,d）

出栈;

求出下一个要试探的方向d++;

while（还有剩余试探方向时）{

if（d方向可走）

则{（x,y,d）入栈;求新点坐标(i,j);将新点（i,j）切换为当前点（x,y）;if((x,ｙ)==(ｍ,n))结束;else重置d=0;}elsed++;}

}//进栈操作MazeStack*push(MazeStack*s,pointx){//x点进栈if(s->top>MAXSIZE-1){cout"栈上溢出\n";returns;}else{

s->top++;

s->data[s->top]=x;

returns;}}//退栈操作point*pop(MazeStack*s){if(isEmpty(s)){cout<<("栈为空！\n";returnNULL;}else{

s->top--;

return&(s->data[s->top+1]);}}typedefstruct{//定义迷宫中的点类型，即为对栈中的元素类型，d为移动方向的下标intx,y,d;}point;structMazeStack{//对栈的结构进行定义

pointdata[MAXSIZE];inttop;};structitem{//定义方向类型对移动数组进行定义，方便进行点的移动intx,y;//xy方向};//对移动数组进行定义，8个方向，方便进行点的移动voiddefineMove(itemxmove[8]){xmove[0].x=0,xmove[0].y=1;.......}

top—>5,8,

2

5,7,

0

5,6,

0

4,5,

1top—>3,6,

03,6,

3

3,5,

03,5,

03,4,

03,4,

03,3,

03,3,

02,2,

12,2,

11,1,

11,1,

1当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向。对于图3-5所示迷宫，依次入栈顺序

4、入栈01234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111

intmaze[m+2][n+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,1,0,1,1,1,1,1},

{1,0,1,0,0,0,0,0,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,0,1,1,0,0,0,1},

{1,0,1,1,0,0,1,1,0,1},

{1,1,1,1,1,1,1,1,1,1}

};//8*1001234567890111111111111011101111211010111113101000001141011101111511001100016101100110171111111111start.x=1;//起点位置start.y=1;start.d=-1;//移动方向的下标，初始为-1s=push(s,start);//将起点压入栈while(!isEmpty(s)){//栈不空p=pop(s);//出栈，p为当前起点x=p->x;y=p->y;

d=p->d+1;//方向数组里取下一个值，代表下一个方向

while(d<8){//每个点的d取值从0号方向开始到7，表示8个方向i=xmove[d].x+x;//移动后的位置点j=xmove[d].y+y;if(maze[i][j]==0){

//移动后的点坐标(i,j),0表示迷宫中该点通p->d=d;//更新p->d,记下从(x,y)走到该点的方向s=push(s,*p);//该路径走成功，达到的该点入栈x=i;y=j;maze[x][y]=-1;//迷宫中，-1记下该点已经走过pointnw;//新的点nw.x=x;nw.y=y;nw.d=-1;//方向的初始值为-1

s=push(s,nw);//该点入栈if(x==m&&y==n){//找到出口，输出路径,退出循环cout<<"找到出口！\n";while(!isEmpty(s)){//输出栈中路线p=pop(s);cout<<"\n("<<p->x<<","<<p->y<<")—>"<<setw(3)<<p->d;} cout<<endl;return1;//退出循环} else{break;} } else {d++;//如果已走过，下一个方向,d从0-7 }}}return0;栈的应用——迷宫问题本节内容：线性结构—栈小结：理解迷宫问题的求解思想掌握迷宫数据结构的定义，八个方向的坐标表示及坐标数组存储理解迷宫求解路径算法的基本思想了解迷宫路径算法的程序设计线性结构—队列学习内容：队列的存储实现及运算实现（顺序、链式）队列的定义与运算队列的应用举例队列的定义与运算本节内容：线性结构—队列

依据先来先服务的规则进行排队模型日常模型：机器模型：

操作系统进行调度服务的程序。先进入队列的成员总是先离开队列。

队列的定义与运算队列(Queue)：也是运算受限的线性表，是一种先进先出(FirstInFirstOut，简称FIFO)的线性表。

只允许在表的一端进行插入，而在另一端进行删除。队首(front)：允许进行删除的一端称为队首。队尾(rear)：允许进行插入的一端称为队尾。队首front队尾rear(1)队列初始化：InitQueue(q)初始条件：队q不存在；操作结果：构造了一个空队。(2)入队操作：InQueue(q,x)初始条件：队q存在；操作结果：对已存在的队列q，插入一个元素x到队尾，队发生变化。(3)出队操作：OutQueue(q,x)初始条件:队q存在且非空；操作结果：删除队首元素，并返回其值，队发生变化。队列的基本运算队列的定义与运算(4)读队头元素：FrontQueue(q,x)初始条件:队q存在且非空；操作结果：读队头元素，并返回其值，队不变；(5)判队空操作：EmptyQueue(q)初始条件：队q存在；操作结果：若q为空队则返回为1，否则返回为0。队列的基本运算队列的定义与运算队列的定义与运算本节内容：线性结构—队列小结：理解队列先进先出的模型掌握队列的队首、队尾的表示，出队与入队的操作过程掌握队列的五个基本操作的定义顺序队列的结构体类型定义本节内容：线性结构—队列

采用一维数组来存储从队首到队尾的元素，称为顺序队列。用两个变量记录队首、队尾元素位置。

顺序队列的结构体类型定义：typedefstructQueueNode{

ElemType

data[MAXSIZE];/*队员的存储空间*/intfront;/*队头指针*/intrear;/*队尾指针*/}SeqQueue;顺序队列的结构体类型定义

队列的顺序存储与实现：SeqQueuesq;/*定义一个指向队列的指针变量*//*申请一个顺序队的存储空间*/访问队列的数据区为：

sq.data[0]---sq.data[MAXSIZE-1]

sq.front

/*队头指针*/

sq.rear

/*队头指针*/data[0]data[Maxsize-1]sq顺序队列的结构体类型定义顺序队列的结构体类型定义

顺序队列的操作示意图：队列中实际元素个数可能远远小于数组大小，但可能由于尾指针已超出向量空间的上界而不能做入队操作。该现象称为假溢出。

为充分利用向量空间，克服上述“假溢出”现象的方法是：将为队列分配的向量空间看成为一个首尾相接的圆环，并称这种队列为循环队列(CircularQueue)。

因为是头尾相接的循环结构，入队时的队尾指针加1操作修改为：

sq.rear=(sq.rear+1)%MAXSIZE;01234567frontrearmaxsize-1顺序队列的结构体类型定义#typedefintElemType;#defineMAXSIZE50;/*栈向量大小*/structSeqQueue{intdata[MAXSIZE];/*数据的存储区*/intfront,rear;/*队头队尾指针*/intnum;/*队中元素的个数*/}/*循环队*/定义一个顺序栈SSeqQueue*q;循环队列的类型定义：顺序队列的结构体类型定义顺序队列的结构体类型定义本节内容：线性结构—队列小结：掌握顺序队列的类型定义、访问队列的数据理解循环队列入队、出队的操作过程理解循环队列队满、队空的状态顺序队列的基本运算本节内容：线性结构—队列SeqQueue*

InitSeqQueue(){

SeqQueueq;

q.front=q.rear=MAXSIZE-1;

q.num=0;returnq;}

顺序队列的基本运算rearfrontrearfront1、初始化队列

2、入队intInSeqQueue(SeqQueueq

,intx){if(q->num==MAXSIZE){cout<<＂队满“;

return–1;/*队满不能入队*/}else{

q.rear=(q.rear+1)%MAXSIZE;

q.data[q.rear]=x;

q.num++;

return1;/*入队成功*/}}XX

顺序队列的基本运算3、出队intOutSeqQueue(SeqQueue&q

,int*x){if(q.num==0){cout<<“队空”；

return–1;/*队空不能出队*/}else{

q.front=(q.front+1)%MAXSIZE;*x=q.data[q.front];/*读出队头元素*/

q.num--;

return1;/*出队成功*/}}

顺序队列的基本运算4、队空intEmptySeqQueue(SeqQueue&q){