bool SetUnion(sqList &la, sqList &Ib) iint b, n, i; bool k, r=true n= Lb, size;∥Lb表的初始长度存入n for(i=n; i>0&&r; i-) 从Lb表中逐次删除表尾元素,这样不必移动元素 ir=Delete Node (Lb, i, b) ∥调用删除算法,被删元素存入b k= Locatenode(La,b);∥在La表中查找b if(lk)r=InsertNode La, b, La size+1); ∥La表中找不到元素b,则插入至a表尾 }∥ end for return ra
bool SetUnion(sqList &la,sqList &lb) { int b, n, i; bool k, r=true ; n=Lb.Size; // Lb表的初始长度存入n for(i=n; i>0 && r ; i--) // 从Lb表中逐次删除表尾元素，这样不必移动元素 { r=DeleteNode(Lb, i, b); // 调用删除算法，被删元素存入b k=LocateNode(La, b); // 在La表中查找b if(!k) r=InsertNode(La, b, La.Size+1); // La表中找不到元素b，则插入至la表尾 } // end_for return r; }
算法分析:由于要从Lb表中逐次删除表尾元素,则 for循环执行 Lb, size次,循环体中的尾删除和尾插入 不需移动元素,但 Locatenode(La,b)的时间复杂度 为 La size,因此 SetUnion的时间复杂度为: O(La size* Lb Size). 【例22】设整数表La和Lb采用顺序结构存储,且 表中的整数均按值非递减有序排列,现要求由La和 Lb归并产生一个新的整数表Lc,要求Lc中的数仍 按值非递减有序排列
算法分析：由于要从Lb表中逐次删除表尾元素，则 for循环执行Lb.Size次，循环体中的尾删除和尾插入 不需移动元素，但LocateNode(La, b) 的时间复杂度 为 La.Size ， 因 此 SetUnion 的 时 间 复 杂 度 为 ： O(La.Size*Lb.Size)。 【例2.2】设整数表La和Lb采用顺序结构存储，且 表中的整数均按值非递减有序排列，现要求由La和 Lb归并产生一个新的整数表Lc，要求Lc中的数仍 按值非递减有序排列
算法思路:由题意可知,Lc中的数据元素或是La中 的数据元素,或是Lb中的数据元素,那么只要先设 Lc为空表,然后将La或Lb中的元素逐个插入到Lc中 即可。为使Lc中元素按值非递减有序排列,可设两个 指针和分别指向La和Lb中某个元素,假设当前所指 的元素为a,j当前所指的元素为b,则当前应插入到 Lc中的元素c为: a当a≤b时 b当a>b时
算法思路：由题意可知，Lc中的数据元素或是La中 的数据元素，或是Lb中的数据元素，那么只要先设 Lc为空表，然后将La或Lb中的元素逐个插入到Lc中 即可。为使Lc中元素按值非递减有序排列，可设两个 指针i和j分别指向La和Lb中某个元素，假设i当前所指 的元素为a，j当前所指的元素为b，则当前应插入到 LC中的元素c为： a 当a ≤ b 时 c = b 当 a > b时
显然,指针和的初值均为1,在所指元素插入Lc之 后,在La或Lb中顺序后移。 此算法执行后整数表La和Lb保持不变。 Bool Merge(sqlist& Lc, sqList& La, sqlist& Lb) ∥l由La和Lb归并产生新的整数表Lc,La和Lb保持不变。 i int i=1, j=1, m=La Size, n=Lb Size int a, b: bool astrue. GetNode(La,a);∥取La表指针所指元素存入a Getnode(Lbb);∥取Lb表指针所指元素存入b while(i<=m & j<=n & r) ∥La和Lb表均没到表尾且插入Lc正常则进入循环体
显然，指针i和j的初值均为1，在所指元素插入Lc之 后，在La或Lb中顺序后移。 此算法执行后整数表La和Lb保持不变。 Bool Merge(sqList& Lc,sqList& La,sqList& Lb) // 由La和Lb归并产生新的整数表Lc，La和Lb保持不变。 { int i=1, j=1, m=La.Size, n=Lb.Size; int a, b; bool r=true; GetNode(La,i,a); // 取La表指针i所指元素存入a GetNode(Lb,j,b); // 取Lb表指针j所指元素存入b while(i<=m && j<=n && r) // La和Lb表均没到表尾且插入Lc正常则进入循环体
if(a<=b)∥La表所指元素较小,将其插入Lc表,指针后移 I rlnsertNode Lc, a, LC Size+1); GetNode La, ++i, a) else∥Lb表所指元素较小,将其插入Lc表,指针后移 irEInsertNode (Lc, b, LC Size+ 1) GetNode( lb, ++j, b) ∥下面两个whie循环有且仅有一个被执行 whle(i<=m)∥将La表中剩余元素插入Lc GetNode ( La, i++, a); r=InsertNode(Lc, a, Lc size+1)
if(a<=b) // La 表所指元素较小，将其插入 Lc 表，指针I 后移 { r=InsertNode(Lc,a, Lc.Size+1); GetNode(La,++i,a); } else // Lb表所指元素较小，将其插入Lc表，指针j后移 { r=InsertNode(Lc,b, Lc.Size+1); GetNode(Lb,++j,b); } // 下面两个while循环有且仅有一个被执行 while(i<=m) // 将La表中剩余元素插入Lc { GetNode(La,i++,a); r=InsertNode(Lc,a,Lc.Size+1); }