Name: Title:

 Name:
ONLINE COMPILERS
LIBRARY
MANUAL PAGES & DOCS
CONTACT

User Submitted Source Code!

Description:
skip
Language: C/C++
Code:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include<time.h>

#define MAXLEVEL 14//define max level
#define PRABABILITY 0.5//define possibility

typedef struct ListStruct* SkipList;
typedef struct NodeStruct* Node;
struct ListStruct
{
int level;
};//skiplist
struct NodeStruct
{
int key;
int value;
int level;
Node* forward;
};//node

int Random(int max){
int r = 1;
//every level has probability p to ascend upwards
while(rand() % 100 < 100 * PRABABILITY){
r++;
if(r >= max) return max;
}
return r;
}
Node MakeNode(int level){
/* create a new node and make space for it */
/*need to implement*/
Node node = (Node)malloc(sizeof(struct NodeStruct));
node->forward = (Node *)malloc(sizeof(Node) * level);
node->level = level;
return node;
}
SkipList MakeList(){
/* create a empty skipList*/
/*need to implement*/
SkipList list = (SkipList)malloc(sizeof(struct ListStruct));
list->level = 0;
int i;
for (i = 0; i < MAXLEVEL; i++) {
list->head->forward[i] = NULL;  //set pointers to null for each level
}
return list;
}
Node Search(int x,SkipList list){
/*the search op of skipList*/
/*need to implement*/
Node p = list->head, next = NULL;
int i;
//nested loop to search the key
for(i = list->level - 1; i >= 0; i--){
//go ahead to reach the closest node to x in the i-th level
for(next = p->forward[i];
next && next->key < x;
p = next, next = p->forward[i]);
//if the next step is exactly x, return
if(next && next->key == x) return next;
}
return NULL;  //return not found
}
int Insert(int x,SkipList list){
/*insert op of skiplist*/
/*need to implememt*/
/*success return 0, not return -1*/
Node update[MAXLEVEL];//keep the nodes whose pointers are likely to be changed in the insertion
Node next = NULL;
int i;
//nested loop to search the key, same as search()
for(i = list->level - 1; i >= 0; i--){
for(next = p->forward[i];
next && next->key < x;
p = next, next = p->forward[i]);
update[i] = p;
}
//the keys should be distinct
if(next && next->key == x) return -1;

int level = Random(list->level + 1);    //random a level
if(level > MAXLEVEL) level = MAXLEVEL;    //can't be higher than maxlevel

//if it is higher than present level of the list, head pointers should also be updated
if(level > list->level) {
list->level = level;
}

//new node
Node node = MakeNode(level);
node->key = x;

//update the list of the closest nodes to x in each level, which is below x's level
for(i = 0; i < node->level; i++){
node->forward[i] = update[i]->forward[i];
update[i]->forward[i] = node;
}
return 0;

}
int Delete(int x,SkipList list){
/*delete node x from skip List*/
/*success return 0, else return -1*/
Node update[MAXLEVEL];
Node next = NULL;
int i;
//nested loop to search the key, same as insert()
for(i = list->level - 1; i >= 0; i--){
for(next = p->forward[i];
next && next->key < x;
p = next, next = p->forward[i]);
update[i] = p;
}
//if x is not in the list, return error
if(!next || next->key != x) return -1;

//next is the exactly node to delete, update the pointers in each level, which is below x's level
for(i = 0; i < next->level; i++)
update[i]->forward[i] = next->forward[i];

//update the highest level of the list
if(next->level > list->level) list->level = next->level;

free(next);  //delete the node x

return 0;
}
void ShowList(SkipList list){
/*print the whole list,with its level information*/
int i;
printf("%d levels\n", list->level);
//for each level, print the linked list in order
for(i = 0; i < list->level; i++){
printf("level %d :", i);
while(p->forward[i])
{
printf("%d ", p->forward[i]->key);
p = p->forward[i];
}
printf("\n");
}
}

int functionalityTest(void){
//a test to make sure all the function works well
//testing for make an empty list
SkipList list = MakeList();
//Testing for insert
for (int  i = 0; i < 100; i++)
{
int is_insert_success = Insert(i,list);
if(is_insert_success != 0){
printf("insert i = %d failure,we break",i);
return -1;
}
}
//testing for showList

printf("the level is %d\n",list->level);

ShowList(list);
//testing for a search
Node is_search_success = NULL;
for (int i = 0; i < 100; i++)
{
is_search_success = Search(i,list);
if(is_search_success == NULL){
printf(" the value  i = %d couldn't be found,we'll break the program",i);
return -1;
}
printf("value i = %d found\t",i);
printf("value: %d;\t key: %d;\tlevel: %d;\t",is_search_success->value,is_search_success->key,is_search_success->level);
putchar('\n');

}
//testing for a delete
int is_delete_success = 1;
for (int i = 0; i < 100; i++)
{
is_delete_success =  Delete(i,list);
if(is_delete_success != 0){
printf(" a delete of i = %d fail, we will break the program",i);
return -1;
}
}
ShowList(list);
printf("the test for functions is success ,qvq");
return 0;
}
/* return a random number between low and up */
int RandTest(int low, int up){
return low + rand()%(up - low);
}
void efficiencyTest(int N){
SkipList list = MakeList();
int i = 0;
float cpu_time_used;

printf("Size = %d\n",N);

clock_t start,end;
unsigned long span = 0;
int val = 0;
int repeatTime = N;
int valSet[N];
//begin measure the insert time span------
start = clock();
for (int i = 0; i < N; i++)
{
val = RandTest(0,N);//generate test case
val = val*5 + 1;
valSet[i] = val;
Insert(val,list);
}
end = clock();
span = end - start;
cpu_time_used = ((double) span)/CLOCKS_PER_SEC;
printf("Insert time span : %lf\n",cpu_time_used);
//end measure-----------------------------------

//output the input set(could be ommitted)----------
for (int i = 0; i < N; i++)
{
//printf("valSet[%d] = %d",i,valSet[i]);
}
//measure random search time-----------------------
start = clock();
for (int i = 0; i < repeatTime; i++)
{
val = RandTest(0,N);
val = val*5 + 1;
Search(val,list);
}
end = clock();
//begin measure the deleteTime span------------------
start = clock();
for (int i = 0; i < repeatTime; i++)
{
val = valSet[i];
Delete(val,list);
}
end = clock();

span = end - start;
cpu_time_used = ((double) span)/CLOCKS_PER_SEC;
printf("Delete time span : %lf\n",cpu_time_used);
printf("-----------------------------------\n");
return;
}

int main(){
printf("first test the function");
//we first test to make sure all the function works well
int test1_resutl = functionalityTest();
if(test1_resutl != 0){
printf("test1 failed\n");
return 0;
}

printf("\n");
printf("--------------------------------------------");
printf("\n");
printf("Now we start our effieciency test");

int size;
//we do so for
//Plot the run times vs. input sizes for illustration (2 pts.).、

//we can change testSetSize and testSetStep to get a proper testSet
int testSetSize = 100;//测试数据集的大小
int testSetStep = 1000;//100000:测试数据集之间的步长

//we now initialize testSet
for (int i = 0; i < testSetSize; i++)
{
size[i] = i*testSetStep;
}

for (int i = 0; i < testSetSize; i++)
{
printf("we now test the time for an input size i",i);
efficiencyTest(size[i]);
//all the key in an input set is random for simplicity
}
return 0;
}