Borland C++ Builder 2007, C++, MS Visual Studio 2010, Практика

C++. Линейный поиск. Разработка класса реализующего линейный поиск в одномерном массиве





Линейный поиск. Разработка класса реализующего линейный поиск в одномерном массиве

В данной теме рассматривается реализация линейного поиска элемента в одномерном массиве. С целью демонстрации разработан класс LSearch<T>, который содержит средства для организации линейного поиска.

Содержание

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

1. Линейный поиск. Понятие

Линейный поиск принадлежит к наиболее простым способам поиска данных. Цель линейного поиска – найти нужный элемент (ключ) в массиве данных. В алгоритме линейного поиска каждый элемент массива последовательно сравнивается с ключом до тех пор, пока не будет найден нужный элемент или не будет просканирован весь массив.

В контексте линейного поиска могут возникать следующие задачи:

  • определить наличие заданного элемента в массиве (наборе данных);
  • определить количество вхождений заданного элемента в массиве;
  • определить номер позиции или массив номеров позиций размещения заданного элемента в массиве.

Реализация линейного поиска может быть расширена для использования в многомерных массивах.

  ⇑

2. Разработка шаблонного класса LSearch<T>, реализующего линейный поиск

Шаблонный класс, который реализует линейный поиск, может быть помещен в отдельный модуль (файл) и использоваться при необходимости. Разработанный класс может быть использован для базовых типов языка C++ таких как int, double, char и других.

Если возникнет необходимость использовать данный класс для массива экземпляров другого класса, то в этом (другому) классе нужно переопределить операцию сравнения (==), которая сравнивает два экземпляра класса на равенство. Но это уже другая тема.

  ⇑

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

Разработать класс, который содержит средства для выполнения линейного поиска в одномерном массиве. В классе нужно реализовать следующие поля и методы:

  • внутренние переменные, которые описывают массив;
  • все необходимые конструкторы класса;
  • методы доступа к массиву в классе;
  • деструктор;
  • операторную функцию operator=(), которая перегружает оператор присваивания;
  • методы реализации линейного поиска как в массиве класса, так и во внешнем массиве.

В функции main() продемонстрировать работу класса.

  ⇑

2.2. Общая структура класса. Внутренние переменные

Поскольку линейный поиск реализуется в одномерном массиве, то внутренними данными класса есть одномерный массив A и его размерность count.

Класс есть шаблонным и работает с обобщенным типом T. После ввода внутренних переменных общий вид класса для приложения типа Console Application следующий

#include <iostream>
using namespace std;

// Шаблонный класс реализующий линейный поиск в одномерном массиве
template <class T>
class LSearch
{
private:
  // Внутренние переменные
  T* A; // массив
  int count; // количество элементов в массиве
}

void main(void)
{
}

  ⇑

2.3. Конструкторы класса

В тело класса в разделе public вписываются коды конструкторов класса.

2.3.1. Конструктор без параметров

Конструктор без параметров устанавливает внутренние переменные нулевыми значениями. Реализация такого конструктора предусматривает:

  • добавление массива данных с помощью метода Set() и его обработку;
  • использование методов линейного поиска для массивов, которые не являются данными текущего экземпляра класса (для любых других внешних массивов).

После добавления конструктора в раздел public общий вид класса следующий

// Шаблонный класс, который реализует линейный поиск в одномерном массиве
template <class T>
class LSearch
{
private:
  // Внутренние переменные
  T* A; // массив
  int count; // количество элементов в массиве

public:
  // Конструктор без параметров
  LSearch()
  {
    A = nullptr;
    count = 0;
  }
}

  ⇑

2.3.2. Конструктор, который инициализирует внутренние поля класса входным массивом

Данный конструктор необходим, когда в программе есть внешний массив с данными. Конструктор делает копирование внешнего массива во внутренний для его дальнейшей обработки.

// Конструктор, получающий входной массив,
// которым инициализируются элементы внутреннего массива
LSearch(T* _A, int _count)
{
  // 1. Проверка, корректно ли значение _count
  if (_count <= 0)
  {
    A = nullptr;
    count = 0;
    return;
  }

  // 2. Установить новое количество элементов
  count = _count;

  // 3. Выделить память для массива A
  try
  {
    A = new T[count];
  }
  catch (bad_alloc e)
  {
    cout << e.what() << endl;
    return;
  }

  // 4. Скопировать A = _A
  for (int i = 0; i < count; i++)
    A[i] = _A[i];
}

  ⇑

2.3.3. Конструктор копирования LSearch(const LSearch&)

Поскольку память в массиве класса выделяется динамически, то необходимо объявить конструктор копирования. Более подробно о необходимости использования констуктора копирования и оператора присваивания в классе описывается здесь.

// Конструктор копирования - перенаправление на конструктор с двумя параметрами
LSearch(const LSearch& _A) :LSearch(_A.A, _A.count)
{
}

  ⇑

2.4. Методы доступа к экземпляру массива

Для доступа к внутреннему массиву класса реализованы два метода Get(), Set(). Эти методы размещаются в разделе public.

2.4.1. Метод Get(). Получить указатель на внутренний массив

С помощью метода Get() можно получить указатель на внутренний массив A класса. Метод получает ссылку на внешнюю переменную, которая получает значение количества элементов массива A.

// Метод, который возвращает указатель на внутренний массив A класса
T* Get(int* _count)
{
  *_count = count;
  return A;
}

  ⇑

2.4.2. Метод Set(). Установить новые значения в массиве

Метод Set() позволяет установить новый массив в качестве обрабатываемого.

// Метод изменения массива в текущем экземпляре
void Set(T* _A, int _count)
{
  // 1. Проверка, корректно ли значение _count
  if (_count <= 0)
  {
    A = nullptr;
    count = 0;
    return;
  }

  // 2. Освободить память, выделенную для массива A текущего экземпляра
  if (count > 0)
    delete[] A;

  // 3. Установить новое количество элементов
  count = _count;

  // 4. Выделить новый фрагмент памяти для A
  try
  {
    A = new T[count];
  }
  catch (bad_alloc e)
  {
    cout << e.what() << endl;
    return;
  }

  // 5. Присвоить A = _A
  for (int i = 0; i < count; i++)
    A[i] = _A[i];
}

  ⇑

2.5. Деструктор

Деструктор освобождает память, занятую под внутренний массив A. Деструктор вызывается автоматически в момент уничтожения экземпляра класса.

// Деструктор
~LSearch()
{
  if (count > 0)
  {
    delete[] A;
  }
}

  ⇑

2.6. Операторная функция operator=()

В классе нужно переопределить оператор присваивания =, который осуществляет присваивание экземпляров класса LSearch<T>. Это необходимо для избежания недостатков побитового копирования, которое возникает в случае, когда в классе используются указатели. Более подробно о необходимости переопределения оператора присваивания в классе описывается здесь.

// Переопределенный оператор присвоения
LSearch& operator=(LSearch& _A)
{
  // Вызвать метод Set() класса
  Set(_A.A, _A.count);

  // Возвратить текущий экземпляр
  return *this;
}

  ⇑

2.7. Методы реализации линейного поиска
2.7.1. Метод IsItem(). Определение, есть ли элемент (ключ) в массиве

Метод IsItem() определяет, есть ли элемент в массиве. Метод осуществляет последовательное сканирование массива от начала до конца. Результатом работы метода есть значение true или false.

В классе метод имеет две перегруженных реализации. Первая реализация предназначена для любого массива. Вторая реализация применяется для внутреннего массива текущего экземпляра класса.

// Перегруженный метод IsItem()
// Определение, есть ли элемент key в массиве, который задан входным параметром
bool IsItem(T* _A, int _count, T key)
{
  for (int i = 0; i < _count; i++)
    if (_A[i] == key) // как только элемент найден, то выход из функции
      return true;
  return false;
}

// Определение, есть ли элемент key в массиве, который задан в экземпляре класса
bool IsItem(T key)
{
  // вызвать обобщенный метод с данными текущего экземпляра
  return IsItem(this->A, this->count, key);
}

  ⇑

2.7.2. Метод NumOccurs(). Получить количество вхождений элемента в массиве

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

// 2. Перегруженный метод NumOccurs()
// Вычислить количество вхождений элемента в массив, который задан входным параметром
int NumOccurs(T* _A, int _count, T key)
{
  int num = 0;
  for (int i = 0; i < _count; i++)
    if (_A[i] == key)
      num++;
  return num;
}

// Вычислить количество вхождений элемента в массив, который задан
// в текущем экземпляре класса
int NumOccurs(T key)
{
  // Вызвать одноименный метод с текущими данными
  return NumOccurs(A, count, key);
}

  ⇑

2.7.3. Метод GetPos(). Получить массив позиций вхождений элемента в массиве

Метод GetPos() возвращает массив позиций вхождений заданного ключа в массиве. Внутри метода GetPos() выделяется память для результирующего массива. Поэтому, при использовании метода нужно позаботиться об освобождении этой памяти.

// 3. Перегруженный метод GetPos()
// Вернуть массив позиций вхождения заданного элемента во входном массиве
int* GetPos(T* _A, int _count, T key, int& nPos)
{
  // 1. Проверка, корректно ли значение count
  if (_count <= 0)
  {
    return nullptr;
  }

  // 2. Объявить внутренние переменные
  int* P = nullptr; // Результирующий массив

  // 3. Вычислить количество вхождений nPos
  nPos = NumOccurs(_A, _count, key);

  // 4. Выделить память для результирующего массива P
  try
  {
    P = new T[nPos];
  }
  catch (bad_alloc e)
  {
    cout << e.what() << endl;
    return nullptr;
  }

  // 5. Цикл вычисления номеров позиций
  //    и формирования массива P
  int t = 0;
  for (int i = 0; i < _count; i++)
    if (_A[i] == key)
      P[t++] = i;

  // 6. Вернуть указатель на массив позиций
  return P;
}

// Вернуть массив позиций в массиве текущего экземпляра
int* GetPos(T key, int& nPos)
{
  // Вызвать одноименную функцию
  return GetPos(A, count, key, nPos);
}

  ⇑

2.8. Метод Print(). Вывод содержимого массива на экран

Метод Print() реализован для консольного приложения и выводит значение элементов массива на экран.

// Метод, который выводит данные массива экземпляра на экран с комментарием text
void Print(const char* text)
{
  cout << text << endl;
  cout << "count = " << count << endl;
  for (int i = 0; i < count; i++)
    cout << A[i] << " ";
  cout << endl;
}

  ⇑

2.9. Функция main(). Тестирование работы класса

Тестирование работы класса осуществляется в функции main() для консольного приложения (тип Console Application).

void main(void)
{
  // Продемонстрировать работу класса LSearch
  // Экземпляр массива типа int - вызывается конструктор без параметров
  LSearch<int> L1;

  // Исследуемый массив чисел типа int
  int A[] = { 0, 2, 3, 5, 7, 3, 4, 8, 4, 0, 0, 2 };
  int count = 12; // количество элементов в массиве A

  // Добавить массив A к экземпляру L1
  L1.Set(A, count); // проверка метода Set

  // Определить, есть ли вобще элемент 3
  if (L1.IsItem(3))
  {
    // Если есть, то вывести количество вхождений элемента 3 в массиве A
    int k = L1.NumOccurs(3);
    cout << "k = " << k << endl;
  }
  L1.Print("L1:");

  // Проверка конструктора копирования
  LSearch<int> L2 = L1;
  L2.Print("L2:");

  // Проверка оператора присваивания
  LSearch<int> L3;
  L3 = L1;
  L3.Print("L3:");

  // Проверка метода Get() - заполнить новый массив значениями
  int* A2;
  int count2;
  A2 = L3.Get(&count2);

  // Вывести массив A2
  cout << "A2.count = " << count2 << endl;
  for (int i = 0; i < count2; i++)
    cout << A2[i] << " ";
  cout << endl;

  // Проверка метода GetPos() - получить массив позиций вхождения
  int nPos;
  int* P = L1.GetPos(0, nPos);
  cout << "nPos = " << nPos << endl;

  for (int i = 0; i < nPos; i++)
    cout << P[i] << " ";
  cout << endl;

  // После использования, нужно освободить память выделенную под массив P
  if (P != nullptr)
    delete[] P;

  // Проверка конструктора, получающего параметром входящий массив типа double
  double B[] = { 3.1, 2.8, 0.85, -10.5 }; // массив данных
  LSearch<double> L4(B, 4); // вызывается конструктор с двумя параметрами
  L4.Print("L4");

  // Определить количество вхождений числа 0.85 в массиве
  int k = L4.NumOccurs(0.85);
  cout << "k = " << k << endl;
}

Результат работы программы

k = 2
L1:
count = 12
0 2 3 5 7 3 4 8 4 0 0 2
L2:
count = 12
0 2 3 5 7 3 4 8 4 0 0 2
L3:
count = 12
0 2 3 5 7 3 4 8 4 0 0 2
A2.count = 12
0 2 3 5 7 3 4 8 4 0 0 2
nPos = 3
0 9 10
L4
count = 4
3.1 2.8 0.85 -10.5
k = 1

  ⇑

2.10. Текст класса (сокращенный вариант)

Последовательно выполнив все предыдущие пункты можно получить полный текст класса LSearch<T>. Ниже приведен программный код класса в сокращенном виде.

#include <iostream>
using namespace std;

// Шаблонный класс, реализующий линейный поиск в одномерном массиве
template <class T>
class LSearch
{
private:
  // Внутренние переменные
  T* A; // массив
  int count; // количество элементов в массиве

public:
  // Конструкторы
  // Конструктор без параметров
  LSearch()
  {
    ...
  }

  // Конструктор, который получает входящий массив,
  // которым инициализируются элементы внутреннего массива
  LSearch(T* _A, int _count)
  {
    ...
  }

  // Конструктор копирования - перенаправление на конструктор с двумя параметрами
  LSearch(const LSearch& _A) :LSearch(_A.A, _A.count)
  { }

  // ------- Методы доступа к экземпляру массива -------------
  // Метод изменения массива в текущем экземпляре
  void Set(T* _A, int _count)
  {
    ...
  }

  // Метод, возвращающий указатель на внутренний массив класса
  T* Get(int* _count)
  {
    ...
  }

  // Деструктор
  ~LSearch()
  {
    ...
  }

  // Переопределенный оператор присваивания
  LSearch& operator=(LSearch& _A)
  {
    ...
  }

  // ------ Методы поиска ----------
  // 1. Перегруженный метод IsItem()
  // Определение, есть ли элемент key в массиве, который задан входящим параметром
  bool IsItem(T* _A, int _count, T key)
  {
    ...
  }

  // Определение, есть ли элемент key в массиве, который задан в экземпляре класса
  bool IsItem(T key)
  {
    ...
  }

  // 2. Перегруженный метод NumOccurs()
  // Вычислить количество вхождений элемента в массив, который задан входящим параметром
  int NumOccurs(T* _A, int _count, T key)
  {
    ...
  }

  // Вычислить количество вхождений элемента в массив, который задан
  // в текущем экземпляре класса
  int NumOccurs(T key)
  {
    ...
  }

  // 3. Перегруженный метод GetPos()
  // Вернуть массив позиций вхождения заданного элемента во входящем массиве
  int* GetPos(T* _A, int _count, T key, int& nPos)
  {
    ...
  }

  // Вернуть массив позиций в массиве текущего экземпляра
  int* GetPos(T key, int& nPos)
  {
    ...
  }

  // Метод, выводящий данные массива экземпляра на экран с комментарием text
  void Print(const char* text)
  {
    ...
  }
};

void main(void)
{
  ...
}

  ⇑

Связанные темы

  ⇑