《确定性跳跃表Java实现（Word）.doc》由会员分享，可在线阅读，更多相关《确定性跳跃表Java实现（Word）.doc（23页珍藏版）》请在三一文库上搜索。
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 implements Serializable /*跳跃表链结点的层数*/ public int levelNum
2、=1; /*跳跃表链结点的数据*/ public S data; /*顶部的链*/ public DSLNode top; /*构造函数*/ public DSLLinkNode() data=null; top=null; /*构造函数*/ public DSLLinkNode(S data,DSLNode top) this.data=data; this.top=top; /*构造函数*/ public DSLLinkNode(S data,DSLNode top,int i) this.data=data; this.top=top; this.levelNum=i; /*判断节点是否
3、相等*/ Override public boolean equals(Object o) if(this=o) return true; if(o=null|!(o instanceof DSLLinkNode) return false; DSLLinkNode a=(DSLLinkNode)o; if(data.equals(a.data) return true; return false; Override public int hashCode() int hash = 7; hash = 41 * hash + this.levelNum; hash += 41 * hash +
4、 (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 java.io.Serializable;/* * * author LENOVO */*确定性跳跃表结点*/public clas
5、s DSLNode implements Serializable /*向右的链*/ public DSLNode right; /*向下的链*/ public DSLNode down; /*确定性跳跃表链的结点*/ public DSLLinkNode link; /*默认构造函数*/ public DSLNode() right=down=null; link=null; /*构造函数*/ public DSLNode(DSLNode right) this.right=right; this.down=null; link=null; /*构造函数*/ public DSLNode(D
6、SLNode right,DSLNode down) this.right=right; this.down=down; link=null; /*构造函数*/ public DSLNode(DSLNode right,DSLNode down,DSLNode top,int i) this.right=right; this.down=down; link=new DSLLinkNode(S)new Object(),top,i); /*构造函数*/ public DSLNode(DSLNode right,DSLNode down,DSLLinkNode link) this.right=
7、right; this.down=down; this.link=link; /*判断节点是否相等*/ Override public boolean equals(Object o) if(this=o) return 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
8、 = 7; hash = 47 * hash + (this.link != null ? this.link.hashCode() : 0); return hash; Override public 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 Luo
9、Sen.DS.Alg.Util.CreateComparator;import LuoSen.DS.Exceptions.IllegalParameterException;import 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;impo
10、rt java.util.logging.Logger;/* * * author 云大09数媒雒森 */*1-5确定性跳跃表*/public class DSkipList implements Serializable,Iterable /*头结点*/ protected DSLNode header; /*尾结点*/ protected DSLNode tailer=null; /*底结点*/ protected DSLNode bottom=null; /*表中元素的个数*/ protected int size=0; /*比较器*/ protected Comparator cp=n
11、ull; /*构造函数*/ public DSkipList() bottom=null; tailer=null; header=new DSLNode(tailer,bottom,null, (byte)0); /*构造函数*/ public DSkipList(Comparator cp) bottom=null; tailer=null; header=new DSLNode(tailer,bottom,null,(byte)0); this.cp=cp; /*使用一个DSkipList跳表初始化，目的是将目标复制到当前表中*/ public boolean initial(DSkip
12、List dsl) if(dsl=null) return false; this.cp=dsl.cp; this.header=dsl.header; this.size=dsl.size; return true; /*返回跳跃表的头*/ public DSLNode getHeader() return header; /*设置比较器*/ public void setComparator(Comparator cp) this.cp=cp; /*返回比较器*/ public Comparator getComparator() return cp; /*判断表中是否有关键字对应值*/
13、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 cur=header; while(cur!=bottom) while(cur.right!=tailer&pare(cur.right.link.data,data)0) cur=cur.right; if(cur.right!=tailer&pare(cur.right.li
14、nk.data,data)=0) return cur.right.link.data; cur=cur.down; return null; /*查找数据为data的数据比较关键字封装在data中,若查不到则返回位于它之后的第一个（最底部）结点*/ public DSLNode searchStart(S data) if(data=null|size=0) return null; DSLNode cur=header; while(cur!=bottom) while(cur.right!=tailer&pare(cur.right.link.data,data)0) cur=cur.r
15、ight; 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的数据比较关键字封装在data中,若查不到则返回位于它之前的第一个（最底部）结点*/ public DSLNode searchEnd(S data) if(data=null|size=0) retur
16、n null; DSLNode 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& pare(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.lin
17、k.data,data)=0) cur=cur.right; return cur; cur=cur.down; return null; /*插入数据data,若已存在返回数据链结点，并不插入数据，你可以在外面修改*/ public DSLLinkNode insert(S data) throws IllegalParameterException if(data=null) return null; if(cp=null) if(Comparable.class.isAssignableFrom(data.getClass() CreateComparator cc =new Creat
18、eComparator(); cp=cc.getComparator(); else throw new IllegalParameterException(数据不可以比较，请先设置比较器！); DSLNode cur=header; DSLNode 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.ri
19、ght; break; if(cur.down=bottom) newNode=new DSLNode(cur.right,bottom); newNode.link=new DSLLinkNode(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.righ
20、t.right.right.right.right!=tailer& (cur.right=tailer|pare(cur.down.right.right.right .right.right.link.data,cur.right.link.data)0) cur.right=new DSLNode(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(hea
21、der.right!=tailer) header.link.levelNum+; header.link.top=header; header=new DSLNode(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.isAssignableFrom(data.g
22、etClass() CreateComparator cc =new CreateComparator(); cp=cc.getComparator(); else throw new IllegalParameterException(数据不可以比较，请先设置比较器！); DSLNode cur=header; DSLNode c=null,cc=null,top=null; while(cur!=bottom) while(cur.right!=tailer&pare(cur.right.link.data,data)0) cur=cur.right; if(cur.down=bottom
23、&cur.right!=tailer&pare(cur.right.link.data,data)=0) if(size=1) header=new DSLNode(tailer,bottom,null,(byte)0); else if(cur.link.levelNumcur.right.link.levelNum)/比较左右位置结点层数高低，待删除的右边结点 c=cur.right.link.top; top=cur.right.link.top; cur.link.levelNum=cur.right.link.levelNum; while(c.down!=cur.link.top.
24、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.link.top=top; else cc=cur.link.top; while(cc.right!=cur.right.link.top) cc=cc.down; c=cur.right.link.top; while(c!=bo
25、ttom&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.link.top=header.down; return true; cur=cur.down; return false; /*获取条件一维区间odr之间的元素集合,该函数主要服务于：KDSkipList,用于检索一维区间*/ public Collection q
26、ueryRegion(ODRegion odr) Set s=new HashSet(); if(odr.isNoHasCondition) DSLNode cur=header; while(cur.down!=bottom) 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 cur=h
27、eader; DSLNode end=null; if(odr.start!=null) cur=this.searchStart(odr.start); else while(cur.down!=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
28、.addAll(KDSLNode)cur.link.data).set); else s.add(cur.link.data); cur=cur.right; return s; /*获取条件一维区间odr之间的元素满足多维条件的数据集合,index为odr在qc中的位置, * 该函数主要服务于：MLDSkipList 用于检索多位区间*/ public Collection queryRegion(Collection s,ODRegion odr,int index ,ListODRegion qc,ListComparator cps) if(s=null) return s; if(o
29、dr.isNoHasCondition) DSLNode 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.
30、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; else DSLNode cur=header; DSLNode end=null; if(odr.start!=null) cur=this.searchStart(odr.start); else while(cur.down!=bottom) cur=cur.down; cur=cur.right; end=this.searchEnd(odr.end); if(cur=null|(cur!=null&end!=null&par