数据结构3ppt课件.ppt
（第四讲）,绍兴文理学院,计算机系计算机应用教研室,数据结构,类似下面的多项式如何相加：S(x)=1+3x100002x20000,22:16,第2章 线性表（3）,一、教学目的：掌握单链表的基本操作和初步应用；算法设计训练。,二、教学重点：单链表的基本操作和应用；算法设计。,三、教学难点：单链表的应用；算法设计。四、教学过程：,2.4 线性表的应用,22:16,2.4.1 一般线性表的合并 例 2.1 设有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A=AB。例如，设 LA=(7，5，3，11)LB=(2，6，3)合并后 LA=(7，5，3，11，2，6)(1)算法思想 扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。(2)实现方法 从线性表LB中依次察看每个数据元素;GetElem(L,i,LocateElem(LA,e,equal()若不存在，则插入之。ListInsert(LA,n+1,e),22:16,(3)算法描述,void union(List/La中不存在和 e 相同的数据元素，则插入之/union,(4)算法分析 算法在GetElem和ListInsert的操作的执行时间和表长无关时，其时间复杂度为：(ListLength(LA)ListLength(LB),22:16,2.4.2 有序表的合并,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，则称该线性表为有序表(Ordered List)。例 2.2 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。例如，设 LA=(3，5，8，11)LB=(2,6,8,9,11,15,20)则 LC=(2,3,5,6,8,8,9,11,11,15,20)(1)算法思想 构造线性表LC，将存在于线性表LA和LB中较小的数据元素插入到线性表LC中去。,(2)实现方法,从线性表LA和LB中依次察看每个数据元素;GetElem(LA,i,ListInsert(LC,+LC_len,ai)或ListInsert(LC,+LC_len,bi)把余下的LA或LB中的元素插入到LC中。ListInsert(LC,+LC_len,ai)或ListInsert(LC,+LC_len,bi)1、顺序有序表的合并(1)算法思想 创建一个空表Lc 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后(2)算法描述,22:16,22:16,pa=La.elem;pb=Lb.elem;Lc.length=Lc.length=La.length+Lb.length;pc=Lc.elem=new ElemTypeLc.length;if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last/merge_listSq,void MergeList_Sq(SqList La,SqList Lb,SqList&Lc),算法 2.15 顺序有序表的合并 S4_1,(3)算法分析,22:16,算法2.15 MergeList的时间复杂度为：(ListLength(LA)+ListLength(LB)2、链式有序表的合并(1)算法思想,Lc指向La,22:16,依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止。继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后 释放 Lb 表的表头结点,pc,*lc,pa,pb,(2)算法描述,pb=lb-next;,void mergelist_l(linklist la,linklist lb,linklist&lc),22:16,else,pa=la-next;,linklist pa,pb,pc;,pc,*lc,pa=pa-next;,pa,pb,lc=pc=la;,while(pa&pb),if(pa-datadata),pc-next=pa;,pc=pa;,pc-next=pb;,pc=pb;,pb=pb-next;,pc-next=pb;,pc=pb;,pb=pb-next;,pc-next=pb;,pc=pb;,pb=pb-next;,pc-next=pa;,pc=pa;,pa=pa-next;,pc-next=pa;,pc=pa;,pa=pa-next;,NULL,pc-next=pa?pa:pb;,delete lb;,算法 2.16 链式有序表的合并 S4_2,22:16,(3)算法分析,算法 2.16 mergelist_l的时间复杂度为：(ListLength(LA)+ListLength(LB)2.4.3一元多项式的表示及相加 1、一元多项式的表示 一元多项式Pn(x)可按升幂写成：,在计算机中，可以用一个线性表来表示:P=(p0，p1，pn)同样可用一个线性表Q来表示一元m次多项式Qm(x)Q=(q0，q1，qm)设mn，则 Rn(x)=Pn(x)+Qm(x)可用线性表R表示为：R=(p0+q0，p1+q1，pm+qm，pm+1，pn),22:16,但是对于形如,可以用下列线性表表示：（p1,e1）,(p2,e2),(pm,em)）例如：P999(x)=7x3-2x12-8x999可用线性表(7,3),(-2,12),(-8,999)表示,Pn(x)=p1xe1+p2xe2+pmxem其中：pi 是指数为ei 的项的非零系数，0e1e2 em=n,S(x)=1+3x100002x20000 的多项式，上述表示方法是不合适的。一般情况下的一元稀疏多项式可写成,对应于线性表的两种存储结构，主要讨论如何利用单链表的基本操作来实觋一元多项式的运算。,22:16,2、一元多项式的相加算法图示,3、一元多项式的存储结构,typedef struct term/用带表头结点的有序链表表示多项式 float coef;/系数 int expn;/指数 term*next;*polynomial;,22:16,4、一元多项式的创建,(1)算法思想 是根据“指数”项的大小建立升序有序的单链表。(2)算法描述 void creatpolyn(polynomial,while(q,算法 2.17多项式的创建 S4_3,22:16,4、一元多项式的相加,(1)算法思想 根据相加两项的指数是否相等可分为三种情况。pl所指项的指数值等于p2所指项，则将两对应项的系数相加，若和不为零，则修改pl所指项的系数值，同时删除p2所指项；若和为零，则删除pl和p2所指的项。pl所指项的指数值小于p2所指项的指数值，则应取pl项插入到正在“成长”的“和多项式”链表的尾部。pl所指项的指数值大于p2所指项的指数值，则应取p2所指项插入到正在“成长”的“和多项式”链表的尾部。最后，当有一个多项式链表为空时，刚将另一个非空多项式的剩余段直接链在正在“成长”的“和多项式”链表的尾部。,22:16,(2)算法描述,void addpolyn(polynomial pa,polynomial pb)polynomial p1,p2,p3,r;float sum;p1=pa-next;p2=pb-next;p3=pa;while(p1,22:16,else,r=p1;p1=p1-next;delete r;r=p2;p2=p2-next;delete r;else if(p1-expnexpn)p3-next=p1;p3=p1;p1=p1-next;else p3-next=p2;p3=p2;p2=p2-next;,p3-next=p1?p1:p2;delete pb;,算法 2.18多项式相加 S4_4,五、作业：,上机编程：(数据结构编程练习中)p43 2中(3)(8803)、(5)(8805)、(8)(8808),？,22:16,
