山大数据结构_5精讲课件

1.The Abstract Data Type 2.Derived Classes and Inheritance3.Formula-Based Representation4.Linked Representation5.ApplicationsChapter5 堆栈(Stacks)6/17/20241The Abstract Data Type Chapter1.堆栈的实现2.堆栈的应用本章重点6/17/20242堆栈的实现本章重点7/31/202321.定义 堆栈是一个线性表，其插入(也称为添加)和删除操作都在表的同一端进行。2.允许插入和删除的一端被称为栈顶(top)，另一端被称为栈底(bot tom)。3.堆栈是一个后进先出（last-in-first-out,LIFO）的数据结构。堆栈(Stacks)6/17/20243定义 堆栈是一个线性表，其插入(也称为添加)和删除操作都在表堆栈6/17/20244堆栈7/31/20234堆栈ADT6/17/20245堆栈ADT7/31/202351.公 式 化 描 述(Formula-Based Representation)2.效率、改进3.链接描述(Linked)Representation4.效率比较堆栈6/17/20246公式化描述(Formula-Based Representa堆栈数据对象是更通用的线性表对象的限制版本。(插入和删除操作仅能在表的同一端进行)例如，如果把表的左端定义为栈底，右端定义为栈顶，那么堆栈的添加操作等价于在表的右端进行插入操作，删除操作等价于在表的右端进行删除操作。继承6/17/20247堆栈数据对象是更通用的线性表对象的限制版本。(插入和删除操作templateclass Stack:private LinearList /LIFO 对象public:Stack(int MaxStackSize=10):LinearList(MaxStackSize)bool IsEmpty()constreturn LinearList:IsEmpty();bool IsFull()constreturn(Length()=GetMaxSize();T Top()constif(IsEmpty()throw OutOfBounds();T x;Find(Length(),x);return x;Stack&Add(const T&x)Insert(Length(),x);return*this;Stack&Delete(T&x)LinearList:Delete(Length(),x);return*this;公式化描述的堆栈类(派生)6/17/20248template公式化描述的堆栈类(派生)templateclass Stack /LIFO 对象public:Stack(int MaxStackSize=10);Stack()delete stack;bool IsEmpty()const return top=-1;bool IsFull()const return top=MaxTo p;T Top()const;Stack&Add(const T&x);Stack&Delete(T&x);private:int top;/栈顶int MaxTop;/最大的栈顶值T*stack;/堆栈元素数组;自定义Stack6/17/20249template自定义Stack7/31/templateStack:Stack(int MaxStackSize)MaxTop=MaxStackSize-1;stack=new TMaxStackSize;top=-1;Stack 类构造函数6/17/202410templateStack 类构造函数7/templateT Stack:Top()constif(IsEmpty()throw OutOfBounds();else return stacktop;复杂性?返回栈顶元素6/17/202411template返回栈顶元素7/31/20templateStack&Stack:Add(const T&x)if(IsFull()throw NoMem();stack+top=x;return*this;复杂性?添加元素x6/17/202412template添加元素x7/31/202templateStack&Stack:Delete(T&x)if(IsEmpty()throw OutOfBounds();x=stacktop-;return*this;复杂性?删除栈顶元素，并将其送入x6/17/202413template删除栈顶元素，并将其送入x哪一端对应栈顶?链表描述6/17/202414哪一端对应栈顶?链表描述7/31/202314templateclass LinkedStack:private Chain public:bool IsEmpty()constreturn Chain:IsEmpty();bool IsFull()const;T Top()constif(IsEmpty()throw OutOfBounds();T x;Find(1,x);return x;LinkedStack&Add(const T&x)Insert(0,x);return*this;LinkedStack&Delete(T&x)Chain:Delete(1,x);return*this;从Chain派生的链表形式的堆栈6/17/202415template从Chain派生的链表形式templatebool LinkedStack:IsFu11()const/堆栈是否满?try ChainNode*p=new ChainNode;delete p;return false;catch(NoMem)return true;从Chain派生的链表形式的堆栈6/17/202416template从Chain派生的链表形式template class Nodefriend LinkedStack;private:T data;Node*link;自定义链表形式的堆栈6/17/202417template 自定义链表形式的堆栈7/templateclass LinkedStack public:LinkedStack()top=0;LinkedStack();bool IsEmpty()const return top=0;bool IsFull()const;T Top()const;LinkedStack&Add(const T&x);LinkedStack&Delete(T&x);private:Node*top;/指向栈顶节点:自定义链表形式的堆栈6/17/202418template自定义链表形式的堆栈7/3templateLinkedStack:LinkedStack()Node*next;while(top)next=top-link;delete top;top=next;析构函数6/17/202419template析构函数7/31/2023templatebool LinkedStack:IsFu11()consttry Node*p=new Node;delete p;return false;catch(NoMem)return true;堆栈是否满?6/17/202420template堆栈是否满?7/31/20templateT LinkedStack:Top()constif(IsEmpty()throw OutOfBounds();return top-data;返回栈顶元素6/17/202421template返回栈顶元素7/31/20templateLinkedStack&LinkedStack:Add(const T&x)Node*p=new Node;p-data=x;p-link=top;top=p;return*this;添加元素x6/17/202422template添加元素x7/31/202templateLinkedStack&LinkedStack:Delete(T&x)if(IsEmpty()throw OutOfBounds();x=top-data;Node*p=top;top=top-link;delete p;return*this;删除栈顶元素，并将其送入x6/17/202423template删除栈顶元素，并将其送入x1.链式栈无栈满问题，空间可扩充2.插入与删除仅在栈顶处执行3.链式栈的栈顶在链头4.适合于多栈操作比较6/17/202424链式栈无栈满问题，空间可扩充比较7/31/2023241.括号匹配(Parenthesis Matching)2.汉诺塔(Towers of Hanoi)3.火车车厢重排(Rearranging Railroad Cars)4.开关盒布线(Switch Box Routing)5.离线等价类(Offline Equivalence Problem)6.迷宫老鼠(Rat in a Maze)应用6/17/202425括号匹配(Parenthesis Matching)应用7/目标:输入一个字符串，输出相互匹配的括号以及未能匹配的括号。例：字符串(a*(b+c)+d)例：字符串(a+b)(括号匹配6/17/202426目标:输入一个字符串，输出相互匹配的括号以及未能匹配的括号。如果从左至右扫描一个字符串，那么每个右括号将与最近遇到的那个未匹配的左括号相匹配。如何实现？观察6/17/202427如果从左至右扫描一个字符串，那么每个右括号将与最近遇到的那个可以在从左至右的扫描过程中把所遇到的左括号存放到堆栈内。每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该左括号。方法6/17/202428可以在从左至右的扫描过程中把所遇到的左括号存放到堆栈内。每当已知n个碟子和3座塔。初始时所有的碟子按从大到小次序从塔1的底部堆放至顶部，需要把碟子都移动到塔2，每次移动一个碟子，而且任何时候都不能把大碟子放到小碟子的上面。汉诺塔问题6/17/202429已知n个碟子和3座塔。初始时所有的碟子按从大到小次序从塔1的为了把最大的碟子移动到塔2，必须把其余n-1个碟子移动到塔3，然后把最大的碟子移动到塔2。接下来是把塔3上的n-1个碟子移动到塔2，为此可以利用塔2和塔1。可以完全忽视塔2上已经有一个碟子的事实，因为这个碟子比塔3上将要移过来的任一个碟子都大，因此，可以在它上面堆放任何碟子。汉诺塔问题-递归方法6/17/202430为了把最大的碟子移动到塔2，必须把其余n-1个碟子移动到塔void TowersOfHanoi(int n,int x,int y,int z)/把n 个碟子从塔x 移动到塔y，可借助于塔zif(n 0)TowersOfHanoi(n-1,x,z,y);coutMove top disk from tower x to top of tower yendl;TowersOfHanoi(n-l,z,y,x);求解汉诺塔问题的递归程序6/17/202431void TowersOfHanoi(int n,int 希望给出每次移动之后三座塔的状态（即塔上的碟子及其次序）进一步要求6/17/202432希望给出每次移动之后三座塔的状态（即塔上的碟子及其次序）进一class Hanoifriend void TowersOfHanoi(i n t);public:void TowersOfHanoi(int n,int x,int y,int z);private:Stack*S4;使用堆栈求解汉诺塔问题6/17/202433class Hanoi使用堆栈求解汉诺塔问题7/31/20void Hanoi:TowersOfHanoi(int n,int x,int y,int z)/把n 个碟子从塔x 移动到塔y，可借助于塔zint d;/碟子编号if(n 0)TowersOfHanoi(n-l,x,z,y);Sx-Delete(d);/从x中移走一个碟子Sy-Add(d);/把这个碟子放到y 上ShowState();TowersOfHanoi(n-l,z,y,x);使用堆栈求解汉诺塔问题6/17/202434void Hanoi:TowersOfHanoi(int void TowersOfHanoi(int n)/Hanoi:towersOfHanoi的预处理程序Hanoi X；X.S1=new Stack(n);X.S2=new Stack(n);X.S3=new Stack(n);for(int d=n;d 0;d-)/初始化X.S1-Add(d);/把碟子d 放到塔1上/把塔1上的n个碟子移动到塔2上，借助于塔3 的帮助X.TowersOfHanoi(n,1,2,3);使用堆栈求解汉诺塔问题6/17/202435void TowersOfHanoi(int n)使用堆栈求在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨(位于入轨和出轨之间)。火车车厢重排问题6/17/202436在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个从前至后依次检查入轨上的所有车厢。如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。缓冲铁轨按照何种方式使用?火车车厢重排方案6/17/202437从前至后依次检查入轨上的所有车厢。火车车厢重排方案7/31/bool Railroad(int p,int n,int k)/k 个缓冲铁轨，车厢初始排序为p 1:n/如果重排成功，返回true，否则返回false/如果内存不足，则引发异常NoMem。/创建与缓冲铁轨对应的堆栈LinkedStack*H;H=new LinkedStack k+1;int NowOut=1;/下一次要输出的车厢int minH=n+l;/缓冲铁轨中编号最小的车厢int minS;/minH号车厢对应的缓冲铁轨火车车厢重排程序6/17/202438bool Railroad(int p,int n,/车厢重排for(int i=1;i=n;i+)if(pi=NowOut)/直接输出tcout“将 车 厢”pi“从 入 轨 移 至 出 轨endl;NowOut+;/从缓冲铁轨中输出while(minH=NowOut)Output(minH,minS,H,k,n);NowOut+;else/将pi 送入某个缓冲铁轨if(!Hold(pi,minH,minS,H,k,n)return false;return true;火车车厢重排程序6/17/202439/车厢重排火车车厢重排程序7/31/202339void Output(int&minH,int&minS,LinkedStack H,int k,int n)/把车厢从缓冲铁轨送至出轨处，同时修改minS和minHint c;/车厢索引/从堆栈minS中删除编号最小的车厢minHHminS.Delete(c);cout Move car minH from holding track minS to output endl;/通过检查所有的栈顶，搜索新的minH和minSminH=n+2;for(int i=1;i=k;i+)if(!Hi.IsEmpty()&(c=Hi.Top()minH)minH=c;minS=i;Output 函数6/17/202440void Output(int&minH,int&mibool Hold(int c,int&minH,int&minS,LinkedStack H,int k,int n)(/在一个缓冲铁轨中放入车厢c/如果没有可用的缓冲铁轨，则返回false/如果空间不足，则引发异常NoMem，否则返回true/为车厢c寻找最优的缓冲铁轨/初始化int BestTrack=0,/目前最优的铁轨BestTop=n+1,/最优铁轨上的头辆车厢x;/车厢索引Hold函数6/17/202441bool Hold(int c,int&minH,in/扫描缓冲铁轨for(int i=1;i=k;i+)if(!Hi.IsEmpty()/铁轨i 不空x=Hi.Top();if(c x&x BestTop)/铁轨i 顶部的车厢编号最小BestTop=x;BestTrack=i;else/铁轨i 为空if(!BestTrack)BestTrack=i;Hold函数6/17/202442/扫描缓冲铁轨Hold函数7/31/202342if(!BestTrack)return false;/没有可用的铁轨/把车厢c 送入缓冲铁轨HBestTrack.Add(c);cout Move car c from input to holding track BestTrack endl;/必要时修改minH 和minSif(c minH)minH=c;minS=BestTrack;return true;复杂性？Hold函数6/17/202443if(!BestTrack)return false;给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚被称为网组。目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。开关盒布线问题6/17/202444给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设四个网组(1,4,)，(2,3)，(5,6)和(7,8)可布线开关盒(routable switch box)开关盒布线示例6/17/202445四个网组(1,4,)，(2,3)，(5,6)和(7,8)开关当两个针脚互连时，其电线把布线区分成两个分区。如果有一个网组，其两个针脚分别位于这两个不同的分区，那么这个网组是不可以布线的，因而整个电路也是不可布线的。如果没有这样的网组，则可以继续判断每个独立的分区是不是可布线的。为此，可以从一个分区中取出一个网组，利用该网组把这个分区又分成两个子分区，如果任一个网组的两个针脚都分布在同一个子分区之中(即不会出现两个针脚分别位于两个子分区的情形)，那么这个分区就是可布线的。策略6/17/202446当两个针脚互连时，其电线把布线区分成两个分区。策略7/31/可以按顺时针或反时针方向沿着开关盒的外围进行遍历。例：按顺时针方向从针脚1开始遍历，将依次检查针脚1,2,.,8。针脚1和4属于同一个网组，那么在针脚1至针脚4之间出现的所有针脚构成了第一个分区，而在针脚4至针脚1之间未出现的所有针脚构成了第二个分区。把针脚1放入堆栈，然后继续处理，直至遇到针脚4。这个过程使我们仅在处理完一个分区之后才能进入下一个分区。方案6/17/202447可以按顺时针或反时针方向沿着开关盒的外围进行遍历。方案7/3输入是元素数目n、关系数目r 以及r 对关系，问题的目标是把n个元素分配至相应的等价类。离线等价类问题6/17/202448输入是元素数目n、关系数目r 以及r 对关系，问题的目标是把等价关系与等价类等价关系与等价类(Equivalence Class)在求解实际应用问题时常会遇到等价类问题。在求解实际应用问题时常会遇到等价类问题。从数学上看，等价类是一个对象从数学上看，等价类是一个对象(或成员或成员)的集的集合，在此集合中所有对象应满足等价关系。合，在此集合中所有对象应满足等价关系。若用符号若用符号“”表示集合上的等价关系，那么表示集合上的等价关系，那么对于该集合中的任意对象对于该集合中的任意对象x,y,z，下列性质成，下列性质成立：立：自反性：自反性：x x(即等于自身即等于自身)。对称性：若对称性：若 x y,则则 y x。传递性：若传递性：若 x y且且 y z,则则 x z。因此，等价关系是集合上的一个自反、对称、因此，等价关系是集合上的一个自反、对称、传递的关系。传递的关系。6/17/202449等价关系与等价类(Equivalence Class)在求解 “相相等等”(=)就就是是一一种种等等价价关关系系，它它满满足足上述的三个特性。上述的三个特性。一一个个集集合合 S 中中的的所所有有对对象象可可以以通通过过等等价价关关系系划划分分为为若若干干个个互互不不相相交交的的子子集集 S1,S2,S3,，它它们们的的并并就就是是 S。这这些些子子集集即即为等价类。为等价类。确定等价类的方法确定等价类的方法分两步走。分两步走。第一步，读入并存储所有的等价对第一步，读入并存储所有的等价对(i,j)；第二步，标记和输出所有的等价类。第二步，标记和输出所有的等价类。6/17/202450 “相等”(=)就是一种等价关系，它满足上述的三个特给定集合给定集合 S=0,1,2,3,4,5,6,7,8,9,10,11,及如下等价对及如下等价对:0 4,3 1,6 10,8 9,7 4,6 8,3 5,2 11,11 06/17/202451给定集合 S=0,1,2,3,4,5,6初始初始 0,1,2,3,4,5,6,7,8,9,10,110 4 0,4,1,2,3,5,6,7,8,9,10,113 1 0,4,1,3,2,5,6,7,8,9,10,116 100,4,1,3,2,5,6,10,7,8,9,11 8 9 0,4,1,3,2,5,6,10,7,8,9,117 4 0,4,7,1,3,2,5,6,10,8,9,116 8 0,4,7,1,3,2,5,6,8,9,10,113 5 0,4,7,1,3,5,2,6,8,9,10,112 110,4,7,1,3,5,2,11,6,8,9,1011 00,2,4,7,11,1,3,5,6,8,9,106/17/202452初始 0,1,2,3,4,5,6确定等价类的链表方法确定等价类的链表方法 设等价对个数为设等价对个数为m，对象个数为对象个数为n。一种可选一种可选的存储表示为的存储表示为单链表单链表。可为集合的每一对象建立一个带表头结点的可为集合的每一对象建立一个带表头结点的单链表，并建立一个一维的指针数组单链表，并建立一个一维的指针数组 seqn 作作为各单链表的表头结点向量。为各单链表的表头结点向量。seqi是第是第 i 个单个单链表的表头结点，第链表的表头结点，第 i 个单链表中所有结点的个单链表中所有结点的data域存放在等价对中与域存放在等价对中与 i 等价的对象编号。等价的对象编号。当输入一个等价对当输入一个等价对(i,j)后，就将集合元素后，就将集合元素 i 链入第链入第 j 个单链表，且将集合元素个单链表，且将集合元素 j 链入第链入第 i 个个单链表。单链表。在输出时，设置一个布尔数组在输出时，设置一个布尔数组 outn，用用 outi 标记第标记第 i 个单链表是否已经输出。个单链表是否已经输出。6/17/202453确定等价类的链表方法 设等价对个数为m，对象个数为n。算法的输出从编号算法的输出从编号 i=0 的对象开始，对所有的对的对象开始，对所有的对象进行检测。象进行检测。在在 i=0 时，循第时，循第0个单链表先找出形式为个单链表先找出形式为(0,j)的的等价对，把等价对，把 0 和和 j 作为同一个等价类输出。再根作为同一个等价类输出。再根据等价关系的传递性，找所有形式为据等价关系的传递性，找所有形式为(j,k)的等的等价对，把价对，把 k 也纳入包含也纳入包含 0 的等价类中输出。如的等价类中输出。如此继续，直到包含此继续，直到包含 0 的等价类完全输出为止。的等价类完全输出为止。接下来再找一个未被标记的编号，如接下来再找一个未被标记的编号，如 i=1，该对，该对象将属于一个新的等价类，我们再用上述方法象将属于一个新的等价类，我们再用上述方法划分、标记和输出这个等价类。划分、标记和输出这个等价类。在算法中使用了一个栈。每次输出一个对象编号在算法中使用了一个栈。每次输出一个对象编号时，都要把这个编号进栈，记下以后还要检测时，都要把这个编号进栈，记下以后还要检测输出的等价对象的单链表。输出的等价对象的单链表。6/17/202454算法的输出从编号 i=0 的对象开始，对所有的对象进行检输入所有等价对后的输入所有等价对后的输入所有等价对后的输入所有等价对后的seqseq数组及各单链表的内容数组及各单链表的内容数组及各单链表的内容数组及各单链表的内容6/17/202455输入所有等价对后的seq数组及各单链表的内容7/31/202void main(void)/离线等价类问题int n,r;/输入n 和rcout Enter number of elements n;if(n 2)cerr Too few elements endl;exit(l);cout Enter number of relations r;if(r 1)cerr Too few relations endl;exit(l);离线等价类程序(一)6/17/202456void main(void)离线等价类程序(一)7/31/创建一个指向n个链表的数组Chain*chain;try chain=new Chain n+1;catch(NoMem)cerr Out of memory endl;exit(1);/输入r个关系，并存入链表for(int i=1;i=r;i+)cout Enter next relation/pair a b;chaina.Insert(0,b);chainb.Insert(0,a);离线等价类程序(一)6/17/202457/创建一个指向n个链表的数组离线等价类程序(一)7/31/对欲输出的等价类进行初始化LinkedStack stack;bool*out;try out=new bool n+1;catch(NoMem)cerrOut of memoryendl;exit(l);for(int i=1;i=n;i+)outi=false;/输出等价类for(int i=1;i=n;i+)if(!outi)/开始一个新的等价类cout Next class is:i ;outi=true;stack.Add(i);离线等价类程序(二)6/17/202458/对欲输出的等价类进行初始化离线等价类程序(二)7/31/从堆栈中取其余的元素while(!stack.IsEmpty()int*q,j;stack.Delete(j);/链表chainj中的元素在同一个等价类中，使用遍历器取这些元素ChainIterator c;q=c.Initialize(chainj);while(q)if(!out*q)cout q ;out*q=true;stack.Add(*q);q=c.Next();cout endl;cout endl End of class list endl;离线等价类程序(二)6/17/202459/从堆栈中取其余的元素离线等价类程序(二)7/31/202迷宫老鼠(rat in a maze)问题要求寻找一条从入口到出口的路径。路径是由一组位置构成的，每个位置上都没有障碍，且每个位置(第一个除外)都是前一个位置的东、南、西或北的邻居。迷宫老鼠问题6/17/202460迷宫老鼠(rat in a maze)问题要求寻找一条从入口假定用nm的矩阵来描述迷宫，位置(1,1)表示入口，(n,m)表示出口，n和m分别代表迷宫的行数和列数。迷宫中的每个位置都可用其行号和列号来指定。在矩阵中，当且仅当在位置(i,j)处有一个障碍时其值为1，否则其值为0。迷宫的描述6/17/202461假定用nm的矩阵来描述迷宫，位置(1,1)表示入口迷宫的描述6/17/202462迷宫的描述7/31/202362首先把迷宫的入口作为当前位置。如果当前位置是迷宫出口，那么已经找到了一条路径，搜索工作结束。如果当前位置不是迷宫出口，则在当前位置上放置障碍物，以便阻止搜索过程又绕回到这个位置。然后检查相邻的位置中是否有空闲的(即没有障碍物)，如果有，就移动到这个新的相邻位置上，然后从这个位置开始搜索通往出口的路径。如果不成功，选择另一个相邻的空闲位置，并从它开始搜索通往出口的路径。如果所有相邻的空闲位置都已经被探索过，并且未能找到路径，则表明在迷宫中不存在从入口到出口的路径。方案6/17/202463首先把迷宫的入口作为当前位置。方案7/31/202363对于迷宫内部的位置(非边界位置)，有四种可能的移动方向：右、下、左和上。对于迷宫的边界位置，只有两种或三种可能的移动。为了避免在处理内部位置和边界位置时存在差别，可以在迷宫的周围增加一圈障碍物。简化算法6/17/202464对于迷宫内部的位置(非边界位置)，有四种可能的移动方向：右、迷宫的描述6/17/202465迷宫的描述7/31/202365可以用行号和列号来指定每个迷宫位置，行号和列号被分别称之为迷宫位置的行坐标和列坐标。可以定义一个相应的类Position来表示迷宫位置，它有两个私有成员row和col。为保存从入口到当前位置的路径，可以采用以下基于公式化描述的堆栈：Stack path(MaxPathLength);其中MaxPathLength是指最大可能的路径长度（从入口到迷宫中任一位置）。位置表示6/17/202466可以用行号和列号来指定每个迷宫位置，行号和列号被分别称之为迷按一种固定的方式来选择可行的位置，将可以使问题得到简化。例如，可以首先尝试向右移动，然后是向下，向左，最后是向上。移动到相邻位置的方法6/17/202467按一种固定的方式来选择可行的位置，将可以使问题得到简化。移动移动到相邻位置的方法6/17/202468移动到相邻位置的方法7/31/202368假定maze、m(迷宫的大小)和path都是按如下方式定义的全局变量：int*maze,m;Stack*path;迷宫算法实现6/17/202469假定maze、m(迷宫的大小)和path都是按如下方式定义bool FindPath()/寻找从位置(1,1)到出口(m,m)的路径/如果成功则返回true，否则返回f a l s e/如果内存不足则引发异常N o M e mpath=new Stack(m*m-1);/对偏移量进行初始化Position offset 4;offset0.row=0;offset0.col=1;/向右offsetl.row=1;offsetl.col=0;/向下offset2.row=0;offset2.col=-1;/向左offset3.row=-1;offset3.col=0;/向上搜索迷宫路径的代码6/17/202470bool FindPath()搜索迷宫路径的代码7/31/2/在迷宫周围增加一圈障碍物for(int i=0;i=m+l;i+)maze0i=mazem+li=1;/底和顶mazei0=mazeim+l=1;/左和右Position here;here.row=1;here.col=1;mazeii=1;/阻止返回入口int option=0;int LastOption=3;搜索迷宫路径的代码6/17/202471/在迷宫周围增加一圈障碍物搜索迷宫路径的代码7/31/20/寻找一条路径while(here.row!=m|here.col!=m)/不是出口/寻找并移动到一个相邻位置int r,c;while(option=LastOption)r=here.row+offsetoption.row;c=here.col+offsetoption.col;if(mazerc=0)break;option+;/下一个选择搜索迷宫路径的代码6/17/202472/寻找一条路径搜索迷宫路径的代码7/31/202372/找到一个相邻位置了吗?if(option Add(here);here.row=r;here.col=c;/设置障碍物以阻止再次访问mazerc=1;option=0;搜索迷宫路径的代码6/17/202473/找到一个相邻位置了吗?搜索迷宫路径的代码7/31/20else/没有可用的相邻位置，回溯if(path-IsEmpty()return false;Position next;path-Delete(next);if(next.row=here.row)/here为next邻居option=2+next.col-here.col;else option=3+next.row-here.row;here=next;return true;/到达迷宫出口搜索迷宫路径的代码6/17/202474else/没有可用的相邻位置，回溯搜索迷宫路径的代码7迷宫问题输入：录入或从文件读取n*n迷宫方阵输出：自(1,1)至(n,n)的路径。输出：自(1,1)至(n,n)的最短路径。课程设计6/17/202475迷宫问题课程设计7/31/2023751.课程设计题目2.姓名、学号、班级3.日期4.课程设计内容描述:需求(输入、输出、功能、测试数据)5.实现思想、算法描述6.使用说明7.调试说明8.实现代码(带注释)课程设计报告要求6/17/202476课程设计题目课程设计报告要求7/31/2023761.堆栈的实现方式2.括号匹配3.汉诺塔4.火车车厢重排5.开关盒布线6.离线等价类7.迷宫老鼠第五章 总结6/17/202477堆栈的实现方式第五章 总结7/31/202377