SHARE
TWEET

Untitled

a guest May 19th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. /*
  3.     Complexitate: teta(1)
  4.     aloca memorie de indice i (intreg)
  5. */
  6.  
  7. aloca() {
  8.     int i = this->primulLiber;
  9.     if (i != -1) {
  10.         this->primulLiber = this->urm[i];
  11.     }
  12.     return i;
  13. }
  14.  
  15. /*
  16.     Complexitate: teta(1)
  17.     dealoca memoria de pe indicele i
  18. */
  19. dealoca(int i) {
  20.     this->urm[i] = this->primulLiber;
  21.     this->primulLiber = i;
  22. }
  23.  
  24.  
  25.  
  26. /*
  27.     Complexitate: teta(n)
  28.     initializare spatiu liber
  29. */
  30. void Colectie::initSpLiber() {
  31.     for (int i = 0; i < this->cp-1; i++) {
  32.         this->urm[i] = i+1;
  33.     }
  34.  
  35.     this->urm[this->cp - 1] = -1; // setam urm pt ultimul element ca fiind NIL
  36.  
  37.     this->primulLiber = 0; // setam pozitia catre primul element din tablou
  38. }
  39.  
  40.  
  41. /*
  42.     Complexitate: O(1)
  43.     initializeaza colectia
  44. */
  45. Colectie() {
  46.     cp = 100;
  47.     this->countElems = 0;
  48.  
  49.  
  50.     this->p = new TPereche[cp];
  51.     this->urm = new int[cp];
  52.  
  53.     this->primulLiber = -1;
  54.     this->primul = -1;
  55.    
  56.     this->initSpLiber();
  57. }
  58.  
  59.  
  60. /*
  61.     Complexitate: O(n)
  62.     creeaza un nod nou in cazul in care nu se poate folosi spatiul de la un nod anterior
  63. */
  64. creeazaNod(TElem e) {
  65.  
  66.     if (this->primulLiber == -1) { // daca lista este plina
  67.         // realoca
  68.         // copiaza elemente + legaturi
  69.         // reinitializeaza lista spartiu liber
  70.  
  71.         TPereche* newP = new TPereche[cp * 2];
  72.         int* newU = new int[cp * 2];
  73.  
  74.         for (int i = 0; i < cp; i++) { // copiem tot ce avem deja existent in lista
  75.             newP[i] = this->p[i];
  76.             newU[i] = this->urm[i];
  77.         }
  78.  
  79.         this->primulLiber = cp; // pozitionam primul liber pe prima pozitie din a doua jumatate a noului tablou
  80.  
  81.         for (int i = cp; i < cp * 2 - 1; i++) {
  82.             newU[i] = i + 1;
  83.         }
  84.  
  85.         newU[cp * 2 - 1] = -1;
  86.  
  87.         // actualizam capacitatea
  88.         this->cp = this->cp * 2;
  89.  
  90.         // stergem fostul tablou si facem noua asociere
  91.         delete[] this->p;
  92.         delete[] this->urm;
  93.  
  94.         this->p = newP;
  95.         this->urm = newU;
  96.     }
  97.  
  98.     int i = this->aloca();
  99.     this->p[i].first = e;
  100.     this->p[i].second = 1;
  101.     this->urm[i] = -1;
  102.     return i;
  103. }
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