arrays

Motivation : let's assume you have been hired by a company(nice feeling isn't it!!!!) and the company wants you to write a program to manage a school 
consisting of say 2000 students and for each student you have to store, say there names(for now only names).
What will you do???
Well, some of you may say that we can declare 2000 variables(what???).
I hope you are smart enough to notice that this idea is taking you nowhere  and you are doomed to fail.
So C++ comes to the rescue and provides what is known as an Array.
So, let's look at what is an array actually!!!! 

Def : An Array is a collection of  homogeneous elements. Which have 

         contiguous allocation in memory and elements 

         have a position independent  constant access time.

Syntax : 

                  data type array name[size] ;

here size denotes the size of the array.

Note : size has to be a constant

Now, that we are familiar with the declaration of an array we can concentrate 
on use of the array.
One of the first question that should pop in your mind is that how do we access a single element of an array. The answer is pretty easy!!!!!
C++ assigns each and every element of an array what we know as an index
and we can use this index to our advantage and access the elements of the array.

So, say that you want to access the ith element of the array the syntax is :  array name [i-1] ;
The Exact mechanism of array element access will be revealed when we will learn about pointers in the next post.

For now just assume that there is some magic way to get access to the elements to the array.



Now, let's look at the memory representation of a 1-Dimensional array : 

This is how a 1D array is represented in memory.Notice that all the array blocks are contiguous in memory which makes available the location of  all blocks if the location of the first blocks is available.
The address of the first block in memory is called the base address of the array.
Note : in the pic above 'a' is the name of the array.

We will now look at ways of initializing an array. there are two ways(as with variables). 
1> compile time initialization or static initialization.
2> runtime initialization.

let's look at both of them in details :

1> compile time initialization or static initialization : This is the method that i followed in the picture of the memory representation of the array above.The values are specified during the declaration of an array

syntax  : 
                 data type array name[] = {val1, val2, val3, .........., valn};
                 
Note : You can either specify the size of the array in declaration or you can leave it blank(Why???? think of it).


2> Dynamic initialization :  In this method the array is just declared during the compile time and the initialization is done by user entered values at the run time. You can use any iterating methods to iterate through the elements of the array and take input from user during runtime. 

syntax : 
               data type array name[SIZE];

              loop ( iterate through all the elements ) :
                                                          for each element take input from user;

Note : i have written it in from of pseudo code since there is no fixed syntax for this initialization method.

                                  

Now, let's look at a program to search for an element in a 1d array(linear search) :

#include<iostream>
#include<conio.h>
using namespace std;
void main() {
 int a[10], key, pos = -1;
 cout<<"\n\n Enter Array elements : \n";
 for (int i = 0; i < 10; i++) {
  cout<<"\n Enter a["<<i<<"] : ";
  cin>>a[i];
 }
 cout<<"\n\n Enter Key : ";
 cin>>key;
 for (int i = 0; i < 10; i++) {
  if(a[i] == key){
   pos = i;
   break;
  }
 }
 if(pos == -1) {
  cout<<"\n\n Sorry !!! The element is not found !!!!";
 }
 else {
  cout<<"\n\n The Key("<<key<<") is found at : "<<pos<<"\n\n ";
  for (int i = 0; i < 10; i++) {
   if(pos == i) {
    cout<<"[";
   }
   cout<<a[i];
   if(pos == i) {
    cout<<"]";
   }
   cout<<" ";
  }
 }
 getch();
}

output :

we will now look at an interesting fact :
1> how to use functions with arrays.
Say you want to write a function that has to work with an array. Say for example you want to create a linear search function.
For this C++ allows you to call a function passing an array as an argument.

Syntax:
               function prototype :

               return type function name (data type array_name[], ......);

 Note : either you can leave the size empty or you can specify a size . 
The '[]' varies with dimension of an array.

              function call :

             function name(array_name, ......);

Note : only provide the array name and not size or type information.
'......' stands for the remaining arguments

Arrays are always passed by reference so any changes made to the array in the function is made to the original array.

Here is a program that creates 2 functions linearSearch() and  markPositionInArray();

#include<iostream>
#include<conio.h>
using namespace std;
int linearSearch(int a[], int n, int key) {
 for (int i = 0; i < 10; i++) 
  if(a[i] == key){
   return i;
  }
 return -1;
}
void markPositionInArray(int a[], int n, int pos) {
 cout<<"\n\n ";
 for (int i = 0; i < 10; i++) {
  if(pos == i) {
   cout<<"[";
  }
  cout<<a[i];
  if(pos == i) {
   cout<<"]";
  }
  cout<<" ";
 }
}
void main() {
 int a[10], key, pos;
 cout<<"\n\n Enter Array elements : \n";
 for (int i = 0; i < 10; i++) {
  cout<<"\n Enter a["<<i<<"] : ";
  cin>>a[i];
 }
 cout<<"\n\n Enter Key : ";
 cin>>key;
 pos = linearSearch(a, 10, key);
 if(pos == -1) {
  cout<<"\n\n Sorry !!! The element is not found !!!!";
 }
 else {
  cout<<"\n\n The Key("<<key<<") is found at : "<<pos;
  markPositionInArray(a, 10, pos);
 }
 getch();
}

All the type of arrays we looked at till now were 1 dimensional.
But C++ also provides what is known as multi-dimensional array.
Let's look at a 2d dimensional array

look at the pic below to understand the 2D array better :

Now the question is how do we access a single element of a 2d array.
It's really simple. In order to access an element of a 2d array you need a row number and a column number(both starting from 0). So, it looks like
this :
Syntax : array name[row_index][column_index]
Note : these indexes are always 1 less than the actual number. Since they start from '0'.

Now, lets write a few programs on 2d array. I hope almost all of us are accustomed with matrices(for those who have not come across them yet
here is  a link :  What is a matrix???).
we will do the following :
1> add two matrices.
2> transpose a matrix
3> multiply two matrices
4> find the diagonal sum(either left or right).
This will also give you a taste of how a menu driven program works.

#include<iostream>
#include<conio.h>
#define LEFT  0
#define RIGHT 1
#define SIZE 3
using namespace std;
void multiply2Matrices(int A[][SIZE], int B[][SIZE], int r1, int c1, int r2, int c2);
void add2Matrices(int A[][SIZE], int B[][SIZE], int r1, int c1, int r2, int c2);
void transposeAMatrix(int A[][SIZE], int r1, int c1);
void findDiaogonalSum(int A[][SIZE], int r1, int c1, int direction);
void input(int A[][SIZE], int r1, int c1);
void print(int a[][SIZE]) {
 for (int i = 0; i < SIZE; i++) {
  cout<<"\n ";
  for (int j = 0; j < SIZE; j++) {
   cout<<a[i][j]<<" ";
  }
 }
}
void main()  {
 int choice, A[SIZE][SIZE], B[SIZE][SIZE];
 while(1) {
  system("cls");
  cout<<"Menu : \n\n";
  cout<<"1> Add\n\n";
  cout<<"2> Multiply\n\n";
  cout<<"3> Transpose\n\n";
  cout<<"4> Find Diagonal Sum\n\n";
  cout<<"5> Exit\n\n   ";
  cout<<"Enter Choice : ";
  cin>>choice;
  switch (choice)
  {
   case 1:
    cout<<"\n\nA : ";
    input(A, SIZE, SIZE);
    cout<<"\n\nB : ";
    input(B, SIZE, SIZE);
    cout<<"\n\n A + B : ";
    add2Matrices(A, B, SIZE, SIZE, SIZE, SIZE);
    break;
   case 2:
    cout<<"\n\nA : ";
    input(A, SIZE, SIZE);
    cout<<"\n\nB : ";
    input(B, SIZE, SIZE);
    cout<<"\n\n A * B : ";
    multiply2Matrices(A, B, SIZE, SIZE, SIZE, SIZE);
    break;
   case 3:
    cout<<"\n\nA : ";
    input(A, SIZE, SIZE);
    cout<<"\n\n Transpose(A) : ";
    transposeAMatrix(A, SIZE, SIZE);
    break;
   case 4:
    cout<<"\n\nA : ";
    input(A, SIZE, SIZE);
    int direction;
    cout<<"Enter Direction : ";
    cin>>direction;
    cout<<"\n\n The sum of the"<<(direction == RIGHT ? " right " : " left ")<<"diagonal : ";
    findDiaogonalSum(A, SIZE, SIZE, direction);
    break;
   default:
    system("cls"); //for clear screen
    cout<<"\n\n Wrong Choice(Hit Enter to Continue!!!) ";
    break;
  }
  getch();
 }
}
void input(int A[][SIZE], int r1, int c1) {
 cout<<"Enter the elements\n\n";
  for (int i = 0; i < r1; i++) {
   cout<<" ";
  for (int j = 0; j < c1; j++) {
   cin>>A[i][j];
  }
 }
}
void multiply2Matrices(int A[][SIZE], int B[][SIZE], int r1, int c1, int r2, int c2) {
 int C[SIZE][SIZE] = {0};
 if(c1 != r2) {
  cout<<"Incompatible Matrices. So, cannot multiply !!!"; 
  return;
 }
 for(int i = 0; i < r1; i++) {
  for(int j = 0; j < c1; j++) {
   for(int k = 0; k < c2; k++) {
    C[i][j] += A[j][k] * B[k][j];
   }
  }
 }
 print(C);
}
void add2Matrices(int A[][SIZE], int B[][SIZE], int r1, int c1, int r2, int c2) {
 if(r1 != r2 || c1 != c2) {
  cout<<"Incompatible Matrices. So, cannot add !!!"; 
  return;
 }
 int C[SIZE][SIZE] = {0};
 for (int i = 0; i < r1; i++) {
  for (int j = 0; j < c1; j++) {
   C[i][j] = A[i][j] + B[i][j];
  }
 }
 print(C);
}
void transposeAMatrix(int A[][SIZE], int r1, int c1) {
 int C[SIZE][SIZE];
 for (int i = 0; i < r1; i++) {
  for (int j = 0; j < c1; j++) {
   C[j][i] = A[i][j];
  }
 }
 print(C);
}
void findDiaogonalSum(int A[][SIZE], int r1, int c1, int direction) {
 int sum = 0;
 if(r1 != c1) {
    cout<<"Incompatible Matrices. So, cannot find diagonal sum !!!";
 }
 if(direction == RIGHT) {
  for (int i = 0; i < r1; i++) {
   sum += A[i][i];
  }
 }
 else {
  for (int i = 0, j = r1-1; i < r1 && j >= 0; i++, j--) {
   sum += A[i][j];
  }
 }
 cout<<sum;
}

here are the programs in the google drive : Learning C++