首页 > 代码库 > 数据结构之集合实现
数据结构之集合实现
集合的抽象数据类型采用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<minSize) n=minSize;
len=0;
setArray=new Object[n];
}
public boolean add(Object obj)
{
for(int i=0;i<len;i++)
if(setArray[i].equals(obj)) retrun false;
if(len==setArray.length){
Object[] p=new Object[len*2];
for(int i=0;i<len;i++) p[i]=setArray[i];
setArray=p;
}
setArray[len]=obj;
len++;
return true;
}
public boolean remove(Object obj)
{
itn i;
for(i=0;i<len;i++)
if(setArray[i].equals(obj)) break;
if(i<len){
setArray[i]=setArray[len-1];
len--;
return true;
}
else return false;
}
public boolean contains(Object obj)
{
for(int i=0;i<le;i++)
{
if(setArray[i].equals(obj)) return true;
}
return false;
}
public Object value(int i)
{
if(i<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<len;i++)
if(setArray[i].equals(obj)) return setArray[i];
return null;
}
public int size() {return len;}
public boolean isEmpty(){return len==0;}
public void output()
{
for(int i=0;i<len;i++)
System.out.println(setArray[i].toString())；
System.out.println();
}
public Set union(Set set)
{
SequenceSet dset=(SequenceSet)set;
SequceceSet setTemp=new SequenceSet(len+dset.len);
int i;
for(i=0;i<len;i++)
setTemp.setArray[i]=setArray[i];
setTemp.len=len;
for(i=0;i<dset.len;i++)
{
Object x=dset.setArray[i];
boolean b=contains(x);
if(!b) setTemp.setArray[setTemp.len++]=x;
}
return setTemp;
}
public Set intersection(Set set)
{
Sequence dset=(SequenceSet)set;
int c;
if(len<dset.len) c=len;else c=dset.len;
SequenceSet setTemp=new SequenceSet(c);
for(int i=0;i<dest.len;i++)
{
Object x=dset.setArray[i];
boolean b=contains(x);
if(b) setTemp.setArray[setTemp.len++]=x;
}
return setTemp;
}
public void clear()
{
len=0;
}
}主类程序调试如下：
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<a.length;i++) set1.add(a[i]);
Set set2=new SequenceSet();
set2.add(16); set2.add(29); set2.add(35);
Set set3;
set3=set1.union(set2);
set3.output();
Set set4;
set=set1.intersection(set2);
set4.output();
set1.remove(new Integer(16));
set1.output();
System.out.println("set1集合长度："+set1.size());
boolean bb=set1.contains(29);
if(bb) System.out.println("set1 contains "+29);
}
}程序运行结果：
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<a.length;i++) set1.add(a[i]);
Set set2=new LinkSet();
set2.add(16); set2.add(29); set2.add(35);
Set set3;
set3=set1.union(set2);
set3.output();
Set set4;
set=set1.intersection(set2);
set4.output();
set1.remove(new Integer(16));
set1.output();
System.out.println("set1集合长度："+set1.size());
boolean bb=set1.contains(29);
if(bb) System.out.println("set1 contains "+29);
}
}结果与顺序存储结构中的调试类运行结果相同。
（完）
本文出自 “仙路千叠惊尘梦” 博客，请务必保留此出处http://secondscript.blog.51cto.com/9370042/1598105
数据结构之集合实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。