集合的抽象数据类型采用Java中的接口来描述。定义如下：
piblic interface Set{ boolean add(Object obj); //向集合中插入一个元素obj boolean remove(Object obj); //从集合中删除一个元素obj boolean contains(Object obj); //判断一个元素obj是否属于集合 Object value(int i); //返回集合中第i个元素的值 Object find(Object obj); //从集合中按值obj查找元素并返回 int size(); //求出集合中元素的个数 boolean isEmpty(); //判断集合是否为空 void output(); //输出集合中所有元素 Set union(Set set); //求当前集合与参数集合set的并集并返回 Set intersection(Set set); //求当前集合与参数集合set的交集并返回 void clear(); //清除集合中所有元素，并使之变为空集} 一般来说，数据结构都分为两种存储方式：顺序存储和链接存储。后面的文章中我们介绍其他数据结构的时候也会分为这两种情况。
1.集合的顺序存储结构和操作实现如下：
public class SequenceSet implements Set{ final int minSize=10; //数组初始长度 private Object[] setArray; //数组声明 private int len; //保存集合当前的长度 public SequenceSet() //无参构造方法定义 { len=0; setArray=new Object[minSize]; } public SequenceSet(int n) //带数组长度参数构造方法定义 { if(n <0||i>len) { System.out.println("输入参数i数值有误，应在1和"+len+"之间!"); System.exit(1); } return setArray[i-1]; } public Object find(Object obj) { for(int i=0;i 主类程序调试如下：
public class Example{ public static void main(String[] args) { Set set1=new SequenceSet(10); int[] a={20,16,38,42,29}; for(int i=0;i 程序运行结果：
20
16
38
42
29
35
16
29
20
29
38
42
set1的集合长度：4
set1 contains 29
2.集合的链接存储结构和操作实现如下：
结点类：
public class Node{ Object element; Node next; public Node(Node nt) {next=nt;} public Node(Object obj,Node nt) { element=obj;next=nt; }} 实现：
public class LinkSet implements Set{ private Node head; private int len; public LinkSet() { len=0; head=new Node(null); } public boolean add(Object obj) { Node p=head; while(p.next!=null){ if(p.next.element.equals(obj)) return false; else p=p.next; } p.next=new Node(obj,null); len++; return true; } public boolean remove(Object obj) { Node p=head; while(p.next!=null) if(p.next.element.equals(obj)) break; else p=p.next; if(p.next!=null){ p.next=p.next.next; len--; return true; } else return false; } public boolean contains(Object obj) { Node p=head.next; while(p!=null){ if(p.element.equals(obj)) return true; else p=p.next; } return false; } public Object value(int i) { if(i<=0||i>len){ System.out.println("参数i值有误，应该在1和"+len+"之间！"); System.exit(1); } int c=1; Node p=head.next; while(p!=null) if(c==i) break; else {c++;p=p.next;} return p.element; } public Object find(Object obj) { Node p=head.next; while(p!=null) { if(p.element.equals(obj)) return p.element; else p=p.next; } return null; } public int size() {return len;} public boolean idEmpty() {return len==0;} public void output() { Node p=head.next; while(p!=null){ System.out.println(p.element.toString()); p=p.next; } System.out.println(); } public Set union(Set set) { LinkSet setTemp=new LinkSet(); Node p=head.next; Node q=setTemp.head; while(p!=null){ Node r=new Node(p.element,null); p=p.next; q.next=r; q=r; } setTemp.len=len; LinkSet dset=(LinkSet)set; p=dset.head.next; while(p!=null){ Object x=p.element; boolean b=contains(x); if(!b){ q.next=new Node(x,null); q=q.next; setTemp.len++; } p=p.next; } return setTemp; } public Set intersection(Set set) { LinkSet setTemp=new LinkSet(); LinkSet dset=(LinkSet)set; Node p=dset.head.next; Node q=setTemp.head; while(p!=null){ Object x=p.element; boolean b=contains(x); if(b){ q.next=new Node(x,null); q=q.next; setTemp.len++; } p=p.next; } return setTemp; } public void clear() { len=0; head.next=null; }
主类程序调试如下：
public class Example{ public static void main(String[] args) { Set set1=new LinkSet(10); int[] a={20,16,38,42,29}; for(int i=0;i 结果与顺序存储结构中的调试类运行结果相同。
（完）