#include <stdio.h>
#include <stdlib.h>

//基本操作函数用到的状态码 
#define TRUE 1;
#define FALSE 0;
#define OK 1;
#define ERROR 0;
#define INFEASIBLE -1;
const int OVERFLOW = -2;
const int MaxSize = 1000;  //表中数据元素的最大数量

typedef int Status; 
typedef int ElemType;
//顺序表定义
typedef struct {
    ElemType *elem;
    int length;
} SqList; 

//顺序表初始化
Status InitList(SqList *list) {
    list->elem=(ElemType*)malloc(sizeof(ElemType)*MaxSize);
    if(!list->elem) {
        return OVERFLOW;
    };
    list->length=0;
    return OK;
};

//顺序表遍历
Status ListTraverse(SqList list){
    int j;
    printf("序号：\t元素值：\n");
    for(j=0;j<list.length;j++){
        printf(" (%d)\t\t %d\n",j+1,list.elem[j]);
    }
    return OK;
}

//初始list创建
Status CreateList(SqList *list,ElemType arrData[],int length){
    int j;
    for(j=0;j<length;j++){
        list->elem[j]=arrData[j];
    }
    list->length=length;
    return OK;
}

//基本操作4：求线性表长
int GetLength(SqList list) {
    if(list.elem){ //线性表存在 
        return list.length;
    };
    return ERROR;
}

//基本操作6：根据结点索引i获取相应位置元素的内容 
Status GetElem(SqList list,int i,ElemType *elem){
    if(i<1||i>list.length) {
        return ERROR;
    } else { 
        *elem=list.elem[i-1];
        return OK;
    }
} 

//基本操作7：查找与目标元素值相同的元素结点，返回逻辑下标 ，若不存在，返回0 
int LocateElem(SqList list,ElemType elem){
    int i;
    for(i=0;i<list.length;i++){
        if(list.elem[i]==elem) return i+1;
    }
    return 0;
}

//基本操作8：插入结点元素到指定位置。(i为逻辑位置) 
Status ListInsert(SqList* list,int i,ElemType elem){
    if(i<1||i>list->length+1) return ERROR;
    if(list->length==MaxSize) return OVERFLOW;
    int j;
    for(j=list->length-1;j>=i-1;j--){
        list->elem[j+1]=list->elem[j];
    }
    list->elem[i-1]=elem;
    list->length++;
    return OK;
}


//有序表合并，顺序表实现,pa,pb,pc分别指向两表第一个元素
Status MergeList(SqList listA,SqList listB,SqList *listC) {
    //由listA和listB长度初始化listC
    listC->length=listA.length+listB.length;
    listC->elem=(ElemType*)malloc(sizeof(ElemType)*(listC->length));
    ElemType *pa,*pb,*pc,*pa_last,*pb_last;
    pa=listA.elem;
    pb=listB.elem;
    pc=listC->elem;
    
    //获得listA、listB尾指针
    pa_last=pa+listA.length-1;
    pb_last=pb+listB.length-1;
    //合并操作
    while(pa<pa_last&&pb<pb_last){
        if(*pa<*pb){
            *pc=*pa;
            *pa++;
        } else {
            *pc=*pb;
            *pb++;
        }
        *pc++;
    }
    while(pa<=pa_last){
        *pc=*pa;
        *pa++;
        *pc++;
    }
    while(pb<=pb_last){
        *pc=*pb;
        *pb++;
        *pc++;
    }
    return OK;
}

//线性表合并，顺序表实现
Status UnionList(SqList *listA,SqList listB){
    int la_len=GetLength(*listA);
    int lb_len=GetLength(listB);
    int j;
    //遍历listB中的元素与listA元素比较
    for(j=1;j<=lb_len;j++){
        ElemType e;
        GetElem(listB,j,&e);
        if(!LocateElem(*listA,e)){
            la_len++;
            ListInsert(listA,la_len,e);
        }
    }
    return OK;
}

/**
 * 已知线性表:
 * list1=(1,7,8),list2=(2,4,6,8,10,11)
 * 有序表合并:(这里为两个非递减线性表list1,list2;合并为一个非递减线性表list3);
 * 则:list3=(1,2,4,6,7,8,8,10,12)
 * 线性表合并:(合并结果放入list1，“list1 并= list2”)
 * 则新的:list1=(1,7,8,2,4,6,10,11)
 */

int main(void){
    //定义一个线性表 
    SqList list1,list2,list3;
    //初始化 
    InitList(&list1); 
    InitList(&list2); 
    
    //list1、list2创建
    ElemType waitInserted1[]={1,7,8,};
    ElemType waitInserted2[]={2,4,6,8,10,11};
    int arrLength1=sizeof(waitInserted1)/sizeof(waitInserted1[0]);
    int arrLength2=sizeof(waitInserted2)/sizeof(waitInserted2[0]);
    CreateList(&list1,waitInserted1,arrLength1);
    CreateList(&list2,waitInserted2,arrLength2);
    
    printf("\nlist1：\n");
    ListTraverse(list1);
    printf("\nlist2：\n");
    ListTraverse(list2);
    
    //有序表合并:
    MergeList(list1,list2,&list3);
    printf("\nlist3：\n");
    ListTraverse(list3);
    
    //线性表合并:
    UnionList(&list1,list2);
    printf("\n新list1：\n");
    ListTraverse(list1);
    
    return 0;
}