非递减有序顺序表的合并

/*问题描述:已知两个有序集合A和B,数据元素按值非递减有序排列,现要求
一个新的集合C=A∪B,使集合C中数据元素仍按值非递减有序排列
//搬点以前写的记录一下

[分析]:无序表LA,LB所以无需遍历LB,设LC为空表
用两个头指针pa,pb遍历两表将小值插入LC并++,最后多余数据表直接补在LC后面
设表长分别为m,n,时间复杂度为○(m+n),最糟的情况不过LA的元素都大于LB,LB表长大于LA
这样导致循环次数达到最大m+n
*/
#include<stdio.h>
#include<iostream.h>//流
#include<malloc.h>
#include<cstdlib>//包含exit头文件
#include<math.h>
#include<string.h>
#define OK 1
#define ERROR 0
#define LENGTH_A 2
#define LENGTH_B 4
#define LENGTH_C LENGTH_A+LENGTH_B
typedef int Status;
typedef struct 
{
 int *elem;//储存空间的基地址0,类似于数组了~
 int length;
}SqList;//逻辑关系 顺序地址表示
Status InitList(SqList &L,int length)
{
 L.elem=(int *)malloc(length*sizeof(int));//数组的第一个元素的首地址,一个数组空间
 if(!L.elem) exit(OVERFLOW);
 L.length=0;
 return OK;
}

Status ListGetvalue(SqList &L,int length)
{//测试用
for(int i=0;i<length;i++) 
{
int a;
cout<<"请输入编号"<<endl;
cin>>a;
L.elem[i]=a;
L.length++;
}
return OK;
}

int MergeList_Sq(SqList &LA,SqList &LB,SqList &LC)
{
LC.elem=(int *)malloc(LENGTH_C*sizeof(int));
int *pa,*pb,*pc,*pa_last,*pb_last;
pa=LA.elem;//指向数组的第一个元素
pb=LB.elem;
pc=LC.elem;
pa_last=pa+LENGTH_A-1;
pb_last=pb+LENGTH_B-1;
while((pa<=pa_last)&&(pb<=pb_last))
{
if(*pa<=*pb) 
{
*pc++=*pa++;
LC.length++;
}else
{
*pc++=*pb++;
LC.length++;
}

}
while(pa<=pa_last)
{
*pc++=*pa++;//等号必须有,进行到最后一个的时候pa,pb均后置++
//此时min(pa,pb)>min(pa,pb)_last,但是另一个表的长度首尾指针是有可能相等的
LC.length++;
}
while(pb<=pb_last)
{
*pc++=*pb++;
LC.length++;
}
return LC.length;
} 
Status ListShow(SqList L)
{
for(int i=0;i<L.length;i++)
{
cout<<L.elem[i]<<endl;
}
return OK;
}
void main()
{
SqList *LA,*LB,*LC;
LA=(SqList *)malloc(sizeof(SqList));
LB=(SqList *)malloc(sizeof(SqList));
LC=(SqList *)malloc(sizeof(SqList));
InitList(*LA,LENGTH_A);//传递表本身,并不是表的地址,所以是*L;
InitList(*LB,LENGTH_B);
InitList(*LC,LENGTH_C);
cout<<"LA赋值"<<endl;
ListGetvalue(*LA,LENGTH_A);
cout<<"LB赋值"<<endl;
ListGetvalue(*LB,LENGTH_B);

MergeList_Sq(*LA,*LB,*LC);
cout<<"合并后的LC"<<endl;
ListShow(*LC);
system("pause");
}

//# 利用有序表的顺序存储结构合并两张表 #

;