《数据结构3ppt课件》由会员分享，可在线阅读，更多相关《数据结构3ppt课件（19页珍藏版）》请在金锄头文库上搜索。
1、（第四讲）（第四讲）绍兴文理学院绍兴文理学院计算机系计算机应用教研室计算机系计算机应用教研室TKSTKS2 2类似下面的多项类似下面的多项式如何相加：式如何相加：S(x)=1+3x100002x20000 00:16 第第2 2章章 线性表（线性表（3 3）一一、教教学学目目的的：掌掌掌掌握握握握单单单单链链链链表表表表的的的的基基基基本本本本操操操操作作作作和和和和初初初初步步步步应应应应用用用用；算算算算法设计训练。法设计训练。法设计训练。法设计训练。二、教学重点：二、教学重点：单链表的单链表的单链表的单链表的基本操作和应用基本操作和应用基本操作和应用基本操作和应用；算法设计。算法设计。算
2、法设计。算法设计。三、教学难点：三、教学难点：单链表的应用；算法设计。单链表的应用；算法设计。单链表的应用；算法设计。单链表的应用；算法设计。四、教学过程：四、教学过程：2.4 2.4 线性表的应用线性表的应用TKSTKS4 400:16 2.4.1 2.4.1 一般线性表的合并一般线性表的合并 例例 2.1 2.1 设有两个集合设有两个集合A A和和B B分别用两个线性表分别用两个线性表LALA和和LBLB表示，即：线表示，即：线性表中的数据元素即为集合中的成员性表中的数据元素即为集合中的成员。现要求一个新的集合现要求一个新的集合A=ABA=AB。 例如，设例如，设 LA=(7LA=(7，5
3、 5，3 3，11) LB=(211) LB=(2，6 6，3)3) 合并后合并后 LA=(7LA=(7，5 5，3 3，1111，2 2，6)6)(1) (1) 算法思想算法思想 扩扩大大线线性性表表LALA，将将存存在在于于线线性性表表LBLB中中而而不不存存在在于于线线性性表表LALA中中的的数据元素插入到线性表数据元素插入到线性表LALA中去。中去。(2) (2) 实现方法实现方法 从线性表从线性表LBLB中依次察看每个数据元素中依次察看每个数据元素; ;GetElem(L,i,&eGetElem(L,i,&e) ) ee 依值在线性表依值在线性表LALA中进行查访中进行查访; ; L
4、ocateElem(LA,e,equalLocateElem(LA,e,equal( )( ) 若不存在，则插入之。若不存在，则插入之。ListInsert(LA,n+1,e)ListInsert(LA,n+1,e)TKSTKS5 500:16 (3) (3) 算法描述算法描述 void union(List &La,List Lb)void union(List &La,List Lb) La_lenLa_len= =ListLength(LaListLength(La) ); ; / / 求线性表的长度求线性表的长度 Lb_lenLb_len= =ListLength(LbListLeng
5、th(Lb) ); ; for(i=1;i=for(i=1;i=Lb_len;iLb_len;i+)+) GetElem(Lb,i,&eGetElem(Lb,i,&e) ); ; / / 取取LbLb中第中第i i个数据元素赋给个数据元素赋给e e if(!if(!LocateElem(La,e,equalLocateElem(La,e,equal( )( ) ) ListInsert(LaListInsert(La, +, +La_lenLa_len, e), e); ; / La/ La中不存在和中不存在和 e e 相同的数据元素，则插入之相同的数据元素，则插入之 / union/ uni
6、on(4) (4) (4) (4) 算法分析算法分析算法分析算法分析 算法在算法在GetElemGetElem和和ListInsertListInsert的操作的执行时间和表长无关时，的操作的执行时间和表长无关时，其时间复杂度为：其时间复杂度为： ( (ListLength(LA)ListLength(LA)ListLength(LBListLength(LB)TKSTKS6 600:16 2.4.2 2.4.2 有序表的合并有序表的合并 若线性表中的数据元素相互之间可以比较，并且数据元素在线若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，则称该线性表为
7、性表中依值非递减或非递增有序排列，则称该线性表为有序表有序表( ( Ordered List)Ordered List)。 例例 2.2 2.2 已知线性表已知线性表LALA和和LBLB中的数据元素按值非递减有序排列，现中的数据元素按值非递减有序排列，现要求将要求将LALA和和LBLB归并为一个新的线性表归并为一个新的线性表LCLC，且，且LCLC中的数据元素仍按值中的数据元素仍按值非递减有序排列。非递减有序排列。 例如，设例如，设 LA=(3LA=(3，5 5，8 8，11)11) LB=(2, 6, 8, 9, 11, 15, 20) LB=(2, 6, 8, 9, 11, 15, 20)
8、 则则 LC=(2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20)LC=(2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20) (1) (1) 算法思想算法思想 构造线性表构造线性表LCLC，将存在于线性表，将存在于线性表LALA和和LBLB中较小的数据元素插入中较小的数据元素插入到线性表到线性表LCLC中去。中去。(2)(2) 实现方法实现方法 从线性表从线性表LALA和和LBLB中依次察看每个数据元素中依次察看每个数据元素; ; GetElem(LA,i,&aiGetElem(LA,i,&ai) ) aiai GetElem(LB,i,&biGet
9、Elem(LB,i,&bi) ) bibi 把把aiai和和bibi较小的一个插入到较小的一个插入到线性表线性表LCLC中中; ; ListInsert(LC,+LC_len,ListInsert(LC,+LC_len,aiai) )或或ListInsert(LC,+LC_len,ListInsert(LC,+LC_len,bibi) ) 把余下的把余下的LALA或或LBLB中的元素插入到中的元素插入到LCLC中。中。 ListInsert(LC,+LC_len,ListInsert(LC,+LC_len,aiai) )或或ListInsert(LC,+LC_len,ListInsert(LC
10、,+LC_len,bibi) )1 1、顺序有序表的合并、顺序有序表的合并(1) (1) 算法思想算法思想 创建一个空表创建一个空表LcLc 依次从依次从 La La 或或 Lb Lb 中中“摘取摘取”元素值较小的结点插入到元素值较小的结点插入到 LcLc 表表的最后，直至其中一个表变的最后，直至其中一个表变空空为止为止 继续将继续将 La La 或或 Lb Lb 其中一个表的剩余结点插入在其中一个表的剩余结点插入在 LcLc 表的最后表的最后(2) (2) 算法描述算法描述TKSTKS7 700:16 TKSTKS8 800:16 pa=pa=La.elem;pbLa.elem;pb= =L
11、b.elemLb.elem; ; Lc.lengthLc.length= =Lc.lengthLc.length= =La.length+Lb.lengthLa.length+Lb.length; ; pc=pc=Lc.elemLc.elem=new =new ElemTypeLc.lengthElemTypeLc.length; if(!Lc.elemif(!Lc.elem) exit(OVERFLOW);) exit(OVERFLOW); pa_last=La.elem+La.length-1; pa_last=La.elem+La.length-1; pb_lastpb_last=Lb.
12、elem+Lb.length-1;=Lb.elem+Lb.length-1; while(pa=pa_last & while(pa=pa_last & pbpb=pb_lastpb_last) ) if(*pa=*if(*pa=*pbpb) ) *pc+=*pa+*pc+=*pa+; ; else else *pc+=*pc+=*pbpb+; ; while(pa=pa_last while(pa=pa_last) ) *pc+=*pa+*pc+=*pa+; ; while(pbwhile(pb=next;=lb-next;void void mergelist_l(linklistmerg
13、elist_l(linklist la,linklistla,linklist lb,linklistlb,linklist & &lclc) )TKSTKS 111100:16 else else lalalala1 17 78 8lblblblb2 24 46 68 810101111pa=la-next; pa=la-next; linklistlinklist pa,pb,pcpa,pb,pc; ;pc pc * *lclc pa=pa=papa-next;-next;pa pa pbpb lclc=pc=la; =pc=la; while(pa&pbwhile(pa&pb) ) if
14、(paif(pa-datadatadata)-data) pc-next=pa; pc-next=pa; pc=pa; pc=pa; pc pc pa pa pc-next=pc-next=pbpb; ; pc=pc=pbpb; ; pc pc pbpb= =pbpb-next;-next;pbpb pc-next=pc-next=pbpb; ; pc=pc=pbpb; ; pc pc pbpb pbpb= =pbpb-next;-next; pc-next=pc-next=pbpb; ; pc=pc=pbpb; ; pc pc pbpb= =pbpb-next;-next;pbpb pc-n
15、ext=pa; pc-next=pa; pc=pa;pc=pa;pc pc pa=pa=papa-next;-next;pa pa pc-next=pa; pc-next=pa; pc=papc=pa; ;pc pc pa=pa=papa-next;-next;pa pa NULLNULLpc-next=pc-next=pa?pa:pbpa?pa:pb; ; delete lb; delete lb; 算法算法算法算法 2.16 2.16 2.16 2.16 链式有链式有链式有链式有序表的合并序表的合并序表的合并序表的合并 S4_2S4_2S4_2S4_2TKSTKS 121200:16 (3
16、) (3) 算法分析算法分析算法分析算法分析 算法算法 2.16 2.16 mergelist_lmergelist_l的时间复杂度为：的时间复杂度为： ( (ListLength(LA)+ListLength(LBListLength(LA)+ListLength(LB) 2.4.32.4.3一元多项式的表示及相加一元多项式的表示及相加 1 1、一、一元多项式的表示元多项式的表示 一元多项式一元多项式P Pn n(x(x) )可按升幂写成：可按升幂写成： 在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示: P=(pP=(p0 0，p p1 1，p pn n) ) 同样可用
17、一个线性表同样可用一个线性表Q Q来表示一元来表示一元m m次多项式次多项式Q Qm m(x(x) ) Q=(qQ=(q0 0，q q1 1，q qm m) ) 设设mnmn，则则 R Rn n(x(x)=)=P Pn n(x)+Q(x)+Qm m(x(x) ) 可用线性表可用线性表R R表示为：表示为： R=(pR=(p0 0+q+q0 0，p p1 1+q+q1 1，p pm m+q+qm m，p pm+1m+1，p pn n) ) TKSTKS 131300:16 但是对于形如但是对于形如 可以用下列线性表表示：可以用下列线性表表示： （p p1 1, e, e1 1）, (p, (p2
18、 2, e, e2 2), , (), , (p pm m,e,em m) ) ） 例如：例如： P P999999(x) = 7x(x) = 7x3 3 - 2x - 2x1212 - 8x - 8x999999可用线性表可用线性表 ( (7, 3), (-2, 12), (-8, 999) ) ( (7, 3), (-2, 12), (-8, 999) ) 表示表示 P Pn n(x(x)=p)=p1 1x xe e1 1+p+p2 2x xe e2 2+ + +p pm mx xe em m其中：其中：p pi i 是指数为是指数为e ei i 的项的非零系数，的项的非零系数， 0e0e
19、1 1ee2 2 next=NULL; p-next=NULL; cincince;ce; while(ewhile(e!=-1)!=-1) s=new term; s=new term; s- s-coefcoef=c;=c; s- s-expnexpn=e;=e; pre=p; pre=p; q=p-next; q=p-next;while(q&qwhile(q&q-expnexpnexpnexpn) ) pre=q;pre=q; q=q-next; q=q-next; s-next=q; s-next=q; / / 链上链上 pre-next=s;pre-next=s;cincince;
20、ce; 算法算法算法算法 2.172.172.172.17多项式的创建多项式的创建多项式的创建多项式的创建 S4_3S4_3S4_3S4_3TKSTKS 161600:16 4 4、一元多项式的相加一元多项式的相加 (1) (1) 算法思想算法思想 根据相加两项的指数是否相等可分为根据相加两项的指数是否相等可分为三种三种情况。情况。 plpl所指项的指数值所指项的指数值等于等于p2p2所指项，则将两对应项的系数相加，所指项，则将两对应项的系数相加，若和不为零，则若和不为零，则修改修改plpl所指项的系数值，同时删除所指项的系数值，同时删除p2p2所指项；若和所指项；若和为零，则为零，则删除删除
21、plpl和和p2p2所指的项。所指的项。 plpl所指项的指数值所指项的指数值小于小于p2p2所指项的指数值，则应取所指项的指数值，则应取plpl项项插入插入到到正在正在“成长成长”的的“和多项式和多项式”链表的尾部。链表的尾部。 plpl所指项的指数值所指项的指数值大于大于p2p2所指项的指数值，则应取所指项的指数值，则应取p2p2所指项插所指项插入到正在入到正在“成长成长”的的“和多项式和多项式”链表的尾部。链表的尾部。 最后，当有一个多项式链表为空时，刚将另一个非空多项式的最后，当有一个多项式链表为空时，刚将另一个非空多项式的剩余段直接链在正在剩余段直接链在正在“成长成长”的的“和多项式
22、和多项式”链表的尾部。链表的尾部。TKSTKS 171700:16 (2) (2) 算法描述算法描述 void void addpolyn(polynomialaddpolyn(polynomial pa,polynomialpa,polynomial pbpb) ) polynomial p1,p2,p3,r;float sum; polynomial p1,p2,p3,r;float sum; p1=pa-next; p2= p1=pa-next; p2=pbpb-next; -next; p3=pa; p3=pa; while(p1&p2) while(p1&p2) if(p1-if(p
23、1-expnexpn=p2-=p2-expnexpn) ) sum=p1-coef+p2-sum=p1-coef+p2-coefcoef; ; if(fabs(sumif(fabs(sum)0.000001)0.000001) p1- p1-coefcoef=sum; =sum; p3-next=p1;p3=p1; p3-next=p1;p3=p1; p1= p1=p1p1-next;-next; r=p2;p2=p2- r=p2;p2=p2-next;deletenext;delete r; r; TKSTKS 181800:16 else else r=p1; p1=r=p1; p1=p1
24、p1-next; delete r;-next; delete r; r=p2; p2= r=p2; p2=p2p2-next; delete r; -next; delete r; else if(p1- else if(p1-expnexpnexpnexpn) ) p3-next=p1; p3-next=p1; p3=p1; p3=p1; p1= p1=p1p1-next;-next; else else p3-next=p2;p3-next=p2; p3=p2; p3=p2; p2= p2=p2p2-next; -next; p3-next=p1?p1:p2; p3-next=p1?p1:p2; delete delete pbpb; ; 算法算法算法算法 2.182.182.182.18多项式相加多项式相加多项式相加多项式相加 S4_4S4_4S4_4S4_4五、作业：五、作业：上机编程：上机编程： ( (数据结构编程练习中数据结构编程练习中) ) p43 2p43 2中中 (3)(3)(8803)(8803)、 (5)(5)(8805)(8805)、(8)(8)(8808)(8808) ？TKSTKS 191900:16
