数据结构--两个线性表的归并及其应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 线性表,(,续,),两个线性表的归并,一元多项式的表示及相加,(,简介,),两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pa=La-next;,pb,=Lb-next;,Lc,=pc=La;,pc,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pa=La-next;,pb,=Lb-next;,Lc,=pc=La;,pc,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,if(,pb,)pc-next=,pb,;,else pc-next=pa;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,La,3,5,8,11,Lb,2,6,8,9,11,15,20,Lc,pa,pb,pc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,if(,pb,)pc-next=,pb,;,else pc-next=pa;,free(Lb,);,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,3,5,8,11,2,6,8,9,11,15,20,Lc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,if(,pb,)pc-next=,pb,;,else pc-next=pa;,两个,线性表,的归并,引例：,La=(,3,5,8,11),Lb=(2,6,8,9,11,15,20),则,:,求,La,与,Lb,的归并,得结果线性表,Lc,如下,:,Lc,=(2,3,5,6,8,8,9,11,11,15,20),线性链表的物理实现过程,:,3,5,8,11,2,6,8,9,11,15,20,Lc,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,if(,pb,)pc-next=,pb,;,else pc-next=pa;,两个,线性表,的归并,归并算法,:,void,MergeList_L(LinkList,&La,LinkList,&Lb,LinkList,&,Lc,),pa=La-next;,pb,=Lb-next;,Lc,=pc=La;,while(pa&,pb,),if(pa-datadata),pc-next=pa;pc=pa;,pa=,pa,-next;,else pc-next=,pb,;pc=,pb,;,pb,=,pb,-next;,if(,pb,)pc-next=,pb,;,else pc-next=pa;,free(Lb,);,/,MergeList_L,示例,:,f,14,(x)=1-10 x,6,+2x,8,+7x,14,f,18,(x)=-x,4,+10 x,6,-3x,10,+8x,14,+4x,18,应用,:,多项式的表示及两多项式的求和,用线性表分别表示两个多项式如下,:,La,1 0,-10 6,2 8,7 14,Lb,-1 4,10 6,-3 10,8 14,4 18,思想：根据指数,(,expn,),项采用归并算法得到表示求和结果的线性表,Lc,。,注意：当遇到两指数相等时其系数相加,相加后结果不为零则作为两项合并为一项增加到结果表,Lc,中,否则该项消失。,结点形式,(node),：,coef,expn,next,作业,:,用,C,或,C+,实现多项式的链结构的线性表表示方法，并完成两个多项式相加算法的相关程序（包括输入与输出等）的设计，并上机验证程序的正确性。,结 束,返回,