#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<iostream>
#include<sys/time.h>
using namespace std;
class skiplist
{
private:
struct lnode
{
int key;
lnode* next;
}*lhead;
struct snode
{
struct lnode *list;
snode *next;
int key;
}*shead;
int count;
public:
skiplist();
void insert(int key);
void insert_skip();
void search(int key);
void remove(int key);
void print();
void print_skip();
void sort();
bool isempty();
bool insert_in_skip();
~skiplist();
};
skiplist::skiplist()
{
lhead=NULL;
shead=NULL;
count=0;
}
bool skiplist::isempty()
{
if(lhead==NULL)
return true;
return false;
}
bool skiplist::insert_in_skip()
{
if(count%4==0)
return true;
return false;
}
void skiplist::insert(int key)
{
if(isempty())
{
lhead=new lnode;
//shead=new snode;
//shead->next=NULL;
lhead->next=NULL;
//shead->key=key;
lhead->key=key;
//shead->list=lhead;
printf("\n Inserted \n");
count++;
return ;
}/*
//if(insert_in_skip())
{
lnode *t=new lnode();
//snode *r=new snode();
t->key=key;
t->next=NULL;
//r->key=key;
///r->next=NULL;
//r->list=NULL;
lnode *p=lhead;
while(p->next!=NULL)
p=p->next;
//snode *q=shead;
while(q->next!=NULL)
q=q->next;
p->next=t;
//q->next=r;
printf("\n Inserted \n");
count++;
return;
}*/
lnode *t=new lnode();
t->key=key;
t->next=NULL;
lnode *p=lhead;
while(p->next!=NULL)
p=p->next;
p->next=t;
printf("\n Inserted \n");
count++;
return ;
}
void skiplist::insert_skip()
{
lnode *p=lhead;
shead=new snode();
shead->key=lhead->key;
shead->list=lhead;
int i=1;
while(p)
{
if(i%4==0)
{
snode *s=new snode;
s->key=p->key;
s->list=p;
snode *r=shead;
while(r->next!=NULL)
r=r->next;
r->next=s;
}
p=p->next;
i++;
}
}
void skiplist::print()
{
cout<<endl;
lnode *p=lhead;
while(p!=NULL)
{
cout<<p->key<<" ";
p=p->next;
}
}
void skiplist::print_skip()
{
cout<<endl;
snode *p=shead;
while(p)
{
cout<<p->key<<" ";
p=p->next;
}
}
void skiplist::sort()
{
lnode *p,*q;
p=lhead;
while(p->next!=NULL)
{
q=p->next;
while(q!=NULL)
{
if(q->key<p->key)
{
int temp=q->key;
q->key=p->key;
p->key=temp;
}
q=q->next;
}
p=p->next;
}
}
void skiplist::search(int key)
{
snode *p=shead;
while(p->next!=NULL)
{
if(p->next->key>key)
{
lnode *q=p->list;
while(q!=NULL)
{
if(q->key==key)
{
printf("\n Found\n");
return;
}
q=q->next;
}
}
if(p->next->key==key)
{
printf("\n found\n");
return ;
}
p=p->next;
}
lnode *q=p->list;
while(q!=NULL)
{
if(q->key==key)
{
printf("\n Found\n");
return;
}
q=q->next;
}
printf("\n Not found");
}
void skiplist::remove(int key)
{
if(lhead->key==key)
{
lnode *r=lhead;
lhead=lhead->next;
shead->list=lhead;
shead->key=lhead->key;
delete r;
return;
}
snode *p=shead;
while(p->next!=NULL)
{
if(p->next->key>key)
{
lnode *q=p->list;
while(q->next!=NULL)
{
if(q->next->key==key)
{
lnode *r=q->next;
q->next=r->next;
delete r;
printf("\n Found\n");
return;
}
q=q->next;
}
}
if(p->next->key==key)
{
lnode *q=p->list;
while(q->next->key!=key)
q=q->next;
lnode *r=q->next;
q->next=r->next;
snode *s=p->next;
p->next=s->next;
delete r;
delete s;
printf("\n found\n");
return ;
}
p=p->next;
}
lnode *q=p->list;
while(q->next!=NULL)
{
if(q->next->key==key)
{
lnode * s=q->next;
q->next=s->next;
delete s;
//printf("\n Found\n");
return;
}
q=q->next;
}
printf("\n Not found");
}
skiplist::~skiplist()
{
snode *p=shead;
while(shead!=NULL)
{
p=shead;
p->list=NULL;
shead=shead->next;
delete p;
}
lnode *q=lhead;
while(lhead!=NULL)
{
q=lhead;
lhead=lhead->next;
delete q;
}
}
int main()
{
skiplist s;
s.insert(10);
s.insert(9);
s.insert(18);
s.insert(1);
s.insert(100);
s.insert(-15);
s.print();
s.sort();
s.insert_skip();
s.print();
s.print_skip();
struct timeval tv_start,tv_end;
gettimeofday(&tv_start,NULL);
s.search(100);
gettimeofday(&tv_end,NULL);
cout<<endl;
cout<<((tv_end.tv_sec-tv_start.tv_sec)+(tv_end.tv_usec-tv_start.tv_usec)/1000000)<<" sec";
s.remove(100);
s.remove(10);
s.remove(-15);
s.remove(9);
s.print();
s.print_skip();
return 0;
}
No comments:
Post a Comment