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

/**
* 含头节点单链表定义及基本操作 
*/

//基本操作函数用到的状态码 
#define TRUE 1;
#define FALSE 0;
#define OK 1;
#define ERROR 0;

//Status函数返回值类型
typedef int Status; 
//数据元素类型
typedef int ElemType;
//单链表定义
typedef struct Lnode {
    ElemType data;        //数据域
    struct Lnode *next;    //指针域
} Lnode, *LinkList;


//基本操作1：单链表初始化 
Status InitList(LinkList *list) { 
    (*list)=(LinkList)malloc(sizeof(Lnode));
    (*list)->next=NULL;
    return OK;
}

//基本操作11：头插法建立链表，数据保存在ElemType类型的数组中 
Status CreateList_H(LinkList *list,ElemType arrData[],int length) {
    int j;
    for(j=length-1;j>=0;j--){
        //新建结点 
        Lnode *node;
        node=(Lnode*)malloc(sizeof(Lnode));
        node->data=arrData[j];
        node->next=NULL;
        //插入为1号结点 
        node->next=(*list)->next;
        (*list)->next=node;
    }
    return OK;
}

//基本操作13：链表元素遍历输出
Status ListTraverse(LinkList list) {
    Lnode *p;
    p=list;
    int j=0;
    printf("序号：    结点数据：\n");
    while(p->next){
        j++;
        p=p->next;
        printf(" (%d)          %d\n",j,p->data);
    }
    return OK;
}

//有序表合并，顺序表实现。pa,pb分别指向listA,listB首元,pc指向新链表表尾
Status MergeList(LinkList *listA,LinkList *listB) {
    Lnode *pa,*pb,*pc;
    pa=(*listA)->next;
    pb=(*listB)->next;
    pc=*listA;
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        } else {
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
    //插入剩余表段
    pc->next=pa?pa:pb;
    //释放listB头结点
    free(*listB);
    return OK;
}

//线性表合并，顺序表实现。pa,pb分别指向listA,listB首元
Status UnionList(LinkList *listA,LinkList *listB){
    Lnode *pa,*pb;  //ra将指向listA尾结点
    pa=(*listA);
    pb=(*listB);
    
    while(pb->next){
        ElemType data=pb->next->data;
        while(pa->next&&pa->next->data!=data){
            pa=pa->next;
        }
        if(pa->next&&pa->next->data==data){  //listA中有目标元素
            Lnode *needDelete=pb->next;
            pb->next=needDelete->next;
            free(needDelete);  //释放listB中的该结点
        } else {
            Lnode *needInsert=pb->next;  //pb->next指向当前结点
            //将该结点接入listA尾
            pa->next=needInsert;  //此时pa为listA的尾指针
            pb->next=pb->next->next;
            needInsert->next=NULL;  //listA的 最后结点->next 置空
        }
        pa=(*listA)->next;
    }
    free(*listB);  //释放listB头结点
    return OK;
}

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

int main(void){
    //定义链表
    LinkList list1,list2,list3,list4;
    
    //链表初始化
    InitList(&list1);
    InitList(&list2);
    InitList(&list3);
    InitList(&list4);
    
    //创建链表
    ElemType waitInserted1[]={1,7,8,};
    ElemType waitInserted2[]={2,4,6,8,10,11,};
    ElemType waitInserted3[]={1,7,8,};
    ElemType waitInserted4[]={2,4,6,8,10,11,};
    int arrLength1=sizeof(waitInserted1)/sizeof(waitInserted1[0]);
    int arrLength2=sizeof(waitInserted2)/sizeof(waitInserted2[0]);
    int arrLength3=sizeof(waitInserted3)/sizeof(waitInserted3[0]);
    int arrLength4=sizeof(waitInserted4)/sizeof(waitInserted4[0]);
    CreateList_H(&list1,waitInserted1,arrLength1);
    CreateList_H(&list2,waitInserted2,arrLength2);
    CreateList_H(&list3,waitInserted3,arrLength3);
    CreateList_H(&list4,waitInserted4,arrLength4);
    
    /*
    printf("\nlist1：\n");
    ListTraverse(list1);
    printf("\nlist2：\n");
    ListTraverse(list2);
    printf("\nlist3：\n");
    ListTraverse(list4);
    printf("\nlist3：\n");
    ListTraverse(list4);
    */
    
    //有序表合并
    MergeList(&list1,&list2);
    printf("\nlist1：(与list2经过有序表合并后)\n");
    ListTraverse(list1);  //遍历测试
    
    //线性表合并
    UnionList(&list3,&list4);
    printf("\nlist3：(与list4经过线性表表合并后)\n");
    ListTraverse(list3);  //遍历测试
    
    printf("\nEND");
    return 0;
}