SHARE
TWEET

asp2dz1

a guest Oct 18th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. const int MAX = 100;
  7.  
  8. class povecanaTabela {
  9.    
  10. private:
  11.    
  12.     int brojElem;
  13.     int zauzetoElem;
  14.     int prosirenje;
  15.     int *niz, *flagNiz;
  16.    
  17.     void sort(int* &niz, int n) {
  18.         for (int i = 0; i < n; i++) {
  19.             for (int j = i; j < n; j++) {
  20.                 if (niz[i] > niz[j]) {
  21.                     int pom = niz[i];
  22.                     niz[i] = niz[j];
  23.                     niz[j] = pom;
  24.                 }
  25.             }
  26.         }
  27.     }
  28.    
  29.     void realociraj() {
  30.         cout << endl << "Doslo je do realokacije tabele!!!" << endl;
  31.         int k = 2 * brojElem;
  32.         int *niz2 = new int[k];
  33.         int *flagNiz2 = new int[k];
  34.        
  35.         for (int i = 0; i < k; i++) {
  36.             niz2[i] = niz[i / 2];
  37.             flagNiz2[i] = (i % 2 ? 0 : 1);
  38.         }
  39.        
  40.         delete[] niz;
  41.         delete[] flagNiz;
  42.         flagNiz = flagNiz2;
  43.         niz = niz2;
  44.         brojElem *= 2;
  45.     }
  46.    
  47.     int ternPret(int key) const {  
  48.         int low = 0;
  49.         int high = brojElem - 1;
  50.        
  51.         while (high >= low) {
  52.             int p1 = low + ceil((high - low)) / 3;
  53.             int p2 = high - ceil((high - low)) / 3;
  54.            
  55.             if (key == niz[p1]) {
  56.                 int k = p1;
  57.                 while (flagNiz[k] == 0 and k >= 0) {
  58.                     if (niz[k] != key) break;
  59.                     k--;
  60.                 }
  61.                 if (niz[k] == key and flagNiz[k] == 1) return k;
  62.                 else {
  63.                     while (flagNiz[k] == 0) k++;
  64.                     if (niz[k] == key) return k;
  65.                 }
  66.                
  67.             }
  68.             else if (key == niz[p2]) {
  69.                 int k = p2;
  70.                 while (flagNiz[k] == 0 and k >= 0) {
  71.                     if (niz[k] != key) break;
  72.                     k--;
  73.                 }
  74.                 if (niz[k] == key and flagNiz[k] == 1) return k;
  75.                
  76.             }
  77.             else if (key < niz[p1]) high = p1 - 1;
  78.             else if (key > niz[p1] and key < niz[p2]) {
  79.                 low = p1;
  80.                 high = p2 - 1;
  81.             }
  82.             else if (key > niz[p2]) low = p2 + 1;
  83.         }
  84.        
  85.         int k = low;
  86.         while (k >= 0) {
  87.             if (flagNiz[k] == 1 and niz[k] < key) break;
  88.             k--;
  89.         }
  90.         while (flagNiz[k] == 1 and niz[k] == key) k++;
  91.         if (k == 0 and key < niz[k]) return -1;
  92.         else return k;
  93.     }     //UVEK VRACA ELEMENT IZA KOGA TREBA DA SE UBACI NOVI ELEMENT
  94.    
  95.    
  96.  
  97.    
  98. public:
  99.    
  100.     int getBrojElem()const {
  101.         return brojElem;
  102.     }
  103.     int getZauzetoElem()const {
  104.         return zauzetoElem;
  105.     }
  106.     int getProsirenje()const {
  107.         return prosirenje;
  108.     }
  109.    
  110.     void formirajTabelu() {
  111.         cout << "Unesite broj elemenata tabele: " << endl;
  112.         int n;
  113.         cin >> n;
  114.        
  115.         if (n < 1 or n > MAX) {
  116.             cout << "Nevazeci broj elemenata!" << endl;
  117.             return;
  118.         }
  119.        
  120.         int *nizx = new int[n];
  121.         for (int i = 0; i < n; i++) {
  122.             cout << "Unesite " << i + 1 << ". element tabele: ";
  123.             cin >> nizx[i];
  124.         }
  125.         sort(nizx, n);
  126.         cout << "Unesite prosirenje: ";
  127.         int p;
  128.         cin >> p;
  129.        
  130.         int *niz2 = new int[n * p];
  131.         flagNiz = new int[n * p];
  132.        
  133.         for (int i = 0; i < n * p; i++) {
  134.             niz2[i] = nizx[i / p];
  135.             flagNiz[i] = (i % p == 0 ? 1 : 0);
  136.         }
  137.        
  138.         delete[] nizx;
  139.         this->niz = niz2;
  140.         this->brojElem = n * p;
  141.         this->prosirenje = p;
  142.         this->zauzetoElem = n;
  143.         cout << endl << "Tabela uspesno formirana! Ispis: " << endl;
  144.         this->ispisiTabelu();
  145.     }
  146.     //MOZDA POPRAVI KONZOLU
  147.    
  148.     void ispisiTabelu() const {
  149.         cout << endl;
  150.         for (int i = 0; i < brojElem; i++) {
  151.             cout << niz[i] << "|";
  152.         }
  153.         cout << endl;
  154.         for (int i = 0; i < brojElem; i++) {
  155.             cout << flagNiz[i] << "|";
  156.         }
  157.         cout << endl;
  158.     }
  159.     //OVDE POPRAVI ISPIS
  160.    
  161.    
  162.     void ispisiElem(int key) const { // *****
  163.         int k = ternPret(key);
  164.         if (niz[k] == key and flagNiz[k] == 1){
  165.             cout << "Element " << key << " nadjen na poziciji " << k << "." << endl;
  166.             return;
  167.         } else {
  168.             cout << "Nije nadjen element koji ima vrednost " << key << endl;
  169.             return;
  170.         }
  171.     }
  172.    
  173.     void umetanjeKljuca(int key) {
  174.        
  175.         if (zauzetoElem == brojElem) realociraj();
  176.        
  177.         int k = ternPret(key);
  178.         if(k != brojElem - 1) k++; //pozicija gde treba da stavimo element
  179.        
  180.         if (k == -1) {
  181.             k = 0;
  182.             while (1) {
  183.                 if (flagNiz[k] == 0) break;
  184.                 k++;
  185.             }
  186.             for (int i = k; i > 0 ; i--) {
  187.                 flagNiz[i] = flagNiz[i - 1];
  188.                 niz[i] = niz[i - 1];
  189.             }
  190.             flagNiz[0] = 1;
  191.             niz[0] = key;
  192.             zauzetoElem++;
  193.             cout << "Kljuc uspesno umetnut na poziciji " << 0 << endl;
  194.             return;
  195.         }
  196.        
  197.         if (k == brojElem - 1) {
  198.             while (1) {
  199.                 if (flagNiz[k] == 0) break;
  200.                 k--;
  201.             }
  202.             for (int i = k; i < brojElem - 1; i++) {
  203.                 flagNiz[i] = flagNiz[i + 1];
  204.                 niz[i] = niz[i + 1];
  205.             }
  206.             flagNiz[brojElem - 1] = 1;
  207.             niz[brojElem - 1] = key;
  208.             zauzetoElem++;
  209.             cout << "Kljuc uspesno umetnut na poziciji " << brojElem - 1 << endl;
  210.             return;
  211.         }
  212.        
  213.         int poz = k;
  214.        
  215.         if (flagNiz[k] == 0) {
  216.             niz[k] = key;
  217.             flagNiz[k] = 1;
  218.             k++;
  219.             while (flagNiz[k] == 0) {
  220.                 niz[k] = key;
  221.                 k++;
  222.             }
  223.             zauzetoElem++;
  224.             cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
  225.             return;
  226.         }
  227.        
  228.         // trazenje mesta udesno
  229.        
  230.         else {
  231.             while (k < brojElem - 1) {
  232.                 if (flagNiz[k] == 0) break;
  233.                 k++;
  234.             }
  235.             if (flagNiz[k] == 0) {
  236.                 for (int i = k; i > poz; i--) {
  237.                     niz[i] = niz[i - 1];
  238.                     flagNiz[i] = flagNiz[i - 1];
  239.                 }
  240.                 niz[poz] = key;
  241.                 flagNiz[poz] = 1;
  242.                 zauzetoElem++;
  243.                 cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
  244.                 return;
  245.             }
  246.            
  247.             // trazenje mesta ulevo
  248.            
  249.             poz--;
  250.            
  251.             while (k >= 0) {
  252.                 if (flagNiz[k] == 0) break;
  253.                 k--;
  254.             }
  255.            
  256.             if (flagNiz[k] == 0) {
  257.                 for (int i = k; i < poz; i++) {
  258.                     niz[i] = niz[i + 1];
  259.                     flagNiz[i] = flagNiz[i + 1];
  260.                 }
  261.                 niz[poz] = key;
  262.                 flagNiz[poz] = 1;
  263.                 zauzetoElem++;
  264.                 cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
  265.                 return;
  266.             }
  267.         }
  268.     }
  269.    
  270.     void brisanjeKljuca(int key){ // ****
  271.         int k = ternPret(key);
  272.         if (niz[k] == key and flagNiz[k] == 1){
  273.             flagNiz[k] = 0;
  274.             cout << "Uspesno brisanje kljuca na poziciji " << k << endl;
  275.             return;
  276.         } else {
  277.             cout << "Element nije pronadjen ili je nevazeci! " << endl;
  278.         }
  279.     }
  280. };
  281.  
  282. void konzola(){
  283.     cout << endl << "Unosom rednog broja izaberite komandu: " << endl << endl;
  284.     cout << "1. Pravljenje i inicijalizacija prosirene tabele" << endl;
  285.     cout << "2. Ispisivanje indeksa(pozicije) odredjenog elementa u tabeli" << endl;
  286.     cout << "3. Umetanje odredjenog elementa u tabelu" << endl;
  287.     cout << "4. Brisanje odredjenog elementa iz tabele" << endl;
  288.     cout << "5. Ispis cele tabele" << endl;
  289.     cout << "0. Izlazak iz programa" << endl << endl << endl;
  290. }
  291.  
  292.  
  293. int main(void) {
  294.    
  295.     cout << "Dobrodosli u program!!! :) :) :)" << endl;
  296.     int napravljenaTabela = 0;
  297.     povecanaTabela *povTab = nullptr;
  298.    
  299.    
  300.    
  301.     while(1){
  302.         konzola();
  303.         cout << "Unesite komandu: ";
  304.         int komanda;
  305.         cin >> komanda;
  306.         int key;
  307.         switch (komanda) {
  308.             case 1:
  309.                 if (napravljenaTabela){
  310.                     cout << "Tabela je vec napravljena!" << endl;
  311.                     break;
  312.                 }
  313.                 cout << "Formiranje povecane tabele: " << endl;
  314.                 povTab = new povecanaTabela;
  315.                 povTab->formirajTabelu();
  316.                 napravljenaTabela = 1;
  317.                 break;
  318.             case 2:
  319.                 if (!napravljenaTabela){
  320.                     cout << "Tabela jos ne postoji!" << endl;
  321.                     break;
  322.                 }
  323.                 cout << "Unesite element(key) za pretragu: ";
  324.                 cin >> key;
  325.                 povTab->ispisiElem(key);
  326.                 break;
  327.             case 3:
  328.                 if (!napravljenaTabela){
  329.                     cout << "Tabela jos ne postoji!" << endl;
  330.                     break;
  331.                 }
  332.                 cout << "Unesite vrednost elementa koji stavljate u tabelu: ";
  333.                 cin >> key;
  334.                 povTab->umetanjeKljuca(key);
  335.                 povTab->ispisiTabelu();
  336.                 break;
  337.             case 4:
  338.                 if (!napravljenaTabela){
  339.                     cout << "Tabela jos ne postoji!" << endl;
  340.                     break;
  341.                 }
  342.                 cout << "Unesite vrednost(key) elementa za brisanje: ";
  343.                 cin >> key;
  344.                 povTab->brisanjeKljuca(key);
  345.                 povTab->ispisiTabelu();
  346.                 break;
  347.             case 5:
  348.                 if (!napravljenaTabela){
  349.                     cout << "Tabela jos ne postoji!" << endl;
  350.                     break;
  351.                 }
  352.                 cout << "Ispis cele tabele: " << endl;
  353.                 povTab->ispisiTabelu();
  354.                 break;
  355.             case 0:
  356.                 exit(1);
  357.                 break;
  358.                
  359.             default:
  360.                 cout << "Nevazeca komanda!!!" << endl;
  361.                 break;
  362.         }
  363.      
  364.        
  365.     }
  366.    
  367. }
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