集合的定义

集合在数学中的定义如下：

集合是具有某种相同数据类型的数据元素，或是一些确认对象的汇集。通常用大写英文字母
A，B，C，… 表示，它的元素通常用小写英文字母 a，b，c，… 表示．

集合可以没有元素，这样的集合叫做空集，用  或符号  表示。如果集合含有有限个元素，那么这个集合可以称为有限集。如果集合含有无限个元素，那么这个集合可以称为无限集。

集合的特性

无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的。

互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。

确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

元素与集合的关系：

（1）如果 a 是集合A的元素，就说 a 属于 A，

     　 记作 aÎA，读作“a 属于 A”；

（2）如果 a 不是集合 A 的元素，就说 a 不属于 A ，

          记作 aÏA，读作“a 不属于 A”.

集合与子集的关系

集合A，B，若∀a∈A，有a∈B；A⊆B。则称A是B的子集，亦称A包含于B，或B包含A，记作A⊆B。

若A⊆B，且A≠B，则称A是B的真子集，亦称A真包含于B，或B真包含A，记作A⊂B。

交、并、差集

给定集合A，B，定义运算∪如下：A∪B = {e|e∈A 或 e∈B}。A∪B称为A和B的并集。

给定集合A，B，定义运算∩如下：A∩B = {e|e∈A 且 e∈B}。A∩B称为A和B的交集。若 A ∩ B  =  ，则 A 和 B 称作不相交。

给定集合A，B，定义运算-如下：A - B = {e|e∈A 且 eB}。A - B称为B对于A的差集，相对补集或相对余集。

给定集合A，B，定义对称差运算△如下：A△B= (A-B)∪(B-A)。

集合的操作

根据以上对集合的定义给出集合的常用操作如下：

（1）   构造一个集合

（2）   添加元素

（3）   删除元素

（4）   返回第i个元素

（5）   判断是否包含元素 o

（6）   是否包某个含集set

（7）   求并集

（8）   求交集

（9）   求差集

（10） 求元素的个数

Set集合操作接口

根据集合常用操作，对集合抽象数据类型定义Set接口如下：

package set;

public interface Set {
	/**
	 * 求元素的个数
	 * @return
	 */
	public  int size();
	/**添加元素
	 * 
	 * @param o
	 */
	public void add(Object o);
	/**
	 * 返回第i个元素
	 * @param i
	 * @return
	 */
	public Object get(int i);
	/**
	 * 删除元素
	 * @param o
	 */
	public void remove(Object o);
	/**
	 * 判断是否包含元素 o
	 * @param o
	 * @return
	 */
	public boolean contain(Object o);
	/**
	 * 是否包含集set
	 * @param set
	 * @return
	 */
	public boolean include(Set set);
	/**
	 * 求并集
	 * @param set
	 * @return
	 */
	public Set unionSet(Set set);
	/**
	 * 求交集
	 * @param set
	 * @return
	 */
	public Set intersection(Set set);
	/**
	 * 求差集
	 * @param set
	 * @return
	 */
	public Set differenceSet(Set set);
	/**
	 * 是否为空
	 * @return
	 */
	public boolean isEmpty();
}

顺序结构的集合类实现

集合也是一种特殊的线性表，可以用顺序结构和链式结构存储。下面给出顺序结构的集合类实现。

package set;

public class ArraySet implements Set {
	/**
	 * 集合默认的初始大小
	 */
	public static final int defLen = 10;
	private int maxLen;	//数组的大小
	private int size;	//元素的大小
	private Object[] e;	
	
	public ArraySet() {
		maxLen = defLen;
		e = new Object[maxLen];
		size = 0;
	}
	/**
	 * 构造函数
	 * @param len 数组的大小
	 */
	public ArraySet(int len) {
		this.maxLen = len;
		e = new Object[maxLen];
		size = 0;
	}
	
	public ArraySet(Set set) {
		size = maxLen = set.size();
		for(int i=0; i<size; i++) {
			e[i] = set.get(i);
		}
	}
	
	/*public boolean valid(Object o) {
		return 
	}*/
	
	private void clear() {
		size = 0;
	}
	
	private void expand() {
		maxLen = 2*maxLen;
		Object newArray[] = new Object[maxLen];
		for(int i=0; i<size; i++) {
			newArray[i] = e[i];
		}
		e = newArray;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public void add(Object o) {
		if(!contain(o)) {
			if(size >= maxLen) {
				expand();
			}
			e[size] = o;
			size ++;
		}
	}

	@Override
	public void remove(Object o) {
		if(!contain(o))
			throw new IllegalArgumentException("this set is not contain o element!");
		else {
			int k = index(o);
			for(int i=k; i<size-1; i++) {
				e[i] = e[i+1];
			}
			size --;
		}
	}
	
	private int index(Object o) {
		int i=0;
		while(i<size) {
			if(e[i] == o)
				return i;
			i++;
		}
		return -1;
	}

	@Override
	public boolean contain(Object o) {
		int i = 0;
		while(i<size) {
			if(e[i] == o)
				return true;
			i++;
		}
		return false;
	}

	@Override
	public boolean include(Set set) {
		if(set.size() > size)
			return false;
		else if(set.size() == 0)
			return true;
		else {
			boolean b = true;
			for(int i=0; i<set.size(); i++) {
				b = b && contain(set.get(i));
				if(!b)
					return false;
			}
			return b;
		}
	}

	@Override
	public Set unionSet(Set set) {
		int len = size + set.size();
		Set rSet = new ArraySet(len);
		//int i=0; 
		for(int i=0; i<size; i++) {
			rSet.add(e[i]);
		}
		for(int i=0; i<set.size(); i++) {
			Object obj = set.get(i);
			if(!contain(obj))
				rSet.add(obj);
		}
		return rSet;
	}

	@Override
	public Set intersection(Set set) {
		int len = size<set.size() ? size : set.size();
		Set rSet = new ArraySet(len);
		for(int i=0; i<set.size(); i++) {
			Object obj = set.get(i);
			if(contain(obj))
				rSet.add(obj);
		}
		return rSet;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public Object get(int i) {
		if(i<0 && i>= size) {
			throw new ArrayIndexOutOfBoundsException(i);
		}else  {
			return e[i];
		}
	}
	@Override
	public Set differenceSet(Set set) {
		Set rSet = new ArraySet(size);
		for(int i=0; i<size; i++) {
			if(!set.contain(e[i]))
				rSet.add(e[i]);
		}
		return rSet;
	}
	@Override
	public boolean equals(Object obj) {
		// TODO Auto-generated method stub
		return super.equals(obj);
	}
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("{");
		for(int i=0; i<size; i++) {
			if(i == size-1)
				sb.append(e[i]);
			else
				sb.append(e[i] + ", ");
		}
		sb.append("}");
		return sb.toString();
	}
	
	

}

测试集合

package set;

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Set a = new ArraySet();
		Set b = new ArraySet();
		Set c = new ArraySet();
		Set d = new ArraySet();
		a.add(2); a.add(3); a.add(4); a.add(8);
		b.add(3); b.add(4); b.add(5);
		c.add(3); c.add(4);
		System.out.println(a.size());
		System.out.println(b.size());
		System.out.println(a);
		System.out.println(a.isEmpty());
		System.out.println(a.get(1));
		System.out.println(a.unionSet(b));
		System.out.println(a.intersection(b));
		System.out.println(a.differenceSet(b));
		System.out.println(a.include(b));
		System.out.println(a.include(c));
		a.remove(8);
		System.out.println(a);
	}

}