Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
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;
     Node head;
};//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;
    list->head = MakeNode(MAXLEVEL);
    list->head->key = -1;
    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 p = list->head;
    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) {
        update[list->level] = list->head;
        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 p = list->head;
    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*/
    Node p = list->head;
    int i;
    printf("%d levels\n", list->level);
    //for each level, print the linked list in order
    for(i = 0; i < list->level; i++){
        p = list->head;
        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[10000];
     //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;
}
Comments: