DS之顺序表实现归并两个非递减线性表

顺序表实现归并两个非递减线性表"/>

DS之顺序表实现归并两个非递减线性表

        早在写线性表的时候就说过这个复杂的操作，今天就来实现归并。

        已知顺序表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的顺序表Lc，且Lc中的数据元素扔按值非递减有序排列。

       例如：La=(3,5,8,11)

                  Lb=(2,6,8,9,11,15,20)

       则       Lc=(2,3,4,6,8,8,9,11,11,15,20)

       要想实现归并，用到的顺序表的基本操作为：0基本操作前准备，1初始化顺序表，6向顺序表插入数据元素，以及自己所写的归并函数，最后需要在主函数中实现输入并输出Lc的所有数据元素。

       归并函数代码：

<span style="font-size:18px;">//归并函数
void MergeList(SqList La,SqList Lb,SqList &Lc)
{ElemType *pa=La.elem; ElemType *pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;ElemType *pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));//从右向左结合方向if(!Lc.elem){exit(OVERFLOW);}ElemType *pa_last=La.elem+La.length-1;ElemType *pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last)//归并{if(*pa<=*pb) {*pc++=*pa++;}else {*pc++=*pb++;}}while(pa<=pa_last)//插入La中剩余的元素{*pc++=*pa++;}while(pb<=pb_last)//插入Lb中剩余的元素{*pc++=*pb++;}
} </span>

         完整的实现归并的代码为：

<span style="font-size:18px;">#include <iostream>
using namespace std;
#include <malloc.h>
#include <stdlib.h>
//0基本操作前准备
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100 
#define LISTINCREMENT  10
typedef int ElemType;
typedef int Status;
typedef struct
{ElemType *elem;//存储空间基址int length;//当前长度int listsize;//当前分配的存储容量
}SqList;//定义了一个结构体类型，并命名为Sqlist
//1初始化顺序表
Status InitList(SqList &L)
{ L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) {exit(OVERFLOW); }L.length=0; L.listsize=LIST_INIT_SIZE; return OK; 
}//6向顺序表插入数据元素
Status ListInsert(SqList &L,int i, ElemType e)
{if(i<1||i>L.length+1){return ERROR;}if (L.length>=L.listsize){ElemType *newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT )*sizeof(ElemType));if(!newbase){exit(OVERFLOW);}L.elem=newbase;L.listsize+=LISTINCREMENT;}ElemType *q=&(L.elem[i-1]);ElemType *p;for(p=&(L.elem[L.length-1]);p>=q;p--){*(p+1)=*p;}*q=e;  ++L.length;return OK;
}
//归并函数
void MergeList(SqList La,SqList Lb,SqList &Lc)
{ElemType *pa=La.elem; ElemType *pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;ElemType *pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));//从右向左结合方向if(!Lc.elem){exit(OVERFLOW);}ElemType *pa_last=La.elem+La.length-1;ElemType *pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last)//归并{if(*pa<=*pb) {*pc++=*pa++;}else {*pc++=*pb++;}}while(pa<=pa_last)//插入La中剩余的元素{*pc++=*pa++;}while(pb<=pb_last)//插入Lb中剩余的元素{*pc++=*pb++;}
} 
int main()
{ SqList La,Lb,Lc;//声明了La和Lb以及LC;InitList(La);InitList(Lb);cout<<"请输入La中数据的个数：";int na;ElemType e;cin>>na;for(int i=1;i<=na;i++) {cin>>e;ListInsert(La,i,e);}cout<<"请输入Lb中数据的个数：";int nb;cin>>nb;for(i=1;i<=nb;i++){cin>>e;ListInsert(Lb,i,e);}MergeList(La,Lb,Lc);for(i=0;i<na+nb;i++){cout<<Lc.elem[i]<<",";}cout<<endl;return 0;
}</span>

          输入的数据为：La=(2,5,6)

                                   Lb=(3,5,7,9,11)

          输出的结果为：