一、线性表的合并
例1 求解一般集合的并集问题
【问题描述】
已知两个集合A和B，现要求一个新的集合A=AUB。例如，设
A=(7,5,3,11)
B=(2,6,3)
合并后
A=(7,5,3,11,2,6)
【问题分析】
可以利用两个线性表LA和LB分别表示集合A和B(即线性表中的数据元素为集合中的成员)，这样只需扩大线性表LA，将存在于LB-中而不存在于LA中的数据元素插入到LA中去。只要从LB中依次取得每个数据元素，并依值在LA中进行查访，若不存在，则插入之。
上述操作过程可用算法2.15来描述。具体实现时既可采用顺序形式，也可采用链表形式。
算法1 线性表的合并
【算法步骤】
① 分别获取LA表长m和LB表长n
② 从LB中第1个数据元素开始，循环n次执行以下操作：
- 从LB中查找第i(1≤i≤n)个数据元素赋给e
- 在LA中查找元素e，如果不存在，则将e插在表LA的最后
【算法描述】
void MergeList(List &LA, List LB) { //将所有在线性表LB中但不在LA中的数据元素插入到LA中 m=ListLength(LA) ;n=ListLength(LB); //求线性表的长度 for( i=1;i<=n;i++) { GetElem( LB,i,e); //取LB中第i个数据元素赋给e if (!LocateElem(LA,e)) //LA中不存在和e相同的数据元素 ListInsert(LA,++m,e); //将e插在LA的最后 } }
【算法分析】
上述算法的时间复杂度取决于抽象数据类型List定义中基本操作的执行时间，假设LA和LB的表长分别为m和n，循环执行n次，则：
当采用顺序存储结构时，在每次循环中，GetElem和ListInsert这两个操作的执行时间和表长无关，LocateElem的执行时间和表长m成正比，因此，算法1的时间复杂度为O(m×n)。
当采用链式存储结构时，在每次循环中，ListInsert的执行时间和表长无关，GetElem的执行时间和表长n成正比，LocateElem的执行时间和表长m成正比，因此，若假设m大于n，算法2.15的时间复杂度也为O(m×n)。
二、有序表的合并
若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列,则称该线性表为有序表(Ordered List)。
例2 求解有序集合的并集问题
【问题描述】
有序集合是指集合中的元素有序排列。已知两个有序集合A和B，数据元素按值非递减有序排列，现要求一个新的集合C=AUB，使集合C中的数据元素仍按值非递减有序排列。例如，设
A=(3,5,8,11)
B =(2,6,8,9,11,15,20)
则
C =( 2,3,5,6,8,8,9,11,11,15,20)
【问题分析】
与例1一样，可以利用两个线性表LA和LB分别表示集合A和B，不同的是，此例中的LA和LB有序，这样便没有必要从LB中依次取得每个数据元素，到LA中进行查访。
如果LA和LB两个表长分别记为m和n，则合并后的新表LC的表长应该为m+n。由于LC中的数据元素或是LA中的元素，或是LB中的元素，因此只要先设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。为使LC中的元素按值非递减有序排列，可设两个指针pa 和pb分别指向LA和LB中的某个元素，若设pa当前所指的元素为a， pb当前所指的元素为b，则当前应插入到LC中的元素c为
显然，指针pa和pb的初值分别指向两个有序表的第一个元素，在所指元素插入LC之后，在LA或LB中顺序后移。
根据上述分析，分别给出有序表的顺序存储结构和链式存储结构相应合并算法的实现。
1、顺序有序表的合并
算法2 顺序有序表的合并
【算法步骤】
① 创建一个表长为m+n的空表LC。
② 指针pc初始化，指向LC的第一个元素。
③ 指针pa和pb初始化，分别指向LA和LB的第一个元素。
④ 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
⑤ 如果pb已到达LB的表尾，依次将LA的剩余元素插入LC的最后。
⑥ 如果pa已到达LA的表尾，依次将LB的剩余元素插入LC的最后。
【算法描述】
void MergeList_Sq(SqListLA,SqListLB,SqList&LC) { //已知顺序有序表LA和LB的元素按值非递减排列 //归并LA和LB得到新的顺序有序表LC，LC的元素也按值非递减排列 LC. length=LA. length+LB. length; //新表长度为待合并两表的长度之和 LC. elem=new ElemType[LC. length]; //为合并后的新表分配一个数组空间 pc=LC. elem; //指针pc指向新表的第一个元素 pa=LA. elem;pb=LB. elem; //指针pa和pb的初值分别指向两个表的第一个元素 pa_last=LA. elem+LA. length-1; //指针 pa_last 指向LA的最后一个元素 pb_last=LB. elem+LB. length-1; //指针 pb_last 指向LB的最后一个元素 while(( pa<= pa_last)&&( pb<= pb_last))⁶//LA和LB均未到达表尾 { if(⋆pa<=⋆pb)⋆pc++=⋆pa++; //依次“摘取”两表中值较小的结点插入到LC的最后 else⋆pc++=⋆pb++; } while( pa<= pa_last) *pc++=*pa++; //LB已到达表尾，依次将LA的剩余元素插入LC的最后 while( pb<= pb_last) *pc++=* pb++;//LA已到达表尾,依次将LB的剩余元素插入LC的最后 }
【算法分析】
若对算法2中第一个循环语句的循环体做如下修改：分出元素比较的第三种情况，当*pa=*pb时，只将两者中之一插入LC，则该算法完成的操作和算法2.15相同，但时间复杂度却不同。在算法2.16中，由于LA和LB中元素依值非递减，则对LB中的每个元素，不需要在LA中从表头至表尾进行全程搜索。如果两个表长分别记为m和n，则算法2.16循环最多执行的总次数为m+n。所以算法的时间复杂度为O(m+n)。
此算法在归并时，需要开辟新的辅助空间，所以空间复杂度也为O(m+n)，空间复杂度较高。利用链表来实现上述归并时，不需要开辟新的存储空间，可以使空间复杂度达到最低。
2、链式有序表的合并
假设头指针为LA和LB的单链表分别为线性表LA和LB的存储结构，现要归并LA和LB得到单链表LC。因为链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需把LA和LB两个表中的结点重新进行链接即可。
按照例2给出的合并思想，需设立3个指针pa、pb和pc，其中pa和pb分别指向LA和LB中当前待比较插入的结点，而pc指向LC中当前最后一个结点(LC的表头结点设为LA的表头结点)。指针的初值为：pa和pb分别指向LA和LB表中的第一个结点， pc指向空表LC中的头结点。同算法2一样，通过比较指针pa和pb所指向的元素的值，依次从LA或LB中“摘取”元素值较小的结点插入到LC的最后，当其中一个表变空时，只要将另一个表的剩余段链接在pc所指结点之后即可。
算法3 链式有序表的合并
【算法步骤】
① 指针pa和pb初始化，分别指向LA和LB的第一个结点。
② LC的结点取值为LA的头结点。
③ 指针pc初始化，指向LC的头结点。
④ 当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
⑤ 将非空表的剩余段插入到pc所指结点之后。
⑥ 释放LB的头结点。
【算法描述】
void MergeList_L(LinkList&LB,LinkList&LA,LinkList&LC) { //已知单链表LA和LB的元素按值非递减排列 //归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列 pa=LA->next;pb=LB->next; //pa和pb的初值分别指向两个表的第一个结点 LC=LA; //用LA的头结点作为LC的头结点 pc=LC; //pc的初值指向LC的头结点 while(pa&&pb) { //LA和LB均未到达表尾，依次“摘取”两表中值较小的结点插入到LC的最后 if(pa->data<=pb->data) //“摘取”pa所指结点 { pc->next=pa; //将pa所指结点链接到pc所指结点之后 pc=pa; //pc指向pa pa=pa->next; //pa指向下一结点 } else //“摘取”pb所指结点 { pc->next=pb; //将pb所指结点链接到pc所指结点之后 pc=pb; //pc指向pb pb=pb->next; //pb指向下一结点 } } //while pc->next=pa? pa:pb; //将非空表的剩余段插入到pc所指结点之后 delete LB; //释放LB的头结点 }
【算法分析】
可以看出，算法2.17的时间复杂度和算法2.16相同，但空间复杂度不同。在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新按元素值非递减的关系将所有结点链接成一个链表即可，所以空间复杂度为O(1)。
原文地址：http://www.cnblogs.com/Santariki/p/16814440.html
