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

《山大数据结构_5精讲课件.ppt》由会员分享，可在线阅读，更多相关《山大数据结构_5精讲课件.ppt（77页珍藏版）》请在三一办公上搜索。

1、3/13/2023,1,The Abstract Data Type Derived Classes and InheritanceFormula-Based RepresentationLinked RepresentationApplications,Chapter5 堆栈(Stacks),3/13/2023,2,堆栈的实现堆栈的应用,本章重点,3/13/2023,3,定义 堆栈是一个线性表，其插入(也称为添加)和删除操作都在表的同一端进行。允许插入和删除的一端被称为栈顶(top)，另一端被称为栈底(bot tom)。堆栈是一个后进先出（last-in-first-out,LIFO）的数据

2、结构。,堆栈(Stacks),3/13/2023,4,堆栈,3/13/2023,5,堆栈ADT,3/13/2023,6,公式化描述(Formula-Based Representation)效率、改进链接描述(Linked)Representation效率比较,堆栈,3/13/2023,7,堆栈数据对象是更通用的线性表对象的限制版本。(插入和删除操作仅能在表的同一端进行)例如，如果把表的左端定义为栈底，右端定义为栈顶，那么堆栈的添加操作等价于在表的右端进行插入操作，删除操作等价于在表的右端进行删除操作。,继承,3/13/2023,8,templateclass Stack:private Li

3、nearList/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,公式化描述的堆栈类(派生),3/13/2023,9,templateclass Stack/LIFO 对

4、象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,自定义Stack,3/13/2023,10,templateStack:Stack(int MaxStackSize)MaxTop=MaxStackSize-1;stack=new TMaxStackSize;top=-1;,Stack 类构造函数,3/13/2023,11,templateT Stack:

5、Top()constif(IsEmpty()throw OutOfBounds();else return stacktop;复杂性?,返回栈顶元素,3/13/2023,12,templateStack 复杂性?,添加元素x,3/13/2023,13,templateStack 复杂性?,删除栈顶元素，并将其送入x,3/13/2023,14,哪一端对应栈顶?,链表描述,3/13/2023,15,templateclass LinkedStack:private Chain public:bool IsEmpty()constreturn Chain:IsEmpty();bool IsFull(

6、)const;T Top()constif(IsEmpty()throw OutOfBounds();T x;Find(1,x);return x;LinkedStack,从Chain派生的链表形式的堆栈,3/13/2023,16,templatebool LinkedStack:IsFu11()const/堆栈是否满?try ChainNode*p=new ChainNode;delete p;return false;catch(NoMem)return true;,从Chain派生的链表形式的堆栈,3/13/2023,17,template class Nodefriend Linked

7、Stack;private:T data;Node*link;,自定义链表形式的堆栈,3/13/2023,18,templateclass LinkedStack public:LinkedStack()top=0;LinkedStack();bool IsEmpty()const return top=0;bool IsFull()const;T Top()const;LinkedStack/指向栈顶节点:,自定义链表形式的堆栈,3/13/2023,19,templateLinkedStack:LinkedStack()Node*next;while(top)next=top-link;de

8、lete top;top=next;,析构函数,3/13/2023,20,templatebool LinkedStack:IsFu11()consttry Node*p=new Node;delete p;return false;catch(NoMem)return true;,堆栈是否满?,3/13/2023,21,templateT LinkedStack:Top()constif(IsEmpty()throw OutOfBounds();return top-data;,返回栈顶元素,3/13/2023,22,templateLinkedStack,添加元素x,3/13/2023,2

9、3,templateLinkedStack,删除栈顶元素，并将其送入x,3/13/2023,24,链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,比较,3/13/2023,25,括号匹配(Parenthesis Matching)汉诺塔(Towers of Hanoi)火车车厢重排(Rearranging Railroad Cars)开关盒布线(Switch Box Routing)离线等价类(Offline Equivalence Problem)迷宫老鼠(Rat in a Maze),应用,3/13/2023,26,目标:输入一个字符串，输出相互匹配的

10、括号以及未能匹配的括号。例：字符串(a*(b+c)+d)例：字符串(a+b)(,括号匹配,3/13/2023,27,如果从左至右扫描一个字符串，那么每个右括号将与最近遇到的那个未匹配的左括号相匹配。如何实现？,观察,3/13/2023,28,可以在从左至右的扫描过程中把所遇到的左括号存放到堆栈内。每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该左括号。,方法,3/13/2023,29,已知n个碟子和3座塔。初始时所有的碟子按从大到小次序从塔1的底部堆放至顶部，需要把碟子都移动到塔2，每次移动一个碟子，而且任何时候都不能把大碟子放到小碟子的上面。,汉诺塔问题,3/1

11、3/2023,30,为了把最大的碟子移动到塔2，必须把其余n-1个碟子移动到塔3，然后把最大的碟子移动到塔2。接下来是把塔3上的n-1个碟子移动到塔2，为此可以利用塔2和塔1。可以完全忽视塔2上已经有一个碟子的事实，因为这个碟子比塔3上将要移过来的任一个碟子都大，因此，可以在它上面堆放任何碟子。,汉诺塔问题-递归方法,3/13/2023,31,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

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

13、nt 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);,使用堆栈求解汉诺塔问题,3/13/2023,35,void TowersOfHanoi(int n)/Hanoi:towersOfHanoi的预处理程序Hanoi X；X.S1=new Stack(n);X.S2=new Stack(n);X.S3=new Stack(n);for

14、(int d=n;d 0;d-)/初始化X.S1-Add(d);/把碟子d 放到塔1上/把塔1上的n个碟子移动到塔2上，借助于塔3 的帮助X.TowersOfHanoi(n,1,2,3);,使用堆栈求解汉诺塔问题,3/13/2023,36,在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨(位于入轨和出轨之间)。,火车车厢重排问题,3/13/2023,37,从前至后依次检查入轨上的所有车厢。如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。缓冲铁轨按照何种方式使用?

15、,火车车厢重排方案,3/13/2023,38,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号车厢对应的缓冲铁轨,火车车厢重排程序,3/13/2023,39,/车厢重排for(int i=1;i=n;i+)if(pi=NowOut

16、)/直接输出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;,火车车厢重排程序,3/13/2023,40,void Output(int,Output 函数,3/13/2023,41,bool Hold(int c,int/车厢索引,Hold函数,3/13/2023,42,/扫描缓冲铁轨for(int i=1;i=k;i+

17、)if(!Hi.IsEmpty()/铁轨i 不空x=Hi.Top();if(c x,Hold函数,3/13/2023,43,if(!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函数,3/13/2023,44,给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布

18、设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果两条电线发生交叉，则会发生电流短路。所以，不允许电线间的交叉。每对互连的针脚被称为网组。目标是要确定对于给定的网组，能否合理地布设电线以使其不发生交叉。,开关盒布线问题,3/13/2023,45,四个网组(1,4,)，(2,3)，(5,6)和(7,8)可布线开关盒(routable switch box),开关盒布线示例,3/13/2023,46,当两个针脚互连时，其电线把布线区分成两个分区。如果有一个网组，其两个针脚分别位于这两个不同的分区，那么这个网组是不可以布线的，因而整个电路也是不可布线的。如果没有这样的网组，则可以

19、继续判断每个独立的分区是不是可布线的。为此，可以从一个分区中取出一个网组，利用该网组把这个分区又分成两个子分区，如果任一个网组的两个针脚都分布在同一个子分区之中(即不会出现两个针脚分别位于两个子分区的情形)，那么这个分区就是可布线的。,策略,3/13/2023,47,可以按顺时针或反时针方向沿着开关盒的外围进行遍历。例：按顺时针方向从针脚1开始遍历，将依次检查针脚1,2,.,8。针脚1和4属于同一个网组，那么在针脚1至针脚4之间出现的所有针脚构成了第一个分区，而在针脚4至针脚1之间未出现的所有针脚构成了第二个分区。把针脚1放入堆栈，然后继续处理，直至遇到针脚4。这个过程使我们仅在处理完一个分区

20、之后才能进入下一个分区。,方案,3/13/2023,48,输入是元素数目n、关系数目r 以及r 对关系，问题的目标是把n个元素分配至相应的等价类。,离线等价类问题,3/13/2023,49,等价关系与等价类(Equivalence Class),在求解实际应用问题时常会遇到等价类问题。从数学上看，等价类是一个对象(或成员)的集合，在此集合中所有对象应满足等价关系。若用符号“”表示集合上的等价关系，那么对于该集合中的任意对象x,y,z，下列性质成立：自反性：x x(即等于自身)。对称性：若 x y,则 y x。传递性：若 x y且 y z,则 x z。因此，等价关系是集合上的一个自反、对称、传递

21、的关系。,3/13/2023,50,“相等”(=)就是一种等价关系，它满足上述的三个特性。一个集合 S 中的所有对象可以通过等价关系划分为若干个互不相交的子集 S1,S2,S3,，它们的并就是 S。这些子集即为等价类。,确定等价类的方法,分两步走。第一步，读入并存储所有的等价对(i,j)；第二步，标记和输出所有的等价类。,3/13/2023,51,给定集合 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 0,3/13/2023,52,初始 0,1,2,3,4,5,6,7,8,9,10,110 4 0

22、,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,10,3/13/2023,53,确定等价类的链表方法,设等价对个数为m，对象个数为n。一种

23、可选的存储表示为单链表。可为集合的每一对象建立一个带表头结点的单链表，并建立一个一维的指针数组 seqn 作为各单链表的表头结点向量。seqi是第 i 个单链表的表头结点，第 i 个单链表中所有结点的data域存放在等价对中与 i 等价的对象编号。当输入一个等价对(i,j)后，就将集合元素 i 链入第 j 个单链表，且将集合元素 j 链入第 i 个单链表。在输出时，设置一个布尔数组 outn，用 outi 标记第 i 个单链表是否已经输出。,3/13/2023,54,算法的输出从编号 i=0 的对象开始，对所有的对象进行检测。在 i=0 时，循第0个单链表先找出形式为(0,j)的等价对，把 0

24、 和 j 作为同一个等价类输出。再根据等价关系的传递性，找所有形式为(j,k)的等价对，把 k 也纳入包含 0 的等价类中输出。如此继续，直到包含 0 的等价类完全输出为止。接下来再找一个未被标记的编号，如 i=1，该对象将属于一个新的等价类，我们再用上述方法划分、标记和输出这个等价类。在算法中使用了一个栈。每次输出一个对象编号时，都要把这个编号进栈，记下以后还要检测输出的等价对象的单链表。,3/13/2023,55,输入所有等价对后的seq数组及各单链表的内容,3/13/2023,56,void main(void)/离线等价类问题int n,r;/输入n 和rcout n;if(n r;i

25、f(r 1)cerr Too few relations endl;exit(l);,离线等价类程序(一),3/13/2023,57,/创建一个指向n个链表的数组Chain*chain;try chain=new Chain n+1;catch(NoMem)cerr a b;chaina.Insert(0,b);chainb.Insert(0,a);,离线等价类程序(一),3/13/2023,58,/对欲输出的等价类进行初始化LinkedStack stack;bool*out;try out=new bool n+1;catch(NoMem)cerrOut of memoryendl;exi

26、t(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);,离线等价类程序(二),3/13/2023,59,/从堆栈中取其余的元素while(!stack.IsEmpty()int*q,j;stack.Delete(j);/链表chainj中的元素在同一个等价类中，使用遍历器取这些元素ChainIterator c;q=c.Initialize(chainj);while(q)if(!out*q)cout q

27、;out*q=true;stack.Add(*q);q=c.Next();cout endl;cout endl End of class list endl;,离线等价类程序(二),3/13/2023,60,迷宫老鼠(rat in a maze)问题要求寻找一条从入口到出口的路径。路径是由一组位置构成的，每个位置上都没有障碍，且每个位置(第一个除外)都是前一个位置的东、南、西或北的邻居。,迷宫老鼠问题,3/13/2023,61,假定用nm的矩阵来描述迷宫，位置(1,1)表示入口，(n,m)表示出口，n和m分别代表迷宫的行数和列数。迷宫中的每个位置都可用其行号和列号来指定。在矩阵中，当且仅当在

28、位置(i,j)处有一个障碍时其值为1，否则其值为0。,迷宫的描述,3/13/2023,62,迷宫的描述,3/13/2023,63,首先把迷宫的入口作为当前位置。如果当前位置是迷宫出口，那么已经找到了一条路径，搜索工作结束。如果当前位置不是迷宫出口，则在当前位置上放置障碍物，以便阻止搜索过程又绕回到这个位置。然后检查相邻的位置中是否有空闲的(即没有障碍物)，如果有，就移动到这个新的相邻位置上，然后从这个位置开始搜索通往出口的路径。如果不成功，选择另一个相邻的空闲位置，并从它开始搜索通往出口的路径。如果所有相邻的空闲位置都已经被探索过，并且未能找到路径，则表明在迷宫中不存在从入口到出口的路径。,方

29、案,3/13/2023,64,对于迷宫内部的位置(非边界位置)，有四种可能的移动方向：右、下、左和上。对于迷宫的边界位置，只有两种或三种可能的移动。为了避免在处理内部位置和边界位置时存在差别，可以在迷宫的周围增加一圈障碍物。,简化算法,3/13/2023,65,迷宫的描述,3/13/2023,66,可以用行号和列号来指定每个迷宫位置，行号和列号被分别称之为迷宫位置的行坐标和列坐标。可以定义一个相应的类Position来表示迷宫位置，它有两个私有成员row和col。为保存从入口到当前位置的路径，可以采用以下基于公式化描述的堆栈：Stack path(MaxPathLength);其中MaxPat

30、hLength是指最大可能的路径长度（从入口到迷宫中任一位置）。,位置表示,3/13/2023,67,按一种固定的方式来选择可行的位置，将可以使问题得到简化。例如，可以首先尝试向右移动，然后是向下，向左，最后是向上。,移动到相邻位置的方法,3/13/2023,68,移动到相邻位置的方法,3/13/2023,69,假定maze、m(迷宫的大小)和path都是按如下方式定义的全局变量：int*maze,m;Stack*path;,迷宫算法实现,3/13/2023,70,bool FindPath()/寻找从位置(1,1)到出口(m,m)的路径/如果成功则返回true，否则返回f a l s e/如

31、果内存不足则引发异常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;/向上,搜索迷宫路径的代码,3/13/2023,71,/在迷宫周围增加一圈障碍物for(int i=0;i=m+l;i+)maze0i=mazem+li=1;/底和顶mazei0=mazeim+l=1;/左和右Pos

32、ition here;here.row=1;here.col=1;mazeii=1;/阻止返回入口int option=0;int LastOption=3;,搜索迷宫路径的代码,3/13/2023,72,/寻找一条路径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+;/下一个选择,搜索迷宫路径的代码,3/13/2023,7

33、3,/找到一个相邻位置了吗?if(option Add(here);here.row=r;here.col=c;/设置障碍物以阻止再次访问mazerc=1;option=0;,搜索迷宫路径的代码,3/13/2023,74,else/没有可用的相邻位置，回溯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;/到达迷宫出口,搜索迷宫路径的代码,3/13/2023,75,迷宫问题输入：录入或从文件读取n*n迷宫方阵输出：自(1,1)至(n,n)的路径。输出：自(1,1)至(n,n)的最短路径。,课程设计,3/13/2023,76,课程设计题目姓名、学号、班级日期课程设计内容描述:需求(输入、输出、功能、测试数据)实现思想、算法描述使用说明调试说明实现代码(带注释),课程设计报告要求,3/13/2023,77,堆栈的实现方式括号匹配汉诺塔火车车厢重排开关盒布线离线等价类迷宫老鼠,第五章 总结,