#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#defineLIST_INIT_SIZE10//线性表存储空间的初始分配量

#defineLISTINCREMENT2//线性表存储空间的分配增量

structSqList

{

int*elem;//存储空间基址

intlength;//当前长度

intlistsize;//当前分配的存储容量(以sizeof(int)为单位)

};

voidInitList(SqList&L)

{//操作结果：构造一个空的顺序线性表

L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!L.elem)

exit(0);//存储分配失败

L.length=0;//空表长度为0

L.listsize=LIST_INIT_SIZE;//初始存储容量

}

intListInsert(SqList&L,inti,inte)

{//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1

//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1

int*newbase,*q,*p;

if(i<1||i>L.length+1)//i值不合法

return0;

if(L.length>=L.listsize)//当前存储空间已满,增加分配

{

if(!(newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int))))

exit(0);//存储分配失败

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存储容量

}

q=L.elem+i-1;//q为插入位置

for(p=L.elem+L.length-1;p>=q;--p)//插入位置及之后的元素右移

*(p+1)=*p;

*q=e;//插入e

++L.length;//表长增1

return1;

}

voidPrint(SqList&L)

{

inti;

for(i=0;i<L.length;i++)

printf("%d",*(L.elem+i));

printf("n");

}

————————————————————————————————————

//函数①

voidMergeList1(SqListLa,SqListLb,SqList&Lc)

{

int*pa,*pa_last,*pb,*pb_last,*pc;

pa=La.elem;

pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;//不用InitList()创建空表Lc

pc=Lc.elem=(int*)malloc(Lc.listsize*sizeof(int));

if(!Lc.elem)//存储分配失败

exit(0);

pa_last=La.elem+La.length-1;

pb_last=Lb.elem+Lb.length-1;

while(pa<=pa_last&&pb<=pb_last)//表La和表Lb均非空

{//归并

if(*pa<*pb)

*pc++=*pa++;

elseif(*pa>*pb)

*pc++=*pb++;

else{

*pc++=*pa++;

pb++;

Lc.length--;

}

}

while(pa<=pa_last)//表La非空且表Lb空

*pc++=*pa++;//插入La的剩余元素

while(pb<=pb_last)//表Lb非空且表La空

*pc++=*pb++;//插入Lb的剩余元素

}

————————————————————————————————————

//函数②

voidMergeList2(SqListLa,SqList&Lb,SqList&Lc)

{

int*pa,*pa_last,*pb,*pb_last,*pc;

pa=La.elem;

pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;//不用InitList()创建空表Lc

pc=Lc.elem=(int*)malloc(Lc.listsize*sizeof(int));

if(!Lc.elem)//存储分配失败

exit(0);

pa_last=La.elem+La.length-1;

pb_last=Lb.elem+Lb.length-1;

while(pa<=pa_last&&pb<=pb_last)//表La和表Lb均非空

{//归并

if(*pa<=*pb)

*pc++=*pa++;

else

*pc++=*pb++;

}

while(pa<=pa_last)//表La非空且表Lb空

*pc++=*pa++;//插入La的剩余元素

while(pb<=pb_last)//表Lb非空且表La空

*pc++=*pb++;//插入Lb的剩余元素

Lb.length=Lc.length;

Lb=Lc;

}

————————————————————————————————————

//函数③

voidInverse(SqList&L){

inti,t;

for(i=0;i<L.length/2;i++)

{

t=*(L.elem+i);

*(L.elem+i)=*(L.elem+L.length-i-1);

*(L.elem+L.length-i-1)=t;

}

}

voidmain(){

SqListLA,LB,LC;

inta[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};

inti;

InitList(LA);

InitList(LB);

InitList(LC);

for(i=0;i<4;i++)

ListInsert(LA,i+1,a[i]);

for(i=0;i<7;i++)

ListInsert(LB,i+1,b[i]);

printf("LA=");

Print(LA);

printf("LB=");

Print(LB);

printf("n");

MergeList1(LA,LB,LC);

printf("①LC=");

Print(LC);

printf("n");

MergeList2(LA,LB,LC);

printf("②LB=");

Print(LB);

printf("n");

printf("③LC=");

Inverse(LC);

Print(LC);

}