归并La和Lb得到新的线性表Lc.docx
《归并La和Lb得到新的线性表Lc.docx》由会员分享，可在线阅读，更多相关《归并La和Lb得到新的线性表Lc.docx（10页珍藏版）》请在冰点文库上搜索。
归并La和Lb得到新的线性表Lc
#include
#include
#defineLIST_INIT_SIZE100//初始化大小
#defineLISTINCREMENT15
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1//不可实行的
#defineOVERFLOW-2//溢出
#include//exit（）
typedefintElemType;//基本（元素）类型
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
intInitList（SqList*L）
//操作结果：
构造一个空的顺序线性表
{
（*L）.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
（*L）.elem）//存储分配失败
exit（OVERFLOW）;
（*L）.length=0;//空表长度为0
（*L）.listsize=LIST_INIT_SIZE;//初始存储容量
returnOK;
}
intDestroyList（SqList*L）
//初始条件：
顺序线性表L已存在。
操作结果：
销毁顺序线性表L
{
free（（*L）.elem）;
（*L）.elem=NULL;
（*L）.length=0;
（*L）.listsize=0;
returnOK;
}
intClearList（SqList*L）
//初始条件：
顺序线性表L已存在。
操作结果：
将L重置为空表
{
（*L）.length=0;
returnOK;
}
intListEmpty（SqListL）
//初始条件：
顺序线性表L已存在。
操作结果：
若L为空表，则返回TRUE，否则返回FALSE
{
if（L.length==0）
returnTRUE;
else
returnFALSE;
}
intListLength（SqListL）
//初始条件：
顺序线性表L已存在。
操作结果：
返回L中数据元素个数
{
returnL.length;
}
intGetElem（SqListL,inti,ElemType*e）
//初始条件：
顺序线性表L已存在，1≤i≤ListLength（L）。
操作结果：
用e返回L中第i个数据元素的值
{
if（i<1||i>L.length）
exit（ERROR）;
*e=*（L.elem+i-1）;
returnOK;
}
intLocateElem（SqListL,ElemTypee）
//初始条件：
顺序线性表L已存在。
操作结果：
返回L中第1个与e相等的数据元素的位序。
若这样的数据元素不存在，则返回值为0。
{
ElemType*p;
inti=1;//i的初值为第1个元素的位序
p=L.elem;//p的初值为第1个元素的存储位置
while（i<=L.length&&（*p++!
=e））
++i;
if（i<=L.length）
returni;
else
return0;
}
intPriorElem（SqListL,ElemTypecur_e,ElemType*pre_e）
//初始条件：
顺序线性表L已存在。
操作结果：
若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
{
inti=2;
ElemType*p=L.elem+1;
while（i<=L.length&&*p!
=cur_e）
{
p++;
i++;
}
if（i>L.length）
returnINFEASIBLE;
else
{
*pre_e=*--p;
returnOK;
}
}
intNextElem（SqListL,ElemTypecur_e,ElemType*next_e）
//初始条件：
顺序线性表L已存在。
操作结果：
若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
{
inti=1;
ElemType*p=L.elem;
while（i=cur_e）
{
i++;
p++;
}
if（i==L.length）
returnINFEASIBLE;
else
{
*next_e=*++p;
returnOK;
}
}
intListInsert（SqList*L,inti,ElemTypee）
//初始条件：
顺序线性表L已存在，1≤i≤ListLength（L）+1。
操作结果：
在L中第i个位置之前插入新的数据元素e，L的长度加1
{
ElemType*newbase,*q,*p;
if（i<1||i>（*L）.length+1）//i值不合法
returnERROR;
if（（*L）.length>=（*L）.listsize）//当前存储空间已满，增加分配
{
newbase=（ElemType*）realloc（（*L）.elem,（（*L）.listsize+LISTINCREMENT）*sizeof（ElemType））;
if（!
newbase）//存储分配失败
exit（OVERFLOW）;
（*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
returnOK;
}
intListDelete（SqList*L,inti,ElemType*e）
//初始条件：
顺序线性表L已存在，1≤i≤ListLength（L）。
操作结果：
删除L的第i个数据元素，并用e返回其值，L的长度减1
{
ElemType*p,*q;
if（i<1||i>（*L）.length）//i值不合法
returnERROR;
if（（*L）.length==0）//i值不合法
returnERROR;
p=（*L）.elem+i-1;//p为被删除元素的位置
*e=*p;//被删除元素的值赋给e
q=（*L）.elem+（*L）.length-1;//表尾元素的位置
for（++p;p<=q;++p）//被删除元素之后的元素左移
*（p-1）=*p;
（*L）.length--;//表长减1
returnOK;
}
voidMergeList（SqListLa,SqListLb,SqList*Lc）
//算法2.2
//已知线性表La和Lb中的数据元素按值非递减排列
//归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减有序排列
{
ElemTypeai,bj;
intLa_len,Lb_len;
inti=1,j=1,k=0;
La_len=ListLength（La）;//求线性表的长度
Lb_len=ListLength（Lb）;
while（（i<=La_len）&&（j<=Lb_len））//La和Lb均非空
{
GetElem（La,i,&ai）;//取La中第i个数据元素赋给ai
GetElem（Lb,j,&bj）;//取Lb中第j个数据元素赋给bj
if（ai<=bj）//将La和Lb中较小的数赋值给Lc
{
ListInsert（Lc,++k,ai）;
++i;
}
else
{
ListInsert（Lc,++k,bj）;
++j;
}
}
while（i<=La_len）//若La中数据元素没有全部赋给Lc，则将剩下的元素都赋给Lc
{
GetElem（La,i++,&ai）;
ListInsert（Lc,++k,ai）;
}
while（j<=Lb_len）//若Lb中数据元素没有全部赋给Lc，则将剩下的元素都赋给Lc
{
GetElem（Lb,j++,&bj）;
ListInsert（Lc,++k,bj）;
}
}
voidprint（ElemType*c）
{
printf（"%d",*c）;
}
voidmain（）
{
SqListLa,Lb,Lc;
inti,j,k;
InitList（&La）;//创建空表La成功
printf（"请输入La的4个数据元素PleaseentertheLafourdataelements：
"）;
for（j=1;j<=4;j++）//在表La中插入4个元素
{
scanf（"%d",&k）;
i=ListInsert（&La,j,k）;
}
printf（"La="）;//输出表La的内容
for（i=0;iprint（&La.elem[i]）;
printf（"\n"）;
InitList（&Lb）;//也可不判断是否创建成功
printf（"请输入Lb的7个数据元素PleaseinputLbsevendataelements：
"）;
for（j=1;j<=7;j++）//在表Lb中插入7个元素
{
scanf（"%d",&k）;
i=ListInsert（&Lb,j,k）;
}
printf（"Lb="）;//输出表Lb的内容
for（i=0;iprint（&Lb.elem[i]）;
printf（"\n"）;
i=InitList（&Lc）;//创建空表La成功
MergeList（La,Lb,&Lc）;
printf（"Lc="）;//输出表Lc的内容
for（i=0;iprint（&Lc.elem[i]）;
printf（"\n"）;
}
升级会员 