问题 :
●假设有两个有序表 LA和LB , 将他们合并成一个有序表LC
●要求不破坏原有的表 LA和 LB
【合并有序表】LA : 1 , 3 , 5
LB : 2,4,8,20
构思:
把这两个表, 合成一个有序表 , 不是简简单单吗 ?
就算是把他们先遍历不按顺序插入到表 C里面 , 然后再排序 ,就行了,
这个的确是最笨的办法 , 但是也能完成
题目上 ,给出的是这两个表都是有序表 , 所以就省去了 ,我们遍历所有节点排序的麻烦 , 那我们
也不能拿一个表进行强行插入, 题目上也不允许,
我们干脆假设 这两个列表是两幅卡片 , 我们都从第一张开始那,左手一直拿 A , 右手一直拿 B
对比这两个卡片 ,哪个小就先装到 LC ,装进去之后,如果是左手卡片小,就装到 Lc , 然后再拿一张A里面的卡片 ,再和右手对比 ,我们这样比较的前提是 ,这两个表里面的元素都是从小到大顺序排列的 ,
这样 LC 就不会出现需要插入的情况 ,如果一副卡片放完了,另一幅如果还有 ,那剩余的卡片一定是大的 ,直接放在 LC 后面就行了
至于我们用顺序表来存储LC ,还是用链表来存储LC, 基本思路还是一样的,操作有些许差别罢了
我们用这种交替的比较两个有序表 ,然后排序的好处是,空间复杂度低, 时间复杂度也低 ,
我们有的同学会有疑问, 难道交叉比较, 不会出现错乱吗?
答案是不会的 ,因为这两个表本身就是有序表 , 然后我们插入Lc之前 , 会让两个列表中小的进行插入 , 然后后面该插入的元素, 因为是有序表,所以都大于前面的元素 . 这就保证了插入的有序性.
下面开始实操: 采用顺序表存放有序表时的归并算法:
我们要将两个有序表的元素进行比较, 就需要各有一个指针指向有序表 , 然后再进行比较 ,
两个指针比较, 小的元素插入到 LC 里面 , 插入完元素的指针向后移动 .
由于两个有序表的长度不同 , 所以交替插入有三种情况 :
●LA 和 LB均未到达末尾时,泽其小优先尾插
●LB已经扫描插入完了, LA尚未扫描插入完 , 将其余元素插入到 Lc中
●LB尚未扫描插入完 , 将其余元素插入到 Lc中
我们先传入 LA 和 LB , 建立的LC
void ( *LA,*LB ,*&LC){
然后,如何判断 LA和LB有没有扫描插入完呢?
我们是根据指针指向两个有序表元素的 , 所以比较指针遍历的元素个数 和 表长度 就可以得出那个表有没有遍历完
所以,先定义指向两个列表的指针
int i = 0 , j=0 , k=0; //LA 插入的数组位序 ,LB插入的数组位序 , LC插入的坐标位序
因为列表是数组 , 所以次指针非彼指针 , 这是比较元素的位序
申请 LC 的空间
LC = ( *)(());
所以我们要进行上面三种情况的处理 :
//LA 和 LB 均未到达末尾时,泽其小优先尾插
while( && ){ 交替插入元素}
//LB已经扫描插入完了, LA尚未扫描插入完 , 将其余元素插入到 Lc中
while(){ 把A中剩余的元素全插入到LC}
//LB尚未扫描插入完 , 将其余元素插入到 Lc中
while(){ 把B中剩余的元素全插入到LC}
然后就把C的长度更新一下就行了\
开始代码实现:
void UnionList(SqList *LA , SqList *LB , SqList *&LC){int i=0; //LA的坐标位序int j=0; //LB的坐标位序int k=0; //LC的坐标位序LC = (SqList *)malloc(sizeof(SqList));//为表C分配空间//LA和LB 均未到达末尾 ,选择小的加入LCwhile(ilength && jlength){if(LA->data[i] < LB ->data[j]){LC->data[k] = LA ->data[i];i++; //相应的LA指针也向后移动k++; //元素加一,位序后移}else//LA->data[i]>= LB->data[j] ,交替比较无所谓的,反正小的会在前面 {LC->data[k] = LB->data[j];j++; //相应的LB指针也向后移动k++; //元素加一,位序后移}}//下面两步最多进行一步://经过上一轮循环插入,LB已经扫描插入完了, LA尚未扫描插入完 , 将LA其余元素插入到 Lc中while(i