确定性跳跃表Java实现Word

1、1-5确定性跳跃表java实现作者：云南大学软件学院09数字媒体技术 雒森/* * to change this template, choose tools | templates * and open the template in the editor. */package luosen.ds.ds;import java.io.serializable;/* * * author lenovo */*确定性跳跃表链的结点*/public class dsllinknode<s> implements serializable /*跳跃表链结点的层数*/ public int

2、 levelnum=1; /*跳跃表链结点的数据*/ public s data; /*顶部的链*/ public dslnode<s> top; /*构造函数*/ public dsllinknode() data=null; top=null; /*构造函数*/ public dsllinknode(s data,dslnode<s> top) this.data=data; this.top=top; /*构造函数*/ public dsllinknode(s data,dslnode<s> top,int i) this.data=data; thi

3、s.top=top; this.levelnum=i; /*判断节点是否相等*/ override public boolean equals(object o) if(this=o) return true; if(o=null|!(o instanceof dsllinknode) return false; dsllinknode<s> a=(dsllinknode<s>)o; if(data.equals(a.data) return true; return false; override public int hashcode() int hash = 7;

4、 hash = 41 * hash + this.levelnum; hash += 41 * hash + (this.data != null ? this.data.hashcode() : 0); return hash; override public string tostring() return ""+data; /* * to change this template, choose tools | templates * and open the template in the editor. */package luosen.ds.ds;import

5、java.io.serializable;/* * * author lenovo */*确定性跳跃表结点*/public class dslnode<s> implements serializable /*向右的链*/ public dslnode<s> right; /*向下的链*/ public dslnode<s> down; /*确定性跳跃表链的结点*/ public dsllinknode<s> link; /*默认构造函数*/ public dslnode() right=down=null; link=null; /*构造函数*

6、/ public dslnode(dslnode<s> right) this.right=right; this.down=null; link=null; /*构造函数*/ public dslnode(dslnode<s> right,dslnode<s> down) this.right=right; this.down=down; link=null; /*构造函数*/ public dslnode(dslnode<s> right,dslnode<s> down,dslnode<s> top,int i) th

7、is.right=right; this.down=down; link=new dsllinknode<s>(s)new object(),top,i); /*构造函数*/ public dslnode(dslnode<s> right,dslnode<s> down,dsllinknode<s> link) this.right=right; this.down=down; this.link=link; /*判断节点是否相等*/ override public boolean equals(object o) if(this=o) retu

8、rn true; if(o=null|!(o instanceof dslnode) return false; dslnode a=(dslnode)o; if(link=a.link|(link!=null&&link.equals(a.link) return true; return false; override public int hashcode() int hash = 7; hash = 47 * hash + (this.link != null ? this.link.hashcode() : 0); return hash; override publ

9、ic string tostring() if(link!=null) return link.tostring(); else return "" /* * to change this template, choose tools | templates * and open the template in the editor. */package luosen.ds.ds;import luosen.ds.alg.util.createcomparator;import luosen.ds.exceptions.illegalparameterexception;i

10、mport java.io.serializable;import java.util.collection;import java.util.comparator;import java.util.hashset;import java.util.iterator;import java.util.list;import java.util.set;import java.util.logging.level;import java.util.logging.logger;/* * * author 云大09数媒雒森 */*1-5确定性跳跃表*/public class dskiplist&

11、lt;s> implements serializable,iterable<s> /*头结点*/ protected dslnode<s> header; /*尾结点*/ protected dslnode<s> tailer=null; /*底结点*/ protected dslnode<s> bottom=null; /*表中元素的个数*/ protected int size=0; /*比较器*/ protected comparator<s> cp=null; /*构造函数*/ public dskiplist() b

12、ottom=null; tailer=null; header=new dslnode<s>(tailer,bottom,null, (byte)0); /*构造函数*/ public dskiplist(comparator<s> cp) bottom=null; tailer=null; header=new dslnode<s>(tailer,bottom,null,(byte)0); this.cp=cp; /*使用一个dskiplist跳表初始化，目的是将目标复制到当前表中*/ public boolean initial(dskiplist<

13、;s> dsl) if(dsl=null) return false; this.cp=dsl.cp; this.header=dsl.header; this.size=dsl.size; return true; /*返回跳跃表的头*/ public dslnode<s> getheader() return header; /*设置比较器*/ public void setcomparator(comparator<s> cp) this.cp=cp; /*返回比较器*/ public comparator<s> getcomparator()

14、return cp; /*判断表中是否有关键字对应值*/ public boolean contain(s data) return this.search(data)!=null; /*查找数据为data的数据比较关键字封装在data中*/ public s search(s data) if(data=null|size=0) return null; dslnode<s> cur=header; while(cur!=bottom) while(cur.right!=tailer&&pare(cur.right.link.data,data)<0) cu

15、r=cur.right; if(cur.right!=tailer&&pare(cur.right.link.data,data)=0) return cur.right.link.data; cur=cur.down; return null; /*查找数据为data的数据比较关键字封装在data中,若查不到则返回位于它之后的第一个（最底部）结点*/ public dslnode<s> searchstart(s data) if(data=null|size=0) return null; dslnode<s> cur=header; while(c

16、ur!=bottom) while(cur.right!=tailer&&pare(cur.right.link.data,data)<0) cur=cur.right; if(cur.down=bottom|(cur.right!=tailer&& pare(cur.right.link.data,data)=0) cur=cur.right; if(cur!=tailer) while(cur.down!=bottom) cur=cur.down; return cur; cur=cur.down; return null; /*查找数据为data的数

17、据比较关键字封装在data中,若查不到则返回位于它之前的第一个（最底部）结点*/ public dslnode<s> searchend(s data) if(data=null|size=0) return null; dslnode<s> cur=header; while(cur!=bottom) while(cur.right!=tailer&&pare(cur.right.link.data,data)<0) cur=cur.right; if(cur.down=bottom|(cur.right!=tailer&& pa

18、re(cur.right.link.data,data)=0) cur=cur.right; if(cur!=tailer) while(cur.down!=bottom) cur=cur.down; if(cur.right!=tailer&&pare(cur.right.link.data,data)=0) cur=cur.right; return cur; cur=cur.down; return null; /*插入数据data,若已存在返回数据链结点，并不插入数据，你可以在外面修改*/ public dsllinknode<s> insert(s dat

19、a) throws illegalparameterexception if(data=null) return null; if(cp=null) if(comparable.class.isassignablefrom(data.getclass() createcomparator<s> cc =new createcomparator<s>(); cp=cc.getcomparator(); else throw new illegalparameterexception("数据不可以比较，请先设置比较器！"); dslnode<s&g

20、t; cur=header; dslnode<s> newnode=null; while(cur!=bottom) while(cur.right!=tailer&&pare(cur.right.link.data,data)<0) cur=cur.right; if(cur.right!=tailer&&pare(cur.right.link.data,data)=0) newnode=cur.right; break; if(cur.down=bottom) newnode=new dslnode<s>(cur.right,b

21、ottom); newnode.link=new dsllinknode<s>(data,newnode); cur.right=newnode; size+; break; else if(cur.down.right!=tailer&&cur.down.right.right!=tailer &&cur.down.right.right.right!=tailer&& cur.down.right.right.right.right!=tailer&& cur.down.right.right.right.righ

22、t.right!=tailer&& (cur.right=tailer|pare(cur.down.right.right.right .right.right.link.data,cur.right.link.data)<0) cur.right=new dslnode<s>(cur.right,cur.down.right.right.right,cur.down.right.right.right.link); cur.right.link.top=cur.right; cur.right.link.levelnum+; cur=cur.down; if

23、(header.right!=tailer) header.link.levelnum+; header.link.top=header; header=new dslnode<s>(tailer,header,header.link); return newnode.link; /*删除数据data*/ public boolean remove(s data) throws illegalparameterexception if(data=null|size=0) return false; if(cp=null) if(comparable.class.isassignab

24、lefrom(data.getclass() createcomparator<s> cc =new createcomparator<s>(); cp=cc.getcomparator(); else throw new illegalparameterexception("数据不可以比较，请先设置比较器！"); dslnode<s> cur=header; dslnode<s> c=null,cc=null,top=null; while(cur!=bottom) while(cur.right!=tailer&&

25、amp;pare(cur.right.link.data,data)<0) cur=cur.right; if(cur.down=bottom&&cur.right!=tailer&&pare(cur.right.link.data,data)=0) if(size=1) header=new dslnode<s>(tailer,bottom,null,(byte)0); else if(cur.link.levelnum<cur.right.link.levelnum)/比较左右位置结点层数高低，待删除的右边结点 c=cur.right

26、.link.top; top=cur.right.link.top; cur.link.levelnum=cur.right.link.levelnum; while(c.down!=cur.link.top.right) c.link=cur.link; c=c.down; c.link=cur.link; c.down=cur.link.top; c=cur.link.top.right; cc=cur.link.top; while(c!=bottom&&cc!=bottom) cc.right=c.right; cc=cc.down; c=c.down; cur.lin

27、k.top=top; else cc=cur.link.top; while(cc.right!=cur.right.link.top) cc=cc.down; c=cur.right.link.top; while(c!=bottom&&cc!=bottom) cc.right=c.right; cc=cc.down; c=c.down; size-; while(header.down!=bottom&&header.down.right=tailer) header=header.down; header.link.levelnum-; header.li

28、nk.top=header.down; return true; cur=cur.down; return false; /*获取条件一维区间odr之间的元素集合,该函数主要服务于：kdskiplist<s>,用于检索一维区间*/ public collection<s> queryregion(odregion<s> odr) set<s> s=new hashset<s>(); if(odr.isnohascondition) dslnode<s> cur=header; while(cur.down!=bottom)

29、 cur=cur.down; cur=cur.right; while(cur!=tailer) if(cur.link.data instanceof kdslnode) s.addall(kdslnode)cur.link.data).set); else s.add(cur.link.data); cur=cur.right; else dslnode<s> cur=header; dslnode<s> end=null; if(odr.start!=null) cur=this.searchstart(odr.start); else while(cur.dow

30、n!=bottom) cur=cur.down; cur=cur.right; end=this.searchend(odr.end); if(cur=null|(cur!=null&&end!=null&&pare(cur.link.data, end.link.data)>0) return s; while(cur!=end) if(cur.link.data instanceof kdslnode) s.addall(kdslnode)cur.link.data).set); else s.add(cur.link.data); cur=cur.r

31、ight; return s; /*获取条件一维区间odr之间的元素满足多维条件的数据集合,index为odr在qc中的位置, * 该函数主要服务于：mldskiplist<s> 用于检索多位区间*/ public collection queryregion(collection s,odregion<s> odr,int index ,list<odregion<s>> qc,list<comparator<s>> cps) if(s=null) return s; if(odr.isnohascondition) d

32、slnode<s> cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; while(cur!=tailer) if(cur.link.data instanceof mldslnode) mldslnode a=(mldslnode) cur.link.data; if(a.dslsl=null) if(this.ismeetqc(cur.link.data, index, qc.size(), qc, cps,index,true) s.add(a.data); else a.dslsl.queryre

33、gion(s,qc.get(index+1), index+1, qc, cps); else if(this.ismeetqc(cur.link.data, 0, qc.size(), qc, cps,index,true) s.add(cur.link.data); cur=cur.right; else dslnode<s> cur=header; dslnode<s> end=null; if(odr.start!=null) cur=this.searchstart(odr.start); else while(cur.down!=bottom) cur=cu

34、r.down; cur=cur.right; end=this.searchend(odr.end); if(cur=null|(cur!=null&&end!=null&&pare(cur.link.data, end.link.data)>0) return s; while(cur!=end) if(cur.link.data instanceof mldslnode) mldslnode a=(mldslnode) cur.link.data; if(a.dslsl=null) if(this.ismeetqc(cur.link.data, ind

35、ex, qc.size(), qc, cps,index,true) s.add(a.data); else a.dslsl.queryregion(s,qc.get(index+1), index+1, qc, cps); else if(this.ismeetqc(cur.link.data, 0, qc.size(), qc, cps,index,true) s.add(cur.link.data); cur=cur.right; return s; /*检测元素o是否满足多位区间条件qc,start为数组偏移索引,end为结束索引， * isfiltercondition表示是否忽略f

36、ilterindex标识的位置的一维区间条件*/ protected boolean ismeetqc(s o,int start,int end,list<odregion<s>> qc,list<comparator<s>> cps,int filterindex, boolean isfiltercondition) for(int i=start;i<end;i+) if(qc.get(i).isnohascondition|(isfiltercondition&& i=filterindex)|(qc.get(i)

37、.start=null&&qc.get(i).end=null) continue; if(qc.get(i).start!=null&&cps.get(i).compare(o, qc.get(i).start)<0)|(qc.get(i).end!=null&& cps.get(i).compare(o, qc.get(i).end)>0) return false; return true; /*返回表中元素的个数*/ public int size() return size; /*返回确定性跳跃表的层数*/ public i

38、nt getlevel() return header.down = null ? 0:header.down.link.levelnum; /*转化为数组,若表中有0个元素返回null*/ public object toarray() if(size=0) return null; object o=new objectsize; int i=0; dslnode<s> cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; while(cur!=tailer) oi=cur.link.data; cur

39、=cur.right; i+; return o; /*当划分跳表后更新跳表元素个数*/ public void updatesize() int i=0; dslnode<s> cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; while(cur!=tailer) cur=cur.right; i+; size=i; /*返回最小的元素,若不存在返回null*/ public s mindata() if(size=0) return null; dslnode<s> cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; return cur=null ? null:cur.link.data; /*返