应用题
35.如果以单链表表示集合,设集合A用单链表LA表示,集合曰用单链表LB表示,设计算法求两个集合的差,即A-B。
【正确答案】由集合运算的规则知,集合的差A-B为包含所有属于A而不属于B的元素,因此,算法的思路在于对于所有属于集合A中的元素e,在集合B中进行查找,若能找到,则说明它不属于A-B,应从LA中删除。若LA的长度为O(n),LB的长度为D(m),则该算法的时间复杂度为0(mxn)。
算法参考伪代码如下:
void Difference(LinkList * LA,LinkList * LB) //设LA,LB均具有头结点
{
Node * pre,* P,* r;
pre=LA;
P=LA一>next: //p指向LA表中的某一结点,而pre指向P的前面一个结点
while(P!=NULL)
{
q=LB一>next;
//遍历LB表,判断LA中元素是否在LB中
Node* while(q!=NULL&&q一>data!=一>data)
q=q一>next
if(q!=NULL){ //在LB中找到相同结点元素,则应在LA中删除该结点
r=P:
pre一>next=r一>next:
P=P一>next:
free(r);
}else{//未能找到,说明该结点属于A-B。继续在LA中对下一个元素进行判断
pre=P:
P=P一>next:
}
}
}
【答案解析】