SHARE
TWEET

Untitled

a guest Nov 18th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string.h>
  3. #include <cstdlib>
  4. #include <stdlib.h>
  5. #include <ctime>
  6. #include <conio.h>
  7. #include <stdio.h>
  8.  
  9.  
  10. using namespace std;
  11. //int LMAX=10;
  12.  
  13. struct skiplist{
  14.         int key;
  15.         int height;
  16.         char litera;
  17.         struct skiplist **next;
  18. };
  19.  
  20. int random_level(int LMAX)
  21. {
  22.         int level=1;
  23.         while((rand()%100<0.5*100)&(level<LMAX))
  24.         {
  25.                 level++;
  26.         }
  27.         return(level);
  28. }
  29.  
  30.  
  31. bool insert(skiplist* head, int new_key, int LMAX)
  32. {
  33.         skiplist* x=head;
  34.         int height=random_level(LMAX);
  35.         skiplist* update[height];
  36.        
  37.        
  38.         for(int i=height-1;i>=0;i--)
  39.         {
  40.                 while(x->next[i]->key < new_key)
  41.                 {
  42.                         x=x->next[i];
  43.                 }
  44.                 update[i]=x;
  45.                
  46.         }
  47.         x=x->next[0];
  48.         if(x->key==new_key)
  49.         {
  50.                 x->litera='D';
  51.                 return false;
  52.         }
  53.         skiplist* new_node = new skiplist;
  54.         new_node->next=new skiplist*[height];
  55.        
  56.         new_node->key=new_key;
  57.         new_node->height=height;
  58.        
  59.         for(int i=0; i<new_node->height;i++)
  60.         {
  61.                 new_node->next[i]=update[i]->next[i];
  62.                 update[i]->next[i]=new_node;
  63.                 new_node->litera='T';
  64.         }
  65.         return true;
  66. }
  67.  
  68. skiplist *createSkipList(int LMAX)
  69. {
  70.         skiplist* skip = new skiplist;
  71.         skiplist* tail = new skiplist;
  72.         skip->next=new skiplist*[LMAX];
  73.         tail->next=new skiplist*[LMAX];
  74.         int height=LMAX;
  75.  
  76.         skip->key=-2147483647;
  77.         skip->height=LMAX;
  78.        
  79.         tail->key=2147483647;
  80.         tail->height=LMAX;
  81.         for(int i=0;i<height;i++)
  82.         {
  83.                 skip->next[i]=tail;
  84.                 tail->next[i]=nullptr;
  85.         }
  86.         return skip;
  87. }
  88.  
  89. bool search(skiplist* head, int key)
  90. {
  91.         skiplist* x = new skiplist;
  92.         x = head;
  93.         int height=x->height;
  94.         for(int i=height-1;i>=0;i--)
  95.         {
  96.                 while(x->next[i]->key<key)
  97.                 {
  98.                         x=x->next[i];
  99.                 }
  100.         }
  101.         x=x->next[0];
  102.         if(x->key==key)
  103.         {
  104.                 return(true);
  105.         }
  106.         return(false);
  107. }
  108.  
  109. void insert_all(skiplist* head, int N, int LMAX)
  110. {
  111.         int liczba;
  112.         for(int i=0; i<N;i++)
  113.         {
  114.                 do
  115.                 {
  116.                         liczba = (rand() % 99900)+ 99;
  117.                 }while(insert(head,liczba, LMAX)==false);
  118.         }
  119. }
  120.  
  121.  
  122. string usun(skiplist* head, int key, int LMAX)
  123. {
  124.         skiplist* x=head;
  125.         skiplist* update[10];
  126.         for(int i=LMAX-1; i>=0;i--)
  127.         {
  128.                 while(x->next[i]->key<key)
  129.                 {
  130.                         x=x->next[i];
  131.                 }
  132.                 update[i]=x;
  133.         }
  134.         x=x->next[0];
  135.         if(x->key>key)
  136.         {
  137.                 return("blad");
  138.         }
  139.         for(int i=0; i<x->height; i++)
  140.         {
  141.                 update[i]->next[i]=x->next[i];
  142.         }
  143.         delete(x);
  144.         return("OK");
  145. }
  146.  
  147. string delete_all(skiplist* head)
  148. {
  149.         skiplist* element=head;
  150.         skiplist* tmp;
  151.        
  152.         while(element)
  153.         {
  154.                 tmp=element->next[0];
  155.                 delete element;
  156.                 element=tmp;
  157.         }
  158.        
  159. }
  160.  
  161. void wypisz(skiplist* head, int Y, int height)
  162. {
  163.         skiplist* x=head;
  164.         /*for(int i=0; i<Y; i++)
  165.         {
  166.                 if(x->key==-2147483647)
  167.                 {
  168.                         x=x->next[0];
  169.                 }
  170.                 if(x->height>=height)
  171.                 {
  172.                       cout<< x->key<< endl;
  173.                       x=x->next[0];
  174.                       continue;
  175.                 }
  176.                 else
  177.                 {
  178.                         while(x->height<height)
  179.                         {
  180.                                 x=x->next[0];
  181.                         }
  182.                         cout<< x->key<<endl;
  183.                         x=x->next[0];
  184.                 }
  185.  
  186.                
  187.         }*/
  188.         for(int i=0; i<Y; i++)
  189.         {
  190.                 x=x->next[height-1];
  191.                 cout<<x->key<<endl;
  192.         }
  193.        
  194.        
  195. }
  196.  
  197. int liczba_wezlow(skiplist* head)
  198. {
  199.         int licznik=1;
  200.         skiplist* x=head;
  201.         while(x->next[0]!=nullptr)
  202.         {
  203.                 x=x->next[0];
  204.                 licznik++;
  205.         }
  206.         licznik=licznik-2;
  207.         return licznik;
  208. }
  209.  
  210.  
  211.  
  212. int main()
  213. {
  214.         int LMAX=7;
  215.         //2001 7 13666 4 7 -1 100001
  216.         srand((unsigned int)time(NULL));
  217.         int N=2001;
  218.         int k1=13666;
  219.         int k2=4;
  220.         int k3=7;
  221.         int k4=-1;
  222.         int k5=100001;
  223.        
  224.        
  225.         clock_t begin, end;
  226.         double time_spent;
  227.         begin = clock();
  228.        
  229.         skiplist* head= new skiplist;
  230.        
  231.         head=createSkipList(LMAX);
  232.  
  233.         insert_all(head,N,LMAX);
  234.        
  235.        
  236.         if(search(head,101)==false)
  237.         {
  238.                 cout<<"Nie znaleziono"<<endl;
  239.         }
  240.         else
  241.         {
  242.                 cout<<"Znaleziono klucz k1"<<endl;
  243.         }
  244.        
  245.        
  246.  
  247.         search(head,100);
  248.         insert(head,100,LMAX);
  249.        
  250.         skiplist* wyswietl=head;
  251.         for(int i=0;i<20;i++)
  252.         {
  253.                 cout<<wyswietl->key<<" "<<wyswietl->litera<<" "<< wyswietl->height<<" "<<" "<<wyswietl<<" "<< wyswietl->next[0]<<" ";
  254.                 if(wyswietl->height>=2)
  255.                 {
  256.                         cout<<wyswietl->next[2]<<" ";
  257.                 }
  258.                 if(wyswietl->height>=2)
  259.                 {
  260.                         cout<<wyswietl->next[1]<<endl;
  261.                 }
  262.                 wyswietl=wyswietl->next[0];
  263.         }
  264.         cout << "" <<endl;
  265.        
  266.         usun(head,100,LMAX);
  267.        
  268.        
  269.         //wypisz(head, 10, 3);
  270.        
  271.         wyswietl=head;
  272.  
  273.        
  274.        
  275.         int licznik;
  276.        
  277.         licznik=liczba_wezlow(head);
  278.        
  279.         delete_all(head);
  280.        
  281.         cout << "Liczba wezlow:" << licznik << endl;
  282.        
  283.         time_spent = (double)(end-begin) / CLOCKS_PER_SEC;
  284.         cout << "Czas wykonania:" << time_spent << endl;
  285.        
  286.        
  287.        
  288.         return 0;
  289. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top