如果以单链表表示集合,设集合A用单链表LA表示,集合B用单链表LB表示,设计算法求两个集合的差,即A—B。

admin2019-08-01  26

问题 如果以单链表表示集合,设集合A用单链表LA表示,集合B用单链表LB表示,设计算法求两个集合的差,即A—B。

选项

答案由集合运算的规则知,集合的差A一B为包含所有属于A而不属于B的元素,因此,算法的思路在于对于所有属于集合A中的元素e,在集合B中进行查找,若能找到,则说明它不属于A—B,应从LA中删除。若LA的长度为O(n),LB的长度为O(m),则该算法的时间复杂度为O(m×n)。 算法参考伪代码如下: 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: } } }

解析
转载请注明原文地址:https://kaotiyun.com/show/DtCi777K
0

最新回复(0)