数据结构第七讲.ppt

单击此处编辑母版标题样式,桂林电子科技大学信息科技学院 赵莹莹,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,复习上节课内容,3.1,栈,3.1.1,栈的定义及运算,3.1.2,栈,的顺序存储结构及基本运算的实现,3.1.3,栈,的链式存储结构及基本运算的实现,3.2,栈的应用,3.2.1,中缀表达式,3.2.2,中缀表达式转换为等价的后缀表达式,3.2.3,后缀表达式及求值,3.3,栈与递归,3.3.1,递归与递归程序的设计,3.3.2,递归程序的执行过程,3.3.3,递归的应用举例,3.4,队 列,3.4.1,队列的定义和运算,3.4.2,队列的顺序存储结构及基本运算的实现,34.3,队列的链式存储结构及基本运算的实现,3.4.4,队列的应用,举例,本章小结,本章要点,3.1,栈,3.1.1,栈的定义及运算,3.1.2,栈,的顺序存储结构及基本运算的实现,3.1.3,栈,的链式存储结构及基本运算的实现,3.2,栈的应用,3.2.1,中缀表达式,3.2.2,中缀表达式转换为等价的后缀表达式,3.2.3,后缀表达式及求值,3.3,栈与递归,3.3.1,递归与递归程序的设计,3.3.2,递归程序的执行过程,3.3.3,递归的应用举例,3.4,队 列,3.4.1,队列的定义和运算,3.4.2,队列的顺序存储结构及基本运算的实现,3.4.3,队列的链式存储结构及基本运算的实现,3.4.4,队列的应用,举例,本章小结,一，,问题求解：,二，算法编写：,以,n,的阶乘为例：,n,!,的定义为：,n,的阶乘等于,n,乘以,n,-1,的阶乘，公式表示：,根据定义可以很自然地写出相应的递归函数,int,fact(,int,n),if(n=0)return 1;,else return (n*fact(n-1);,若一个对象部分地包含它自己，或用它自己给自己定义，则这个对象是递归的。,3.3.1,递归与递归程序的设计,递归算法要点：,(1),问题具有类同自身的子问题的性质，被定义项在定义中的应用具有更小的尺度。,(2),被定义项在最小尺度上有直接解。,设计递归算法的方法是：1),寻找方法，将问题化为原问题的子问题求解,(,例如,n!=n*(n-1)!),。,(2),设计递归出口，确定递归终止条件,(,例如求解,n!,时，当,n=1,时，,n!=1),。,递归算法书写要点及方法,例,3-3,采用递归算法求解,Fibonacci,级数第,n,项的值。,long fib,（,int n,）,int f;,if(n=1,n=2,),f=1;,else,f=fib(n-1)+fib(n-2);,return f;,本章要点,3.1,栈,3.1.1,栈的定义及运算,3.1.2,栈,的顺序存储结构及基本运算的实现,3.1.3,栈,的链式存储结构及基本运算的实现,3.2,栈的应用,3.2.1,中缀表达式,3.2.2,中缀表达式转换为等价的后缀表达式,3.2.3,后缀表达式及求值,3.3,栈与递归,3.3.1,递归与递归程序的设计,3.3.2,递归程序的执行过程,3.3.3,递归的应用举例,3.4,队 列,3.4.1,队列的定义和运算,3.4.2,队列的顺序存储结构及基本运算的实现,3.4.3,队列的链式存储结构及基本运算的实现,3.4.4,队列的应用,举例,本章小结,3.3.2,递归,程序的执行过程（,1,）,以求,3!,为例说明执行调用的过程如下图所示。,递归函数的递归过程：在递归进层,(,i,i,+1,层,),时系统需要做三件事：,(1),保留本层参数与返回地址,(,将所有的实际参数、返回地址等,信息传递给被调用函数保存,),；,(2),给下层参数赋值,(,为被调用函数的局部变量分配存储区,),；,(3),将程序转移到被调函数的入口。,而从被调用函数返回调用函数之前，递归退层,(,i,i,+1,层,),系统也应完成三件工作：,(1),保存被调函数的计算结果；,(2),恢复上层参数,(,释放被调函数的数据区,),；,(3),依照被调函数保存的返回地址，将控制转移回调用函数。,3.3.2,递归程序的执行过程（,2,）,本章要点,3.1,栈,3.1.1,栈的定义及运算,3.1.2,栈,的顺序存储结构及基本运算的实现,3.1.3,栈,的链式存储结构及基本运算的实现,3.2,栈的应用,3.2.1,中缀表达式,3.2.2,中缀表达式转换为等价的后缀表达式,3.2.3,后缀表达式及求值,3.3,栈与递归,3.3.1,递归与递归程序的设计,3.3.2,递归程序的执行过程,3.3.3,递归的应用举例,3.4,队 列,3.4.1,队列的定义和运算,3.4.2,队列的顺序存储结构及基本运算的实现,3.4.3,队列的链式存储结构及基本运算的实现,3.4.4,队列的应用,举例,本章小结,汉诺塔问题：,设有,3,跟标号为,A,B,C,的针，再,A,针上穿有,n,个盘子，一个比一个小，要求把,A,针上的盘子全部移动到,C,针上，移动的规则是：,1,，一次只能移动一个盘子,2,，移动过程中，大盘子始终在小盘子下面。,3,，移动过程，盘子可以放到任意一根针上。,汉诺塔的演示,如果,n,1,，则直接移动，否则：,1,，用,C,针过渡，将,A,针上的,n,1,个盘子移动到,B,针上。,2,，将,A,针上最后一个盘子直接移动到,C,针上。,3,.3.3,递归的应用,-,汉诺塔,汉诺塔算法,include,Void,hanoi(int,n,char,A,char,B,char,C),If(n=1),cout,“move”A“to”C,endl,;,Else,hanoi(n-1,A,C,B);,cout,“move”A“to”Cfront=SQ-rear=0;,0,1,2,3,4,5,6,7,front,rear,队,列为空：,front,rear,顺序队列的相关运算（,2,）,2,）入队,int EnQueue(,SQUEUE*SQ,Elemtype x,),/,进队操作,if(SQ-rear+1)%,Max,size)!=SQ-front),SQ-rear=(SQ-rear+1)%m,ax,size;,SQ-dataSQ-rear=,x,;,return 1;,else,return 0;,顺序队列的相关运算（,3,）,3,）判断队列是否为空,Int Empty(SQUEUE*SQ),if(SQ-front=SQ-rear),return 1;,else,return 0;,0,1,2,3,4,5,6,7,front,rear,队,列为空：,front,rear,4),出队,int O,ut,Queue(,SQUEUE*SQ,Elem,Type*x),/,出队操作,if(!Empty(,SQ,),SQ-,front=(,SQ-,front+1)%size;,*,x,=,SQ-data,SQ-front,;,return 1;,else,return 0;,顺序队列的相关运算（,4,）,队列的相关运算（,5,）,5,）取队头元素,int GetH,ead,(SQUEUE,*SQ,Elem,Type*x),/,取队头元素操作,if(!,Empty(SQ),),*,x,=SQ-,data,(SQ-front+1)%M,ax,size;,return 1;,else,return 0;,本章要点,3.1,栈,3.1.1,栈的定义及运算,3.1.2,栈,的顺序存储结构及基本运算的实现,3.1.3,栈,的链式存储结构及基本运算的实现,3.2,栈的应用,3.2.1,中缀表达式,3.2.2,中缀表达式转换为等价的后缀表达式,3.2.3,后缀表达式及求值,3.3,栈与递归,3.3.1,递归与递归程序的设计,3.3.2,递归程序的执行过程,3.3.3,递归的应用举例,3.4,队 列,3.4.1,队列的定义和运算,3.4.2,队列的顺序存储结构及基本运算的实现,3.4.3,队列的链式存储结构及基本运算的实现,3.4.4,队列的应用,举例,本章小结,链队列的节点可定义如下：,class,QueueNode,public:,DataType,data;,QueueNode,*next;,QueueNode,(),next=NULL;,;,;,队列的链式存储结构如如图所示：,4.2.3,链队列,(1),链队的类描述如下：,class,LinkQueue,private:,QueueNode,*front;,QueueNode,*rear;,public:,LinkQueue,()front=NULL;rear=NULL;,LinkQueue()QueueNode,*p,*q;,p=front;,while(p,),q=p;,p=p-next;,delete q;,front=NULL;,rear=NULL;,;/,销毁一个已存在的队列,4.2.3,链队列,(2),int,Empty_Queue,();/,判断队列是否为空,int,En_Queue(DataType,e);/,将元素,e,插入到队头,int,De_Queue(DataType,/,从队头删除一个元素到,e,中返回,int,Front_Queue(DataType,/,从队头取出一个元素到,e,中返回,;,4.2.3,链队列,(4),链队列的各成员函数的实现算法如下：1),判断队列是否为空。,int,LinkQueue:Empty_Queue,(),return(front=,NULL&rear,=NULL);,(2),进队操作。,int,LinkQueue:En_Queue(DataType,e),QueueNode,*p=new,QueueNode,;,if(p,),p-data=e;,p-next=null;,if(rear,),rear-next=p;,rear,p,；,else,front=p;,rear=p;,return 1;,else,return 0;,4.2.3,链队列,(5),(3),出队操作。,int,LinkQueue:De_Queue(DataType,&e),QueueNode,*p;,if(front,),p=front;,e=p-data;,front=,front,-next;,if(!front,),rear=NULL;,delete p;,return 1;,else,return 0;,(4),取队头元素操作。,int,LinkQueue:Front_Queue(DataType,&e),if(front,),e=front-data;,return 1;,else,return 0;,4.1,栈,4.1.1,栈的抽象数据类型,4.1.2,顺序栈,4.1.3,链栈,4.1.4,栈的应用,4.2,队 列,4.2.1,队列的抽象数据类型,4.2.2,顺序队列,4.2.3,链队列,4.2.4,队列的应用,4.3,递 归,4.3.1,递归算法书写要点及方法,4.3.2,递归过程的调用和返回,4.3.3,递归的应用,4.3.4,递归函数的非递归化,本章小结,本章要点,1,、问题叙述,假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。,4.2.4,队列的应用,舞伴问题,2,、问题分析,先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。,在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。,3,、具体算法及相关的类型定义,typedef,struct,char name20;char sex;/,性别，,F,表示女性，,M,表示男性,Person;,typedef,Person,DataType,;/将队列中元素的数据类型改为,Person void,DancePartner(Person,dancer,int,num)/,结构数组,dancer,中存放跳舞的男女，,num,是跳舞的人数。,int,i;Person p;,CirQueue,Mdancers,Fdancers,;,InitQueue(&Mdancers,);/,男士队列初始化,InitQueue(&Fdancers,);/,女士队列初始化,for(i,=0;i,num;i,+)/,依次将跳舞者依其性别入队,p=,danceri,;,if(p.sex,=F),EnQueue(&Fdancers.p,);/,排入女队,elseEnQueue(&Mdancers.p,);/,排入男队,printf(The,dancing partners are:n,n,);,while(!QueueEmpty(&Fdancers)&!QueueEmpty(&Mdancers,)/,依次输入男女舞伴名,p=,DeQueue(&Fdancers,);/,女士出队,printf(%s,p.name,);/,打印出队女士名,p=,DeQueue(&Mdancers,);/,男士出队,printf(%sn,p.name,);/,打印出队男士名,if(!QueueEmpty(&Fdancers,)/,输出女士剩余人数及队头女士的名字,printf(n,There are%d women,waitin,for the next round.,n,Fdancers.count,);p=,QueueFront(&Fdancers,);/,取队头,printf(%s,will be the first to get a partner.,n,p.name,);else,if(!QueueEmpty(&Mdancers,)/,输出男队剩余人数及队头者名字,printf(n,There,are%d,men waiting for the next round.,n,Mdacers.count,);p=,QueueFront(&Mdancers,);,printf(%s,will be the first to get a partner.,n,p.name,);/,DancerPartners,1,，队列的链式存储（重点）,2,，队列的应用,舞伴问题,3,，递归的定义和过程,4,，递归的消除（重点）,本 章 小 结,一，,Page110,：,4,，,7,，,9,，,10,二，写出中缀表达式转换成后缀表达式的算法。,三，写出使用栈来实现后缀表达式求值的算法。,四，写出舞伴配对问题的算法。,作业,