山大数据结构5精讲课件.ppt

1、2/10/202311.The Abstract Data Type 2.D e r i v e d C l a s s e s a n d Inheritance3.Formula-Based Representation4.Linked Representation5.ApplicationsChapter5 堆栈(Stacks)2/10/202321.堆栈的实现2.堆栈的应用本章重点2/10/202331.定义 堆栈是一个线性表，其插入(也称为添加)和删除操作都在表的同一端进行。2.允许插入和删除的一端被称为栈顶(top)，另一端被称为栈底(bot tom)。3.堆栈是一个后进先出（la

2、st-in-first-out,LIFO）的数据结构。堆栈(Stacks)2/10/20234堆栈2/10/20235堆栈ADT2/10/202361.公式化描述(Formula-Based Representation)2.效率、改进3.链 接 描 述(L i n k e d)Representation4.效率比较堆栈2/10/20237n堆栈数据对象是更通用的线性表对象的限制版本。(插入和删除操作仅能在表的同一端进行)n例如，如果把表的左端定义为栈底，右端定义为栈顶，那么堆栈的添加操作等价于在表的右端进行插入操作，删除操作等价于在表的右端进行删除操作。继承2/10/20238templa

3、teclass 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

4、(),x);return*this;Stack&Delete(T&x)LinearList:Delete(Length(),x);return*this;公式化描述的堆栈类(派生)2/10/20239templateclass 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

5、(T&x);private:int top;/栈顶int MaxTop;/最大的栈顶值T*stack;/堆栈元素数组;自定义Stack2/10/202310templateStack:Stack(int MaxStackSize)MaxTop=MaxStackSize-1;stack=new TMaxStackSize;top=-1;Stack 类构造函数2/10/202311templateT Stack:Top()constif(IsEmpty()throw OutOfBounds();else return stacktop;复杂性?返回栈顶元素2/10/202312templateSt

6、ack&Stack:Add(const T&x)if(IsFull()throw NoMem();stack+top=x;return*this;复杂性?添加元素x2/10/202313templateStack&Stack:Delete(T&x)if(IsEmpty()throw OutOfBounds();x=stacktop-;return*this;复杂性?删除栈顶元素，并将其送入x2/10/202314哪一端对应栈顶?链表描述2/10/202315templateclass LinkedStack:private Chain public:bool IsEmpty()constret

7、urn 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派生的链表形式的堆栈2/10/202316templatebool LinkedStack:IsFu11()const/堆栈是否满?try ChainNode*p=new

8、 ChainNode;delete p;return false;catch(NoMem)return true;从Chain派生的链表形式的堆栈2/10/202317template class Nodefriend LinkedStack;private:T data;Node*link;自定义链表形式的堆栈2/10/202318templateclass LinkedStack public:LinkedStack()top=0;LinkedStack();bool IsEmpty()const return top=0;bool IsFull()const;T Top()const;L

9、inkedStack&Add(const T&x);LinkedStack&Delete(T&x);private:Node*top;/指向栈顶节点:自定义链表形式的堆栈2/10/202319templateLinkedStack:LinkedStack()Node*next;while(top)next=top-link;delete top;top=next;析构函数2/10/202320templatebool LinkedStack:IsFu11()consttry Node*p=new Node;delete p;return false;catch(NoMem)return tru

10、e;堆栈是否满?2/10/202321templateT LinkedStack:Top()constif(IsEmpty()throw OutOfBounds();return top-data;返回栈顶元素2/10/202322templateLinkedStack&LinkedStack:Add(const T&x)Node*p=new Node;p-data=x;p-link=top;top=p;return*this;添加元素x2/10/202323templateLinkedStack&LinkedStack:Delete(T&x)if(IsEmpty()throw OutOfBo

11、unds();x=top-data;Node*p=top;top=top-link;delete p;return*this;删除栈顶元素，并将其送入x2/10/2023241.链式栈无栈满问题，空间可扩充2.插入与删除仅在栈顶处执行3.链式栈的栈顶在链头4.适合于多栈操作比较2/10/2023251.括号匹配(Parenthesis Matching)2.汉诺塔(Towers of Hanoi)3.火车车厢重排(Rearranging Railroad Cars)4.开关盒布线(Switch Box Routing)5.离线等价类(Offline Equivalence Problem)6.

12、迷宫老鼠(Rat in a Maze)应用2/10/202326n目标:输入一个字符串，输出相互匹配的括号以及未能匹配的括号。n例：字符串(a*(b+c)+d)n例：字符串(a+b)(括号匹配2/10/202327n如果从左至右扫描一个字符串，那么每个右括号将与最近遇到的那个未匹配的左括号相匹配。n如何实现？观察2/10/202328n可以在从左至右的扫描过程中把所遇到的左括号存放到堆栈内。每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该左括号。方法2/10/202329n已知n个碟子和3座塔。初始时所有的碟子按从大到小次序从塔1的底部堆放至顶部，需要把碟子都移动

13、到塔2，每次移动一个碟子，而且任何时候都不能把大碟子放到小碟子的上面。汉诺塔问题2/10/202330n为了把最大的碟子移动到塔2，必须把其余n-1个碟子移动到塔3，然后把最大的碟子移动到塔2。n接下来是把塔3上的n-1个碟子移动到塔2，为此可以利用塔2和塔1。可以完全忽视塔2上已经有一个碟子的事实，因为这个碟子比塔3上将要移过来的任一个碟子都大，因此，可以在它上面堆放任何碟子。汉诺塔问题-递归方法2/10/202331void TowersOfHanoi(int n,int x,int y,int z)/把n 个碟子从塔x 移动到塔y，可借助于塔zif(n 0)TowersOfHanoi(n

14、-1,x,z,y);coutMove top disk from tower x to top of tower yendl;TowersOfHanoi(n-l,z,y,x);求解汉诺塔问题的递归程序2/10/202332n希望给出每次移动之后三座塔的状态（即塔上的碟子及其次序）进一步要求2/10/202333class Hanoifriend void TowersOfHanoi(i n t);public:void TowersOfHanoi(int n,int x,int y,int z);private:Stack*S4;使用堆栈求解汉诺塔问题2/10/202334void Hanoi

15、: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);使用堆栈求解汉诺塔问题2/10/202335void TowersOfHanoi(int n)/Hanoi:towersOfHanoi的预处理程序Hanoi X；X.S1=new Stack(n);X.S2=new Stack(

16、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);使用堆栈求解汉诺塔问题2/10/202336n在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨(位于入轨和出轨之间)。火车车厢重排问题2/10/202337n从前至后依次检查入轨上的所有车厢。n如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它

17、放到出轨上。n缓冲铁轨按照何种方式使用?火车车厢重排方案2/10/202338bool 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号车厢对应的缓冲铁轨火车车厢重排程序2/10/202339/车厢重排for(int i=1;i=n;i+)

18、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;火车车厢重排程序2/10/202340void Output(int&minH,int&minS,LinkedStack H,int k,int n)/把车厢从缓冲铁轨送至出轨处，同时修改minS和minHint c;/车厢索引/从堆栈mi

19、nS中删除编号最小的车厢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 函数2/10/202341bool Hold(int c,int&minH,int&minS,LinkedStack H,int k,int n)(/在一个缓冲铁轨中放入车厢c/如果没有可用的缓冲铁轨，则返回

20、false/如果空间不足，则引发异常NoMem，否则返回true/为车厢c寻找最优的缓冲铁轨/初始化int BestTrack=0,/目前最优的铁轨BestTop=n+1,/最优铁轨上的头辆车厢x;/车厢索引Hold函数2/10/202342/扫描缓冲铁轨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函数2/10/202343if(!BestTrac

21、k)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函数2/10/202344n给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚被称为网

22、组。n目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。开关盒布线问题2/10/202345n四个网组(1,4,)，(2,3)，(5,6)和(7,8)n可布线开关盒(routable switch box)开关盒布线示例2/10/202346n当两个针脚互连时，其电线把布线区分成两个分区。n如果有一个网组，其两个针脚分别位于这两个不同的分区，那么这个网组是不可以布线的，因而整个电路也是不可布线的。n如果没有这样的网组，则可以继续判断每个独立的分区是不是可布线的。为此，可以从一个分区中取出一个网组，利用该网组把这个分区又分成两个子分区，如果任一个网组的两个针脚都分布在同一个子分区之

23、中(即不会出现两个针脚分别位于两个子分区的情形)，那么这个分区就是可布线的。策略2/10/202347n可以按顺时针或反时针方向沿着开关盒的外围进行遍历。n例：按顺时针方向从针脚1开始遍历，将依次检查针脚1,2,.,8。n针脚1和4属于同一个网组，那么在针脚1至针脚4之间出现的所有针脚构成了第一个分区，而在针脚4至针脚1之间未出现的所有针脚构成了第二个分区。n把针脚1放入堆栈，然后继续处理，直至遇到针脚4。这个过程使我们仅在处理完一个分区之后才能进入下一个分区。方案2/10/202348n输入是元素数目n、关系数目r 以及r 对关系，问题的目标是把n个元素分配至相应的等价类。离线等价类问题2/

24、10/2023492/10/202350 2/10/202351 2/10/202352 0,1,2,3,4,5,6,7,8,9,10,11 0,4,1,2,3,5,6,7,8,9,10,11 0,4,1,3,2,5,6,7,8,9,10,110,4,1,3,2,5,6,10,7,8,9,11 0,4,1,3,2,5,6,10,7,8,9,11 0,4,7,1,3,2,5,6,10,8,9,11 0,4,7,1,3,2,5,6,8,9,10,11 0,4,7,1,3,5,2,6,8,9,10,110,4,7,1,3,5,2,11,6,8,9,100,2,4,7,11,1,3,5,6,8,9,1

25、02/10/2023532/10/2023542/10/202355 链链序序号号等等价价 对对OUT初初态态输输出出OUT终终态态 栈栈 0False 0 True 0 11 False 11 True 11 0 4 False 4 True 11,4 4 7 False 7 True 11,7 4 0 True True 11,7 链链序序号号等等价价 对对OUT初初态态输输出出OUT终终态态栈栈 7 4 True True 11 11 0 True True 11 0 True True 11 2 False 2 True 2 2 11 True True2/10/202356void

26、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);离线等价类程序(一)2/10/202357/创建一个指向n个链表的数组Chain*chain;try chain=new Chain n+1;catch(NoMem)cerr Out of memory endl;exit(1);/输

27、入r个关系，并存入链表for(int i=1;i=r;i+)cout Enter next relation/pair a b;chaina.Insert(0,b);chainb.Insert(0,a);离线等价类程序(一)2/10/202358/对欲输出的等价类进行初始化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)/开始一个新的等价

28、类cout Next class is:i ;outi=true;stack.Add(i);离线等价类程序(二)2/10/202359/从堆栈中取其余的元素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;

29、离线等价类程序(二)2/10/202360n迷宫老鼠(rat in a maze)问题要求寻找一条从入口到出口的路径。n路径是由一组位置构成的，每个位置上都没有障碍，且每个位置(第一个除外)都是前一个位置的东、南、西或北的邻居。迷宫老鼠问题2/10/202361n假定用nm的矩阵来描述迷宫，位置(1,1)表示入口，(n,m)表示出口，n和m分别代表迷宫的行数和列数。n迷宫中的每个位置都可用其行号和列号来指定。在矩阵中，当且仅当在位置(i,j)处有一个障碍时其值为1，否则其值为0。迷宫的描述2/10/202362迷宫的描述2/10/202363n首先把迷宫的入口作为当前位置。n如果当前位置是迷宫

30、出口，那么已经找到了一条路径，搜索工作结束。n如果当前位置不是迷宫出口，则在当前位置上放置障碍物，以便阻止搜索过程又绕回到这个位置。n然后检查相邻的位置中是否有空闲的(即没有障碍物)，如果有，就移动到这个新的相邻位置上，然后从这个位置开始搜索通往出口的路径。如果不成功，选择另一个相邻的空闲位置，并从它开始搜索通往出口的路径。n如果所有相邻的空闲位置都已经被探索过，并且未能找到路径，则表明在迷宫中不存在从入口到出口的路径。方案2/10/202364n对于迷宫内部的位置(非边界位置)，有四种可能的移动方向：右、下、左和上。n对于迷宫的边界位置，只有两种或三种可能的移动。n为了避免在处理内部位置和边

31、界位置时存在差别，可以在迷宫的周围增加一圈障碍物。简化算法2/10/202365迷宫的描述2/10/202366n可以用行号和列号来指定每个迷宫位置，行号和列号被分别称之为迷宫位置的行坐标和列坐标。n可以定义一个相应的类Position来表示迷宫位置，它有两个私有成员row和col。n为保存从入口到当前位置的路径，可以采用以下基于公式化描述的堆栈：Stack path(MaxPathLength);n其中MaxPathLength是指最大可能的路径长度（从入口到迷宫中任一位置）。位置表示2/10/202367n按一种固定的方式来选择可行的位置，将可以使问题得到简化。n例如，可以首先尝试向右移动

32、，然后是向下，向左，最后是向上。移动到相邻位置的方法2/10/202368移动到相邻位置的方法2/10/202369假定maze、m(迷宫的大小)和path都是按如下方式定义的全局变量：int*maze,m;Stack*path;迷宫算法实现2/10/202370bool 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;/向右off

33、setl.row=1;offsetl.col=0;/向下offset2.row=0;offset2.col=-1;/向左offset3.row=-1;offset3.col=0;/向上搜索迷宫路径的代码2/10/202371/在迷宫周围增加一圈障碍物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;搜索迷宫路径的代码2/10/202372/寻找一条路径w

34、hile(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+;/下一个选择搜索迷宫路径的代码2/10/202373/找到一个相邻位置了吗?if(option Add(here);here.row=r;here.col=c;/设置障碍物以阻止再次访问mazerc=1;option=0;搜索迷宫路径的代码2/10/202374else/没有可

35、用的相邻位置，回溯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;/到达迷宫出口搜索迷宫路径的代码2/10/202375n迷宫问题n输入：录入或从文件读取n*n迷宫方阵n输出：自(1,1)至(n,n)的路径。n输出：自(1,1)至(n,n)的最短路径。课程设计2/10/2023761.课程设计题目2.姓名、学号、班级3.日期4.课程设计内容描述:需求(输入、输出、功能、测试数据)5.实现思想、算法描述6.使用说明7.调试说明8.实现代码(带注释)课程设计报告要求2/10/2023771.堆栈的实现方式2.括号匹配3.汉诺塔4.火车车厢重排5.开关盒布线6.离线等价类7.迷宫老鼠第五章 总结