Skip List

#include<stdio.h> #include<stdlib.h> struct skipnode { int info; struct skipnode **next; }; struct skipset { int level; struct skipnode *header; }; #define MAXLEVEL 4; void insert (struct skipnode *, int, int); int search (struct skipnode *, int); int rand_level(); void display(struct skipnode *); void delete(struct skipnode *,int); struct skipnode *makenode (int, int); int main () { char Another; int element; char cntnu='y'; int choice,found,level,r,dkey; struct skipnode *head = makenode (4, 0); while(cntnu=='y'){ system("clear"); printf("\n\n\t1.Insert to the list\n "); printf("\t2.Search in the list\n"); printf("\t3.Display list\n"); printf("\t4.Delete element from list\n"); printf("\t4.Exit\n"); printf("\n\nSelect choice [1,2,3,4]:"); scanf("%d",&choice); switch(choice){ case 1: system("clear"); printf("Enter element to insert :"); scanf("%d",&element); found=search(head,element); if(found==1){ printf("Element already in the list\n"); } else{ printf("\nEnter level of the element[ less than 4] \n"); scanf("%d",&level); if(level<=4){ insert(head,level,element); } else{ printf(" Enter other level\n"); } } break;

case 2: system("clear"); printf("Enter element to search :\n"); scanf("%d",&element); found=search(head,element); if(found==1){ printf("Given element is in the list\n"); } else{ printf("Given element is not in the list\n"); } break; case 3: system("clear"); display(head); break; case 4: system("clear"); printf("\nEnter element to delete : "); scanf("%d",&dkey); found=search(head,dkey); if(found==1){ delete(head,dkey); printf(" %d is deleted from list \n",dkey); } else{ printf("Element is not in the list \n"); } break; case 5: exit(0); } printf("\nDo you want to continue[y/n]:\n"); cntnu=getchar(); cntnu=getchar(); } return 0; } struct skipnode *makenode (int level, int info) { struct skipnode *sn = (struct skipnode *) malloc (sizeof (struct skipnode)); sn->info = info; sn->next = (struct skipnode **) calloc (level + 1, sizeof (struct skipnode *)); return sn; } int rand_level(){ return rand()%(4-0+1)+0; } void insert (struct skipnode *head,int level, int info) { int i,j; struct skipnode *temp = makenode (level, info); int count; if (head->next[0] == NULL) { for(i=0;i<=level;i++) head->next[i]=temp;

} else { struct skipnode *traverse1=NULL; for(i=4;i>=0;i--){ count=0; traverse1=head; struct skipnode *prev=NULL; struct skipnode *prev1=NULL; if(traverse1->next[i]==NULL && i<=level){ temp->next[i]=traverse1->next[i]; traverse1->next[i]=temp; } else{

&& i<=level){

count=1; while (traverse1->next[i]!=NULL){ count=0; if (temp->info < traverse1->next[i]->info

} else{

prev=traverse1; temp->next[i]=traverse1->next[i]; break; if(traverse1->next[i]-

>next[i]==NULL && i<=level){

traverse1-

>next[i]->next[i]=temp;

break; }

} traverse1=traverse1->next[i]; if(!traverse1->next[i]) { count++; } } if(traverse1->next[i]==NULL && count>0 && i<=level){

traverse1->next[i]=temp; } if(prev!=NULL){ prev->next[i]=temp; } }

}

}

} int search(struct skipnode *head,int key){ int i,count=0;

int found=0; if(head->next[0]==NULL){ found=0; } else{ struct skipnode *search=NULL; search=head; for(i=4;i>=0;i--){

}

while(search->next[i]!=NULL){ count++; if(key==search->next[i]->info){ found=1; i=0; printf("\n Number of tries to search %d \n",count); break; } search=search->next[i]; count++; }

} return found;

} //void update(struct skipnode *head,int){ //} void display(struct skipnode *head){ int i; if(head->next[0]==NULL){ printf("\nno element inserted\n"); } else{ struct skipnode *t=NULL; for(i=4;i>=0;i--){ t=head; printf("\nElements in %d level :",i); while(t->next[i]!=NULL){ printf(" %d ",t->next[i]->info); t=t->next[i]; } printf("\n"); } } } void delete(struct skipnode *head,int dkey){ int i; if(head->next[0]==NULL){ printf("No element to delete\n"); } else{ struct skipnode *traverse=NULL; for(i=4;i>=0;i--){ traverse=head;

>next[i]==NULL){

while(traverse->next[i]!=NULL){ if(traverse->next[i]->info==dkey && traverse->next[i]traverse->next[i]=NULL; break; } else if(traverse->next[i]->info==dkey && traverse->next[i]-

>next[i]!=NULL){ } else{

traverse->next[i]=traverse->next[i]->next[i]; break;

printf("element is not found\n"); } traverse=traverse->next[i]; } } }

}