C#. Development of a generic class that contains tools for implementing linear search for an element in an array

Development of a generic class that contains tools for implementing linear search for an element in an array

This topic demonstrates a step-by-step process of developing the LSearch<T> class, which contains a number of methods that implement a linear search for an element (key) in a one-dimensional array of elements of type T. After passing all the points of this topic, you can gain experience in developing classes in the C# language and learn the basics of object-oriented programming.

Search other websites:

Task

Using the tools of the C# language, develop a class LSearch<T> that contains methods that search for a given key in a one-dimensional array. In the class, implement:

internal variables for storing data;
constructors and methods for accessing internal data;
a method that determines the presence of an element in an array;
a method that determines the number of occurrences of a given element in the array;
a method that returns an array of position numbers for the occurrence of a given element in the array.

⇑

Instruction

1. Creating an application of type Console Application. The structure of the project

The initial module code that includes the LSearch<T> and Program classes is as follows

using static System.Console;

namespace ConsoleApp1
{
  // Class that handles the generic type T
  class LSearch<T>
  {
  }

  class Program
  {
    static void Main(string[] args)
    {
    }
  }
}

⇑

2. Developing a generic LSearch<T> class

2.1. Internal class variables

Linear search is implemented on a one-dimensional array. Therefore, class LSearch<T> includes a one-dimensional array of type T

...

class LSearch<T>
{
  // Internal class variables
  private T[] A; // One-dimensional array
}

...

⇑

2.2. Class constructors

Two constructors are introduced into the body of the LSearch<T> class:

constructor without a parameters LSearch() – initializes the array to null;
constructor with parameter LSearch(T[]) – initializes the internal array A with the values of elements of another array. To allocate memory and copy data into array A, the Clone() method is used, which can be used for all arrays.

// Class constructors.
// Constructor without parameters
public LSearch()
{
  A = null;
}

// A constructor that receives an array of elements of type T as input
public LSearch(T[] _A)
{
  // Use the Clone() method
  A = (T[])_A.Clone(); // copy array
}

⇑

2.3. Methods to access the internal array

To access the array A of an instance of the LSearch<T> class, the following methods are implemented

// Array access methods
// Get a reference to the entire array
public T[] Get()
{
  return A;
}

// Set a new array
public void Set(T[] _A)
{
  A = (T[])_A.Clone();
}

⇑

2.4. Methods of implementation of linear search

2.4.1. Method IsItem(). Determining if a given element is in an array

The IsItem() method determines if there is an item in the array at all. The method has two overloaded implementations. The first implementation searches for a key (element) in an external array, which is passed to the method as an input parameter. The second implementation uses the internal array A.

// Methods that implement linear search
// Determining if a given element is in the array
public bool IsItem(T[] A, T key)
{
  for (int i = 0; i < A.Length; i++)
    if (A[i].Equals(key)) // checking if object values are equal
      return true;
  return false;
}

// An overloaded version of the IsItem method that processes an internal array.
public bool IsItem(T key)
{
  return IsItem(this.A, key);
}

⇑

2.4.2. Method GetNOccurences(). Determining the number of occurrences of a given element in an array

The GetNOccurences() method returns the number of occurrences of the specified element in the array. The method performs a sequential scan of the array from beginning to end and compares the input key (element) with each element of the array. For comparison, the Equals() method of the System.Object class is used.

// Determining the number of occurrences of an element in the array
// Method implementation for any external array
public int GetNOccurences(T[] A, T key)
{
  int k = 0;
  for (int i = 0; i < A.Length; i++)
    if (A[i].Equals(key))
      k++;
  return k;
}

// Method implementation for internal array
public int GetNOccurences(T key)
{
  return GetNOccurences(this.A, key);
}

⇑

2.4.3. Method GetPositions(). Get an array of positions of occurrence of a given element in the array

Using the overloaded GetPositions() method, you can get an array that contains the numbers of positions in which the specified key (element) is located. The GetPositions() method uses the CopyTo() method to copy one array to another.

// Get an array of positions of occurrence of an element in the array
public int[] GetPositions(T[] A, T key)
{
  int[] AP = new int[0]; // at the beginning there are 0 elements in the array
  int[] AP2; // additional array

  for (int i = 0; i < A.Length; i++)
  {
    if (A[i].Equals(key))
    {
      // Allocate 1 element more memory for a new array
      try
      {
        AP2 = new int[AP.Length + 1];

        // Copy AP => AP2 - use the CopyTo() method
        AP.CopyTo(AP2, 0);

        // Add last item
        AP2[AP.Length] = i;

        // Redirect reference
        AP = AP2;
      }
      catch (Exception e)
      {
        WriteLine(e.Message);
      }
    }
  }
  return AP;
}

// An overloaded version of the GetPositions() method
public int[] GetPositions(T key)
{
  return GetPositions(this.A, key);
}

⇑

2.5. Inner array output method

For testing purposes, the Print() method of printing the internal array A to the screen has been introduced into the LSearch<T> class.

// Array display method
public void Print(string comment)
{
  WriteLine(comment);
  for (int i = 0; i < A.Length; i++)
    Write("{0}   ", A[i]);
  WriteLine();
}

⇑

2.6. Abbreviated text of the LSearch<T> class

An abbreviated form of the LSearch<T> class is as follows

// Development of a generic class that contains tools for implementing linear search
// The class handles the generic type T
class LSearch<T>
{
  // Internal class variables
  private T[] A; // One-dimensional array

  // Class constructors.
  // Constructor without a parameters
  public LSearch()
  {
    ...
  }

  // A constructor that receives an array of elements of type T as input
  public LSearch(T[] _A)
  {
    ...
  }

  // Array access methods
  // Get a reference to the entire array
  public T[] Get()
  {
    ...
  }

  // Set a new array
  public void Set(T[] _A)
  {
    ...
  }

  // Methods that implements a linear search
  // Determining if a given element is in an array
  public bool IsItem(T[] A, T key)
  {
    ...
  }

  // An overloaded version of the IsItem method that processes an internal array.
  public bool IsItem(T key)
  {
    ...
  }

  // Determining the number of occurrences of an element in an array
  // Method implementation for any external array
  public int GetNOccurences(T[] A, T key)
  {
    ...
  }

  // Method implementation for an internal array
  public int GetNOccurences(T key)
  {
    ...
  }

  // Get an array of positions of occurrence of an element in an array
  public int[] GetPositions(T[] A, T key)
  {
    ...
  }

  // Overloaded version of GetPositions() method
  public int[] GetPositions(T key)
  {
    ...
  }

  // Array display method
  public void Print(string comment)
  {
    ...
  }
}

⇑

3. Testing the LSearch<T> class. Method main()

Testing the LSearch<T> class. Method main()

class Program
{
  static void Main(string[] args)
  {
    // Testing the LSearch<T> class
    int[] AI = { 5, 8, 9, -1, 4 };

    // Create an instance of LSearch<int> class with specified AI array
    LSearch<int> L1 = new LSearch<int>(AI);

    // Determine if there is an item 8. Method IsItem()
    if (L1.IsItem(8))
      WriteLine("Item 8 is in array AI");
    else
      WriteLine("Item 8 is not in array AI");

    // Testing the GetNOccurences() method
    char[] AC = { 'a', 'b', 'f', 'a', 'a', 'c', 'd', 'i', 'f' };
    LSearch<char> L2 = new LSearch<char>(AC);
    int n = L2.GetNOccurences('a');
    WriteLine("n = {0}", n); // n = 3

    // Testing GetPositions() method
    bool[] AB = { true, true, false, false, true, false, true, true }; // array
    LSearch<bool> L3 = new LSearch<bool>(); // invoke the constructor without parameters
    L3.Set(AB); // Method Set() - set a new array
    int[] Positions = L3.GetPositions(true);

    // Print positions of true value in array AB
    for (int i = 0; i < Positions.Length; i++)
    {
      Write("{0}   ", Positions[i]);
    }
    WriteLine();
    ReadLine();
  }
}

After running for execution, the program will give the following result

Item 8 is in array AI
n = 3
0 1 4 6 7

BestProg