数据结构—有序表—归并排序

旧城等待， 2022-08-21 13:59 37阅读 0赞

假设有两个有序表LA和LB，设计一个程序，将它们合并成一个有序表LC（假设每个有序表中和两个有序表间均不存在重复元素）。要求不破坏原有表LA和LB。

思路：

二路归并算法：分别扫描LA和LB两个有序表，当两个有序表都没有扫描完时循环：比较LA、LB的当前元素，将其中较小的元素放入LC中，再从较小元素所在的

有序表中取下一个元素。重复这个过程直到LA或LB比较完毕，最后将未比较完的有序表余下的元素放入LC中。

顺序表：

#include <iostream>
    #include <malloc.h>
    #define MaxSize 100
    using namespace std;
    typedef int ElemType;
    typedef struct
    {
        ElemType data[MaxSize];
        int length;
    } SqList;
    void InitList(SqList *&L)  //初始化顺序表L
    {
        L=(SqList *)malloc(sizeof (SqList));
        L->length=0;
    }
    
    void ListInsert(SqList *&L,ElemType a[],int n)   //采用尾插法依次插入元素
    {
        for(int i=0; i<n; i++)
            L->data[i]=a[i];
        L->length=n;
    }
    
    void DispList(SqList *L)         //输出顺序表L
    {
        for(int i=0; i<L->length; i++)
            cout<<L->data[i]<<" ";
        cout<<endl;
    }
    
    void UnionList(SqList *LA,SqList *LB,SqList *&LC)   //合并两个有序表
    {
        int i=0,j=0,k=0;
        LC=(SqList *)malloc(sizeof(SqList));
        while(i<LA->length&&j<LB->length)          //LA和LB均未到达表尾时，择其小插入LC中
        {
            if(LA->data[i]<LB->data[j])
            {
                LC->data[k]=LA->data[i];
                i++;
                k++;
            }
            else
            {
                LC->data[k]=LB->data[j];
                j++;
                k++;
            }
        }
        while(i<LA->length)           //LA尚未扫描完，将其它元素插入LC中
        {
            LC->data[k]=LA->data[i];
            i++;
            k++;
        }
        while(j<LB->length)          //LB尚未扫描完，将其它元素插入LC中
        {
            LC->data[k]=LB->data[j];
            j++;
            k++;
        }
        LC->length=k;
    }
    int main()
    {
        ElemType a[3]={1,3,5},b[4]={2,4,8,10};
        SqList *LA,*LB,*LC;
        InitList(LA);
        InitList(LB);
        ListInsert(LA,a,3);
        cout<<"LA中的元素：";
        DispList(LA);
        ListInsert(LB,b,4);
        cout<<"LB中的元素：";
        DispList(LB);
        UnionList(LA,LB,LC);
        cout<<"LC中的元素：";
        DispList(LC);
        return 0;
    }

运行结果：

![Center][]

单链表：

#include <iostream>
    #include <malloc.h>
    using namespace std;
    typedef int ElemType;
    typedef struct LNode
    {
        ElemType data;
        struct LNode *next;
    } LinkList;
    
    void InitList(LinkList *&L)  //初始化单链表
    {
        L=(LinkList *)malloc(sizeof (LinkList));
        L->next=NULL;
    }
    void CreateListR(LinkList *&L,ElemType a[],int n)   //采用尾插法依次插入元素
    {
        LinkList *s,*r;
        int i;
        L=(LinkList *)malloc(sizeof(LinkList));
        r=L;
        for(i=0; i<n; i++)
        {
            s=(LinkList *)malloc(sizeof(LinkList));
            s->data=a[i];
            r->next=s;
            r=s;
        }
        r->next=NULL;
    }
    void DispList(LinkList *L)         //输出单链表
    {
        LinkList *p=L->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
    void UnionList(LinkList *LA,LinkList *LB,LinkList *&LC)   //合并两个有序表
    {
        LinkList *pa=LA->next,*pb=LB->next,*r,*s;
        LC=(LinkList *)malloc(sizeof(LinkList));
        r=LC;
        while(pa!=NULL&&pb!=NULL)     //LA和LB均未到达表尾时，择其小插入LC中
        {
            if(pa->data<pb->data)
            {
                s=(LinkList *)malloc(sizeof(LinkList));
                s->data=pa->data;
                r->next=s;
                r=s;
                pa=pa->next;
            }
            else
            {
                s=(LinkList *)malloc(sizeof(LinkList));
                s->data=pb->data;
                r->next=s;
                r=s;
                pb=pb->next;
            }
        }
        while(pa!=NULL)          //LA尚未扫描完，将其它元素插入LC中
        {
            s=(LinkList *)malloc(sizeof(LinkList));
            s->data=pa->data;
            r->next=s;
            r=s;
            pa=pa->next;
        }
        while(pb!=NULL)         //LB尚未扫描完，将其它元素插入LC中
        {
            s=(LinkList *)malloc(sizeof(LinkList));
            s->data=pb->data;
            r->next=s;
            r=s;
            pb=pb->next;
        }
        r->next=NULL;
    }
    int main()
    {
        LinkList *LA,*LB,*LC;
        ElemType a[3]= {1,3,5},b[4]= {2,4,8,10};
        InitList(LA);
        InitList(LB);
        CreateListR(LA,a,3);
        CreateListR(LB,b,4);
        cout<<"LA中的元素：";
        DispList(LA);
        cout<<"LB中的元素：";
        DispList(LB);
        UnionList(LA,LB,LC);
        cout<<"LC中的元素：";
        DispList(LC);
        return 0;
    }

运行结果：

![Center 1][]

[Center]: /images/20220724/0fc2c1eb796045158a5f642937059e9c.png
[Center 1]: /images/20220724/7c576080a03843bf8362500cb88df431.png