要求同
题
试对单链表编写求C的算法
解
// 将AB求交后的结果放在C表中并删除B表
Status ListCross_L(LinkList &ALinkList &BLinkList &C)
{
LinkList papbqaqbpt;
pa=A;
pb=B;
qa=pa;// 保存pa的前驱指针
qb=pb;// 保存pb的前驱指针
pa=pa>next;
pb=pb>next;
C=A;
while(pa&&pb){
if(pa>data<pb>data){
pt=pa;
pa=pa>next;
qa>next=pa;
free(pt);
}
else
if(pa>data>pb>data){
pt=pb;
pb=pb>next;
qb>next=pb;
free(pt);
}
else{
qa=pa;
pa=pa>next;
}
}
while(pa){
pt=pa;
pa=pa>next;
qa>next=pa;
free(pt);
}
while(pb){
pt=pb;
pb=pb>next;
qb>next=pb;
free(pt);
}
pb=B;
free(pb);
return OK;
}
对题的条件作以下两点修改对顺序表重新编写求得表C的算法
() 假设在同一表（A或B）中可能存在值相同的元素但要求新生成的表C中的元素值各不相同
() 利用A表空间存放表C
解
()
// AB求交然后删除相同元素将结果放在C表中
Status ListCrossDelSame_Sq(SqList &ASqList &BSqList &C)
{
int i=j=k=;
while(i<Alength && j<Blength){
if(Aelem[i]<Belem[j])i++;
else
if(Aelem[i]>Belem[j])j++;
else{
if(Clength==){
ListInsert_Sq(CkAelem[i]);
k++;
}
else
if(Celem[Clength]!=Aelem[i]){
ListInsert_Sq(CkAelem[i]);
k++;
}
i++;
}
}
return OK;
}
()
// AB求交然后删除相同元素将结果放在A表中
Status ListCrossDelSame_Sq(SqList &ASqList &B)
{
int i=j=k=;
while(i<Alength && j<Blength){
if(Aelem[i]<Belem[j])i++;
else
if(Aelem[i]>Belem[j])j++;
else{
if(k==){
Aelem[k]=Aelem[i];
k++;
}
else
if(Aelem[k]!=Aelem[i]){
Aelem[k]=Aelem[i];
k++;
}
i++;
}
}
Alength=k;
return OK;
}
[] [] []
![数据结构与算法线性表复习习题【5】[2]](/UploadFiles/9.jpg)