Facebook
From Sharp Bushbaby, 1 Week ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 30
  1. #include <iostream>
  2. #include <time.h>
  3. #include <fstream>
  4. #include <cstdlib>
  5.  
  6. using namespace std;
  7.  
  8. int X=2001, k1=13666, k2=4, k3=7, k4=-1, k5=100001, tab[2001], licznik = 0; // X wskazuje ilosc wylosowanych struktur, licznik to liczba wylosowanych intow,
  9.  
  10. struct element {
  11.     int klucz;
  12.     double d;
  13.     char c;
  14.     element * nastepny;
  15.     element * poprzedni;
  16. };
  17.  
  18. struct Lista {
  19.     element * pierwszy = NULL;
  20.     element * ostatni = NULL;
  21. } lista;
  22.  
  23.  
  24.  
  25. /*
  26. void odczyt_pliku(){
  27.     fstream plik;
  28.     plik.open("labin02.txt", ios::in);
  29.  
  30.     if(plik.good()==false){
  31.         cout<<"Nie udalo sie odczytac pliku lub plik nie istnieje";
  32.         exit(0);
  33.     }
  34. plik >>x>>k1>>k2>>k3>>k4>>k5;
  35. plik.close();
  36. }
  37.  
  38. */
  39. int losuj_int(){
  40.     int wylosowana;
  41.     int j;
  42.  
  43.     do
  44.     {
  45.         wylosowana = rand() % 10000 - 1000;
  46.  
  47.         for(j = 0; j < licznik; ++j)
  48.         {
  49.             if(wylosowana == tab[j]) break;
  50.         }
  51.     }
  52.     while(j != licznik);
  53.  
  54.     tab[licznik++] = wylosowana;
  55.     return wylosowana;
  56. }
  57.  
  58. double losuj_double(){
  59.         int losowa = rand()%10000-1000;
  60.         double wylosowana = losowa/100;
  61.  
  62.  return wylosowana;
  63. }
  64.  
  65. void wstaw_x_nowych(int x){
  66.     for(int i = 0; i<=x-1; i++){
  67.         if (licznik==0){ //przypadek gdy lista jest pusta
  68.             element*nowy = new element;//utworz element
  69.             nowy->c=(char)84;
  70.             nowy->d = losuj_double();
  71.             nowy->klucz = losuj_int();
  72.             lista.pierwszy = nowy;
  73.             lista.ostatni = nowy;
  74.             nowy->nastepny = nowy;
  75.             nowy->poprzedni = nowy;
  76.         }
  77.         else{//przypadek gdy lista nie jest pusta
  78.             element*nowy = new element;
  79.             nowy->c=(char)84;
  80.             nowy->d = losuj_double();
  81.             nowy->klucz = losuj_int();
  82.             if(nowy->klucz < lista.pierwszy->klucz){//przypadek gdy klucz nowego elementu jest mniejszy od pierwszego na liscie
  83.                     nowy->nastepny = lista.pierwszy;
  84.                     nowy->poprzedni = lista.ostatni;
  85.                     lista.pierwszy->poprzedni = nowy;
  86.                     lista.ostatni->nastepny = nowy;
  87.                     lista.pierwszy = nowy;
  88.             }
  89.             if(nowy->klucz > lista.ostatni->klucz){//przypadek gdy klucz nowego elementu jest wiekszy od ostatniego na liscie
  90.                     nowy->poprzedni = lista.ostatni;
  91.                     nowy->nastepny=lista.pierwszy;
  92.                     lista.ostatni->nastepny = nowy;
  93.                     lista.pierwszy->poprzedni = nowy;
  94.                     lista.ostatni = nowy;
  95.             }
  96.             else{//przypadek gdy klucz nowego elementu miesi sie miedzy pierwszym a ostatnim na liscie
  97.                 element * wsk = lista.pierwszy;
  98.                 while (wsk!=lista.ostatni){
  99.                     if((nowy->klucz > wsk->klucz) &&(nowy->klucz < wsk->nastepny->klucz)){
  100.                         nowy->poprzedni=wsk;
  101.                         nowy->nastepny=wsk->nastepny;
  102.                         wsk->nastepny = nowy;
  103.                         wsk->nastepny->poprzedni = nowy;
  104.                         break;
  105.                         }
  106.                     wsk=wsk->nastepny;
  107.                     }
  108.                 }
  109.         }
  110.     }
  111.     cout<<endl<<"Dodano "<<licznik<<" nowych wezlow"<<endl;
  112. }
  113.  
  114. void wstaw_nowy(int k){
  115.     element * wsk = lista.pierwszy;
  116.  
  117.     while(wsk->nastepny != lista.pierwszy){
  118.         if(wsk->klucz == k){
  119.             cout<<endl<<"Przy probie dodania elementu wykryto ze element o kluczu "<<k<<" juz istnieje"<<endl;
  120.             return;
  121.         }
  122.         wsk=wsk->nastepny;
  123.     }
  124.  
  125.             element*nowy = new element;
  126.             nowy->c=(char)84;
  127.             nowy->d = losuj_double();
  128.             nowy->klucz =k;
  129.                 if(nowy->klucz < lista.pierwszy->klucz){//przypadek gdy klucz nowego elementu jest mniejszy od pierwszego na liscie
  130.                     nowy->nastepny = lista.pierwszy;
  131.                     nowy->poprzedni = lista.ostatni;
  132.                     lista.pierwszy->poprzedni = nowy;
  133.                     lista.ostatni->nastepny = nowy;
  134.                     lista.pierwszy = nowy;
  135.                     licznik++;
  136.                 }
  137.                 if(nowy->klucz>lista.ostatni->klucz){//przypadek gdy klucz nowego elementu jest wiekszy od ostatniego na liscie
  138.                     nowy->poprzedni = lista.ostatni;
  139.                     nowy->nastepny=lista.pierwszy;
  140.                     lista.ostatni->nastepny = nowy;
  141.                     lista.pierwszy->poprzedni = nowy;
  142.                     lista.ostatni = nowy;
  143.                     licznik++;
  144.                 }
  145.                 else{//przypadek gdy klucz nowego elementu miesi sie miedzy pierwszym a ostatnim na liscie
  146.                     element * wsk = lista.pierwszy;
  147.                 while (wsk!=lista.ostatni){
  148.                     if((nowy->klucz > wsk->klucz) &&(nowy->klucz < wsk->nastepny->klucz)){
  149.                         nowy->poprzedni=wsk;
  150.                         nowy->nastepny=wsk->nastepny;
  151.                         wsk->nastepny = nowy;
  152.                         wsk->nastepny->poprzedni = nowy;
  153.                         break;
  154.                         }
  155.                     wsk=wsk->nastepny;
  156.                     }
  157.                 }
  158. cout<<endl<<"Wstawiono nowy element o kluczu "<<k<<endl;
  159. }
  160.  
  161. int licz_wezly(){
  162.   int ile_wezlow = 0;
  163.   element * wsk = lista.pierwszy;
  164.  
  165.   if(wsk)
  166.     do{
  167.         ile_wezlow++;
  168.         wsk = wsk->nastepny;
  169.   } while(wsk != lista.pierwszy);
  170.   return ile_wezlow;
  171. }
  172.  
  173. void wyszukaj(int k){
  174.     int pozycja = 1;
  175.     if(lista.pierwszy!=NULL){//jezeli lista nie jest pusta
  176.         element * wsk = lista.pierwszy;
  177.         while(wsk->klucz!=k){//przeszukuj liste
  178.             wsk=wsk->nastepny;
  179.             pozycja++;
  180.             if(wsk==lista.pierwszy){// jezeli przeszukales liste do konca
  181.                 cout<<endl<<"Szukany element o kluczu "<<k<<" nie istnieje"<<endl;
  182.                 return;
  183.             }
  184.         }
  185.      cout<<endl<<"Szukany element o kluczu "<<k<<" znajduje sie na pozycji "<<pozycja<<endl;
  186.    }
  187.   else{//jezeli lista jest pusta
  188.     cout<<endl<<"Szukany element nie istnieje - lista jest pusta"<<endl;
  189.   }
  190. }
  191.  
  192. void pokaz_pierwsze(int Y){
  193.     element * wsk = lista.pierwszy;
  194.     cout<<endl<<"Wartosci skladowych kluczowych pierwszych "<<Y<<" wezlow"<<endl;
  195.     for(int i=0; i<=Y; i++){
  196.         cout<<i+1<<"."<<wsk->klucz<<endl;
  197.         wsk=wsk->nastepny;
  198.     }
  199. }
  200.  
  201. void pokaz_ostatnie(int Z){
  202.       element * wsk = lista.ostatni;
  203.     cout<<endl<<"Wartosci skladowych kluczowych ostatnich "<<Z<<" wezlow"<<endl;
  204.     for(int i=0; i<=Z; i++){
  205.         cout<<i<<"."<<wsk->klucz<<endl;
  206.         wsk=wsk->poprzedni;
  207.     }
  208. }
  209.  
  210. void usun(int k){
  211.     if(lista.pierwszy!=NULL){//jezeli lista nie jest pusta
  212.         element * wsk = lista.pierwszy;
  213.         while(wsk->klucz!=k){//przeszukuj liste
  214.             wsk=wsk->nastepny;
  215.             if(wsk==lista.pierwszy){// jezeli przeszukales liste do konca
  216.                 cout<<endl<<"Szukany element o kluczu "<<k<<" nie istnieje"<<endl;
  217.                 return;
  218.             }
  219.             if(wsk->klucz==k){
  220.                 wsk->nastepny->poprzedni = wsk->poprzedni;
  221.                 wsk->poprzedni->nastepny = wsk->nastepny;
  222.                 delete wsk;
  223.             }
  224.         }
  225.    }
  226.   else{//jezeli lista jest pusta
  227.     cout<<endl<<"Szukany element nie istnieje"<<endl;
  228.   }
  229.  
  230. }
  231.  
  232. void usun_wszystko(){
  233. }
  234.  
  235. int main(){
  236.     clock_t begin, end;
  237.     double time_spent;
  238.     begin = clock();
  239.  
  240.     srand(time(NULL));
  241.  
  242.     wyszukaj(k1);
  243.     wstaw_x_nowych(X);
  244.     cout<<endl<<"Aktualna liczba wezlow: "<<licz_wezly()<<endl;
  245.     pokaz_pierwsze(20);
  246.     wstaw_nowy(k2);
  247.     wyszukaj(k2);
  248.     pokaz_pierwsze(20);
  249.     wstaw_nowy(k3);
  250.     wyszukaj(k3);
  251.     pokaz_pierwsze(20);
  252.     wstaw_nowy(k4);
  253.     wyszukaj(k4);
  254.     pokaz_pierwsze(20);
  255.     wstaw_nowy(k5);
  256.     wyszukaj(k5);
  257.     usun(k3);
  258.     pokaz_pierwsze(20);
  259.     usun(k2);
  260.     wyszukaj(k2);
  261.     //pokaz_pierwsze(20);
  262.     //usun(k5);
  263.     //wyszukaj(k5);
  264.    // pokaz_ostatnie(11);
  265.     //cout<<endl<<"Aktualna liczba wezlow: "<<licz_wezly()<<endl;
  266.    // usun_wszystko();
  267.     //pokaz_ostatnie(11);
  268.    // cout<<endl<<"Aktualna liczba wezlow: "<<licz_wezly()<<endl;
  269.  
  270.     end = clock();
  271.     time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  272.     cout<<endl<<time_spent;
  273.     return 0;
  274. }
  275.