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)
{
  ...
}

  ⇑

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

  ⇑