2. 考研
  3. 如果以单链表表示集合，设集合A用单链表LA表示，集合曰用单链表LB表示，设计算法求两个集合的差，即A-B。

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

admin2019-08-15  117
问题 如果以单链表表示集合，设集合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： } } }
解析
转载请注明原文地址:https://kaotiyun.com/show/VlCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)