第8章 跳表和散列表.doc

《第8章 跳表和散列表.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第8章跳表和散列表程序8.1跳表结点类templatestructSNode{SNode(intmSize){link=newSNode*[mSize];}~SNode(){delete[]link;}Telement;SNode**link;}程序8.2跳表类templateclassSkiplist:publicDynamicSet{public:Skiplist(Tlarge,intmLev);~Skiplist();ResultCodeSearch(T

2、&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);private:intlevel();SNode*SaveSearch(constT&x);intmaxLevel,levels;SNode*head,*tail,**last;};程序8.3构造函数templateSkiplist::Skiplist(Tlarge,intmLev){6maxLevel=mLev;levels=0;head=newSNode(

3、maxLevel+1);tail=newSNode(0);last=newSNode*[maxLevel+1];tail->element=large;for(inti=0;i<=maxLevel;i++)head->link[i]=tail;}程序8.4跳表的搜索templateResultCodeSkiplist::Search(T&x)const{if(x>=tail->element)returnRangeError;SNode*p=head;for(in

4、ti=level;i>=0;i--)while(p->link[i]->elementlink[i];if(x==p->link[0]->element){x=p->link[0]->element;returnSuccess;}elsereturnNotPresent;}程序8.5跳表的插入templateintSkipList::Level(){intlev=0;while(rand()<=RAND_MAX/2)lev++;return(lev<=maxLeve

5、l)?lev:maxLevel;}templateSNode*SkipList::SaveSearch(constT&x){SNode*p=head;6for(inti=levels;i>=0;i--){while(p->link[i]->elementlink[i];last[i]=p;}return(p->link[0]);}templateResultCodeSkiplist::Insert(T&x)const{if(x>=t

6、ail->element)returnRangeErroe;SNode*p=SaveSearch(x);if(p->element==x){x=p->element;returnDuplicate;}intlev=Level();if(lev>levels){lev=++levels;last[lev]=head;}SNode*y=newSNode(lev+1);y->element=x;for(inti=0;i<=lev;i++){y->link[i]=last[i]->link[i

7、];last[i]->link[i]=y;}returnSuccess;}程序8.6跳表的删除templateResultCodeSkiplist::Remove(T&x){if(x>=tail->element)returnRangeError;6SNode*p=SaveSearch(x);if(p->element!=x)returnNotPresent;for(inti=0;i<=levels&&last[i]->link[i]==p;i++)last[i]->link

8、[i]=p->link[i];while(levels>0&&head->link[levels]==tail)level--;x=p->element;deletep;returnSuccess;}程序8.7散列表类templateclassHashTable:publicDynamicSet{public:HashTable(intdivisor=11);~HashTable(){delete[]ht;delete