arrays

Binary Search

http://install4install.com

Binary Search

The binary search technique works only on sorted array.It works by comparing the input element to the middle element of array.The comparison determines whether the element is less than.greater than or equal to middle element.Subsequent steps to be followed are written and explained by the following program.

Program

#include <stdio.h>

int main()
{
	int val[10] = {10,20,30,40,50,55,68,77,89,90};//Fig 3
	int beg = 0;   //first index of array
	int end = 9;  //end(last index of array)  = n-1 where n is the size of array and is 10 in this case.
	int mid = (beg+end)/2; // finds middle index of array.
	int i;
	int element;
	//printf("enter the element you want search for");
	scanf("%d",&element);
	for(i=0;i<10;i++) //Fig 4
	{
	if(val[mid] == element)	{
		break;
	}
	else if(val[mid] < element) {
	beg = mid +1;
	mid = (beg +end)/2;
	}
	else{
	end =mid -1;
		mid = (beg +end)/2;
	}
	}
	printf("Location of element is %d",mid);
	return 0;
}

Run

Illustration
Fig 3:An Array

Fig 3:An Array

  • val[10] of int type is initialized with values 10,20,30,40,50,55,68,77,89,90.
  • beg variable of int type denotes the first index of array i.e. 0
  • end variable of int type denotes the last index of array .It is equal to (n-1),where n is the size of array.Here it is 10 so end=10-1=9
  • mid index is calculated by adding beg plus end and the dividing the result by 2.
  • element variable of int type is the data item which needs to be searched for in array and is entered by user using scanf.
  • Say we want to search for 68 .
  • The following  figure explains the working of for loop to find 68.
Screen Shot 2014-03-19 at 4.43.35 PM

Fig 4 : Explanation of Binary Search Program


Short URL: http://tinyit.cc/89edd
By Cusp2207 on July 18, 2014 | Algorithms, Computer Science | A comment?
Tags:

Merge Sort

Merge sort is the divide and conquer method to arrange elements in the order.The steps followed in merge sort are :

  • Divide the sequence of n elements into two sub-sequences of n/2 elements each.
  • Sort the sub-sequences using merge sort.If the size of sequence is 1,nothing more can be done.
  • Merge the sub-sequences to form a sorted sequence of elements.

The complexity of merge sort is O(n log n).It runs faster than insertion and bubble sort but requires large amount of memory.

 

Program

#include<stdio.h>
void merge(int [],int ,int ,int );
void partition(int [],int ,int );
int main()
{
 int a[20];
 int i,size;
 printf("Unsorted List:\t");
 //printf("Enter total no. of elements : ");
 scanf("%d",&size);
 for(i=0; i<size; i++)
 {
   scanf("%d",&a[i]);
   printf("%d\t",a[i]);
 }
 printf("\n");
 partition(a,0,size-1);
 printf("Sorted List  :\t");
 for(i=0; i<size; i++)
 printf("%d \t",a[i]);
 return 0;
}
void partition(int a[],int min,int max)
{
 int mid;
 if(min<max)
 {
   mid=(min+max)/2;
   partition(a,min,mid);
   partition(a,mid+1,max);
   merge(a,min,mid,max);
 }
}
void merge(int a[],int min,int mid,int max)
{
  int temp[20];
  int i,j,k,m; 
  j=min;
  m=mid+1;
  for(i=min; j<=mid && m<=max ; i++)
  {
     if(a[j]<=a[m])
     {
        temp[i]=a[j];
      	j++;
     }
     else
     {
         temp[i]=a[m];
         m++;
     }
  }
  if(j>mid)
  {
     for(k=m; k<=max; k++)
     {
         temp[i]=a[k];
         i++;
     }
  }
  else
  {
     for(k=j; k<=mid; k++)
     {
        temp[i]=a[k];
        i++;
     }
  }
  for(k=min; k<=max; k++)
     a[k]=temp[k];
}

Run

 

Example

Consider a sequence 7,44,2,10,1,35,74,88,5,3,15.We need to sort this  using merge sort.The list contains 11 elements(Fig 1).Divide the list such that first sub-list has 6 elements and second sub-list has 5 elements(vice-versa is also possible).Keep on dividing till we get single elements in the last.After dividing merge all the elements step by step as shown in Fig 2.

Screen Shot 2014-06-26 at 1.53.09 PM

Fig 1 : Dividing

 

Screen Shot 2014-06-26 at 1.57.46 PM

Fig 2 : Merging

 


Short URL: http://tinyit.cc/d2ed
By Cusp2207 on June 26, 2014 | Computer Science | A comment?
Tags:

Bubblesort

Bubblesort is a sorting technique which arrange elements in the increasing order by moving across the array and swapping the adjacent elements that are out of order.The complexity of bubble sort is O(n2).

The steps followed are :

  • Move from first to the last element of array.
  • Swap the element if it is greater than adjacent element.
  • No need to swap if adjacent element is greater.

Program

#include <stdio.h>

void bubble(int [], int);

int main()
{
  int arr[50], n, a, b;
  //printf("Enter number of elements\n");
  scanf("%d", &n);
  //printf("Enter elements of array \n");
  printf("Unsorted list is :\t");
  for (a = 0; a < n; a++)
  {
  scanf("%d", &arr[a]);
  printf("%d\t",arr[a]);
  }
  bubble(arr, n);
  printf("\nSorted list is:\t");
  for ( a = 0 ; a < n ; a++ )
  {
     printf("%d\t", arr[a]);
  }
  return 0;
}

void bubble(int array[], int n)
{
  int a, b, temp;
  for (a = 0 ; a < ( n - 1 ); a++)
  {
    for (b = 0 ; b < n - a - 1; b++)
    {
      if (array[b] > array[b+1])
      {
      	temp         = array[b];
        array[b]   = array[b+1];
        array[b+1] = temp;
      }
    }
  }
}

Run Example Consider an  array with elements 3,7,2,10,1,35,15,5,30,4,8.In order to sort elements,iterations are used.In the first iteration when i=1 sorting is done as given in  Fig 1 and Fig 2.Refer to Fig 3 and 4 for second iteration i.e i=2,Fig 5 and 6 for i=3.Fig 7 and 8 for i=4,Fig 9 and 10 for i=5.Fig 11 and 12 for i =6 respectively.

Screen Shot 2014-06-18 at 3.21.24 PM

Fig 1 : i=1

Screen Shot 2014-06-18 at 3.23.04 PM

Fig 2 : i=1

Screen Shot 2014-06-18 at 3.25.55 PM

Fig 3 : i=2

Screen Shot 2014-06-18 at 3.26.57 PM

Fig 4 : i =2

Screen Shot 2014-06-18 at 3.29.25 PM

Fig 5 : i=3

Screen Shot 2014-06-18 at 3.32.47 PM

Fig 6 : i=3

Screen Shot 2014-06-18 at 3.35.19 PM

Fig 7 : i=4

Screen Shot 2014-06-18 at 3.37.45 PM

Fig 8 : i=4

Screen Shot 2014-06-18 at 3.42.22 PM

Fig 9 : i=5

Screen Shot 2014-06-18 at 3.44.58 PM

Fig 10 : i=5

Screen Shot 2014-06-18 at 3.47.25 PM

Fig 11 : i=6

Screen Shot 2014-06-18 at 3.50.03 PM

Fig 12 : i=6

 


Short URL: http://tinyit.cc/4d00f0
By Cusp2207 on June 18, 2014 | Computer Science | A comment?
Tags:

Quicksort

Sorting is a technique to arrange the sequence of elements either in ascending or descending order. Quicksort is an efficient way to sort elements of array.The average running time of quicksort is O(nlogn).The steps followed in quicksort are :

  • Choose the pivot element(Say we choose the pivot element in the beginning of array).
  •  Scan from right to left and find first element in list which is less than the pivot element.Stop scanning as soon the element is found.
  • Swap it with the pivot element.
  • Now scan from left to right to find the first element which is greater than pivot element.
  • Swap the element with pivot.
  • Continue the process till the list is sorted or we get a list for which the above process fails to be followed up.
  • Divide/partition  the array with pivot in between into two sub-arrays .
  • Same process is followed on both the sub-arrays separately and further partitioning and processing is done if necessary.
  • Combine all the sub-arrays and their pivot elements to get a sorted array.

Program

#include<stdio.h>
void swap (int arr[], int left, int right)
 {
 int temp;
 temp=arr[left];
 arr[left]=arr[right];
 arr[right]=temp; 
 }
void quicksort( int arr[], int low, int high )
 {
 int pivot;
 if ( high > low )
 {
  pivot = partition( arr, low, high );
  quicksort( arr, low, pivot-1 );
  quicksort( arr, pivot+1, high );
 }
 } 
int partition( int arr[], int low, int high )
{
 int left, right;
 int item_pivot;
 int pivot = left = low; 
 item_pivot = arr[low]; 
 right = high;
 while ( left < right ) 
 {
  while( arr[left] <= item_pivot ) 
   left++;
  while( arr[right] > item_pivot) 
   right--;
  if ( left < right ) 
   swap(arr,left,right);
 }
 arr[low] = arr[right];
 arr[right] = item_pivot;
 return right;
}
void printarray(int arr[], int);
int main()
{
 int arr[30], i, n;
 //printf("\nEnter no. of elements: "); 
 scanf("%d", &n);
 //printf("\nEnter the elements: \n");
 for (i=0; i<n; i++)
  scanf ("%d", &arr[i]);
 printf("\nUnsorted array: \n");
 printarray(arr,n);
 quicksort(arr,0,n-1);
 printf("\nSorted array: \n");
 printarray(arr,n);
 }
 void printarray(int arr[], int n)
{
 int i;
 for (i=0; i<n; i++)
  printf(" %d ", arr[i]);
 printf("\n");
}

Run

 

Example

Say we have an array with elements 7,44,2,10,1,35,74,88,5,3,15.Scanning from right to left is done to to find element less than pivot and from left to right is done to find element greater than pivot.

Figure 1

  • The pivot element is the first element i.e 7.
  • Scan from  right to left and find element less than 7.3 is the first element so it is swapped with the pivot element.
  • Scan from left to right and find element greater than 7.44 is the first element encountered so it swapped with 7.
  • Scan from right to left.5 is less than pivot element i.e. 7 so they are swapped.
  • Scan from left to right.10 >7,so it swapped with 7.
  • Scan right-left.1 <7 so they are swapped.
  • Scan from left to right.There is no element in the list before pivot which is greater than pivot itself.Thus list is divided into two sub-lists S1 and S2 such that elements in S1 are less than pivot and elements in S2 are greater than pivot.
Screen Shot 2014-06-16 at 7.19.46 PM

Fig 1 : Example

 

Figure 2

  • S1 has 3,5,2,1  with pivot element 3 and S2 has 35 74 88 10 44 15 with pivot element 35.(Fig 2)
  • Scan right to left in S1 and find element less than 3.1 <3 so they are exchanged.
  • Scan left-right in S1 and find element greater than 3.5>3 so they are swapped.
  • Scan right-left in S1.2<3 so they are swapped and sub-list S1 gets sorted.
Screen Shot 2014-06-16 at 7.21.49 PM

Fig 2 : Sublist S1

 

Figure 3

  • Scan right-left in S2.15<35 ,so they are swapped
  • Left-right -74>35 so they are swapped.
  • Right-left-10<35 so they are swapped.
  • Left-Right – 88 >35 so they are swapped.
Screen Shot 2014-06-16 at 7.23.01 PM

Fig 3 : Sublist S2 

 

Figure 4

  • Partition the sub-list into two further sub-lists S3 and S4.S3 has 15,10 and S4 has 88,44,74 .
  • Scan right-left in S3.10<15 so they are swapped and scanning from left-right does not gives any result.
  • S3 becomes sorted.
Screen Shot 2014-06-16 at 7.23.41 PM

Fig 4 : Sublist S3

 Figure 5

  • Scan right-left in S4.Pivot is 88.74<88 so they are swapped.
  • Scanning left to right is a failed attempt.
Screen Shot 2014-06-16 at 7.25.58 PM

Fig 5 : Sublist S4

Figure 6

  • Partition S4 into S5 and S6.S5 has 74,44 and S6 is empty.
  • Scan right-left in S5.Pivot is 74.44<74 so they are swapped and list becomes sorted.
Screen Shot 2014-06-16 at 7.25.08 PM

Fig 6 : Sublist S5

 

Combine sub-lists to obtain a sorted list.

Screen Shot 2014-06-16 at 7.32.19 PM

Fig 7 : Sorted Array

 


Short URL: http://tinyit.cc/9f8899

Deletion of element from array

Deleting  an  element means to remove element from the array.It is quite easy to delete the element from the end of array.On the controversial side,what is needed to delete the element from our  desired location  like somewhere in the middle of array .Deleting an element requires that all the subsequent elements must be moved one location up to keep the order of array.

The following program is to delete element from the end of array.

Program

#include <stdio.h>

int main()
{
   int arr[10] = {10,20,30,40,50};
   int pos;
   int i;
   printf("Enter the location where you wish to delete element\n");
   scanf("%d", &pos);
   if ( pos > 4 )
      printf("Deletion not possible.\n");
   else
   {
     for ( i = pos  ; i < 4 ; i++ )
     {
     a[i] = a[i + 1];
     }
     printf("Resultant array is\n");
     for( i = 0 ; i < 4 ; i++ )
     {
      printf("%d\t", arr[i]);
      }
   }  

return 0;
}
Run

Illustration of Program

  • Array arr  of  integer type and size 10 is initialized with values 10,20,30,40,50.(Fig 1)
  • pos is the location from where user wants to delete the element.Say user enters 2.
  • The location of elements varies from 0 to 4 as 5 values are initialized.If user enters any location greater than 5,then deletion is not possible since element is not present at that location.
  • Working of for loops is explained in Fig 2.
Fig 1 : Elements of array before deletion.

Fig 1 : Elements of array before deletion.

Fig 2 : Working of for loops

Fig 2 : Working of for loops

Fig 3 :Elements after deletion of 30 at 2 position.

Fig 3 :Elements after deletion of 30 at 2 position.

 

 


Short URL: http://tinyit.cc/94100c

Insertion of element in an array

Inserting an element means to embed element in the array.It is quite easy to insert the element in the end of array provided sufficient memory locations are present to accommodate the additional element.On the controversial side,what is needed to insert the element at our desired location like somewhere in the middle of array .All the elements( after insertion at requisite location) must be moved downwards to welcome new element and to keep their order.By the word downward I mean moving to larger subscripts.

Ways to insert an element in the array

  • In the beginning of array
  • In the end of array
  • At any location of user choice

In the beginning of array

The following program is to insert element in the beginning of array.

Program

#include<stdio.h>

 int main()
 {
 int a[10];
 int i,k;
 int element;
 //printf("enter array elements:");
 for(i=0;i<5;i++)
 {
 scanf("%d",&a[i]);
 }
 //printf("enter the element you want to insert:");
 scanf("%d",&element);
 for(k=5;k>0;k--)
 a[k]=a[k - 1];
 a[0]=element;//Fig 3
  printf("\n");
 for(i=0;i<6;i++)//display the result
 printf("%d \t",a[i]);
return 0;
 }

Run

Illustration of Program

  • Array a of integer type and size 10 is declared.
  • i is set to 0 and condition of for loop is i <5 which means that we can enter up to 5 values in array.The remaining memory locations are to adjust the new elements if user wants to insert at later stage.
  • scanf reads 5 values  from the user .If user gives more than 5 values then those will be simply discarded as loop runs only 5 times.Control exits the loop when i becomes equal to 5. Say user enters 10,20,30,40,50(Fig 1)
  • Say user want to insert 45 in the beginning of array.
  • Working of for loop is explained in the Fig 2.
Screen Shot 2014-03-20 at 3.31.20 PM

Fig 1 : Elements of array before insertion

Screen Shot 2014-03-20 at 3.32.56 PM

Fig 2 : Working of Program.

Screen Shot 2014-03-20 at 3.33.11 PM

Fig 3 : Insertion at the beginning of array.

 

In the end of array

The following program is to insert element in the end of array.

Program

#include<stdio.h>

 int main()
 {
 int a[10];
 int i;
 int element;
 //printf("enter array elements:");
 for(i=0;i<5;i++)
 scanf("%d",&a[i]);
 //printf("enter the element you want to insert:");
 scanf("%d",&element);
 a[5]=element;//Fig 4
 for(i=0;i<6;i++)
 printf(" %d",a[i]);
 return 0;
 }

Run

Illustration of Program

  • Array a of integer type and size 10 is declared.
  • i is set to 0 and condition of for loop is i <5 which means that we can enter up to 5 values in array.The remaining memory locations are to adjust the new elements if user wants to insert at later stage.
  • scanf reads 5  values  from the user .If user gives more than 5 values then those will be simply discarded as loop runs only 5 times.Control exits the loop when i becomes equal to 5. Say user enters 10,20,30,40,50(Fig 3)
  • Say user wants to insert 65 at the end of array.
  • The elements are located till 4 index.
  • In order to insert element at the last,we give value of element to value of  5th index.(a[5] = element).(Fig 4)
  • All the elements are displayed through printf.
Screen Shot 2014-03-20 at 3.31.20 PM

Fig 3: Elements of array before insertion

Fig 4 : Insertion in the end of array

Fig 4 : Insertion at the end of array

 

At any location of user choice

The following program is to insert element at any location.

Program

#include<stdio.h>

 int main()
 {
 int a[6];
 int i,k;
 int element_choice;
 int element;
 //printf("enter array elements:");
 for(i=0;i<5;i++)
 {
  scanf("%d",&a[i]);
 }
 //printf("enter the element:");
 scanf("%d",&element);
 //printf("enter the element after which the number has to be inserted:");
 scanf("%d",&element_choice);
 for(i=0;i<5;i++)
 {
 if(a[i]==element_choice)//finding the element
 break;
 }
 for(k=5;k>i;k--)
{
  a[k]=a[k -1];//shifting the element
}
 a[i+1]=element;
 printf("\n");
 for(i=0;i<6;i++)
{ 
 printf("%d \t",a[i]);
}
 return 0;
 }

Run

Illustration of Program

  • Array a of  integer type  and  size 10 is declared.
  •  is set to 0 and condition of for loop is i <5 which means that we can enter up to 5 values in array.The remaining memory locations are to adjust the new elements if user wants to insert at later stage.
  • scanf reads 5 values  from the user .If user gives more than 5 values then those will be simply discarded as loop runs only 5 times.Control exits the loop when i becomes equal to 5. Say user enters 10,20,30,40,50(Fig 5)
  • Say user wants to insert 90 after 30 in array.(Fig 6)
Screen Shot 2014-03-20 at 3.31.20 PM

Fig 5 : Elements of array before insertion

Screen Shot 2014-03-20 at 4.54.13 PM

Fig 6 :Working of Program

Screen Shot 2014-03-20 at 4.54.22 PM

Fig 7 : Insertion at any location of user choice.

 


Short URL: http://tinyit.cc/4088dc

Linear Search

Searching in an array refers to finding the location of a particular element in the given array. It can be done in two ways :

  • Linear Search
  • Binary Search

Linear Search

Searching

Searching

It is done by comparing each and every element of array with the data item for which index needs to be found.The data item is compared with the items from 0 index till the last element of array.If the match is found then the index where items matched is returned to user.

Program

#include <stdio.h>

int main()
{
	int arr[5];
	int i;
	int element;
        //printf("enter the elements of array");	
	for(i=0;i<5;i++)
	{
		scanf("%d \t",&arr[i]);//Fig 1
	}
	// printf("Enter the element for which you want the search the respective index");
	scanf("%d",&element);
	for(i=0;i<5;i++)
	{
		if(arr[i] == element)

		printf("Location of this element is %d",i);
	}

	return 0;
}

Run

Explanation of above Program

  1. arr[5] is declared as an integer array.
  2. i is a variable to be used in for loop.
  3. element is the data item of int type which needs to be searched in array.
  4. scanf inside for loop is used to read all the values of array from user.Say user enters  100 200 130 140 150(Fig 1)
  5. User enters the element to be searched for in the array.Say 140.
  6. for loop starts and the initial value of i is 0,it will enter the loop as it less than 5(Condition is true).For further explanation refer Fig 2.

Fig 1 : An Array

Fig 3 :

Fig 2 :Explanation of Linear Search Program

TipIf element is present at two or more locations,then the respective indices will be returned to user.


Short URL: http://tinyit.cc/0d4829

Traversing an Array

The various operations that are performed on arrays are :

  • Traversal
  • Searching
  • Insertion
  • Deletion
  • Sorting and Merging

Traversing in array

This article explains about how to traverse in an array.

Traversing means to visit/to go/travel across each and every element of an array.

Program

#include<stdio.h>

int main()
{
 int rank[5] = {10,20,30,13,15};
 int i;
 printf("\nThe elements of array are :");
 for(i=0; i<5; i++)
 {
  printf("%d \t", rank[i]); 
 }
return 0;
}

Run

Illustration

  • Integer type array of size 5 is declared with values 10,20,30,13,15(Fig 2).
  • Variable i of int type is declared which is to be used in for loop.
  • The initial value of i=0,rank[0] which is 10 gets traversed.i is incremented by 1.
  • Now i=1,rank[1] = 20 gets traversed.
  • Now i = 2,rank[2] = 30 gets traversed.
  • i = 3,rank[3] = 13 gets traversed.
  • i=4,rank[4] = 15 gets traversed.
  • All the elements of array get displayed on the screen.
Fig 2 : Traversing an Array

Fig 2 : Traversing an Array


Short URL: http://tinyit.cc/c48dd8

Two Dimensional Arrays

Whether it be playing a tic tac toe game(Fig 3) , storing data in a spreadsheet(Fig 2) or a Rating chart of movie by reviewers(Fig 1), a single dimensional or 1D array cannot store the data. Instead, it needs to be stored in 2 dimensional or multi-dimensional array.

Fig 3 : Tic Tac Toe Game(2D Array)

Fig 3 : Tic Tac Toe Game(2D Array) [1]

Fig 2 : Spreadsheet

Fig 2 : Spreadsheet [2]

Fig 3 : Movie Review Chart

Fig 1 : Movie Review Chart [3]

 

Types of Arrays

  • Single Dimensional Array
  • Two Dimensional Array
  • Multi-Dimensional Array

Two Dimensional Array

In a 2D array,the data is stored in form of a table i.e in form of rows and columns. The data is specified using indices/subscripts(locations of array). The first index refers to row and other refers to column.

Syntax to declare a 2D Array

data_type  array_name[size_row][size_column]; Example: If I want to store marks of 2 subjects 0f 3 different students, I can use a 2D array and will declare according to the following syntax. int marks[2][3]; Illustration

  • Data type of array is int
  • Name of the array is marks.
  • 2 and 3 are the subscripts(indices) of the array. In declaration of 2D array, 2 and 3 here means that the array will have 2 rows and 3 columns respectively.

Consider the example shown in figure 4 that stores data of 3 students in English and Physics in a 2D array.

Fig 4 : A Two Dimensional Array

Fig 4 : A Two Dimensional Array

Here,

  • marks[0][0] – Refers to marks of Jack in English.
  • marks[1][0] – Refers to marks of Joe in English.
  • marks[2][0] – Refers to marks of Ben in English.
  •  marks[0][1] – Refers to marks of Jack in Physics.
  • marks[1][1] – Refers to marks of Joe in Physics.
  • marks[2][1]  – Refers to marks of Ben in Physics

Initialization of 2D Array

data_type   name_array [size_row][size_column] = {values}; Program Example

#include<stdio.h>

int main()
{
int val[2][3] = {10,20,30,40,50,60};//or int val[2][3] = {(10,20,30),(40,50,60)}:
int i,j;
printf("The values of 2D Array are ");
for(i=0;i<2;i++)
{
printf("\n");
for(j=0;j<3;j++)
printf("%d \t",val[i][j]);
}
return 0;
}

Run Illustration

  • val[2][3] is 2D  integer array.
  • Subscripts 2 and 3 indicates that the array would have two rows and three columns.Thus it would store 6 values(2*3).
  • 10,20,30 are the values of row 1 and 40,50,60 are the values of row 2 respectively.
  • for loop has been used to display the values of array.

1. Initial value of i = 0.There are two rows of array so the upper bound of i taken as 2. 2.Nested for loop is used for the columns.Initial value of j is set to 0.There are 3 columns of array so the upper bound of j is taken as 3.

Fig 5 : Explanation of above program

Fig 5 : Explanation of above program

Initialization of 2 D Array through user input:

#include<stdio.h>

int main()
{
   int val[2][3];
   int i,j;
   printf("The values of 2D Array" are);
   for(i=0;i<2;i++)
    {
    for(j=0;j<3;j++)
    scanf("%d",&val[i][j]);
    }
   for(i=0;i<2;i++)
    {
    printf("\n");
    for(j=0;j<3;j++)
    printf("%d \t",val[i][j]);
    }
return 0;
}

Run This program has the same working like previous program except that the values are initialized from user through scanf. Two for loops are used separately for scanf function in order to take all the values from the user  first and then all the values are printed through printf function which is placed in another two for loops. If we will use scanf and prinf in the same for loops then output will be generated one by one as  the input is given to the system.


Short URL: http://tinyit.cc/480b99
By Cusp2207 on March 18, 2014 | Computer Science, Data Structures | A comment?
Tags:

Introduction to Arrays

Fig 1 : Table

Well, we all know what a multiplication table does(Fig 1). We pick any number and multiply with Series from 1-10,and hence we get the resultant series. For example If we want to store this result sequence 5 10 15 20 in computer memory using any programming language, what would we do?

To store this or any sequence in the programming world I can use Arrays as my data structure.Array is storehouse/collection of similar data items. By Data Items I mean the entries or the actual data, which needs to be stored. In this case 5 10 15 20 are the data items.
To store items in an array, they must be of same Data Type(Fig 2). If an array stores integer values all the items must be of integer type. Any other data type like float or char is not to be used with integer data type and the case hold for vice-versa also.

Fig 2 : An integer array

The elements of array are stored in consecutive memory locations called as  Index.

Declaration of an Array

Specify three things in order to declare an array:

  1. Data type: – Example: int , char, float
  2. Name of array
  3. Size: – Maximum no of values that array can store.

Examples:

int marks [5];  //(Fig 3)
float  percnt[5];
char grades[5];

In the first example:

1. Data Type of Array is int, which means it is meant to store integer values.

2. Name of array is marks.

3.The maximum no of values that can be stored in this array is 5.

Screen Shot 2014-03-15 at 3.15.31 PM

Fig 3 : An integer array

Store values in an array

  • Initialization

    The values of array are directly initialized/given by the user at the time of program creation.

int marks[5] = {20,40,50,10,30}; //(Fig 4)

Fig 4 : Initialized Integer Array

float percnt[5] = {95.2,45.5,20.0,30.6,67.9}; //Fig 5
Fig 6 : Initialized float array

Fig 5 : Initialized float array

char grades[5] = {a,d,c,a,b}; //Fig 6
Screen Shot 2014-03-15 at 3.31.04 PM

Fig 6 : Initialized character array

 

  • Input the values

    The user enters the values of array at run time. It is done through the concept of loops.

Example

In C language:

/* visit http://letslearncs.com for complete Computer Science tutorials*/ 
#include <stdio.h>

void main(){
    int   i ;
    int  rollno[5] ;
    for(i=0;i<5;i++)
    {
    	printf("%s","Please enter a number: ");
        scanf("%d",&rollno[i]);
        printf("\nYou entered: %d\n", rollno[i]);
    }
}

Run

1. Variable i is declared of integer type to use in loop.

2. Array rollno is declared to store roll numbers of 5 students as the size specified is 5. Since rollno is an integer value, we took int as the data type.

3. The For loop is used to read five values from the user at run time using the standard scanf function of stdio.h library.

Functionality

Initial value of i =0 which is less than 5 (the upper bound of the array rollno). Thus the for loop condition is true and it will enter the loop.

Now, rollno[i] is rollno[0]. Say user enters 25.So when i=0, the array would like as shown in fig 7.

Fig 8 :  i=0

Fig 7 : i=0

Value of i is incremented to 1. Now when the value of  i=1 which is still less than 5. Now, say user enters 30. The array would like as shown in fig 8.

Fig 9: i=1

Fig 8 : i=1

The same process goes till the value of i  becomes 5 and the condition becomes false (remember: we start the loop from 0 not 1). So it wont enter the loop and will thus stop reading the next value from user.

Calculating the Memory Address of array’s elements

The address of data item can be found by formula:

A[k] = BA(A) + w(k - lower bound)
Here,

  • A is an array
  • k is the index of data item for which we need to find address. By address I mean the location of data item in computer memory (Note :address and index are two different things in arrays).
  • BA is the base address of array A.
  • w is the word size of one element in memory. For e.g. size of int is 2,float is 4 and char is 1 byte.
  • Lower bound is starting index of an array.

Consider an array(Fig 9), which stores percentage of 4 students.

Screen Shot 2014-03-15 at 3.45.53 PM

Fig 9

Let the BA of percnt array be 2000 and w is 4 of type float.

TipUse int BA = &percnt to calculate the actual base address in C.

If we need to find memory location of the value 30.6 which is at index 3 then we can use the following formula :
A[k] = BA(A) + w( k - lower bound)
percnt[3] = 2000 + 4(3 - 0)
=2000 + 12
= 2012


Short URL: http://tinyit.cc/ce4fe9
By Cusp2207 on March 15, 2014 | Computer Science, Data Structures | A comment?
Tags: