集合

2021年9月5日 18点热度 0条评论 来源: luoweifu

集合的定义

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

集合是具有某种相同数据类型的数据元素,或是一些确认对象的汇集。通常用大写英文字母 ABC,… 表示,它的元素通常用小写英文字母 abc,… 表示.

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

集合的特性

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

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

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

元素与集合的关系:

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

}

结果

4
3
{2, 3, 4, 8}
false
3
{2, 3, 4, 8, 5}
{3, 4}
{2, 8}
false
true
{2, 3, 4}

    原文作者:luoweifu
    原文地址: https://blog.csdn.net/luoweifu/article/details/8655874
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。