摘要 集合最重要的特点就是它里面的元素是不会存在重复的,所以集合的内部实现中,添加元素函数是需要先判断是否已经存在这个元素,是代码实现的核心部分。 集合是一个存储数据的序列,序列中的元素不会存在重复,这个就是集合最重要的特点。 就是因为这个特点,它可以被用作序列中元素的去重处理,比如存放新增加的IP,统计新增的IP数量,存放词汇或者统计词汇量等。 集合的内部实现可以直接利用之前学过的数据结构来实现,比如动态数组、链表、AVL树或者红黑树(属于二叉搜索树)。 这里先用动态数组来实现集合。首先创建一个动态数组的对象来存放元素。privateListElistnewLinkedList(); 集合中的其他函数,比如集合中的元素数量、集合是否为空、清除集合中的所有元素和集合中是否包含某个元素这4个函数可以直接调用list的函数来处理,比如实现集合中的元素数量:集合中的元素数量publicintsize(){returnlist。size();} 移除集合中的元素函数需要先在list中找到元素的index,然后再移除list中的index位置元素。ELEMENTNOTFOUND:集合空元素标识符,常量为1publicvoidremove(Eelement){intindexlist。indexOf(element);if(index!List。ELEMENTNOTFOUND){list。remove(index);}} 最后就是实现集合的主要函数,即添加元素函数。因为集合要满足元素不可以重复的要求,所以在添加元素的时候需要先判断集合中是否已经存在该元素:publicvoidadd(Eelement){intindexlist。indexOf(element);if(index!List。ELEMENTNOTFOUND){存在,则替换list。set(index,element);}else{不存在,则直接添加list。add(element);}} 如果用AVL树或者红黑树,那么添加元素的逻辑就更简单。因为这两种树中的元素都是不会有重复的,所以使用这两种树来实现,就直接调用树的添加函数就可以实现。publicvoidadd(Eelement){tree。add(element);} 集合中的其他函数,就可以直接使用树已经有的函数来直接调用,和套用动态数组的方式是一样的。