Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <cmath>
- using namespace std;
- const int MAX = 100;
- class povecanaTabela {
- private:
- int brojElem;
- int zauzetoElem;
- int prosirenje;
- int *niz, *flagNiz;
- void sort(int* &niz, int n) {
- for (int i = 0; i < n; i++) {
- for (int j = i; j < n; j++) {
- if (niz[i] > niz[j]) {
- int pom = niz[i];
- niz[i] = niz[j];
- niz[j] = pom;
- }
- }
- }
- }
- void realociraj() {
- cout << endl << "Doslo je do realokacije tabele!!!" << endl;
- int k = 2 * brojElem;
- int *niz2 = new int[k];
- int *flagNiz2 = new int[k];
- for (int i = 0; i < k; i++) {
- niz2[i] = niz[i / 2];
- flagNiz2[i] = (i % 2 ? 0 : 1);
- }
- delete[] niz;
- delete[] flagNiz;
- flagNiz = flagNiz2;
- niz = niz2;
- brojElem *= 2;
- }
- int ternPret(int key) const {
- int low = 0;
- int high = brojElem - 1;
- while (high >= low) {
- int p1 = low + ceil((high - low)) / 3;
- int p2 = high - ceil((high - low)) / 3;
- if (key == niz[p1]) {
- int k = p1;
- while (flagNiz[k] == 0 and k >= 0) {
- if (niz[k] != key) break;
- k--;
- }
- if (niz[k] == key and flagNiz[k] == 1) return k;
- else {
- while (flagNiz[k] == 0) k++;
- if (niz[k] == key) return k;
- }
- }
- else if (key == niz[p2]) {
- int k = p2;
- while (flagNiz[k] == 0 and k >= 0) {
- if (niz[k] != key) break;
- k--;
- }
- if (niz[k] == key and flagNiz[k] == 1) return k;
- }
- else if (key < niz[p1]) high = p1 - 1;
- else if (key > niz[p1] and key < niz[p2]) {
- low = p1;
- high = p2 - 1;
- }
- else if (key > niz[p2]) low = p2 + 1;
- }
- int k = low;
- while (k >= 0) {
- if (flagNiz[k] == 1 and niz[k] < key) break;
- k--;
- }
- while (flagNiz[k] == 1 and niz[k] == key) k++;
- if (k == 0 and key < niz[k]) return -1;
- else return k;
- } //UVEK VRACA ELEMENT IZA KOGA TREBA DA SE UBACI NOVI ELEMENT
- public:
- int getBrojElem()const {
- return brojElem;
- }
- int getZauzetoElem()const {
- return zauzetoElem;
- }
- int getProsirenje()const {
- return prosirenje;
- }
- void formirajTabelu() {
- cout << "Unesite broj elemenata tabele: " << endl;
- int n;
- cin >> n;
- if (n < 1 or n > MAX) {
- cout << "Nevazeci broj elemenata!" << endl;
- return;
- }
- int *nizx = new int[n];
- for (int i = 0; i < n; i++) {
- cout << "Unesite " << i + 1 << ". element tabele: ";
- cin >> nizx[i];
- }
- sort(nizx, n);
- cout << "Unesite prosirenje: ";
- int p;
- cin >> p;
- int *niz2 = new int[n * p];
- flagNiz = new int[n * p];
- for (int i = 0; i < n * p; i++) {
- niz2[i] = nizx[i / p];
- flagNiz[i] = (i % p == 0 ? 1 : 0);
- }
- delete[] nizx;
- this->niz = niz2;
- this->brojElem = n * p;
- this->prosirenje = p;
- this->zauzetoElem = n;
- cout << endl << "Tabela uspesno formirana! Ispis: " << endl;
- this->ispisiTabelu();
- }
- //MOZDA POPRAVI KONZOLU
- void ispisiTabelu() const {
- cout << endl;
- for (int i = 0; i < brojElem; i++) {
- cout << niz[i] << "|";
- }
- cout << endl;
- for (int i = 0; i < brojElem; i++) {
- cout << flagNiz[i] << "|";
- }
- cout << endl;
- }
- //OVDE POPRAVI ISPIS
- void ispisiElem(int key) const { // *****
- int k = ternPret(key);
- if (niz[k] == key and flagNiz[k] == 1){
- cout << "Element " << key << " nadjen na poziciji " << k << "." << endl;
- return;
- } else {
- cout << "Nije nadjen element koji ima vrednost " << key << endl;
- return;
- }
- }
- void umetanjeKljuca(int key) {
- if (zauzetoElem == brojElem) realociraj();
- int k = ternPret(key);
- if(k != brojElem - 1) k++; //pozicija gde treba da stavimo element
- if (k == -1) {
- k = 0;
- while (1) {
- if (flagNiz[k] == 0) break;
- k++;
- }
- for (int i = k; i > 0 ; i--) {
- flagNiz[i] = flagNiz[i - 1];
- niz[i] = niz[i - 1];
- }
- flagNiz[0] = 1;
- niz[0] = key;
- zauzetoElem++;
- cout << "Kljuc uspesno umetnut na poziciji " << 0 << endl;
- return;
- }
- if (k == brojElem - 1) {
- while (1) {
- if (flagNiz[k] == 0) break;
- k--;
- }
- for (int i = k; i < brojElem - 1; i++) {
- flagNiz[i] = flagNiz[i + 1];
- niz[i] = niz[i + 1];
- }
- flagNiz[brojElem - 1] = 1;
- niz[brojElem - 1] = key;
- zauzetoElem++;
- cout << "Kljuc uspesno umetnut na poziciji " << brojElem - 1 << endl;
- return;
- }
- int poz = k;
- if (flagNiz[k] == 0) {
- niz[k] = key;
- flagNiz[k] = 1;
- k++;
- while (flagNiz[k] == 0) {
- niz[k] = key;
- k++;
- }
- zauzetoElem++;
- cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
- return;
- }
- // trazenje mesta udesno
- else {
- while (k < brojElem - 1) {
- if (flagNiz[k] == 0) break;
- k++;
- }
- if (flagNiz[k] == 0) {
- for (int i = k; i > poz; i--) {
- niz[i] = niz[i - 1];
- flagNiz[i] = flagNiz[i - 1];
- }
- niz[poz] = key;
- flagNiz[poz] = 1;
- zauzetoElem++;
- cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
- return;
- }
- // trazenje mesta ulevo
- poz--;
- while (k >= 0) {
- if (flagNiz[k] == 0) break;
- k--;
- }
- if (flagNiz[k] == 0) {
- for (int i = k; i < poz; i++) {
- niz[i] = niz[i + 1];
- flagNiz[i] = flagNiz[i + 1];
- }
- niz[poz] = key;
- flagNiz[poz] = 1;
- zauzetoElem++;
- cout << "Kljuc uspesno umetnut na poziciji " << poz << endl;
- return;
- }
- }
- }
- void brisanjeKljuca(int key){ // ****
- int k = ternPret(key);
- if (niz[k] == key and flagNiz[k] == 1){
- flagNiz[k] = 0;
- cout << "Uspesno brisanje kljuca na poziciji " << k << endl;
- return;
- } else {
- cout << "Element nije pronadjen ili je nevazeci! " << endl;
- }
- }
- };
- void konzola(){
- cout << endl << "Unosom rednog broja izaberite komandu: " << endl << endl;
- cout << "1. Pravljenje i inicijalizacija prosirene tabele" << endl;
- cout << "2. Ispisivanje indeksa(pozicije) odredjenog elementa u tabeli" << endl;
- cout << "3. Umetanje odredjenog elementa u tabelu" << endl;
- cout << "4. Brisanje odredjenog elementa iz tabele" << endl;
- cout << "5. Ispis cele tabele" << endl;
- cout << "0. Izlazak iz programa" << endl << endl << endl;
- }
- int main(void) {
- cout << "Dobrodosli u program!!! :) :) :)" << endl;
- int napravljenaTabela = 0;
- povecanaTabela *povTab = nullptr;
- while(1){
- konzola();
- cout << "Unesite komandu: ";
- int komanda;
- cin >> komanda;
- int key;
- switch (komanda) {
- case 1:
- if (napravljenaTabela){
- cout << "Tabela je vec napravljena!" << endl;
- break;
- }
- cout << "Formiranje povecane tabele: " << endl;
- povTab = new povecanaTabela;
- povTab->formirajTabelu();
- napravljenaTabela = 1;
- break;
- case 2:
- if (!napravljenaTabela){
- cout << "Tabela jos ne postoji!" << endl;
- break;
- }
- cout << "Unesite element(key) za pretragu: ";
- cin >> key;
- povTab->ispisiElem(key);
- break;
- case 3:
- if (!napravljenaTabela){
- cout << "Tabela jos ne postoji!" << endl;
- break;
- }
- cout << "Unesite vrednost elementa koji stavljate u tabelu: ";
- cin >> key;
- povTab->umetanjeKljuca(key);
- povTab->ispisiTabelu();
- break;
- case 4:
- if (!napravljenaTabela){
- cout << "Tabela jos ne postoji!" << endl;
- break;
- }
- cout << "Unesite vrednost(key) elementa za brisanje: ";
- cin >> key;
- povTab->brisanjeKljuca(key);
- povTab->ispisiTabelu();
- break;
- case 5:
- if (!napravljenaTabela){
- cout << "Tabela jos ne postoji!" << endl;
- break;
- }
- cout << "Ispis cele tabele: " << endl;
- povTab->ispisiTabelu();
- break;
- case 0:
- exit(1);
- break;
- default:
- cout << "Nevazeca komanda!!!" << endl;
- break;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement