归并La和Lb得到新的线性表LcWord文档下载推荐.docx
《归并La和Lb得到新的线性表LcWord文档下载推荐.docx》由会员分享，可在线阅读，更多相关《归并La和Lb得到新的线性表LcWord文档下载推荐.docx（10页珍藏版）》请在冰点文库上搜索。
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）.listsize=0;
intClearList（SqList*L）
将L重置为空表
intListEmpty（SqListL）
若L为空表，则返回TRUE，否则返回FALSE
if（L.length==0）
returnTRUE;
else
returnFALSE;
intListLength（SqListL）
返回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）;
intLocateElem（SqListL,ElemTypee）
返回L中第1个与e相等的数据元素的位序。
若这样的数据元素不存在，则返回值为0。
ElemType*p;
inti=1;
//i的初值为第1个元素的位序
p=L.elem;
//p的初值为第1个元素的存储位置
while（i<
=L.length&
&
（*p++!
=e））
++i;
=L.length）
returni;
return0;
intPriorElem（SqListL,ElemTypecur_e,ElemType*pre_e）
若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
inti=2;
ElemType*p=L.elem+1;
*p!
=cur_e）
{
p++;
i++;
}
if（i>
returnINFEASIBLE;
*pre_e=*--p;
intNextElem（SqListL,ElemTypecur_e,ElemType*next_e）
若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
ElemType*p=L.elem;
L.length&
if（i==L.length）
else
*next_e=*++p;
intListInsert（SqList*L,inti,ElemTypee）
顺序线性表L已存在，1≤i≤ListLength（L）+1。
在L中第i个位置之前插入新的数据元素e，L的长度加1
ElemType*newbase,*q,*p;
（*L）.length+1）//i值不合法
returnERROR;
if（（*L）.length>
=（*L）.listsize）//当前存储空间已满，增加分配
newbase=（ElemType*）realloc（（*L）.elem,（（*L）.listsize+LISTINCREMENT）*sizeof（ElemType））;
newbase）//存储分配失败
（*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
intListDelete（SqList*L,inti,ElemType*e）
删除L的第i个数据元素，并用e返回其值，L的长度减1
ElemType*p,*q;
（*L）.length）//i值不合法
if（（*L）.length==0）//i值不合法
p=（*L）.elem+i-1;
//p为被删除元素的位置
*e=*p;
//被删除元素的值赋给e
q=（*L）.elem+（*L）.length-1;
//表尾元素的位置
for（++p;
p<
++p）//被删除元素之后的元素左移
*（p-1）=*p;
（*L）.length--;
//表长减1
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）;
ListInsert（Lc,++k,bj）;
++j;
=La_len）//若La中数据元素没有全部赋给Lc，则将剩下的元素都赋给Lc
GetElem（La,i++,&
while（j<
=Lb_len）//若Lb中数据元素没有全部赋给Lc，则将剩下的元素都赋给Lc
GetElem（Lb,j++,&
voidprint（ElemType*c）
printf（"
%d"
*c）;
voidmain（）
SqListLa,Lb,Lc;
inti,j,k;
InitList（&
La）;
//创建空表La成功
请输入La的4个数据元素PleaseentertheLafourdataelements：
"
）;
for（j=1;
j<
=4;
j++）//在表La中插入4个元素
scanf（"
%d"
&
k）;
i=ListInsert（&
La,j,k）;
La="
//输出表La的内容
for（i=0;
i<
La.length;
i++）
print（&
La.elem[i]）;
\n"
Lb）;
//也可不判断是否创建成功
请输入Lb的7个数据元素PleaseinputLbsevendataelements：
=7;
j++）//在表Lb中插入7个元素
Lb,j,k）;
Lb="
//输出表Lb的内容
Lb.length;
Lb.elem[i]）;
i=InitList（&
Lc）;
MergeList（La,Lb,&
Lc="
//输出表Lc的内容
Lc.length;
Lc.elem[i]）;
升级会员 