已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出A与B的交集,并存放于A链表中。
已知两个链表A和B分别表示两个集合,其元素递增排列。请设计算法求出A与B的交集,并存放于A链表中。
相关考题：
函数Node *difference(A,B)用于求两个集合之差C=A-B，即当且仅当e是A中的一个元素，但不是B中的元素时，e是C中的元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之间按递增排列。执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空，则表示其链表根据元素之值按递增排列。函数append()用于在链表中添加节点。[C函数]typedef struct node{int element;struct node *link；}Node；Node *A，*B，*C；Node *append(last，e)Node *last；int e；{last-＞link=(Node *)malloc(sizeof(Node))；last-＞link-＞element=e；return(last-＞link)；}Node *difference(A,B)Node *A，*B；{ Node *c，*last；C=last=(Node *)malloc(sizeof(Node))；while( (1) )if(A-＞element＜B-＞element){last=append(last，A-＞element);A=A-＞link：}else if( (2) ){A：A-＞link；B：B-＞link;}elSe(3) ；while( (4) ){last=append(last，A-＞element)；A=A-＞link：}(5) ;last=c；c=c-＞link;free(last)；return(c);}
试题一（共15分）阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的对应栏内。【说明】两个包含有限个元素的非空集合A、B的相似度定义为IAUBI/IA U Bl，即它们的交集大小(元素个数)与并集大小之比。以下的流程图计算两个非空整数集合（以数组表示）的交集和并集，并计算其相似度。己知整数组A[1：m】和B【1：n】分别存储了集合A和B的元素（每个集合中包含的元素各不相同），其交集存放于数组C[1：s】，并集存放于数组D【1：t】，集合A和B的相似度存放于SIM。例如，假设A={1，2，3，4}，B={1，4，5，6}，则C={1，4}，D={1，2，3，4，5，6}，A与B的相似度SIM=1/3。
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。[说明]两个包含有限个元素的非空集合A、B的相似度定义为|A∩B|/|A∪B|，即它们的交集大小(元素个数)与并集大小之比。以下的流程图计算两个非空整数集合(以数组表示)的交集和并集，并计算其相似度。已知整数组A[1:m]和B[1:n]分别存储了集合A和B的元素(每个集合中包含的元素各不相同)，其交集存放于数组C[1:s]，并集存放于数组D[1:t]，集合A和B的相似度存放于SIM。例如，假设A={1，2，3，4}，B={1，4，5，6}，则C={1，4)，D={1，2，3，4，5，6}，A与B的相似度SIM=1/3。[流程图]
已知一个带有表头结点的非空单链表，结点结构为： data link 假设该链表中data域中存放的是整数，且只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，输出链表中所有间隔为k（k为正整数）的两个结点元素的和。要求： （1）给出算法的基本设计思想（3分） （2）根据设计思想，采用类C语言描述算法，关键之处给出简要注释。（7分）
1、有两个递增有序表，所有元素为整数，均采用带头结点的单链表存储，结点类型定义如下： typedef struct node { int data; struct node *next; } LinkNode; 设计一个尽可能高效的算法，将两个递增有序单链表ha、hb合并为一个递减有序单链表hc，要求算法空间复杂度为O（1)。