Java. Лінійний пошук. Розробка узагальненого класу, що містить засоби реалізації лінійного пошуку

Лінійний пошук. Розробка узагальненого класу, що містить засоби реалізації лінійного пошуку

Зміст

Пошук на інших ресурсах:

Умова задачі

Розробити узагальнений клас LSearch<T>, що містить засоби для реалізації лінійного пошуку в одновимірному масиві. Продемонструвати роботу класу у функції main().

Виконання

1. Структура консольної програми. Класи LSearch<T> та TestLSearch

Перш за все потрібно створити новий клас, який містить функцію main(). У нашому випадку ім’я класу TestLSearch. Створюється файл з іменем TestLSearch.java, який містить два класи:

узагальнений клас LSearch<T>, який потрібно розробити згідно з умовою задачі;
клас TestLSearch, який містить функцію main() в якій буде проводитись тестування (дослідження роботи) класу LSearch<T>.

Загальна структура класів наступна:

// Узагальнений клас, що реалізує лінійний пошук.
// Клас працює з узагальненим типом T
class LSearch<T> {

}

// Клас, що містить функцію main(), в якій тестується робота класу LSearch
public class TestLSearch {

  public static void main(String[] args) {

  }

}

На наступних кроках у клас LSearch<T> будуть вводитись внутрішні змінні та методи для реалізації виконання задачі. У тіло функції main() буде вписуватись код тестування методів класу.

⇑

2. Розробка класу LSearch<T>

2.1. Ввід внутрішніх змінних класу

Оскільки, алгоритм лінійного пошуку використовується для одновимірних масивів, то в клас LSearch<T> вводиться прихований (private) одновимірний внутрішній масив A.

class LSearch<T> {
  // Внутрішні змінні класу
  private T[] A; // масив узагальненого типу T
}

⇑

2.2. Конструктори класу

Для зручної ініціалізації внутрішнього масиву A, в класі вводяться три загальнодоступні (public) конструктори:

конструктор без параметрів. Ініціалізує масив A значеням null;
конструктор з параметром типу масив T[]. Цей конструктор ініціалізує внутрішній масив A значеннями зовнішнього масиву. З допомогою методу clone() робиться повна копія (з виділенням пам’яті) вхідного масиву;
конструктор з параметром типу клас LSearch<T>. Це випадок, коли потрібно ініціалізувати екземпляр класу даними іншого екземпляру без використання додаткових перетворюючих методів.

Після вводу конструкторів текст класу наступний

class LSearch<T> {

  // Внутрішні змінні класу
  private T[] A; // масив узагальненого типу T

  // ------------ Конструктори класу --------------
  // Конструкто без параметрів
  public LSearch() {
    A = null;
  }

  // Конструктор з 1 параметром.
  // Параметр: _A - зовнішній масив елементів, яким ініціалізується
  //               внутрішній масив
  public LSearch(T[] _A) {
    A = _A.clone(); // Зробити копію в іншому місці пам'яті
  }

  // Конструктор, який ініціалізує екземпляром іншого класу типу LSearch<T>
  public LSearch(LSearch<T> L) {
    this.A = L.A.clone();
  }
}

⇑

2.3. Методи доступу до внутрішніх даних в класі

Для доступу до внутрішніх змінних класу використовуються методи Get() та Set(), які мають наступну реалізацію

// Метод, що повертає посилання на внутрішній масив даних
public T[] Get() {
  return this.A;
}

// Метод, що встановлює новий масив даних
public void Set(T[] _A) {
  this.A = _A.clone();
}

⇑

2.4. Методи реалізації лінійного пошуку

З метою забезпечення зручного лінійного пошуку заданого елементу (ключа) в масиві в класі реалізовано 5 перевантажених методів (подаються нижче).

2.4.1. Перевантажений метод IsItem(). Визначення наявності заданого елементу в масиві

Метод IsItem() має дві реалізації: приховану (private) та загальнодоступну (public).

У першій прихованій реалізації метод отримує вхідним параметром масив типу T[] та ключ типу T. Метод повертає true, якщо елемент key є у вхідному масиві. Даний метод розміщується в розділі private.

У другій реалізації метод отримує ключ key. Пошук ведеться у внутрішньому масиві A даного класу.

// Прихований метод, що визначає, чи елемент key є в масиві _A
private boolean IsItem(T[] _A, T key) {
  for (int i=0; i<_A.length; i++)
    if (key==_A[i])
      return true;
  return false;
}

// Загальнодоступний метод, що визначає, чи елемент key є у внутрішньому масиві A
public boolean IsItem(T key) {
  return IsItem(A, key); // викликати прихований метод
}

Метод GetFirstPos() реалізує лінійний пошук з початку масиву. Метод послідовно сканує масив до першого співпадіння. Як тільки значення ключа key співпало з елементом в масиві, відбувається вихід з методу і повернення позиції (нумерується з 0) цього елементу.

Метод має дві реалізації: приховану та загальнодоступну.

// Прихований метод, що визначає позицію першого входження елементу key в масиві _A.
// Якщо елементу немає в масиві, метод повертає -1
private int GetFirstPos(T[] _A, T key) {
  for (int i=0; i<_A.length; i++)
    if (key == _A[i])
      return i;
  return -1;
}

// Перевантажений метод GetFirstPos(), обробляє внутрішній масив A класу
public int GetFirstPos(T key) {
  return GetFirstPos(A, key); // викликати прихований метод
}

⇑

2.4.3. Перевантажений метод GetLastPos(). Визначення позиції останнього входження елементу в масиві

Метод GetLastPos() повертає позицію останнього входження елементу в масиві. Пошук шуканого ключа здійснюється з кінця масиву.

// Метод, що визначає позицію останнього входження елементу в масиві _A
private int GetLastPos(T[] _A, T key) {
  for (int i=_A.length-1; i>=0; i--)
    if (key == _A[i])
      return i;
  return -1;
}

// Перевантажений варіант GetLastPos() - обробляє масив A класу
public int GetLastPos(T key) {
  return GetLastPos(A, key);
}

⇑

2.4.4. Перевантажений метод GetNOccurences(). Визначення кількості входжень елементу в масиві

// Метод, що визначає кількість входжень елементу в масиві _A
private int GetNOccurences(T[] _A, T key) {
  int n = 0;
  for (int i=0; i<_A.length; i++)
    if (key==_A[i])
      n++;
  return n;
}

// Перевантажений варіант методу GetNOccurences() - працює з внутрішнім масивом A
public int GetNOccurences(T key) {
  return GetNOccurences(A, key);
}

⇑

2.4.5. Перевантажений метод GetPositions(). Отримати масив позицій входження елементу в масиві

Корисним для використання є метод GetPositions(), що дозволяє отримати масив, в якому записані позиції входження заданого ключа key в масиві.

// Метод, що повертає масив входжень елементу key в масиві _A
private int[] GetPositions(T[] _A, T key) {
  // Обчислити кількість позицій
  int nPos = GetNOccurences(key);

  // Оголосити масив
  int[] AP = new int[nPos];

  // Додати номери позицій в масив AP
  int t=0;

  for (int i=0; i<_A.length; i++)
    if (key==_A[i])
      AP[t++] = i;

  // Повернути масив
  return AP;
}

// Перевантажений варіант GetPositions()
public int[] GetPositions(T key) {
  // Викликати однойменний прихований метод
  return GetPositions(A, key);
}

⇑

2.5. Метод виведення внутрішнього масиву

Додатково у класі реалізовано метод Print(), який виводить елементи масиву. Метод отримує параметром рядок коментаря text. Метод може використовуватись для контролю та тестування роботи класу.

// Метод, що виводить внутрішній масив
public void Print(String text) {
  System.out.println(text);
  for (int i=0; i<A.length; i++) {
    System.out.print(A[i]+" ");
  }
  System.out.println("");
}

⇑

3. Розробка класу TestLSearch. Функція main()

Для тестування роботи класу LSearch<T> створюється клас, що містить функцію main() – точку входу в програму. У функції main() продемонстровано створення екземплярів класу LSearch<T> для різних типів. Також продемонстровано використання конструкторів, методів доступу та лінійного пошуку.

Текст класу TestLSearch наступний.

// Клас, що містить функцію main(), в якій тестується робота класу LSearch
public class TestLSearch {

  public static void main(String[] args) {
    // ----------------- Тестування конструкторів -----------------
    // Деякий масив цілих чисел
    Integer[] AI = { 2, 3, 5, -77 };

    // Оголосити екземпляр A1
    LSearch<Integer> A1 = new LSearch<Integer>(AI); // викликається конструктор LSearch(T[])
    A1.Print("A1:");

    // Оголосити екземпляр A2
    LSearch<Integer> A2 = A1; // викликається конструктор  LSearch(LSearch<T>)
    A2.Print("A2");

    // --------------- Тестування методів доступу -------------------
    // Оголосити масив дійсних чисел AD
    Double[] AD = { 2.8, 3.5, -7.7, -9.99 };

    // Оголосити екземпляр A3 дійсних чисел
    LSearch<Double> A3 = new LSearch<Double>(); // викликається конструтор без параметрів

    // Встановити в екземплярі A3 новий масив і вивести його
    A3.Set(AD);
    A3.Print("A3");

    // Отримати посилання на внутрішній масив в екземплярі A3
    Double[] AD2 = A3.Get();
    AD2[1] = 100.33; // Змінити елемент внутрішнього масиву A3 через посилання
    A3.Print("A3:");

    System.out.print("AD2: ");
    for (int i=0; i<AD2.length; i++)
      System.out.print(AD2[i] + " ");
    System.out.println();

    // ------------- Тестування методів лінійного пошуку ----------------
    // Метод IsItem() - визначення наявності елементу в масиві
    if (A1.IsItem(5))
      System.out.println("Element 5 is present in array A1");
    else
      System.out.println("Element 5 is absent in the array A1");

    // Метод GetFirstPos()
    int pos = A2.GetFirstPos(5);
    System.out.println();
    System.out.print("Array A2: ");
    A2.Print("");
    System.out.println("position of 5 is: " + pos);

    // Метод GetNOccurences()
    Integer[] AI2 = { 5, 8, -3, 2, 5, 0, 0, 1, 3, 5, 8 }; // оголосити масив
    LSearch<Integer> A4 = new LSearch<Integer>(AI2); // оголосити екземпляр класу LSearch<>
    int n;

    n = A4.GetNOccurences(5); // кількість входжень числа 5 в масиві A4
    System.out.println("n = " + n);

    // Метод GetPositions() - отримати масив позицій
    int[] AP; // AP - результуючий масив позицій
    AP = A4.GetPositions(5);

    System.out.print("Array of positions AP: ");
    for (int i=0; i<AP.length; i++)
      System.out.print(AP[i]+" ");
    System.out.println();
  }
}

⇑

4. Текст усього модуля. Скорочений варіант

Пройшовши послідовно усі етапи даної теми можна отримати програмний код модуля TestLSearch.java. Нижче наведено скорочений варіант класів LSearch<T> та TestLSearch.

// Узагальнений клас, що реалізує лінійний пошук.
// Клас працює з узагальненим типом T
class LSearch<T> {

  // Внутрішні змінні класу
  private T[] A; // масив узагальненого типу T

  // ------------ Конструктори класу --------------
  // Конструктор без параметрів
  public LSearch() {
    ...
  }

  // Конструктор з 1 параметром.
  // Параметр: _A - зовнішній масив елементів, яким ініціалізується
  //               внутрішній масив
  public LSearch(T[] _A) {
    ...
  }

  // Конструктор, який ініціалізує екземпляром іншого класу типу LSearch<T>
  public LSearch(LSearch<T> L) {
    ...
  }

  // -------------- Методи доступу до внутрішніх даних в класі --------------
  // Метод, що повертає посилання на внутрішній масив даних
  public T[] Get() {
    ...
  }

  // Метод, що встановлює новий масив даних
  public void Set(T[] _A) {
    ...
  }

  // -------------- Методи лінійного пошуку ---------------------
  // Прихований метод, що визначає, чи елемент key є в масиві _A
  private boolean IsItem(T[] _A, T key) {
    ...
  }

  // Загальнодоступний метод, що визначає, чи елемент key є у внутрішньому масиві A
  public boolean IsItem(T key) {
    ...
  }

  // Прихований метод, що визначає позицію першого входження елементу key в масиві _A.
  // Якщо елементу немає в масиві, метод повертає -1
  private int GetFirstPos(T[] _A, T key) {
    ...
  }

  // Перевантажений метод GetFirstPos(), обробляє внутрішній масив A класу
  public int GetFirstPos(T key) {
    ...
  }

  // Метод, що визначає позицію останнього входження елементу в масиві _A
  private int GetLastPos(T[] _A, T key) {
    ...
  }

  // Перевантажений метод GetLastPos() - обробляє масив A класу
  public int GetLastPos(T key) {
    ...
  }

  // Метод, що визначає кількість входжень елементу в масиві _A
  private int GetNOccurences(T[] _A, T key) {
    ...
  }

  // Перевантажений метод GetNOccurences() - працює з внутрішнім масивом A
  public int GetNOccurences(T key) {
    ...
  }

  // Метод, що повертає масив входжень елементу key в масиві _A
  private int[] GetPositions(T[] _A, T key) {
    ...
  }

  // Перевантажений варіант GetPositions()
  public int[] GetPositions(T key) {
    ...
  }

  // Метод, що виводить внутрішній масив
  public void Print(String text) {
    ...
  }
}

// Клас, що містить функцію main(), в якій тестується робота класу LSearch
public class TestLSearch {
  public static void main(String[] args) {
    ...
  }
}

⇑

Зв’язані теми

⇑

BestProg