#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
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;
}
int ListLength(SqList L)
{
    return L.length;
}

Status GetElem(SqList L,int i,ElemType *e)
{
    if(i<1 || i>L.length)
        exit(ERROR);
    *e=*(L.elem+i-1);
    return OK;
}

Status ListInsert(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 Visit(ElemType *c)
{
    printf("%d ",*c);
    return OK;
}

Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        Visit(L.elem+i);
    printf("\n");
    return OK;
}


void MergeList(SqList La,SqList Lb,SqList *Lc) //歸并線性表La和Lb得到新的線性表Lc,Lc的數據元素安置遞減排列
{
    int i=1,j=1,k=0;
    int La_len,Lb_len;
    ElemType ai,bj;
    InitList_Sq(Lc);
    La_len=ListLength(La);
    Lb_len=ListLength(Lb);
    while((i<=La_len) && (j<=Lb_len)) //如果表La和表Lb都非空
    {
        GetElem(La,i,&ai);
        GetElem(Lb,j,&bj);
        if(ai<=bj)
        {
            ListInsert(Lc,++k,ai); ++i;
        }
        else
        {
            ListInsert(Lc,++k,bj); ++j;
        }
    }

    while(i<=La_len)  //如果只有La非空
    {
        GetElem(La,i++,&ai);
        ListInsert(Lc,++k,ai);
    }

    while(j<=Lb_len)
    {
        GetElem(Lb,j++,&bj);
        ListInsert(Lc,++k,bj);
    }
}
int main()
{
    SqList La,Lb,Lc;
    int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
    InitList_Sq(&La);
    for(j=1;j<=4;j++)
        ListInsert(&La,j,a[j-1]);
    printf("print La: \n");
    ListTraverse(La);
    
    InitList_Sq(&Lb);
    for(j=1;j<=7;j++)
        ListInsert(&Lb,j,b[j-1]);
    printf("print Lb: \n");
    ListTraverse(Lb);

    MergeList(La,Lb,&Lc);

    printf("print Lc: \n");
    ListTraverse(Lc);

    return 0;
}