第3章 栈、队列和递归-V0.1

数据结构实验指导与习题解答——Python语言描述张光河

主编guanghezhang@163.com人民邮电出版社2022年09月1ISBN：978-7-115-56280-7ISBN：978-7-115-56280-7ISBN：978-7-115-48577-9配套教材主教材主教材与配套教材2第三章栈、队列和递归3习题解答3.3综合实验3.2基础实验3.1目录CONTENTS43.1基础实验53.1.1实现顺序栈的基本操作基础实验1基础实验23.1.23.1.33.1.43.1.5实现链栈的基本操作实现顺序队列的基本操作实现循环顺序队列的基本操作实现链式队列的基本操作基础实验3基础实验4基础实验53.1.6基础实验6实现循环链式队列的基本操作

基础实验1实现顺序栈的基本操作6考察能否正确理解栈的顺序存储结构，以及对顺序栈基本操作的掌握程度。实验目的实验内容创建名为ex030501_01.py的文件，在其中编写一个顺序栈的类，该类必须包含顺序栈的定义及基本操作，并通过以下步骤测试基本操作的实现是否正确。（1）初始化一个顺序栈SequenceStack。（2）判断栈是否为空。（3）将元素1，3，5依次进栈。（4）遍历栈内所有元素。（5）获取栈顶元素。（6）获取栈的长度。（7）将栈中元素依次出栈并输出。（8）判断栈是否为空。71#############################################################2#文件名：ex030501_01.py3#版本号：0.14#创建时间：2017-09-145#修改时间：2017-01-076###########################################################7#类名称：SequenceStack8#类说明：定义一个栈9#类释义：提供顺序栈的相关操作10###########################################################11classSequenceStack:12############################13#默认的初始化栈的函数14############################15def__init__(self):16self.MaxStackSize=1017self.s=[Noneforxinrange(0,self.MaxStackSize)]18self.top=-119############################实验代码820#初始化栈的函数21############################22defInitStack(self):23self.MaxStackSize=1024self.s=[Noneforxinrange(0,self.MaxStackSize)]25self.top=-126#############################27#访问某一元素的函数28#############################29defStackVisit(self,element):30print(element,end='')31############################32#判断栈是否为空的函数33############################34defIsEmptyStack(self):35ifself.top==-1:36iTop=True37else:38iTop=False39returniTop40############################41#元素进栈的函数42############################43defPushStack(self,x):44ifself.top<self.MaxStackSize-1:945self.top=self.top+146self.s[self.top]=x47else:48print("栈满")49return50############################51#元素出栈的函数52############################53defPopStack(self):54ifself.IsEmptyStack():55print("栈为空")56return57else:58iTop=self.top59self.top=self.top-160returnself.s[iTop]61#############################62#依次访问栈中元素的函数63#############################64defStackTraverse(self):65ifself.IsEmptyStack():66print("栈为空")1067return68else:69foriinrange(0,self.top+1):70self.StackVisit(self.s[i])71############################72#获取当前栈顶元素的函数73############################74defGetTopStack(self):75ifself.IsEmptyStack():76print("栈为空")77return78else:79returnself.s[self.top]80############################81#输出当前栈长度的函数82############################83defGetStackLength(self):84ifself.IsEmptyStack():85print("栈为空")86return87else:88returnself.top+189#############################################################90#类名称：TestSequenceStack1191#类说明：定义一个测试顺序栈的类92#类释义：提供测试的方法93############################################################94classTestSequenceStack:95############################96#测试顺序串相关操作的函数97############################98defPrintOut(self,st):99print("（1）经判断当前栈",end='')100ifst.IsEmptyStack()==True:101print("为空")102else:103print("不为空")104st.PushStack('1')105st.PushStack('3')106st.PushStack('5')107print("（2）元素",end='')108st.StackTraverse()109print("依次进栈",end='')110print("\n（3）当前栈顶元素为",end='')111print(st.GetTopStack())112print("（4）当前栈中共有",end='')113print(st.GetStackLength(),end='')12118st.StackTraverse()119print("\n（6）元素",st.GetTopStack(),"出栈，当前栈中元素为",end='')120st.PopStack()121st.StackTraverse()122print("\n（7）元素",st.GetTopStack(),"出栈，当前",end='')123st.PopStack()124ifst.IsEmptyStack()==True:125print("栈为空")126else:127print("栈不为空")128if__name__=='__main__':129SS=SequenceStack()130TSS=TestSequenceStack()131TSS.PrintOut(SS)注意：在上述代码中，我们在PrintOut()函数中调用初始化顺序表函数（__init__(self)）、判断顺序表是否为空（IsEmpty()）和创建顺序表（CreateSequenceList()）时使用了Python提供的异常处理代码（try......except），其目的是为了在发生错误时，及时捕获所产生的异常，并对其做出调整，以便程序更为稳定流畅的运行。在之后的例子中，由于篇幅的限制，调用其它函数时没有增加异常处理代码，请在实际编写代码时参照此实例加上。

基础实验2实现链栈的基本操作13考察能否正确理解栈的链式存储结构，以及对链栈基本操作的掌握程度。实验目的实验内容创建名为ex030501_02.py的文件，在其中编写结点的类和链式栈的类，后者必须包含链式栈的定义及基本操作，并通过以下步骤测试基本操作的实现是否正确。（1）初始化一个链栈LinkStack。（2）判断栈是否为空。（3）将元素2，4，6依次进栈。（4）获取栈顶元素。（5）将栈中元素依次出栈并输出。141#########################################################2#文件名：ex030501_02.py3#版本号：0.24#创建时间：2017-11-095#修改时间：2018-01-076##########################################################7#类名称：StackNode8#类说明：定义一个结点9#类释义：分别有数据元素data，指向下一个结点的指针next10##############################################################11classStackNode:12#############################13#默认的初始化结点的函数14#############################15def__init__(self):16self.data=None17self.next=None18##############################################################19#类名称：LinkStack20#类说明：定义一个链栈21#类释义：提供链栈的相关操作实验代码1522##############################################################23classLinkStack:24#############################25#默认的初始化链栈的函数26#############################27def__init__(self):28self.top=StackNode()29#############################30#初始化链栈的函数31#############################32defInitStack(self):33self.top=StackNode()34#############################35#判断链栈是否为空的函数36#############################37defIsEmptyStack(self):38ifself.top.next==None:39iTop=True40else:41iTop=False42returniTop43#############################44#访问某一元素的函数45#############################1646defStackVisit(self,element):47print(element,end='')48#############################49#进栈的函数50#############################51defPushStack(self,data):52tStackNode=StackNode()53tStackNode.data=data54tStackNode.next=self.top.next55self.top.next=tStackNode56#############################57#出栈的函数58#############################59defPopStack(self):60ifself.IsEmptyStack()==True:61print("栈为空。")62return63else:64tStackNode=self.top.next65self.top.next=tStackNode.next66returntStackNode.data67#############################68#获得当前栈顶元素的函数69#############################70defGetTopStack(self):1771ifself.IsEmptyStack():72print("栈为空。")73return74else:75returnself.top.next.data76############################77#测试链栈相关操作的函数78############################79defPrintOut(self):80print("（1）经判断当前栈",end='')81ifself.IsEmptyStack()==True:82print("为空。")83else:84print("不为空。")85self.PushStack(2)86self.PushStack(4)87self.PushStack(6)88print("（2）当前栈顶元素为",self.GetTopStack(),"。")89print("（3）元素",self.PopStack(),"出栈。")90print("（4）元素",self.PopStack(),"出栈。")91print("（5）元素",self.PopStack(),"出栈。",end='')92self.PopStack()93if__name__=='__main__':94LS=LinkStack()95LS.PrintOut()

基础实验3实现顺序队列的基本操作18考察能否正确理解队列的顺序存储结构，以及对顺序队列基本操作的掌握程度。实验目的实验内容创建名为ex030501_03.py的文件，在其中编写一个顺序队列的类，该类必须包含顺序队列的定义及基本操作，并通过以下步骤测试基本操作的实现是否正确。（1）初始化一个顺序队列SequenceQueue。（2）判断队列是否为空。（3）遍历队列内的所有元素。（4）将元素1，3，5，7，9，……依次进队至队满。（5）遍历队列内的所有元素。（6）获取队头元素。（7）获取队列的长度。（8）将一个元素出队并输出。（9）尝试能否将一个新元素进队。191################################################################2#文件名：ex030501_03.py3#版本号：0.24#创建时间：2017-09-145#修改时间：2018-01-076################################################################7#类名称：SequenceQueue8#类说明：定义一个队列9#类释义：提供顺序队列的相关操作10################################################################11classSequenceQueue:12############################13#默认的初始化队列的函数14############################15def__init__(self):16self.MaxQueueSize=517self.s=[Noneforxinrange(0,self.MaxQueueSize)]18self.front=019self.rear=020############################21#初始化队列的函数22############################实验代码2023defInitQueue(self):24MaxQueueSize=425self.s=[Noneforxinrange(0,self.MaxQueueSize)]26self.front=027self.rear=028#############################29#判断队列是否为空的函数30#############################31defIsEmptyQueue(self):32ifself.front==self.rear:33iQueue=True34else:35iQueue=False36returniQueue37#############################38#元素入队的函数39#############################40defEnQueue(self,x):41if(self.rear<self.MaxQueueSize-1):42self.rear=self.rear+143self.s[self.rear]=x44else:45print("队列已满，无法进队")46return47#############################2148#访问队列中某一元素的函数49#############################50defQueueVisit(self,element):51print(element,end='')52#############################53#元素出队的函数54#############################55defDeQueue(self):56ifself.IsEmptyQueue():57print("队列为空，无法出队")58return59else:60self.front=self.front+161returnself.s[self.front]62#############################63#依次访问队列中元素的函数64#############################65defQueueTraverse(self):66ifself.IsEmptyQueue():67print("队列为空，队列无元素可以访问")68return69else:70foriinrange(self.front+1,self.rear+1):71self.QueueVisit(self.s[i])72#############################2273#获取当前队头元素的函数74#############################75defGetHead(self):76ifself.IsEmptyQueue():77print("队列为空，无法输出队头元素")78return79else:80returnself.s[self.front+1]81#############################82#获取队列长度的函数83#############################84defGetQueueLength(self):85ifself.IsEmptyQueue():86print("队列为空，队列长度为0")87return88else:89returnself.rear-self.front90############################91#测试顺序队列相关操作的函数92############################93defPrintOut(self):94print("（1）经判断当前队列",end='')95ifself.IsEmptyQueue()==True:96print("为空")97else:2398print("不为空")99self.EnQueue(1)100self.EnQueue(3)101self.EnQueue(5)102self.EnQueue(7)103print("（2）元素",end='')104self.QueueTraverse()105print("依次进队，",end='')106self.EnQueue(9)107print("（3）当前队头元素为",end='')108print(self.GetHead())109print("（4）当前队列中共有",end='')110print(self.GetQueueLength(),end='')111print("个元素，分别为",end='')112self.QueueTraverse()113print("\n（5）元素",self.GetHead(),"出队，当前队列中的元素为",end='')114self.DeQueue()115self.QueueTraverse()116print("\n（6）尝试将新元素进队：",end='')117self.EnQueue(9)118if__name__=='__main__':119SQ=SequenceQueue()120SQ.PrintOut()

基础实验4实现循环顺序队列的基本操作24考察能否正确理解队列的顺序存储结构，以及对循环顺序队列基本操作的掌握程度。实验目的实验内容创建名为ex030501_04.py的文件，在其中编写一个循环顺序队列的类，该类必须包含循环顺序队列的定义及基本操作，并通过以下步骤测试各种基本操作的实现是否正确。（1）初始化一个循环顺序队列CircularSequenceQueue。（2）判断队列是否为空。（3）遍历队列内的所有元素。（4）将元素1、3、5、7、9、……依次进队至队满。（5）遍历队列内的所有元素。（6）获取队头元素。（7）获取队列的长度。（8）出队一个元素并输出。（9）尝试能否将一个新元素进队。251###########################################################2#文件名：ex030501_04.py3#版本号：0.24#创建时间：2017-09-145#修改时间：2018-01-076#########################################################7#类名称：CircularSequenceQueue8#类说明：定义一个循环顺序队列9#类释义：提供循环顺序队列的相关操作10#########################################################11classCircularSequenceQueue:12###############################13#默认的初始化循环顺序队列的函数14###############################15def__init__(self):16self.MaxQueueSize=517self.s=[Noneforxinrange(0,self.MaxQueueSize)]18self.front=019self.rear=020############################实验代码2621#初始化循环顺序队列的函数22############################23defInitQueue(self,Max):24self.MaxQueueSize=Max25self.s=[Noneforxinrange(0,self.MaxQueueSize)]26self.front=027self.rear=028#############################29#访问某一元素的函数30#############################31defQueueVisit(self,element):32print(element,end='')33################################34#判断循环顺序队列是否为空的函数35################################36defIsEmptyQueue(self):37ifself.front==self.rear:38iQueue=True39else:40iQueue=False41returniQueue42###################43#元素入队的函数44#############################45defEnQueue(self,x):46if(self.rear+1)%self.MaxQueueSize!=self.front:2747self.rear=(self.rear+1)%self.MaxQueueSize48self.s[self.rear]=x49else:50print("队列已满，无法进队")51return52#############################53#元素出队的函数54#############################55defDeQueue(self):56ifself.IsEmptyQueue():57print("队列为空，无法出队")58return59else:60self.front=(self.front+1)%self.MaxQueueSize61returnself.s[self.front]62#############################63#依次访问队列中元素的函数64#############################65defQueueTraverse(self):66ifself.IsEmptyQueue():67print("队列为空，队列无元素可以访问")68return69else:70ifself.front<self.rear:71i=self.front+12872whilei<self.rear:73self.QueueVisit(self.s[i])74i=i+175self.QueueVisit(self.s[self.rear])76else:77i=self.front+178whilei<self.MaxQueueSize:79self.QueueVisit(self.s[i])80i=i+181i=082whilei<=self.rear:83self.QueueVisit(self.s[i])84i=i+185#############################86#获取队头元素的函数87#############################88defGetHead(self):89ifself.IsEmptyQueue():90print("队列为空，无法输出队头元素")91return92else:93returnself.s[(self.front+1)%self.MaxQueueSize]94#############################95#输出当前队列中元素个数的函数96#############################97defGetQueueLength(self):2998ifself.IsEmptyQueue():99print("队列为空，队列长度为0")100return101else:102return(self.rear-self.front+self.MaxQueueSize)%self.MaxQueueSize103###############################104#测试循环顺序队列相关操作的函数105###############################106defPrintOut(self):107print("（1）经判断当前队列",end='')108ifself.IsEmptyQueue()==True:109print("为空")110else:111print("不为空")112self.EnQueue(1)113self.EnQueue(3)114self.EnQueue(5)115self.EnQueue(7)116print("（2）元素",end='')117self.QueueTraverse()118print("依次进队，",end='')119self.EnQueue(9)120print("（3）当前队头元素为",end='')121print(self.GetHead())30126

cNode=cNode.next127

Pos=Pos+1128

ifcNode.data==key:129

print("查找成功！值为",key,"的结点位于该双链表的第",Pos,"个位置")130

else:131

print("查找失败！当前双链表中不存在值为",key,"的结点")132

#####################################133

#按prev域遍历双链表函数134

#####################################135

defTraverseDoubleLinkedListByPrev(self):136

cNode=self.head137

print("按prev域遍历带头结点的双链表：")138

ifself.IsEmpty():139

print("当前双链表为空！")140

return141

whilecNode.next!=None:142

cNode=cNode.next143

whilecNode.prev!=self.head:144

self.VisitElementByPrev(cNode)145

cNode=cNode.prev146

print(cNode.data)147

#####################################148

#按prev域输出双链表某一元素函数149

#####################################150

defVisitElementByPrev(self,tNode):31122print("（4）当前队列中共有",end='')123print(self.GetQueueLength(),end='')124print("个元素，分别为",end='')125self.QueueTraverse()126print("\n（5）元素",self.GetHead(),"出队，当前队列中的元素为",end='')127self.DeQueue()128self.QueueTraverse()129self.EnQueue(9)130print("\n（6）尝试将新元素进队后，当前队列中的元素为",end='')131self.QueueTraverse()132if__name__=='__main__':133CSQ=CircularSequenceQueue()134CSQ.PrintOut()

基础实验5实现链式队列的基本操作32考察能否正确理解队列的链式存储结构，以及对链式队列基本操作的掌握程度。实验目的实验内容创建名为ex030501_05.py的文件，在其中编写一个链式队列的类，该类必须包含链式队列的定义及基本操作，并通过以下步骤测试基本操作的实现是否正确。（1）初始化一个链式队列LinkQueue。（2）判断队列是否为空。（3）将元素1，3，5依次进队。（4）遍历队列内的所有元素。（5）获取队头元素。（6）获取队列的长度。（7）将队列中元素依次出队并输出。（8）判断队列是否为空。331###################################################2#文件名：ex030501_05.py3#版本号：0.24#创建时间：2017-9-155#修改时间：2018-01-076####################################################7#类名称：QueueNode8#类说明：定义一个结点9#类释义：分别有数据元素data，指向下一个结点的指针next10#####################################################11classQueueNode:12def__init__(self):13self.data=None14self.next=None15###################################################16#类名称：LinkQueue17#类说明：定义一个链式队列18#类释义：提供链式队列的相关操作19###################################################20classLinkQueue:实验代码3421############################22#默认的初始化队列的函数23############################24def__init__(self):25TQueueNode=QueueNode()26self.front=TQueueNode27self.rear=TQueueNode28############################29#初始化队列的函数30############################31defInitQueue(self):32TQueueNode=QueueNode()33self.front=TQueueNode34self.rear=TQueueNode35#############################36#判断队列是否为空的函数37#############################38defIsEmptyQueue(self):39ifself.front==self.rear:40iQueue=True41else:42iQueue=False43returniQueue44#############################45#访问队列中某一元素函数3546#############################47defQueueVisit(self,element):48print(element,end='')49#############################50#入队的函数51#############################52defEnQueue(self,data):53TQueueNode=QueueNode()54TQueueNode.data=data55self.rear.next=TQueueNode56self.rear=TQueueNode57#############################58#出队的函数59#############################60defDeQueue(self):61ifself.IsEmptyQueue():62print("队列为空")63return64else:65TQueueNode=self.front.next66self.front.next=TQueueNode.next67ifself.rear==TQueueNode:68self.rear=self.front69returnTQueueNode.data70############################36118LQ=LinkQueue()119LQ.PrintOut()

基础实验6实现循环链式队列的基本操作37考察能否正确理解队列的链式存储结构，以及对循环链式队列基本操作的掌握程度。实验目的实验背景创建名为ex030501_06.py的文件，在其中编写一个循环链式队列的类，该类必须包含循环链式队列的定义及基本操作，并通过以下步骤测试基本操作的实现是否正确。（1）初始化一个循环链式队列CircularLinkQueue。（2）判断队列是否为空。（3）将元素2，4，6依次进队。（4）遍历队列内的所有元素。（5）获取队头元素。（6）获取队列的长度。（7）将队列中元素依次出队并输出。（8）判断队列是否为空。381###################################################2#文件名：ex030501_06.py3#版本号：0.24#创建时间：2017-9-155#修改时间：2018-01-076####################################################7#类名称：QueueNode8#类说明：定义一个结点9#类释义：分别有数据元素data，指向下一个结点的指针next10#####################################################11classQueueNode:12def__init__(self):13self.data=None14self.next=None15######################################################16#类名称：CircularLinkQueue17#类说明：定义一个带头结点的循环链式队列18#类释义：有指向队尾的指针rear和队列的长度length实验代码3919######################################################20classCircularLinkQueue:21############################22#默认的初始化队列的函数23############################24def__init__(self):25self.rear=QueueNode()26self.rear.next=self.rear27self.length=028############################29#初始化队列的函数30############################31defInitQueue(self):32self.rear=QueueNode()33self.rear.next=self.rear34self.length=035#############################36#判断队列是否为空的函数37#############################38defIsEmptyQueue(self):39ifself.rear.next==self.rear:40iQueue=True41else:42iQueue=False4044#############################45#访问某一元素的函数46#############################47defQueueVisit(self,element):48print(element,end='')49#############################50#入队的函数51#############################52defEnQueue(self,data):53tQueueNode=QueueNode()54tQueueNode.data=data55tQueueNode.next=self.rear.next56self.rear.next=tQueueNode57self.rear=tQueueNode58self.length=self.length+159#############################60#出队的函数61#############################62defDeQueue(self):63ifself.IsEmptyQueue():64print("队列为空")65return66else:67tQueueNode=self.rear.next.next68self.rear.next.next=tQueueNode.next4169iftQueueNode==self.rear:70self.rear=self.rear.next71self.length=self.length-172returntQueueNode.data73############################74#获得当前队首元素的函数75############################76defGetHead(self):77ifself.IsEmptyQueue():78print("队列为空")79return80else:81returnself.rear.next.next.data82############################83#依次访问队列中元素的函数84############################85defQueueTraverse(self):86ifself.IsEmptyQueue():87print("队列为空")88return89else:90tQueueNode=self.rear.next.next91whiletQueueNode!=self.rear:92self.QueueVisit(tQueueNode.data)93tQueueNode=tQueueNode.next94self.QueueVisit(self.rear.data)4295#############################96#获取队列长度的函数97#############################98defGetQueueLength(self):99ifself.IsEmptyQueue():100print("队列为空，队列长度为0")101return102else:103returnself.length104###############################105#测试循环链式队列相关操作的函数106###############################107defPrintOut(self):108print("（1）经判断当前队列",end='')109ifself.IsEmptyQueue()==True:110print("为空")111else:112print("不为空")113self.EnQueue(2)114self.EnQueue(4)115self.EnQueue(6)116print("（2）元素",end='')117self.QueueTraverse()118print("依次进队",end='')119print("\n（3）当前队首元素为",end='')120print(self.GetHead())43121print("（4）元素",self.GetHead(),"出队，当前队列中的元素为：",end='')122self.DeQueue()123self.QueueTraverse()124print("\n（5）元素",self.GetHead(),"出队，当前队列中的元素为：",end='')125self.DeQueue()126self.QueueTraverse()127print("\n（6）元素",self.GetHead(),"出队，当前队列中的元素为：",end='')128self.DeQueue()129self.QueueTraverse()130if__name__=='__main__':131CLQ=CircularLinkQueue()132CLQ.PrintOut()3.2综合实验443.2.1分析英文文章综合实验1综合实验23.2.23.2.3电子转盘抽奖递归程序设计综合实验3

综合实验1学生成绩录入45熟练掌握递归算法的设计思路，深入理解递归算法的执行过程，并尝试将递归算法转换为非递归算法。实验目的实验背景递归程序具有结构清晰、可读性好和易于理解等优点，但从空间复杂度上来看，由于每一次递归调用都需要在栈中分配空间来保存数据（如实参、返回地址和局部变量等），所以在一个递归程序执行的过程中会占用很多的空间，而且若递归次数太多，可能会导致栈溢出，甚至系统的崩溃；而从时间复杂度上来看，每一次递归调用向栈里压入数据和从栈里弹出数据都需要时间，并且有时会有重复的计算。因此，递归算法的空间和时间复杂度较大，执行效率低下，通常我们需要把递归算法转换为非递归算法。46实验内容创建名为ex030502_03.py的文件，在其中编写Ackerman函数的递归算法及非递归算法。

Ackerman函数定义如下。实验代码41deftest(self):42lst=[(0,0),(1,0),(2,2)]43form,ninlst:44r1=self.Ack(m,n)45r2=self.Ack_recursive(m,n)46assertr1==r2,f'm{m},n{n},r1{r1},r2{r2}'47print(f'm{m},n{n},r1{r1},r2{r2}')47习题解答一、选择题1~5CCCBA【解析】1.栈满条件是top<MaxStackSize-1。参考主教材P92算法3-3进栈函数。2.栈具有“后进先出”的特点。对于选项A，元素a、b、c、d、e依次进栈，然后依次出栈；对于选项B，元素a、b先依次进栈，然后依次出栈，然后元素c、d、e依次进栈，再依次出栈；对于选项D，元素a、b依次进栈，然后元素b出栈，元素c进栈，然后元素c出栈，元素d、e依次进栈，然后依次出栈，最后元素a出栈。3.严格按照栈“后进先出”的特点，ab进b出，cd进dc出，ef进fea出，g进g出。故S最大容量是3。4.若连续出队导致队空时，队尾指针与队头指针值相同，所以可能修改队尾指针。5.仅当n=0时，才不必继续调用，故从n到0，共n+1次。48二、填空题1．n-1。【解析】可能的取值是在1~n之间除3以外的任何数。2．提高存储空间的利用率。【解析】参考主教材P118。3．rear=(rear+1)%n、front=(front+1)%n。【解析】分别参考主教材P120算法3-36元素进队的函数和P121算法3-37元素出队的函数。4．都是操作受限的线性表。【解析】参考主教材P154。5．递归出口（终止条件），递归部分。【解析】参考主教材P141。49三、编程题1．在例3-1（主教材P95）中我们用了两个栈来实现判断一个单词是否是回文单词，其实我们也可以只用一个栈来判断，思路如下：通过将一个待判断的单词按照从前往后的顺序依次进栈后，再将栈内元素逐一出栈并与待判断单词的字母依次比较，若完全相等，则该待判断单词是回文单词；否则不是回文单词。请借助栈的基本操作按照以上要求用一个栈完成对一个单词是否为回文单词的判断（文件名：ex030603_01.py）。【解析】本题是一个栈的典型应用实例，请注意提供的参考代码栈的最大空间为100，如果单词超过这个长度，程序将提示“栈满”。86defTestPlalindrome(self):87str=input("请输入一个英文单词：")88i=089whilei<len(str):90if(str[i]>='a'andstr[i]<='z')or(str[i]>='A'andstr[i]<='Z'):91i=i+192else:93break94ifi==len(str):95self.Plalindrome(str)96else:97print("输入错误！")502．请使用顺序栈的基本操作实现例3-2（主教材P104）的括号匹配问题（文件名：ex030603_02.py）。【解析】本题是一个栈的典型应用实例，请注意提供的参考代码栈的最大空间为100，这意味着匹配的括号之间的字符不能超过这个值，否则程序将提示“栈满”；代码中只检查了左右大括号（{}）的匹配情况，对于中括号和小括号等参考实现之.111defPrintOut(self):112filePath=input("请输入文件example3-2.c的路径：");113self.BracketMatch(TBM.ReadFile(filePath))513．请尝试使用链式栈的基本操作找出例3-3（主教材P107）中的迷宫路径（文件名：ex030603_03.py）。【解析】本题是一个栈的典型应用实例，由于使用的是链栈，所以空间限制较为宽松。迷宫的求解思路可以参考主教材P107，算法的实现思路参考主教材P108~111。142defPrintOut(self):143mazeroute=[[1,1,1,1,1,1,0,1,1,1],144[1,0,0,0,0,1,0,1,1,1],145[1,0,1,1,0,1,0,0,0,1],146[1,0,1,1,0,1,1,1,0,1],147[1,0,1,1,0,0,0,0,0,1],148[1,0,1,1,0,1,1,1,1,1],149[1,0,1,1,0,0,0,0,0,1],150[1,0,1,1,1,1,1,1,1,1],151[1,0,0,0,0,0,0,0,0,0],152