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;
}