注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

跳跃表示例代码  

2009-06-13 09:21:54|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
#include <cstdio>
#include <stdlib.h>
#include <ctime>
using namespace std;
template<class KEY,class DATA>
struct Lnode{KEY key;DATA data;
Lnode*son,*next;Lnode(){son=next=NULL;}
};
template<class KEY,class DATA>
struct JTable{
typedef Lnode<KEY,DATA> jNode;
jNode *head[16];
int H;
JTable(KEY low,KEY up){
H=0;jNode *p;
for (int i=0;i<15;i++){
head[i]=p=new jNode;if (i)p->son=head[i-1];
p=p->next=new jNode;if (i)p->son=head[i-1]->next;
head[i]->key=low;p->key=up;
}
}
jNode *jIns(KEY key){
int f,i;jNode *p,*q,*l;
f=(rand()&16383)+1;f&=-f;
while ((1<<H)<f)H++;
p=head[i=H];l=NULL;
while (i>=0){
while (p->next->key<=key)p=p->next;
if ((1<<i)<=f){q=new jNode;
q->key=key;
q->next=p->next;p->next=q;
if (l)l->son=q;l=q;
}
p=p->son;i--;
}
return l;
}
jNode* jFind(KEY key){
int i;jNode *p;
for (p=head[i=H];i>=0;i--){
while (p->next->key<=key)p=p->next;
if (i)p=p->son;
}
return (p->key==key)?p:NULL;
}
void jDel(KEY key){
int i;jNode *p,*q;
for (p=head[i=H];i>=0;i--){
while (p->next->key<key)p=p->next;
if (p->next->key==key){
q=p->next;p->next=q->next;
delete q;
}
p=p->son;i--;
}
}
~JTable(){
jNode *p,*q;
for (int i=0;i<15;i++){
p=head[i];
while (p){
q=p;p=p->next;
delete q;
}
}
}
};
typedef struct{} empty;
typedef JTable<int,empty> intJtable;
#define NMax 1000000
int dat[NMax];
int main()
{
int t1,N;
scanf("%d",&N);
intJtable J(-2100000000,2100000000);
for (int i=0;i<N;i++)dat[i]=((rand()<<14)|rand());
srand(1325);
t1=clock();
for (int i=0;i<N;i++)J.jIns(dat[i]);
printf("inserting time %d\n",clock()-t1);
srand(1325);
t1=clock();
for (int i=0;i<N;i++)J.jFind(dat[i])->key;
printf("finding time %d\n",clock()-t1);
srand(1325);
t1=clock();
for (int i=0;i<N;i++)J.jDel(dat[i]);
printf("deleting time %d\n",clock()-t1);
getchar();getchar();
return 0;
}

  评论这张
 
阅读(432)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017