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

admin2018-08-12 38

问题如果以单链表表示集合，设集合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/6cRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

埃及曾两次被波斯帝国征服，波斯第二次征服埃及的时间是()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

第一国际成立前，各国无产阶级强烈要求加强国际团结的直接原因是()。

宁夏回族自治区的设立时间是()。

美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后，美国创立了资产阶级共和制度③地理位置优越，远离动乱的欧洲④拥有潜在的广阔的国内市场

解放军渡江战役中横渡长江的东西两个攻击点是()。

“瓜步之战”发生在下列哪两个政权之间?()

摩擦焊的原理是电流通过焊料接触点的同时瞬间施于高压。

决定休克病人补液量较可靠的依据是

若完成1m3墙体砌筑工作的基本工时为0．5工日，辅助工作时间占工序作业时间的4％。准备与结束工作时间、不可避免的中断时间、休息时间分别占工作时间的6％、3％、和12％，该工程时间定额为()工日／m3。

全色谱全塑双绞通信电缆的一个基本单元U中，b线颜色有蓝、橙、()。

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

社会服务机构的项目实施过程的正确流程为()

下列关于意识和注意说法不正确的是()

()附属于劳动权，是劳动权的必要补充。