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

admin2019-08-01 62

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

选项

答案由集合运算的规则知，集合的差A-B为包含所有属于A而不属于B的元素，因此，算法的思路在于对于所有属于集合A中的元素e，在集合B中进行查找，若能找到，则说明它不属于A—B，应从LA中删除。若LA的长度为O(n)，LB的长度为O(m)，则该算法的时间复杂度为O(mXn)。算法参考伪代码如下： void Difference(LinkList*LA，LinkList * LB) ／／设LA，LB均具有头结点 { Node*pre，*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/QtCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

提出帝王“受命不于天。于其人”观点的唐代思想家是()。

导致东欧国家和苏联发生剧变的根本原因是()。

在欧美资产阶级革命时代，最能体现出资产阶级革命要求的文献是()。

洋务运动期间，军事企业主要采取的方式是()。

中国共产党在抗日民主根据地实行的土地政策是()。

世界天文史上最早实地测量子午线的记录是由谁进行的?()

20世纪30年代，美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势，维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务

在机器数中，正数的符号位用“1”表示的是()。

护士在护理实践中应遵循对患者的尊重原则，主要是尊重患者的

函数y＝f(x)在点x＝x0处取得极小值，则必有：

下列关于企业资源的说法中．正确的是()。

()是心理咨询中的参与技巧。

2013年全国农村居民人均纯收入比2010年增长约为()。

下列各句中，没有语病的一项是()。

Completethesummaryusingthelistofwords/phrases,A-H,below.ControversyaboutclimatescienceThereve

ShesaidshewouldliveinLondonfor______fourorfiveyears.