Advertisement
dydziek

ASiD zadanie rosnąco/malejąco konstruktor

Dec 2nd, 2019
436
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.00 KB | None | 0 0
  1. package aisd.strukturyA.z2;
  2.  
  3. //Implementacja uporzadkowanej tablicy dynamicznej liczb calkowitych
  4. public class OrdIntDynArray {
  5.  
  6.     private int[] table; // Referencja do tablicy
  7.     private int nElems; // Aktualna liczba elementow w tablicy
  8.     private boolean isDescending = false;
  9.  
  10.     public OrdIntDynArray(int maxSize) { // Konstruktor
  11.         table = new int[maxSize]; // Tworzymy tablice
  12.         nElems = 0; // Na razie brak elementow w tablicy
  13.     }
  14.  
  15.     public OrdIntDynArray(int maxSize, boolean isDescending) {// ustawiamy flagę dla sortowania malejąco
  16.         table = new int[maxSize];
  17.         nElems = 0;
  18.         this.isDescending = isDescending;
  19.     }
  20.  
  21.     public void add(int value) { // Wstawienie elementu do tablicy
  22.         if (nElems >= table.length) { // Potrzeba relokacji
  23.             int[] locTable = new int[table.length * 2];
  24.             for (int i = 0; i < table.length; i++) {
  25.                 locTable[i] = table[i];
  26.             }
  27.             table = locTable;
  28.         }
  29.  
  30.         int j = 0;
  31.  
  32.         if (!isDescending) {
  33.             for (j = 0; j < nElems; j++) { // Znajdujemy miejsce dla elementu
  34.                 if (table[j] > value) {
  35.                     break;
  36.                 }
  37.             }
  38.         }
  39.  
  40.         if (isDescending) {
  41.             for (j = 0; j < nElems; j++) { // Znajdujemy miejsce dla elementu
  42.                 if (table[j] < value) {
  43.                     break;
  44.                 }
  45.             }
  46.         }
  47.  
  48.         for (int k = nElems; k > j; k--) { // Przesuwamy większe elementy
  49.             table[k] = table[k - 1];
  50.         }
  51.  
  52.         table[j] = value; // Wstawiamy element
  53.         nElems++; // Zwiekszamy licznik elementow
  54.     }
  55.  
  56.     public int get(int index) { // Pozyskanie elementu o danym indeksie
  57.         return table[index];
  58.     }
  59.  
  60.     public int size() { // Aktualna liczba elementow w tablicy
  61.         return nElems;
  62.     }
  63.  
  64.     public boolean remove(int index) { // Usuniecie elementu o danym indeksie
  65.         if (nElems == 0) {
  66.             return false;
  67.         }
  68.         for (int j = index; j < nElems - 1; j++) {// Przesuwamy pozostale elementy w lewo
  69.             table[j] = table[j + 1];
  70.         }
  71.         nElems--; // Zmniejszamy licznik elementow
  72.         return true;
  73.     }
  74.  
  75.     public int find(int searchElem) {// Szukanie okreslonego elementu
  76.         int left = 0; // ograniczenie lewe
  77.         int right = nElems - 1; // ograniczenie prawe
  78.         int currIndex; // aktualnie sprawdzany indeks
  79.  
  80.         while (true) { // 23 na index 0
  81.             currIndex = (left + right) / 2;
  82.             if (table[currIndex] == searchElem) {
  83.                 return currIndex; // Element znaleziony
  84.             } else if (left > right) {
  85.                 return -1; // Brak elementu
  86.             } else {
  87.                 if ( !isDescending ) {
  88.                     if (table[currIndex] < searchElem) {
  89.                         left = currIndex + 1; // Jest w górnej połowie tablicy
  90.                     } else {
  91.                         right = currIndex - 1; // Jest w dolnej połowie tablicy
  92.                     }
  93.                 }
  94.                 else if (isDescending) {
  95.                     if (table[currIndex] > searchElem) {
  96.                         left = currIndex + 1; // Jest w górnej połowie tablicy
  97.                     } else {
  98.                         right = currIndex - 1; // Jest w dolnej połowie tablicy
  99.                     }
  100.                 }
  101.                
  102.             }
  103.         }
  104.     }
  105.  
  106.     public void print() {
  107.         for (int i = 0; i < nElems; i++) {
  108.             System.out.print(get(i) + " ");
  109.         }
  110.         System.out.println();
  111.     }
  112.  
  113.     public static void main(String[] args) {
  114.         int maxSize = 2;
  115.         OrdIntDynArray array = new OrdIntDynArray(maxSize, true); // tworzymy tablice
  116.  
  117.         array.add(21);
  118.         array.add(04);
  119.         array.add(23);
  120.         array.add(14);
  121.         array.print();
  122.         int index = array.find(23);
  123.         System.out.println(index);
  124.     }
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement