/*【例2-3】有两个顺序表 A 和 B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表 C，要求 C 的元素也是从小到大排列。
算法的时间复杂度是O(A.length + B.length)*/

//顺序表的建立
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>


#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;

typedef struct std_info
{
    long int num;
    char name[8];
    float score;
} ElemType;

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct
{
    ElemType *elem;
    int length;
    int listsize;
} Sqlist;

int n;

/*定义功能选择菜单函数*/
void print()
{
    printf("----线性表（顺序结构）的基本操作----\n");
    printf("----------开始----------\n");
}
/*打印线性表（顺序结构）*/
void printout(Sqlist  *L)
{
    int  i;
    for(i=1; i<=L->listsize; i++)
        printf("   [%d]", i);
    printf("\n");
    for(i=0; i<L->listsize; i++)
        printf("%6d", L->elem[i]);
    printf("\n");
}

//初始化一个顺序表
Status InitList_sq(Sqlist&L)
{
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); //what does it mean?
    if (!L.elem)
        exit(OVERFLOW);
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
}
/*02创建线性表（顺序结构）*/
void  creatlist_sq(Sqlist *L)
{
    int   i;
    int tmp;
    printf("请输入线性表中数据的个数：");
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        printf("data[%d]=", i);
        fflush(stdin);         /*清除掉键盘缓冲区*/
        scanf ("%d", &tmp);
        (L->elem[i]).num = tmp;
    }
    L->length=n;
}

/* 合并顺序表 */
// 已知顺序线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。
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;
    pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
    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).score<=(*pb).score)//错这里了！！！！！！！
            *pc++=*pa++;
        else
            *pc++=*pb++;
    }
    while(pa<=pa_last) *pc++=*pa++;
    while(pb<=pb_last) *pc++=*pb++;
}

void sortlist(Sqlist *L)
{
    int i,j,k;
    for (j=0; j<L->length-1; j++)
    {
        for(i=0; i<L->length-1-j; i++)
        {
            if( (L->elem[i]).num > (L->elem[i+1]).num )
            {
                k=(L->elem[i]).num;
                (L->elem[i]).num=(L->elem[i+1]).num;
                (L->elem[i+1]).num=k;
            }
        }
    }
}

void main()
{
    Sqlist La,Lb,Lc;
    int i;
    if(InitList_sq(La))
    {
        printf("输入顺序表La:\n");
        for(i=0; i<5; i++)
        {
            scanf("%d",&La.elem[i]);
            La.length++;
        }
        sortlist(&La);
    }
    if(InitList_sq(Lb))
    {
        printf("输入顺序表Lb:\n");
        for(i=0; i<5; i++)
        {
            scanf("%d",&Lb.elem[i]);
            Lb.length++;
        }
        sortlist(&Lb);
    }
    MergeList_sq(La,Lb,Lc);
    for(int j=0; j<Lc.length; j++)
    {
        printf("输出顺序表Lc:\n");
        printf("%d ",Lc.elem[j].num);
    }
    printf("\n");


}