根据实例给出线性表归并的算法 ●实例3-1:已知线性表LA和LB中的数据元素按值非递减有 序排列,现要求将LA和LB归并为一个新的线性表 LC← LAULE,且LC中的数据元素仍按值非递减有序排列。 设 LA=(1,5,7,15) LB=(3,6,8,913,15,17 则 LC=(1,3,5,6,7,8,9,13,15,15,17)
根据实例给出线性表归并的算法 实例3-1：已知线性表LA和LB中的数据元素按值非递减有 序排列，现要求将LA和LB归并为一个新的线性表 LC←LA∪LB，且LC中的数据元素仍按值非递减有序排列。 设 LA＝（1，5，7，15） LB＝（3，6，8，9，13，15，17） 则 LC＝（1，3，5，6，7，8，9，13，15，15，17）
●算法思想: o设LC为空表。 将LA或LB中的元素逐个插入到LC中即可 ●具体方法:为使LC中元素按值非递减有序排列,可设 两个指针和分别指向LA和LB中某个元素,若设i当前 所指的元素为a,j前所指的元素为b,则当前应插入 到LC中的元素c为 b >b C=t aa=b a ●算法的时间复杂度为 O(ListLength(La+ListLength(Lb)
设LC为空表。 将LA或LB中的元素逐个插入到LC中即可。 具体方法：为使LC中元素按值非递减有序排列，可设 两个指针i和j分别指向LA和LB中某个元素，若设i当前 所指的元素为a，j当前所指的元素为b，则当前应插入 到LC中的元素c为： 算法的时间复杂度为： O(ListLength(La)+ListLength(Lb)) 算法思想：
●归并算法 Void MergeList (List*La, List*Lb, List *LC) Initlist(Lc);/*构造一个空的线性表Lc*/ i=j=1;k=0;/*指针和初始值为1* La_len=listlength (La); Lb_len=ListLength (Lb); while ((i=La_len)&&(j<=Lb_1en) {/*La和Lb均非空*/ GetElem (La, i, ai) GetElem(Lb, j, bj); if (ai <bj) ListInsert (Lc, ++k, ai)i 十1 }/*将La中的元素插入到表Lc中*
归并算法 Void MergeList（List *La， List *Lb， List *LC） { InitList（Lc）； /*构造一个空的线性表Lc*/ i=j=1；k=0； /*指针i和j初始值为1*/ La_len=ListLength（La）； Lb_len=ListLength（Lb）； while（（i<=La_len）＆＆（j＜=Lb_1en） { /* La和Lb均非空*/ GetElem（La，i，ai）； GetElem（Lb，j，bj）； if （ai ＜bj） { Listlnsert（Lc，++k，ai）； ++i； } /*将La中的元素插入到表Lc中*/
se ifai=bj) (Listlnsert(Lc, ++k, bj)i ++i; ++j else (ListInsert (Lc, ++k, bj) ++j; l While(i<=La len) /*如果表La没有取完,则将表La中的所剩元素插入到表lc中* GetElem (La, i++,ai) ListInsert (Lc,++k, ai)i While (j<=Lb_len) GetElem (Lb, j++, bj)i istInsert (Lc, ++k, bj)i *MergeList
else if (ai = bj ) { Listlnsert（Lc，++k，bj）；++i；++j;} else { Listlnsert（Lc，++k，bj）；++j;} } While（i <＝La_len） { /*如果表La没有取完，则将表La中的所剩元素插入到表lc中*/ GetElem（La，i++,ai）； Listlnsert（Lc，++k，ai）； } While（j＜＝Lb_len） { GetElem（Lb，j++，bj）； Listlnsert（Lc，++k，bj）； } }/*MergeList*/
实例3-2:利用线性表的基本运算来实现清除线性表LA 中多余的重复结点,生成一个新的表LB。如有表 LA=(2,3,4,3,56,7,4,8,9) 存在多余的重复结点,则 LB=(2,3,425,6,7,8,9) 利用算法实现。 算法思想:从表LA的第一个结点i=1开始,逐个检查结 点以后的位置为k的任一元素,若两点相同,则从表LA 中将位置k上数据元素删除掉,当遍历了i后面的所有元 素后,i就成为表LA中无重复的结点,然后将后移动 个位置。重复上述过程,直到移到表LA的最后一个 元素为止。 算法的时间复杂度:(n-1)+(n-2)+(n-3)+…+1,即0n
实例3-2：利用线性表的基本运算来实现清除线性表LA 中多余的重复结点，生成一个新的表LB。如有表 LA=(2,3,4,3,5,6,7,4,8,9) 存在多余的重复结点，则 LB=(2,3,4,5,6,7,8,9) 利用算法实现。 算法思想：从表LA的第一个结点i=1开始，逐个检查结 点i以后的位置为k的任一元素，若两点相同，则从表LA 中将位置k上数据元素删除掉，当遍历了i后面的所有元 素后，i就成为表LA中无重复的结点，然后将i向后移动 一个位置。重复上述过程，直到i移到表LA的最后一个 元素为止。 算法的时间复杂度：(n-1)+(n-2)+(n-3)+…..+1,即