有序表的合并
已知线性表La 和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。
La=(1 ,7, 8)
Lb=(2, 4, 6, 8, 10, 11)
Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11)
0.新建一个链表
新建一个空表C，直接在A和B中每次选取最小值插入到C中，复杂度O(A.length+B.length)，但是需要新开辟一个空表比较占用内存。
void MergeList_Sq(SqList LA,SqList LB,SqList &LC){ pa = LA.elem; pb = LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素 LC.length = LA.length+LB.length; //新表长度为待合并两表的长度之和 LC.elem = new ElemType[LC.length]; //为合并后的新表分配一个数组空间 pc = LC.elem; //指针pc指向新表的第一个元素 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){ //两个表都非空 if(*pa <= *pb) *pc++ = *pa++; //依次“摘取”两表中值较小的结点 else *pc++ = *pb++; } //此时a,b 之中一定有一个表为空 while(pb <= pb_last) *pc++ = *pb++; //LB表已到达表尾 while(pa <= pa_last) *pc++ = *pa++; //LA表已到达表尾 }//MergeList_Sq
1.直接合并
只建一个新结点，相当于尾插法的end尾结点，而不是创建一个新链表，结点Pc每次指向A/B中最小值的结点，把两个链表连在一起（B连到A上面），不需要新开辟一个链表浪费空间，时间复杂度和上面的一样，都是暴力循环。
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ pa=La->next; pb=Lb->next; pc=Lc=La; //用La的头结点作为Lc的头结点 while(pa && pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb; pc=pb; pb=pb->next;} pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点}