如何用c语言编合并两个线性表的程序

最简单的想法是从B中取出一个数，然后插入A中；再从B中取出一个数……,
不过这样做的效率有点低。

#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define Compare( a, b) ( ((a) == (b)) ? (1) : (0) )
typedef int ElemType;
typedef int Status;
typedef struct{
ElemType *elem;
int length;
int listsize;
}Sqlist;
Status InitList_Sq(Sqlist *L) {
L->elem = (ElemType *) malloc (LIST_INIT_SIZE * sizeof(ElemType) );
if(!L->elem) exit( OVERFLOW );
L->length=0;
L->listsize = LIST_INIT_SIZE;
return OK;
}
Status ListInsert_Sq ( Sqlist *L, int i, ElemType e ){
ElemType *newbase, *p, *q;
if(i<1 || i>L->length+1) return ERROR;
if(L->length >= L->listsize) {
newbase = (ElemType *)realloc(L->elem, (L->listsize+LISTINCREMENT)*sizeof(ElemType) );
if(!newbase) exit(OVERFLOW);
L->elem = newbase;
L->listsize += LISTINCREMENT;
}
q = &(L->elem[i-1]);
for( p = &(L->elem[L->length-1]); p >= q; --p)
*(p+1)=*p;
*q = e;
++L->length;
return OK;
}
Status ListDisplay(Sqlist A){
int i=0;
while(i < A.length) {
printf("%5d", A.elem[i]);
i++;
}
}
void Mergelist_Sq(Sqlist La, Sqlist Lb, Sqlist *Lc) {
ElemType *pa, *pb, *pc, *pa_last, *pb_last;
pa = La.elem;
pb = Lb.elem;
Lc->listsize = Lc->length = La.length + Lb.length;
Lc->elem = (ElemType*) malloc (Lc->listsize * sizeof(ElemType));
pc = Lc->elem;
if(!Lc->elem) exit(OVERFLOW);
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while( pa <= pa_last && pb <= pb_last) {
if(*pa <= *pb) *pc++ = *pa++;
else *pc++ = *pb++;
}
while(pa <= pa_last) *pc++ = *pa++;
while(pb <= pb_last) *pc++ = *pb++;
}
void INSERTION_SORT(Sqlist *A)
{
int i, j, key;//key 是关键字，从j开始的部分，是未排序的部分；i 则代表已排序数组最后元素的数组下标
for(j = 1; j != A->length; j++) {
key = A->elem[j];
i = j - 1;
while( i >= 0 && A->elem[i] > key ) {
A->elem[i+1] = A->elem[i];
--i;
}
A->elem[i+1] = key;
}
}
int main( void ) {
int e, i, a, b;
Sqlist A, B, C;
InitList_Sq(&A);
InitList_Sq(&B);
printf("请输入第一个表结点数：");
scanf("%d", &a);
for(i=0; i< a; i++){
printf("请输入第%d个数\n", i+1);
scanf("%d", &e);
ListInsert_Sq(&A,i+1,e);
}
ListDisplay(A);
printf("\n请输入第二个表结点数：");
scanf("%d", &a);
for(i=0; i< a; i++){
printf("请输入第%d个数\n", i+1);
scanf("%d", &e);
ListInsert_Sq(&B,i+1,e);
}
ListDisplay(B);
printf("\n");
INSERTION_SORT(&A);
INSERTION_SORT(&B);
ListDisplay(A);
printf("\n");
ListDisplay(B);
printf("\n两个表的合并：\n");
Mergelist_Sq(A, B, &C);
ListDisplay(C);
printf("\n");
system("PAUSE");
}
/*当两个顺序表合并的时候，最大的问题，可能不是合并本身，而是合并前的排序 ,考虑到
了了们的水平有限，这里就使用了比较简单的插入排序。*/
//这里只有顺序表的合并，有需要的话，我会把链表的合并也写一下