假设递增有序的顺序表AB分别表示一个集合,设计算法以判断集合A受否是集合B的子集若是,则返回TRUE,若否,则返回FALSE,并要求时间尽量少.

Question

假设递增有序的顺序表AB分别表示一个集合,设计算法以判断集合A受否是集合B的子集
若是,则返回TRUE,若否,则返回FALSE,并要求时间尽量少.

Answer 1

由于A和B都是有序集合,那么,可以采用一次遍历来判断A是否为B的子集.遍历的过程如下：
1.用两个指针a和b,分别指向A和B的第一个元素；
2.取出指针a处取出一个元素ai；
3.从指针b处取出一元素bi；
4.将ai和bi进行比较,如果ai等于bi,跳至5处继续执行,如果ai小于bi,b指针后移一位,跳至3处继续执行；如果bi大于ai,则证明元素ai未在B集合中出现,返回FALSE；
5.指针a,b分别后移一位,若a指针已超出A集合的范围,则证明A中所有元素均在B中出现,即A是B的子集,返回TRUE；若b指针已超出B集合的范围,则说明A中剩余元素不可能在B中出现,返回FALSE；否则跳回2处继续执行；
以下代码是依照上面算法编写,可以做为参考：
#define TRUE 1
#define FALSE 0
int isSubset(int *a,int len_a,int *b,int len_b)
{
int i,j;
// 加入了对A、B中剩余元素数量的判断条件,以提高算法的执行效率
for(i = 0,j = 0; i < len_a && j < len_b && len_b - j >= len_a - i; ++i,++j)
{
// 从B中寻找ai
while(b[j] < a[i] && j < len_b)
{
++j;
}
// 若bj>ai,则结束查找过程
if(j >= len_b || b[j] > a[i])
{
break;
}
}
// 若已完成了对A的遍历,则说明A是B的子集,否则不是
if(i == len_a)
{
return TRUE;
}
return FALSE;
}