Friday, June 27, 2014

Basic Operations on Array (Traversal, Insertion, Deletion, Search) - Data Structures - C++ Program (Object Oriented)

Problem Question


Implement the data structure, Array, and write a program to perform basic operations, Traversal, Insertion, Deletion, and Search on it.

Explanation of Problem


In this program, we are required to use array and perform the basic operations, listed above, on it. Since traversal is nothing but going through all the elements, there is no point performing only traversal since there won't be any output of it. So the method, displayArray, which displays the whole array in my program, is to be considered as traversal of the array. Search is implemented as sequential search for simplicity of the program in the method findPosition.

Code


#include <iostream> //Support c++
#include <cstdlib> //For exit()

/**@Title: OOArray.cpp*
*@Programming Paradigm: Object Oriented*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 27-06-2014*
*/

class myArray
{
private:
  int arr[1000];

public:
  int arraySize;

  myArray()
  {
    std::cout << "\n\aEnter the size of the array(Upto 1000): ";
    std::cin >> arraySize;
    std::cout << "\n\aFill the array with " << arraySize;
    std::cout << " elements: ";
    int i = 0;
    for ( i = 0; i < arraySize; i++ )
      std::cin >> arr[i];
  }

  myArray(int argArraySize)
  {
    arraySize = argArraySize;
    std::cout << "\n\aFill the array with " << arraySize;
    std::cout << " elements: ";
    int i = 0;
    for ( i = 0; i < arraySize; i++ )
      std::cin >> arr[i];
  }

  void insertIntoArray(int insertAt, int insertMe)
  {
    if ( arraySize < 1000 )
    {
      arraySize++;
      if ( insertAt > arraySize )
      {
        std::cout << "\nThe array as yet has " << arraySize - 1;
        std::cout << " elements.\nThus the new element will be inserted at position " << arraySize;
        std::cout << " in the array.\n";
        insertAt = arraySize;
      }
      int i = 0;
      for ( i = arraySize + 1; i >= insertAt; i-- )
        arr[i] = arr[i - 1];
      arr[insertAt - 1] = insertMe;
    }
    else
      std::cout << "\n\n\aALREADY AT LIMITS\n\n\a";
  }

  void findPosition(int findMe)
  {
    int i = 0, flag = 0;
    for ( i = 0; i < arraySize; i++)
    {
      if ( arr[i] == findMe )
      {
        std::cout << "The number was found at: " << i + 1 << std::endl;
        flag = 1;
      }
    }
    if ( flag != 1 )
      std::cout<<"The number was not found!" << std::endl;
  }

  void deleteFromArray(int deleteMe)
  {
    int i = 0, j = 0, flag = 0;
    for ( i = 0; i < arraySize; i++)
    {
      if ( arr[i] == deleteMe )
      {
        arraySize--;
        for ( j = i; j < arraySize + 1; j++ )
          arr[j] = arr[j + 1];
        flag = 1;
        i = -1;
      }
    }
    if ( flag != 1 )
      std::cout<<"The number was not found!" << std::endl;
  }

  void displayArray()
  {
    int i = 0;
    std::cout << "\n\aCurrently the array is:";
    for (i = 0; i < arraySize; i++)
      std::cout << " " << arr[i];
  }
};

int main()
{
  std::cout << "\n\aWelcome to ArrayOps v2.0\n\aMade by Rogue Coder\n";
  myArray arrayObject;
  int choice = 0, num, pos;
  do
  {
    arrayObject.displayArray();
    std::cout << "\a\nChoices:\n1. Insert\n2. Delete\n3. Find\n4. Exit\nYour Choice: ";
    std::cin >> choice;
    switch (choice)
    {
    case 1:
      std::cout << "\nEnter the number to be inserted: ";
      std::cin >> num;
      std::cout << "\nEnter the position where to enter: ";
      std::cin >> pos;
      arrayObject.insertIntoArray(pos, num);
      break;
    case 2:
      std::cout << "\nEnter the number to be deleted: ";
      std::cin >> num;
      arrayObject.deleteFromArray(num);
      break;
    case 3:
      std::cout << "\nEnter the number to be found: ";
      std::cin >> num;
      arrayObject.findPosition(num);
      break;
    case 4:
      std::cout << "\n\n\aThank You for Using ArrayOps v2.0\n\aMade by Rogue Coder\n\aPress any key to exit.";
      std::cin.get();
      exit(0);
      break;
    default:
      std::cout << "\a\n\nWRONG CHOICE\a\n\n";
      break;
    }
  }
  while ( choice != 4 );
  return 0;
}


Explanation of Code


#include <iostream> -> The compiler calls the Preprocessor to include the IOSTREAM(Standard Input / Output Streams Library) header file into the program, thus letting the use of the Standard Input / Output Streams functions like std::cin and std::cout. As per C++11 specification, including <iostream> automatically includes also <ios>, <streambuf>, <istream>, <ostream> and <iosfwd>.

int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.

std::cin (extern istream cin) -> Standard Input Stream, and object of class istream. It is generally used with the extraction operator (>>), though we can use member functions like get (cin.get()), read (cin.read()), etc. for the input. The use of extraction operator is much more popular due to the fact that it aids in getting formatted input.

std::cout (extern ostream cout) -> Standard Output Stream, and object of class ostream. It is generally used with the insertion operator (<<), though we can use member functions like write (cout.write()) for the output. The use of insertions operator is much more popular due to the fact that it aids in giving formatted output.

std::endl (ostream& endl (ostream& os)) -> This is a function which is used to insert a newline character and flush the stream. Because this function is a manipulator, it is designed to be used alone with no arguments in conjunction with the insertion (<<) operations on output streams.

class myArray -> The class that would wrap the array, int arr[1000], and the methods that are used to accessed it.

int arraySize -> This variable is used to store the size of the array. Though we have defined the array to be of length 1000, but 'arraySize' represents a bound on this length upto which the methods should access the array elements.

myArray()
{
std::cout << "\n\aEnter the size of the array(Upto 1000): ";
std::cin >> arraySize;
std::cout << "\n\aFill the array with " << arraySize;
std::cout << " elements: ";
int i = 0;
for ( i = 0; i < arraySize; i++ )
std::cin >> arr[i];
}
This is the constructor for the myArray class. When the object is created for myArray class, the constructor is called. Since before we perform any operations on the array, we should have an initial array in hand. Thus, the constructor prompts the user to enter an initial arraySize and fill the array with that many elements.

myArray(int argArraySize)
{
arraySize = argArraySize;
std::cout << "\n\aFill the array with " << arraySize;
std::cout << " elements: ";
int i = 0;
for ( i = 0; i < arraySize; i++ )
std::cin >> arr[i];
}

I have made this constructor but never called it. If you wish to make a different kind of object initialisation, you can use this constructor. To use this, you'll have to pass the arraySize to the object when it is created. You can either get the user input and use that user input to act as the argument for the constructor, else you can use a constant int for the purpose.

void insertIntoArray(int insertAt, int insertMe)
{
if ( arraySize < 1000 )
{
arraySize++;
if ( insertAt > arraySize )
{
std::cout << "\nThe array as yet has " << arraySize - 1;
std::cout << " elements.\nThus the new element will be inserted at position " << arraySize;
std::cout << " in the array.\n";
insertAt = arraySize;
}
int i = 0;
for ( i = arraySize + 1; i >= insertAt; i-- )
arr[i] = arr[i - 1];
arr[insertAt - 1] = insertMe;
}
else
std::cout << "\n\n\aALREADY AT LIMITS\n\n\a";
}
This method is used to insert a value into the array. It takes to arguments, first, the position where to enter, second, the value to be entered. The if condition in the beginning of this method is used to do a little bounds checking, to make sure if the array is at limits (1000 in this case), no more insertions are possible. In case the if condition fails, a message telling the user that the array has reached it's limits is issued. In case the if condition stands true, i.e., the array is still in it's limits, we proceed with the insertion. The first thing to do in such case is to increment the value of variable arraySize so that the upper bound on the limit of traversal can be set to correct value. Then we check if the position that user asked is greater than this new value of arraySize. This would mean, insertion outside the bound on the limit. Thus, a message is issued telling the suer the current array size, and thus inserting at the last possible position in the array. To do that, insertAt's value is changed to that of arraySize, in the case explained above only!. Next, a for loop is used to traverse the array upto the position that the user asked. The user asks for a position in the range, [1 , arraySize ], and the computer sees the array in the range [0 , arraySize - 1 ], thus the values of 'i' in the for loop. When the correct position is reached, the value is inserted into the array.

void findPosition(int findMe)
{
int i = 0, flag = 0;
for ( i = 0; i < arraySize; i++)
{
if ( arr[i] == findMe )
{
std::cout << "The number was found at: " << i + 1 << std::endl;
flag = 1;
}
}
if ( flag != 1 )
std::cout<<"The number was not found!" << std::endl;
}
This method is used to find the position of an element in the array, i.e., to implement sequential search on the array. The variable 'i' is the loop counter, and the variable, 'flag' is used to determine success/failure of the search. The for loop searches for the element to be found traversing the array sequentially, and matching the element with every element of the array as the loop moves forward. On each successful match, which is checked by the if condition inside the for loop, the user is signalled by a message denoting the position of the element in the array. To keep the output as per user's perception of array's range, i.e., [1 , arraySize], the 'i+1' is printed and not 'i'. The flag is set to 1 on a successful search. On exiting the loop, the flag value is checked again. If the value is not 1, it indicates that the search was unsuccessful, and hence the user is signalled a failure message.

void deleteFromArray(int deleteMe)
{
int i = 0, j = 0, flag = 0;
for ( i = 0; i < arraySize; i++)
{
if ( arr[i] == deleteMe )
{
arraySize--;
for ( j = i; j < arraySize + 1; j++ )
arr[j] = arr[j + 1];
flag = 1;
i = -1;
}
}
if ( flag != 1 )
std::cout<<"The number was not found!" << std::endl;
}
This method is used to delete an element from the array. If the element has multiple occurrences in the array, this method would delete all the occurrences of that element. We have 'i' and 'j' as the loop counters, and 'flag' to signal success/failure, which is a consequence of success/failure of the search. The outer for loop simply performs a sequential search on the array to find the element that the user requested to delete from the array. If the element is found, the arraySize is decremented since a deletion implies reduction in array's size. Next, the inner for loop, which starts from the position where the search was successful, i.e., the current value of 'i', and goes on to one more than upper bound on the array limit, i.e., arraySize+1 (because we decremented the arraySize already, but we might still need the last element of the array), moves the elements one position left, thereby deleting the element from the array. The flag is set to 1 since it was a success case. Then the value of 'i' is set to -1, since the out loop will increment the value of 'i', and in case we have 2 successive occurrences of the element, we won't be able to remove both without traversing the array again. Why does this happen? Consider we didn't have the statement i=-1. let the element is present at position 3 and 4. When the loop found the element at position 3, it shifted the array elements one position left. Now the loop would increment the counter. The element formerly on 4, is now on 3, and since the counter has moved to 4, we would skip that occurrence! That's why we need the statement, i=-1. It would force the loop to restart (restart from 0 since i=-1, and the loop will increment it to 0) on each successful search-and-delete operation. Since i=-1 is executed only if the search was successful, we don't end up being caught in an infinite loop. Once we exit the outer for loop, the value of flag is checked. If that value is not 1, it denotes failure, and thus the user is signalled the same.

void displayArray()
{
int i = 0;
std::cout << "\n\aCurrently the array is:";
for (i = 0; i < arraySize; i++)
std::cout << " " << arr[i];
}
This method is used to display the current state of the array. It has a for loop that prints the array upto the arraySize bound.

myArray arrayObject; -> The object is instantiated, and thus the constructor is called.

int choice = 0, num, pos; -> 'choice' is used to hold the value of user's choice in the switch menu, 'num' is used to get the user's input of the element to be inserted/deleted/searched. 'pos' is used to get the user input denoting, the position of the element in case of insertion operation.

case 1:
std::cout << "\nEnter the number to be inserted: ";
std::cin >> num;
std::cout << "\nEnter the position where to enter: ";
std::cin >> pos;
arrayObject.insertIntoArray(pos, num);
break;
Case 1, which gets the user input on what element to be inserted and where it is to be inserted. Then the method insertIntoArray is called with the user input as arguments.

case 2:
std::cout << "\nEnter the number to be deleted: ";
std::cin >> num;
arrayObject.deleteFromArray(num);
break;
Case 2, where the user asks to delete a number, 'num', from the array, and the method deleteFromArray is called with the user input as argument.

case 3:
std::cout << "\nEnter the number to be found: ";
std::cin >> num;
arrayObject.findPosition(num);
break;
Case 3, where the user asks to find the position(s) of occurrence(s) of the number, 'num' in the array. The method findPosition is called with the user input as argument.

case 4:
std::cout << "\n\n\aThank You for Using ArrayOps v2.0\n\aMade by Rogue Coder\n\aPress any key to exit.";
std::cin.get();
exit(0);
break;
Case 4, where the user exits the program.

default:
std::cout << "\a\n\nWRONG CHOICE\a\n\n";
break;
Default case, used to handle unspecified cases, that is, wrong choices in the menu.

exit(0); -> This function is used to exit the program with an error code as it's argument. '0' implies normal exit. Other values are used for debugging purposes.

std::cin.get() -> This statement is used to pause our program, until user presses a key. This function is not necessary in your program, I use it to see my outputs at a paused screen. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.

Output(s)




Download Source Code


1 comment:

Need help?