#include<stdlib.h>
#include<stdio.h> //长度与空间是检测
typedef int Status; // Status 是函数返回值类型,其值是函数结果状态代码。
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define List_Init_Size 10 //线性表存储空间初始分配量
#define Listincerment 10 //线性表存储空间的分配增量
typedef struct SqList
{
int *elem;
int length;
int listsize; //当前分配的存储容量()
}SqList;
Status InitList(SqList*L)
{//初始化顺序线性表//
L->elem=(int*)malloc(List_Init_Size*sizeof(int));
if(!L->elem)exit(OVERFLOW); //存储分配失败
L->length=0;
L->listsize=List_Init_Size;
return OK;
}
Status GetElem(SqList a,int i,int*e)
{ //读取元素
if(i<0||i>a.length) return ERROR;//在表内
e=&a.elem[i-1]; //i-1存储第i个元素
return OK;
}
int ListLength(SqList L)
{ //计算长度
if(!L.elem)exit(ERROR); //空间存在
return L.length;
}
Status ListInsert(SqList *L, int i, int e)
{
//i位置之前。。。插入新元素e
if(i<1||i>L->length+1)return ERROR; //在表内
if((L->length)>=(L->listsize)){
//当前存储空间已满,增加分配
int*newbase,*q,*p;
newbase=(int*)realloc(L->elem,(L->listsize+Listincerment)*sizeof(int));
if(!newbase)exit(OVERFLOW);//存储分配失败}
L->elem=newbase; //新的基址
L->listsize+=Listincerment; //增加容器容量
q=&(L->elem[i-1]); //q为插入位置
for(p=&(L->elem[L->length-1]);p>=q;--p) //实质为数组,所以下标注意。
*(p+1)=*p; //插入位置及以后的元素后移 ,副本的覆盖。
*q=e; //插入e
++L->length;
}
return OK;}
void output(SqList L)
{
int i;
for(i=0;i<L.length;i++)
{
printf("%d ",L.elem[i]);
}
}
void MergeList(SqList LA, SqList LB, SqList *LC) //顺序有序表的合并
{
//归并LA和LB得到新的顺序有序表LC,LC的元素也按值非递减排列
int *pa, *pb, *pc, *pa_last, *pb_last;
pa = LA.elem;
pb = LB.elem; //指针pa和pb的初值分别指向两个表的第一次元素
LC->listsize=LC->length = LA.length + LB.length; //新表长度为待合并两表的长度之和
LC->elem = (int*)malloc(LC->listsize*sizeof(int)); //为合并后的新表分配一个数组空间
pc = LC->elem; //指针pc指向新表的第一个元素
pa_last = LA.elem + LA.length - 1; //指针pa_last指向LA表的最后一个元素
pb_last = LB.elem + LB.length - 1; //指针pb_last指向LB表的最后一个元素
while (pa <= pa_last && pb <= pb_last) //两个表都非空
{
if (*pa <= *pb) //依次“摘取”两表中值较小的结点插入到LC表的最后
*pc++ = *pa++;
else
*pc++ = *pb++;
}
while (pa <= pa_last) //LB已到达表尾,依次将LA的剩余元素插入LC表的最后
*pc++ = *pa++;
while (pb <= pb_last) //LA已到达表尾,依次将LB的剩余元素插入LC表的最后
*pc++ = *pb++;
}
void main()
{
SqList a,b,c;
int i,j,k;
InitList(&a); InitList(&b);
printf("输入要写入链表a中元素的个数\n");
scanf("%d",&j);
printf("输入每个元素");
for(i=1;i<=j;i++)
{
int e;
scanf("%d",&e);
ListInsert(&a,i,e);
}
printf("输入要写入链表b中元素的个数\n");
scanf("%d",&k);
printf("输入每个元素");
for(j=1;j<=k;i++)
{
int e;
scanf("%d",&e);
ListInsert(&b,i,e);
}
MergeList(a,b,&c);
output(c);
}