已知递增有序的单链表 A,B和C分别存储了一个集合设计算法实现 A:=A∪(B∩C),并使求解结构A仍保持递增.
来源:学生作业帮 编辑:灵鹊做题网作业帮 分类:综合作业 时间:2024/06/17 02:47:18
已知递增有序的单链表 A,B和C分别存储了一个集合设计算法实现 A:=A∪(B∩C),并使求解结构A仍保持递增.
要求算法的时间复杂度为 O(|A|+|B|+|C|).其中,|A|为集合A 的元素个数.用C语言实现.
要求算法的时间复杂度为 O(|A|+|B|+|C|).其中,|A|为集合A 的元素个数.用C语言实现.
![已知递增有序的单链表 A,B和C分别存储了一个集合设计算法实现 A:=A∪(B∩C),并使求解结构A仍保持递增.](/uploads/image/z/17279524-28-4.jpg?t=%E5%B7%B2%E7%9F%A5%E9%80%92%E5%A2%9E%E6%9C%89%E5%BA%8F%E7%9A%84%E5%8D%95%E9%93%BE%E8%A1%A8+A%2CB%E5%92%8CC%E5%88%86%E5%88%AB%E5%AD%98%E5%82%A8%E4%BA%86%E4%B8%80%E4%B8%AA%E9%9B%86%E5%90%88%E8%AE%BE%E8%AE%A1%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0+A%3A%3DA%E2%88%AA%28B%E2%88%A9C%29%2C%E5%B9%B6%E4%BD%BF%E6%B1%82%E8%A7%A3%E7%BB%93%E6%9E%84A%E4%BB%8D%E4%BF%9D%E6%8C%81%E9%80%92%E5%A2%9E.)
#include <stdio.h>
#include <stdlib.h>
int la,lb,lc,lA,lbc,i;
int a[1001],b[1001],c[1001],bc[1001];
int A[1001];
void init()
{
\x09scanf("%d%d%d",&la,&lb,&lc);
\x09for (i=1;i<=la;i++) scanf("%d",a+i);
\x09for (i=1;i<=lb;i++) scanf("%d",b+i);
\x09for (i=1;i<=lc;i++) scanf("%d",c+i);
}
void work()
{
\x09int ta,tb,tc,tbc;
\x09tb=tc=1;
\x09while (tb<=lb&&tc<=lc)
\x09{
\x09\x09if (b[tb]<c[tc])
\x09\x09{
\x09\x09\x09while (b[tb]<c[tc]&&tb<=lb) tb++;
\x09\x09} else {
\x09\x09\x09while (c[tc]<b[tb]&&tc<=lc) tc++;
\x09\x09}
\x09\x09if (tb>lb||tc>lc) break;
\x09\x09if (b[tb]==c[tc])
\x09\x09{
\x09\x09\x09bc[++lbc]=b[tb];
\x09\x09\x09tb++; tc++;
\x09\x09}
\x09}
\x09tbc=1; ta=1;
\x09while (ta<=la||tbc<=lbc)
\x09{
\x09\x09if (ta<=la&&tbc<=lbc&&a[ta]==bc[tbc])
\x09\x09{
\x09\x09\x09ta++; tbc++;
\x09\x09\x09A[++lA]=a[ta-1];
\x09\x09} else if (ta<=la&&(a[ta]<bc[tbc]||tbc>lbc)) A[++lA]=a[ta++];
\x09\x09else if (tbc<=lbc&&(bc[tbc]<a[ta]||ta>la)) A[++lA]=bc[tbc++];
\x09}
}
int main()
{
\x09init();
\x09work();
\x09printf("%d\n",lA);
\x09for (i=1;i<=lA;i++) printf("%d ",A[i]);
\x09printf("\n");
}以上代码,题目中说A,B,C是单链表,那就直接当作数组来做了,反正差不多.
la,lb,lc分别为A,B,C的大小,a,b,c存储其中的元素,A用来存最终的答案.bc数组存储的是 B∩C 的答案,lbc为 |B∩C|
思路如下:
首先由于a,b,c都是递增的,所以可以利用它的单调性.在求 B∩C 时,两个指针分别指向链表头 (tb,tc) 若 b[tb]<c[tc] 那么和c[tc]相等的b集合中的值一定存在tb之后,所以一直将tb指针向后跳,直到b[tb]>=c[tc] 相反的话类似.当得到一个 b[tb]==c[tc] 时,将它加入bc中,两个指针同时向后走一步.显然,由于tb和tc都恰好遍历了整个链一次,所以复杂度 O ( |B|+|C| )
接下来需要做的就是合并两张有序表 a 和 bc,同样两个指针( ta,tbc ) 然后哪个小放哪个,一直到两个指针都到尾端为止,复杂度类似于上一步 O ( |A| + |BC| )
综上,复杂度为 O ( |A| + 2*( |B|+|C| ) ) 2为常数,可以略去
#include <stdlib.h>
int la,lb,lc,lA,lbc,i;
int a[1001],b[1001],c[1001],bc[1001];
int A[1001];
void init()
{
\x09scanf("%d%d%d",&la,&lb,&lc);
\x09for (i=1;i<=la;i++) scanf("%d",a+i);
\x09for (i=1;i<=lb;i++) scanf("%d",b+i);
\x09for (i=1;i<=lc;i++) scanf("%d",c+i);
}
void work()
{
\x09int ta,tb,tc,tbc;
\x09tb=tc=1;
\x09while (tb<=lb&&tc<=lc)
\x09{
\x09\x09if (b[tb]<c[tc])
\x09\x09{
\x09\x09\x09while (b[tb]<c[tc]&&tb<=lb) tb++;
\x09\x09} else {
\x09\x09\x09while (c[tc]<b[tb]&&tc<=lc) tc++;
\x09\x09}
\x09\x09if (tb>lb||tc>lc) break;
\x09\x09if (b[tb]==c[tc])
\x09\x09{
\x09\x09\x09bc[++lbc]=b[tb];
\x09\x09\x09tb++; tc++;
\x09\x09}
\x09}
\x09tbc=1; ta=1;
\x09while (ta<=la||tbc<=lbc)
\x09{
\x09\x09if (ta<=la&&tbc<=lbc&&a[ta]==bc[tbc])
\x09\x09{
\x09\x09\x09ta++; tbc++;
\x09\x09\x09A[++lA]=a[ta-1];
\x09\x09} else if (ta<=la&&(a[ta]<bc[tbc]||tbc>lbc)) A[++lA]=a[ta++];
\x09\x09else if (tbc<=lbc&&(bc[tbc]<a[ta]||ta>la)) A[++lA]=bc[tbc++];
\x09}
}
int main()
{
\x09init();
\x09work();
\x09printf("%d\n",lA);
\x09for (i=1;i<=lA;i++) printf("%d ",A[i]);
\x09printf("\n");
}以上代码,题目中说A,B,C是单链表,那就直接当作数组来做了,反正差不多.
la,lb,lc分别为A,B,C的大小,a,b,c存储其中的元素,A用来存最终的答案.bc数组存储的是 B∩C 的答案,lbc为 |B∩C|
思路如下:
首先由于a,b,c都是递增的,所以可以利用它的单调性.在求 B∩C 时,两个指针分别指向链表头 (tb,tc) 若 b[tb]<c[tc] 那么和c[tc]相等的b集合中的值一定存在tb之后,所以一直将tb指针向后跳,直到b[tb]>=c[tc] 相反的话类似.当得到一个 b[tb]==c[tc] 时,将它加入bc中,两个指针同时向后走一步.显然,由于tb和tc都恰好遍历了整个链一次,所以复杂度 O ( |B|+|C| )
接下来需要做的就是合并两张有序表 a 和 bc,同样两个指针( ta,tbc ) 然后哪个小放哪个,一直到两个指针都到尾端为止,复杂度类似于上一步 O ( |A| + |BC| )
综上,复杂度为 O ( |A| + 2*( |B|+|C| ) ) 2为常数,可以略去
用c++实现,假设有两个元素递增的有序排列线性表A和B,均以顺序表作存储结构.试编写算法将A表和B表归并成一个按元素值递
数据结构假设分别以两个元素的值递增有序线性表a,b表示两个集合,现在要构成一个新的线性表c,c表示a b的交,且c中的元
数据结构算法实现:利用两个线性表LA和LB分别表示两个集合A和B,现要求一个新的集合A=A并B.
已知两个顺序表A和B分别表示两个集合,其元素递增排列,编写一个函数求出A和B的交集
已知两个单链表A与B分别表示两个集合,其元素类型为int且递增排列,其头结点指针分别为a,b.编写一个函数求出A和B的交
设计一个算法求a,b,c的最大值
美国降水分布的特点是A.自东向西递增 B.自西向东递增 C.自南向北递增 D.自北向南递增
有A,B,C,D,E五种短周期元素元素,他们的原子序数依次递增.已知:A和C,B和D分别位于同主族,A是原子半径最
C语言编程题,利用两个线性表LA和LB分别表示两个集合A和B,现要求一个集合A=A并B
数据结构课程设计题.\x05有两个相等长度的正整数序列A和B,都是有序的(递增排序),同时一个序列中没有重复元素,现在需
A,B,C,D,E为原子序数依次递增的五种短周期元素,已知:①A,B,C同周期,C
任意给定实数a,b,c,设计一个算法判断大小,并画出流程图