一、顺序表

利用顺序存储结构合并有序表， 需要依次从两个有序表中取出一个元素进行比较，将较小的元素放入第三个表中，最后输出第三个表，就是合并后的有序表了。

1.1 初始化顺序表

int Init_List(PList L){
    L->data=(int *)malloc(sizeof(int)*SIZE);   //初始化动态分配内存
    L->len=0;      //初始化表长为空
    L->size=SIZE;
    return 1;
}

1.2 创建顺序表

int Creat_List(PList L){
    int e,i=0;
    while(scanf("%d",&e)==1){
        if(L->len>=L->size){     //当前顺序表超长时要重新分配空间
            L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
            L->size+=INCREAM;
        }
        L->data[i++]=e;
        L->len++;
    }
    return 1;
}

1.3 合并两个有序表

int Connect_List(PList L1,PList L2,PList L3){
    int i=0,j=0,k=0;
    if(L1->len+L2->len>L3->size){    //合并有序表要先判断两者长度和是否大于第三个表
        L3->data=(int *)realloc(L3->data,(L3->size+INCREAM)*sizeof(int));
        L3->size+=INCREAM;
    }
    while(i<L1->len&&j<L2->len){     //循环判断
        if(L1->data[i]==L2->data[j]){
            j++;    
        }else if(L1->data[i]<L2->data[j]){    //将较小元素放入第三个顺序表
            L3->data[k++]=L1->data[i++];
        }else{
            L3->data[k++]=L2->data[j++];
        }
    }
    while(i<L1->len){              //将另一个未空的顺序表剩余元素放入第三个顺序表
        L3->data[k++]=L1->data[i++];    
    }
    while(j<L2->len){
        L3->data[k++]=L2->data[j++];
    }
    L3->len=k;     //最后别忘了第三个顺序表的长度
    return 1;
}

1.4 完整代码

#include<stdio.h>
#include<malloc.h>
#define SIZE 10
#define INCREAM 10
typedef struct List{
    int *data;
    int len;
    int size;
}List,*PList;
int Init_List(PList L){
    L->data=(int *)malloc(sizeof(int)*SIZE);
    L->len=0;
    L->size=SIZE;
    return 1;
}
int Creat_List(PList L){
    int e,i=0;
    while(scanf("%d",&e)==1){
        if(L->len>=L->size){
            L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
            L->size+=INCREAM;
        }
        L->data[i++]=e;
        L->len++;
    }
    return 1;
}
int Print_List(PList L){
    int i;
    for(i=0;i<L->len;i++){
        printf("%d ",L->data[i]);
    }
    printf("\n");
    return 1;
}
int Connect_List(PList L1,PList L2,PList L3){
    int i=0,j=0,k=0;
    if(L1->len+L2->len>L3->size){
        L3->data=(int *)realloc(L3->data,(L3->size+INCREAM)*sizeof(int));
        L3->size+=INCREAM;
    }
    while(i<L1->len&&j<L2->len){
        if(L1->data[i]==L2->data[j]){
            j++;    
        }else if(L1->data[i]<L2->data[j]){
            L3->data[k++]=L1->data[i++];
        }else{
            L3->data[k++]=L2->data[j++];
        }
    }
    while(i<L1->len){
        L3->data[k++]=L1->data[i++];
    }
    while(j<L2->len){
        L3->data[k++]=L2->data[j++];
    }
    L3->len=k;
    return 1;
}
int main(){
    List L1,L2,L3;
    Init_List(&L1);
    Init_List(&L2);
    Init_List(&L3);
    Creat_List(&L1);
    getchar();
    Creat_List(&L2);
    Connect_List(&L1,&L2,&L3);
    Print_List(&L3);
    return 0;
}

二、单链表

用单链表合并两个有序表，我们有两种方法，一种是带头结点的单链表，另一个是不带头结点的单链表

2.1 不带头结点的单链表

运用不带头结点单链表时，我们需要先找到两个有序表中首元素较小的有序表，然后将它给第三个表，作为第三个表的首元素，在执行接下来的判断

2.1.1 初始化不带头结点的单链表

PNode Init1_Node(){
    PNode head;
    head=NULL;     //初始置头结点为空
    return head;
}

2.1.2 创建不带头结点的单链表

int Creat1_Node(PNode *head){
    int e;
    PNode Last;
    while(scanf("%d",&e)==1){
        PNode Pnew=(PNode)malloc(sizeof(Node));
        Pnew->data=e;
        Pnew->next=NULL;
        if(*head==NULL){    //判断头结点是否为空
            *head=Pnew;        //不带头结点单链表的创建具体见我的专栏
            Last=Pnew;     
        }else{
            Last->next=Pnew;
            Last=Pnew;
        }
    }
    return 1;
}

2.1.3 合并两个有序表

PNode Connect1_Node(PNode p,PNode q){
    PNode r;
    if(p->data<q->data){     //首先要找到首元素较小的，使r的首元素为这个较小元素
        r=p;                                     
        p=p->next;
    }else if(p->data<q->data){
        r=q;
        q=q->next;
    }else{
        r=p;
        p=p->next;
        q=q->next;
    }
    while(p&&q){           //然后一直循环，直到其中一个单链表为空
        if(p->data<q->data){       //将较小的元素插入r后面
            r->next=p;
            r=p;
            p=p->next;
        }else if(p->data>q->data){   
            r->next=q;
            r=q;
            q=q->next;
        }else{          //当两者相等时，我们直接跳过即可
            q=q->next;
        }
    }
    if(p) r->next=p;    //最后将另一个还有元素的单链表连接到r后面
    if(q) r->next=q;
    return r;
}

2.2 带头结点的单链表

运用带头结点的单链表合并有序表，我们直接进行判断，将较小的元素插入第三个表的表尾

2.2.1 初始化带头结点的单链表

PNode Init2_Node(){
    PNode head=(PNode)malloc(sizeof(Node));    //初始化一个头结点
    head->next=NULL;
    return head;
}

2.2.2 创建带头结点的单链表

int Creat2_Node(PNode head){
    PNode p=head;
    int e;
    while(scanf("%d",&e)==1){ 
        PNode Pnew=(PNode)malloc(sizeof(Node));    //具体见专栏 
        Pnew->data=e;
        p->next=Pnew;
        p=Pnew; 
    }
    p->next=NULL;
    return 1;
}

2.2.3 合并两个有序表

int Connect2_Node(PNode head1,PNode head2){
    PNode head3,p,q,r;
    p=head1->next;
    q=head2->next;
    r=Init2_Node();
    while(p&&q){          //思路其实和顺序表，不带头结点单链表的思路一样，就是这里
        if(p->data<q->data){      //不用管两个链表中哪个首元素较小，因为
            r->next=p;            //我们的头结点没有值
            r=p;  
            p=p->next;             //其他和不带头结点单链表方法一样
        }else if(p->data>q->data){
            r->next=q;
            r=q;
            q=q->next;
        }else{
            q=q->next;
        }
    }
    if(p) r->next=p;
    if(q) r->next=q;
    return 1;
}

2.3 完整代码

#include<stdio.h>
#include<malloc.h>
typedef struct Node{
    int data;
    struct Node *next;
}Node,*PNode;
PNode Init1_Node(){
    PNode head;
    head=NULL;
    return head;
}
PNode Init2_Node(){
    PNode head=(PNode)malloc(sizeof(Node));
    head->next=NULL;
    return head;
}
int Creat1_Node(PNode *head){
    int e;
    PNode Last;
    while(scanf("%d",&e)==1){
        PNode Pnew=(PNode)malloc(sizeof(Node));
        Pnew->data=e;
        Pnew->next=NULL;
        if(*head==NULL){
            *head=Pnew;
            Last=Pnew;
        }else{
            Last->next=Pnew;
            Last=Pnew;
        }
    }
    return 1;
}
int Creat2_Node(PNode head){
    PNode p=head;
    int e;
    while(scanf("%d",&e)==1){
        PNode Pnew=(PNode)malloc(sizeof(Node));
        Pnew->data=e;
        p->next=Pnew;
        p=Pnew; 
    }
    p->next=NULL;
    return 1;
}
int Print1_Node(PNode head){
    while(head){
        printf("%d ",head->data);
        head=head->next;
    }
    printf("\n");
}
int Print2_Node(PNode head){
    PNode p=head->next;
    while(p){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    return 1;
}
PNode Connect1_Node(PNode p,PNode q){
    PNode r;
    if(p->data<q->data){
        r=p;
        p=p->next;
    }else if(p->data<q->data){
        r=q;
        q=q->next;
    }else{
        r=p;
        p=p->next;
        q=q->next;
    }
    while(p&&q){
        if(p->data<q->data){
            r->next=p;
            r=p;
            p=p->next;
        }else if(p->data>q->data){
            r->next=q;
            r=q;
            q=q->next;
        }else{
            q=q->next;
        }
    }
    if(p) r->next=p;
    if(q) r->next=q;
    return r;
}
int Connect2_Node(PNode head1,PNode head2){
    PNode head3,p,q,r;
    p=head1->next;
    q=head2->next;
    r=Init2_Node();
    while(p&&q){
        if(p->data<q->data){
            r->next=p;
            r=p;
            p=p->next;
        }else if(p->data>q->data){
            r->next=q;
            r=q;
            q=q->next;
        }else{
            q=q->next;
        }
    }
    if(p) r->next=p;
    if(q) r->next=q;
    return 1;
}
int main(){
    PNode p,q;
    p=Init2_Node();
    Creat2_Node(p);
    getchar();
    q=Init2_Node();
    Creat2_Node(q);
    Connect2_Node(p,q);
    Print2_Node(p);
    return 0;
}

三、运行结果