一、题目:
假设递增有序的带头结点的链表A、B分别表示一个集合,试设计算法以判断集合A是否是集合B的子集,如是返回1,否则返回0。
二、思路:
1.A的值大于B的值,那就A的元素不变,B指向下一个元素,再比较;
2.A的值小于B的值,那就A指向下一个元素,B的元素不变,再比较;
3.A的值等于B的值,然后A,B同时指向下一个元素,而且n累加1;(此处的n最后用来与A链表的长度比较,若n=A链表的长度,则说明A的元素在B中全部都有,即A是B的子集)
三、思路的代码:
public boolean gather(Node a,Node b){
Node A=a.next; //指向链表A的第一个结点
Node B=b.next; //指向链表B的第一个结点
int n=0; //用来计数
while(A!=null){
while(B!=null){
if(A.data<B.data){ //如果集合A的数值大于集合B中的数值
A=A.next;//A的指针指向下一个元素,B的指针不变,依旧是这个元素
break;//终止内循环,从外循环开始,A的在一个元素和B的本元素比较
}
if(A.data==B.data){//如果集合A的数值等于集合B中的数值
A=A.next; //A的指针指向下一个元素
B=B.next; //B的指针指向下一个元素
n++; //当n的值等于A集合的元素个数,说明A是B的子集
break;
}
if(A.data>B.data){ //如果集合A的数值小于集合B的数值
B=B.next;//那么B的指针指向下一个元素,A的指针依旧是指向本元素
if(A.next==null&&B.next==null){
if(A.data==B.data)//A和B均为最后一个元素且相等,则计数
n++;
A=A.next; //如果A和B均为最后一个元素不相等, 则A指向空,让外部循环停止
}
break;
}
}
}
if(n==List_Length(a)) //当n的值等于A集合的元素个数,说明A是B的子集
return true;
else
return false;
}
四、完整程序的输出结果:
①A为非空集合
②A为空集合