[C++知识库]顺序有序表和链式有序表的合并（C++）

一、顺序有序表的合并

[算法步骤]
①创建一个表长为m+n的空表C。
②指针pc初始化，指向C的第一一个元素。
③指针pa和pb初始化，分别指向A和B的第一个元素。
④当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从A或B中“摘取”元素值较小的结点插人到C的最后。
⑤如果pb已到达B的表尾，依次将LA的剩余元素插人C的最后。
⑥如果pa已到达A的表尾，依次将LB的剩余元素插人C的最后。

#include "iostream"
using namespace std;
#define MAXSIZE 100
typedef struct {
    int *elem;    //存储空间基地址
    int length;   //表长
}SqList;

void CreatList(SqList &L){    //创建表
    int a,i=0;
    L.elem = new int[MAXSIZE];
    L.length = 0;
    cin>>a;
    while (a!=-1){
        if(L.length == MAXSIZE){
            cout<<"顺序表已满";
        } else{
            L.elem[i++] = a;
            L.length++;
            cin>>a;
        }
    }
}

bool GetElem(SqList L,int i,int &e){    //取值
    if(i<1 || i>L.length+1) return false;
    e = L.elem[i-1];
    return true;
}

int LocateList(SqList L,int e){    //查找
    for (int i = 0; i < L.length; ++i) {
        if(L.elem[i] == e)
            return i+1;
        return -1;
    }
}

void InsertList(SqList &L,int i,int e){    //插入
    if(i<1 || i>L.length+1) cout<<"错误";
    else if(L.length == MAXSIZE) cout<<"错误";
    else{
    	for(int j = L.length-1;j>=i-1;j--)
        L.elem[j+1] == L.elem[j];
    L.elem[i-1] = e;
    L.length++;
	} 
}

void MergeList(SqList &A, SqList B, SqList &C){    //合并
    //已知顺序表A、B的元素按值非递减排列
    int *pa,*pb,*pc,*pa_last,*pb_last;
    C.length = A.length + B.length;
    C.elem = new int[C.length];
    pa = A.elem; pb = B.elem; pc = C.elem;  //指针分别指向表的首元素
    pa_last = A.elem + A.length-1;  //指针指向表的最后一个元素
    pb_last = B.elem + B.length-1;
    while((pa <= pa_last) && (pb <= pb_last)){
        if (*pa < *pb) *pc++ = *pa++;
        else *pc++ = *pb++;
    }
    while (pa <= pa_last) *pc++ = *pa++;  //表B已到表尾，将A中元素插入到C中
    while (pb <= pb_last) *pc++ = *pb++;  //表A已到表尾，将B中元素插入到C中
}

void print(SqList L){    //输出表
    for (int i = 0; i < L.length; ++i)
        cout<<L.elem[i]<<" ";
    cout<<endl;
}

int main(){
    SqList LA,LB,LC;
    int i,e;
    cout<<"创建表A(输入-1结束)："<<endl;
    CreatList(LA);
    cout<<"创建表B(输入-1结束)："<<endl;
    CreatList(LB);
    MergeList(LA,LB,LC);
    cout<<"合并结果："<<endl;
    print(LC);
    return 0;
}

运行结果：

?

?

?

二、链式有序表的合并
[算法步骤]
①指针pa和pb初始化，分别指向A和B的第一一个结点。
②C的结点取值为A的头结点。
③指针pc初始化，指向C的头结点。
④当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从A或B中“摘取”元素值较小的结点插人到C的最后。
⑤将非空表的剩余段插人到pc所指结点之后。
⑥释放B的头结点。

#include <iostream>
using namespace std;

typedef struct LNode{   //定义单链表存储结构
    int data;   //数据域
    struct LNode *next;   //指针域
}LNode,*LinkList;

void CreateList(LinkList &L, int n){   //尾插法创建链表
    L = new LNode;
    L->next = NULL;
    LinkList p;
    LinkList r = L;
    for (int i = 0; i < n; ++i) {
        p = new LNode;
        cin>>p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
    cout<<"创建成功"<<endl;
}

void MergeList(LinkList A, LinkList B, LinkList &C){
    //已知单链表A、B的元素按值非递减排列
    LinkList pa,pb,pc;
    C = new LNode;
    C->next = NULL;
    pa = A->next; pb = B->next;  //pa pb分别指向两个表的第一个结点
    C = A;   //A的头节点作为C的头节点 
    pc = C;  //pc指向C的头节点 
    while (pa && pb){   //当A B均未到末尾，取两表中较小的结点插入到C中
        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;  //将非空的剩余段插入C中
    delete B;
}

void ShowList(LinkList L){   //输出链表
    LinkList p = L->next;
    while (p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

int main() {
    int m,n;
    LinkList A,B,C;
    cout<<"创建表A,请输入插入元素个数：";
    cin>>m;
    cout<<"请输入插入的元素："<<endl;
    CreateList(A,m);
    cout<<"创建表B,请输入插入元素个数：";
    cin>>n;
    cout<<"请输入插入的元素："<<endl;
    CreateList(B,n);
    MergeList(A,B,C);
    cout<<"合并结果："<<endl;
    ShowList(C);
    return 0;
}

运行结果：

?

?

?

?