C++ Program To Implement Skip List

«
»
This C++ Program demonstrates the implementation of Skip List.

Here is source code of the C++ Program to demonstrate skip list. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Skip List 
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <cmath>
  7. #include <cstring>
  8. #define MAX_LEVEL 6
  9. const float P = 0.5;
  10. using namespace std;
  11. /*
  12.  * Skip Node Declaration
  13.  */
  14. struct snode
  15. {
  16.     int value;
  17.     snode **forw;
  18.     snode(int level, int &value)
  19.     {
  20.         forw = new snode * [level + 1];
  21.         memset(forw, 0, sizeof(snode*) * (level + 1));
  22.         this->value = value; 
  23.     }
  24.     ~snode()
  25.     {
  26.         delete [] forw;        
  27.     } 
  28. };
  29. /*
  30.  * Skip List Declaration
  31.  */
  32. struct skiplist
  33. {
  34.     snode *header;
  35.     int value;
  36.     int level;
  37.     skiplist() 
  38.     {
  39.         header = new snode(MAX_LEVEL, value);
  40.         level = 0;
  41.     }
  42.     ~skiplist() 
  43.     {
  44.         delete header;
  45.     }
  46.     void display();
  47.     bool contains(int &);
  48.     void insert_element(int &);
  49.     void delete_element(int &);        
  50. };
  51. /*
  52.  * Main: Contains Menu
  53.  */
  54. int main() 
  55. {
  56.     skiplist ss;
  57.     int choice, n;
  58.     while (1)
  59.     {
  60.         cout<<endl<<"-----------------------"<<endl;
  61.         cout<<endl<<"Operations on Skip list"<<endl;
  62.         cout<<endl<<"-----------------------"<<endl;
  63.         cout<<"1.Insert Element"<<endl;
  64.         cout<<"2.Delete Element"<<endl;
  65.         cout<<"3.Search Element"<<endl;
  66.         cout<<"4.Display List "<<endl;
  67.         cout<<"5.Exit "<<endl;
  68.         cout<<"Enter your choice : ";
  69.         cin>>choice;
  70.         switch(choice)
  71.         {
  72.         case 1:
  73.              cout<<"Enter the element to be inserted: ";
  74.              cin>>n;
  75.              ss.insert_element(n);
  76.              if(ss.contains(n))
  77.                  cout<<"Element Inserted"<<endl;
  78.              break;
  79.         case 2:
  80.              cout<<"Enter the element to be deleted: ";
  81.              cin>>n;
  82.              if(!ss.contains(n))
  83.              {
  84.                  cout<<"Element not found"<<endl;
  85.                  break;
  86.              }
  87.              ss.delete_element(n);
  88.              if(!ss.contains(n))
  89.                  cout<<"Element Deleted"<<endl;
  90.              break;
  91.         case 3:
  92.              cout<<"Enter the element to be searched: ";
  93.              cin>>n; 
  94.              if(ss.contains(n))
  95.                  cout<<"Element "<<n<<" is in the list"<<endl;
  96.              else
  97.                  cout<<"Element not found"<<endl;
  98.         case 4:
  99.              cout<<"The List is: ";
  100.              ss.display();
  101.              break;
  102.         case 5:
  103.              exit(1);
  104.              break;
  105.         default:
  106.              cout<<"Wrong Choice"<<endl;
  107.         }
  108.     }
  109.     return 0;
  110. }
  111.  
  112. /*
  113.  * Random Value Generator
  114.  */
  115. float frand() 
  116. {
  117.     return (float) rand() / RAND_MAX;
  118. }
  119.  
  120. /*
  121.  * Random Level Generator
  122.  */
  123. int random_level() 
  124. {
  125.     static bool first = true;
  126.     if (first) 
  127.     {
  128.         srand((unsigned)time(NULL));
  129.         first = false;
  130.     }
  131.     int lvl = (int)(log(frand()) / log(1.-P));
  132.     return lvl < MAX_LEVEL ? lvl : MAX_LEVEL;
  133. }
  134.  
  135. /*
  136.  * Insert Element in Skip List
  137.  */
  138. void skiplist::insert_element(int &value) 
  139. {
  140.     snode *x = header;	
  141.     snode *update[MAX_LEVEL + 1];
  142.     memset(update, 0, sizeof(snode*) * (MAX_LEVEL + 1));
  143.     for (int i = level;i >= 0;i--) 
  144.     {
  145.         while (x->forw[i] != NULL && x->forw[i]->value < value) 
  146.         {
  147.             x = x->forw[i];
  148.         }
  149.         update[i] = x; 
  150.     }
  151.     x = x->forw[0];
  152.     if (x == NULL || x->value != value) 
  153.     {        
  154.         int lvl = random_level();
  155.         if (lvl > level) 
  156.         {
  157.             for (int i = level + 1;i <= lvl;i++) 
  158.             {
  159.                 update[i] = header;
  160.             }
  161.             level = lvl;
  162.         }
  163.         x = new snode(lvl, value);
  164.         for (int i = 0;i <= lvl;i++) 
  165.         {
  166.             x->forw[i] = update[i]->forw[i];
  167.             update[i]->forw[i] = x;
  168.         }
  169.     }
  170. }
  171.  
  172. /*
  173.  * Delete Element from Skip List
  174.  */
  175. void skiplist::delete_element(int &value) 
  176. {
  177.     snode *x = header;	
  178.     snode *update[MAX_LEVEL + 1];
  179.     memset (update, 0, sizeof(snode*) * (MAX_LEVEL + 1));
  180.     for (int i = level;i >= 0;i--) 
  181.     {
  182.         while (x->forw[i] != NULL && x->forw[i]->value < value)
  183.         {
  184.             x = x->forw[i];
  185.         }
  186.         update[i] = x; 
  187.     }
  188.     x = x->forw[0];
  189.     if (x->value == value) 
  190.     {
  191.         for (int i = 0;i <= level;i++) 
  192.         {
  193.             if (update[i]->forw[i] != x)
  194.                 break;
  195.             update[i]->forw[i] = x->forw[i];
  196.         }
  197.         delete x;
  198.         while (level > 0 && header->forw[level] == NULL) 
  199.         {
  200.             level--;
  201.         }
  202.     }
  203. }
  204.  
  205. /*
  206.  * Display Elements of Skip List
  207.  */
  208. void skiplist::display() 
  209. {
  210.     const snode *x = header->forw[0];
  211.     while (x != NULL) 
  212.     {
  213.         cout << x->value;
  214.         x = x->forw[0];
  215.         if (x != NULL)
  216.             cout << " - ";
  217.     }
  218.     cout <<endl;
  219. }
  220.  
  221. /*
  222.  * Search Elemets in Skip List
  223.  */
  224. bool skiplist::contains(int &s_value) 
  225. {
  226.     snode *x = header;
  227.     for (int i = level;i >= 0;i--) 
  228.     {
  229.         while (x->forw[i] != NULL && x->forw[i]->value < s_value)
  230.         {
  231.             x = x->forw[i];
  232.         }
  233.     }
  234.     x = x->forw[0];
  235.     return x != NULL && x->value == s_value;
  236. }

advertisement
$ g++ skip_list.cpp
$ a.out
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 7
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 9
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 3
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 5
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 6
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 5 - 6 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 2
Enter the element to be deleted: 20
Element not found
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 2
Enter the element to be deleted: 6
Element Deleted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 3
Enter the element to be searched: 20
Element not found
The List is: 3 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 3
Enter the element to be searched: 7
Element 7 is in the list
The List is: 3 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 4
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 4 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 5
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn