已知AB和C为三个递增有序的线性表现要求对A表作如下操作删去那些既在B表中出现又在C表中出现的元素试对顺序表编写实现上述操作的算法并分析你的算法的时间复杂度（注意题中没有特别指明同一表中的元素值各不相同）
解
// 在A中删除既在B中出现又在C中出现的元素结果放在D中
Status ListUnion_Sq(SqList &DSqList &ASqList &BSqList &C)
{
SqList Temp;
InitList_Sq(Temp);
ListCross_L(BCTemp);
ListMinus_L(ATempD);
}
要求同题试对单链表编写算法请释放A表中的无用结点空间
解
// 在A中删除既在B中出现又在C中出现的元素并释放BC
Status ListUnion_L(LinkList &ALinkList &BLinkList &C)
{
ListCross_L(BC);
ListMinus_L(AB);
}
// 求集合AB结果放在A表中并删除B表
Status ListMinus_L(LinkList &ALinkList &B)
{
LinkList papbqaqbpt;
pa=A;
pb=B;
qa=pa;// 保存pa的前驱指针
qb=pb;// 保存pb的前驱指针
pa=pa>next;
pb=pb>next;
while(pa&&pb){
if(pb>data<pa>data){
pt=pb;
pb=pb>next;
qb>next=pb;
free(pt);
}
else
if(pb>data>pa>data){
qa=pa;
pa=pa>next;
}
else{
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;
}
假设某个单向循环链表的长度大于且表中既无头结点也无头指针已知s为指向链表中某个结点的指针试编写算法在链表中删除指针s所指结点的前驱结点
解
// 在单循环链表S中删除S的前驱结点
Status ListDelete_CL(LinkList &S)
{
LinkList pq;
if(S==S>next)return ERROR;
q=S;
p=S>next;
while(p>next!=S){
q=p;
p=p>next;
}
q>next=p>next;
free(p);
return OK;
}
[] [] []
![数据结构与算法线性表复习习题【6】[1]](/UploadFiles/8.jpg)