数据结构——集合

集合是具有某种相似特性的事物的全体。它的重要特点是其中的数据元素无序且不重复，这也就是判断是否使用该容器的依据。

集合类既可以基于向量类来实现，也可以用其他方法比如基于哈希表来实现，本文讨论基于向量类。首先我们要在上文建立的向量类中添加四个函数，以方便集合类的设计。

四个函数如下：

public int indexOf(Object element){ if(element == null){ for(int i=0;i<elementCount;i++) if(elementData[i] == null) return i; }else{ for(int i=0;i<elementCount;i++) if(element.equals(elementData[i])) return i; } return -1; } public boolean contain(Object element){ return indexOf(element)>=0; } public void remove(Object element){ int i = indexOf(element); if(i>=0){ remove(i); } } public void remove(int index){ if(index>=elementCount){ throw new ArrayIndexOutOfBoundsException(index+">="+elementCount); } else if(index<0){ throw new ArrayIndexOutOfBoundsException(index); } int j = elementCount-index-1; if(j>0){ System.arraycopy(elementData, index+1, elementData, index, j); } elementCount--; elementData[elementCount] = null; } 接着设计集合类：（主要是集合的属于，包含，相等操作）

package ArrayVectorSetMatrix; /** * @author sun * 创建时间：2017年4月13日下午2:45:16 */ //基于向量类的集合类实现方法 public class MySet { private MyVector values = new MyVector(); public void add(Object obj){ if(obj == null) return; if(values.indexOf(obj)<0)//判断集合中是否已存在相等元素 values.add(obj); } public void remove(Object obj){ values.remove(obj); } public boolean contain(Object obj){//数据元素obj是否属于集合 return values.contain(obj); } public boolean include(Object obj){//当前对象集合是否包含集合otherSet if(obj instanceof MySet){//首先要判断obj是不是集合 MySet set = (MySet)obj; int counter = 0; while(counter<set.values.size()){ Object temp = set.values.get(counter); counter++; if(!contain(temp)) return false; } return true; } else return false; } public boolean equals(Object obj){//相等 if(obj instanceof MySet){ MySet set = (MySet)obj; if(include(set) && set.include(this)) return true; else return false; } else return false; } public int size(){ return values.size(); } public boolean isEmpty(){ return values.size()>0; } public void print(){ int counter = 0; while(counter < values.size()){ System.out.print(values.get(counter)+" "); counter++; } } } 测试功能：

package ArrayVectorSetMatrix; /** * @author sun * 创建时间：2017年4月13日下午3:16:06 */ public class TestMySet { public static void main(String[] args) { MySet os1 = new MySet(); MySet os2 = new MySet(); MySet os3 = new MySet(); os1.add(new Integer(0)); os1.add(new Integer(2)); os1.add(new Integer(5)); os2.add(new Integer(5)); os2.add(new Integer(0)); os2.add(new Integer(2)); os2.add(new Integer(5));//测试添加重复元素 os3.add(new Integer(7)); os3.remove(new Integer(7)); System.out.print("Set of os1 is:{"); os1.print(); System.out.println("}"); System.out.print("Set of os2 is:{"); os2.print(); System.out.println("}"); System.out.print("Set of os3 is:{"); os3.print(); System.out.println("}"); if(os1.include(os3)) System.out.println("os1 including os3"); else System.out.println("os1 does not including os3"); if(os1.include(os2)) System.out.println("os1 including os2"); else System.out.println("os1 does not including os2"); if(os1.equals(os2)) System.out.println("os1 is equal with os2"); else System.out.println("os1 is not equal with os2"); } }