Java. Линейный поиск. Разработка обобщенного класса, который содержит средства реализации линейного поиска

Линейный поиск. Разработка обобщенного класса, который содержит средства реализации линейного поиска

Содержание

Поиск на других ресурсах:

Условие задачи

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

Выполнение

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

Прежде всего нужно создать новый класс, который содержит функцию main(). В нашем случае имя класса TestLSearch. Создается файл с именем TestLSearch.java с двумя классами:

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

Общая структура классов следующая:

// Обобщенный класс, реализующий линейный поиск.
// Класс работает с типом T
class LSearch<T> {

}

// Класс, содержащий функцию main(), в которой тестируется работа класса LSearch<T>
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); // вызвать скрытый метод
}

⇑

2.4.2. Перегруженный метод GetFirstPos(). Определение позиции первого вхождения элемента в массиве

Метод 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 в массиве A.

// Метод, который возвращает массив вхождений элемента 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