线性表2

已知线性表LA和LB中的数据元素是按照值非递减的有序的排列，现在要求将LA和LB归并为一个新的数据表LC，且LC中的数据元素仍然是按照值非递减的有序排列

LA (3,5,8.11)

LB(2,6,8,9,11,15,20)

求LC

#include<iostream> 

#include<iomanip>

using namespace std;

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define LIST_INTSIZE 50

#define LISTINCREMENT 10

#define OVERFLOW -2

typedef int DataType; 

typedef struct {   

DataType*  elem;                    

int  length;

int  listsize;

}SqList;  

int InitList(SqList* L)  

{ 

L->elem=(DataType *)malloc((LIST_INTSIZE+1)*sizeof(DataType));  /*数组的0元素没有使用*/

if (!L->elem)

{

cout<<"\t\t\t内存分配失败\n";

return 0;

}

L->length=0;

L->listsize=LIST_INTSIZE;  

//cout<<"\t\t\t内存分配成功\n";

return OK;

}

int  insertList(SqList* L, int i, DataType x)

{  

if(i<1 || i>L->length+1) return ERROR;//插入位置不合法

if(L->length>=L->listsize)//表满

{

L->elem=(DataType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(DataType));

if(!L->elem) exit(OVERFLOW);

L->listsize=L->listsize+LISTINCREMENT;

}

DataType *p;

DataType *q=&(L->elem[i-1]);//从这个地方可以看出的是L->elem[0]依然是一个数据

for(p=&(L->elem[L->length-1]);p>=q;--p)

*(p+1)=*p;

*q=x;

++L->length;

return OK;

   /*插入成功，返回*/

}

int ListLength(SqList* L)

/* 返回线性表Ｌ的长度*/

{

    return  L->length;

}

/*返回线性表中的第ｉ个元素的值*/

DataType GetElem(SqList *L, int i)

{  

if(i<0||i>L->length)

{ cout<<i<<"\n\t\t\t输入位置不合法"<<endl; return 0;}

else

return L->elem[i];

} 

/*显示线性表中的所有元素*/

void ListTraverse(SqList* L)

{

int i;

if(L->length==0)//线性表为空

cout<<"\n\t\t\t线形表为空!\n";

else

{

for(i=0;i<L->length;i++)

cout<<setw(3)<<L->elem[i];

}

        cout<<endl;

}

/*对线性表La,Lb进行合并,合并后放入到Lc*/

void Mergelist(SqList La,SqList Lb,SqList *Lc)

{  

InitList(Lc);

    int a[100],b[100];

int i=0,j=0,k=0,La_len,Lb_len;

    La_len=ListLength(&La);Lb_len=ListLength(&Lb);

while((i<La_len)&&(j<=Lb_len))//均非空

{ 

a[i]=GetElem(&La,i);b[j]=GetElem(&Lb,j);

if(a[i]<=b[j])

{

insertList(Lc,++k,a[i]);++i;

}

        else

{

insertList(Lc,++k,b[j]);++j;

}

}

while(i<La_len)

{

  a[i]=GetElem(&La,i++);

  insertList(Lc,++k,a[i]);

}

while(j<Lb_len)

{

b[j]=GetElem(&Lb,j++);

insertList(Lc,++k,b[j]);

}

}//mergeList

int main()

{

int j=1,i=0;

    SqList La,Lb,Lc;

    DataType x;

char c;

InitList(&La);//初始化线性表La

cout<<"请输入LA的数据的元素(元素之间利用空格隔开，'回车'表示输入结束)"<<endl;

while(j)

{

  cin>>x;

  i++;

       insertList(&La,i,x);

  c=getchar();

  if(c=='\n')

  j=0;

}

//遍历La表中的元素

cout<<"你输入的LA的数据为: ";ListTraverse(&La);

InitList(&Lb);//初始化线性表Lb

cout<<"请输入LB的数据的元素(元素之间利用空格隔开，'回车'表示输入结束)"<<endl;

j=1;i=0;

while(j)

{

  cin>>x;

  i++;

       insertList(&Lb,i,x);

  c=getchar();

  if(c=='\n')

  j=0;

}

//遍历Lb表中的元素

cout<<"你输入的LB的数据为: ";ListTraverse(&Lb);

//现在要进行的是表的合并

     Mergelist(La,Lb,&Lc);

cout<<"合并之后得到的LC:";

ListTraverse(&Lc);

return 0;