Arrays in C Language

Suppose you want to store the 10 numbers. The one choice is to create a 10 different variable but it is difficult when number of variable are increases. So the next solution that is more feasible is array.

An array is the collection of various similar type elements stored in contiguous memory locations. All the array elements share the common name. To uniquely identify each element an index or subscript is associated with the element. so the array is also known as subscript variable.
memory map of array

In the given figure arrangement of array elements are shown. The address of the first element is 100. If the given array is of type integer and integer occupies 2 bytes then the next element in the array has address 102,104 etc as given in the figure. How to access array elements using subscript operator it is also shown in the given figure.

Array index always start with 0. To access array element subscript operator is used.[] is called subscript operator.a[0] read a of 0 or 0th element of a

Creating/Declaring an Array variable

Just like other variable,in C array should be declared before it is used.

int arr[20];
In the above program snippet int is a data type, arr is array name and 20 is array size. Remember one thing that in c array size must be constant otherwise, it is compiled time error.

Initialization of an array

int arr[5];//all the array elements are initialize with garbage by default.
int arr[5]={10,20,30,40,50};//|10|20|30|40|50| Array elements are initialized as given.
int arr[5]={10,20};//|10|20|0|0|0| If array is partially initialized then rest will initialized with 0(zero).
int arr[3]={10,20,30,40,50};//compile time error, too many arguments
int arr[]={10,20,30}; //while initializing array, size is optional,size is automatically adopted as number of elements.
static int arr[5];//all elements are initialized with 0 because static variable have default value 0.

Accessing an array elements

int arr[]={10,20,30,40,50};
for(i=0;i<5;i++){
	printf("%d ",arr[i]);
}
//output: 10 20 30 40 50

Input array element

int arr[20];
printf("Enter how many element you want to enter: ");
scanf("%d",&n);
        
for(i=0;i < n;i++){
	printf("Enter element %d: ",i+1);
        scanf("%d",&arr[i]);
}

Trace the above program snippet yourself and try to find the logic behind it.

Program: To print all those elements above than average of array elements

#include<stdio.h>
int main() {
 	int arr[20];
 	int i,n,sum;
 	float avg;
 
 	printf("Enter how many elements: ");
 	scanf("%d",&n);
 	
 	/*array Input*/
 	sum=0;
 	for(i=0;iavg)
			printf("%-4d",arr[i]);	
 		}
 	return 0;
}

Output

Enter how many elements: 5
Enter element 1: 2
Enter element 2: 9
Enter element 3: 6
Enter element 4: 18
Enter element 5: 3
Elements above than avg...
9   18

Program: To demonstrate the bound checking failure.

#include<stdio.h>
int main() {
	int arr[5],i;
	for(i=0;i<10;i++) {
		printf("Enter element %d: ",i+1);
 		scanf("%d",&arr[i]);
 	}
 	printf("Array elements are...\n");
 	for(i=0;i<10;i++){
 		printf("%d ",arr[i]);
 	}
 	return 0;	
}

Output

Enter element 1: 2
Enter element 2: 1
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
Enter element 6: 6
Enter element 7: 7
Enter element 8: 8
Enter element 9: 6
Enter element 10: 4
Array elements are...
2 1 3 4 5 6 7 8 6 4

Program Description

As shown in the above program the array arr is created of 5 elements but while performing input/output 10 elements are entered and gets printed. Actually, this should be an error. But the compiler is not aware of it so it is not a compile-time error. On the run time, the program can be terminated due to some problem because when program access the illegal memory space the OS sends a signal to terminate the program.

So in c/c++ compiler doesn't check array boundary and if the boundary is crossed then it won't be a compile-time error.

Array and pointer

Array and pointer have close relationship.Lets take an example to discuss it.

Program: To demonstrate the relation of array and pointer

#include<stdio.h>
int main() {
	int arr[]={10,20,30,40,50};
	printf("%d ",arr[0]);
 	printf("%d ",0[arr]);
 	printf("%d ",*(arr+0));
 	printf("%d ",*(0+arr));
 	return 0;	
} 

Output

10 10 10 10

Program Description

  1. As shown in the above program that arr[0],0[arr],*(arr+0),*(0+arr) all prints the same output. Actually arr[i] is equivalent to *(arr+i) (value at ith element of arr) or *(i+arr) or i[arr](ith element or arr).
  2. Actually the name of the array represents the base address (address of the first element). why so happens? and why not we use the & address of operator for the address of an array? The answer is related to the above discussion we have recently done.
  3. arr[i] is equivalent to *(arr+i). So arr[0] is equivalent to *(arr+0) or *arr. *(arr+0) or *arr gives the base value(first element) of the array. We have already read that if we dereference a pointer then it gives the value of the variable which addresses it holds. So in reverse, we can say that *arr gives the base value then arr have the base address. But how to use this fact. This is shown in the example discussed in a few minutes.

Program: To demonstrate the relation of array and pointer and pointer arithmetic

#include<stdio.h>
int main() {
	int arr[]={10,20,30,40,50};
 	int *p;
 	
 	p=arr;/*copy the base address of array into pointer p*/
 	printf("%d ",arr[0]);
	printf("%d ",*arr);
 	printf("%d ",*p);
	printf("%d ",p[0]);
 
	p++;/*pointer increment, move to the next element*/
 
	printf("%d ",*p);
 	printf("%d ",p[0]);
 	printf("%d ",p[1]);
 	printf("%d ",*(arr+1));
 	
 	p--;
 	
 	printf("%d ",*p);
 
	p+=2;
 
	printf("%d ",*p);
	printf("%d ",*(p+1));
 	printf("%d ",*p);	
 	
 	//arr++; error
 	
 	return 0;	
}

Output

10 10 10 10 20 20 30 20 10 30 40 30

Program Description

  1. In the above-given program, in line 6 the address of array arr is saved into a pointer p by using statement p=arr because p point to integer array, so p should be declared as integer pointer as in line 4.
  2. In line 7, arr[0] gets printed and the result is 10, the first element(0th index element) of the array. In line 8, *arr gets printed and the result is 10 because arr is the base address of array so *arr is the value at the base address of the array that is 10.
  3. In line 9, *p gets printed and the result is 10 because p holds the base address of array so *p is the value at the base address of the array that is 10.
  4. In line 10, p[0] gets printed and the result is 10 because p[0] means *(p+0) equivalent to *p that means value at the base address of the array that is 10.
  5. In line 12, p++ increments the pointer. Whenever a pointer gets incremented the pointer moves to the next element in the array. That means if the array is an integer type then pointer moves 2 bytes if integer occupies 2 bytes. if an array is of float type the pointer move 4 bytes to point the next element and same for char array pointer move 1 byte to point the next element. so in the above program p moves to the next element, means the second element of the array. and in line 14 *p gets printed and print 20.
    In the pointer arithmetic, if pointer gets incremented, increase by an element not by value as a simple variable. The same rule applied for decrements also.
  6. In line 17 p[0] gets printed,p[0] means *(p+0) equivalent to *p, Because in line 14 p already incremented and point the second element so output *p is 20. same as in line 21 p[1] gets printed that is 30 because p[1]means 1 element next to the current address in p.but in 22 *(arr+1) gets printed that is 20 because arr still holds the base address of the array and arr+1 means 1 element next to arr.
    Remember one thing, that if pointer points the base address of the array, then it is the same as an array and accesses the array element same as an array. if arr is an array p is a pointer holds the base address of arr then arr[0],arr[1],arr[2] are the array elements whereas p[0],p[1],p[2] are also the same elements. But if array gets incremented it doesn't point the base address and now array and pointer are different because p[1] means 1 element next to the current address in p.
  7. same as ++/-- operator the +/- ,+=/-= operator can be used to perform the arithmetic on pointer. In line 23 p gets incremented by 2 moves the pointer 2 elements next to the current address in p. Till the execution on line 23, p is on the base address of the array. so now p moves to the 3rd element of the array and gets printed in line 25 and print 30. In the next line, p+1 means the next element to the current address of p and gets printed so the output is 40. but this doesn't *(p+1) only print the next element to the current address of p but never change the address stored in p so in the next line *p prints 30.
  8. The last concept is, in line 29 arr++ try to increment the array but it is compiled time array. because the array is just like a constant pointer and change its address once it is created.

Passing an array into a function

To pass a array into a function we need to pass two things. one is the base address of array and second is the size of array as given in the example below.

Program: To demonstrate how to pass array into function

#include<stdio.h>
void prn(int arr[],int n) {
	int i;
	for(i=0;i < n;i++)
		printf("%d ",arr[i]);
}
 
int main() {
 	int arr[]={10,20,30,40,50};
 	prn(arr,5);
 	return 0;	
}

Output

10 20 30 40 50

Program Description

In the above program to print the array using a function, a function prn is created which receive the base address of the array and the size of the array into n.

From main() function prn() is called with array base address and size of array. Array base address can be received by an array because an array is also a pointer. so in the function definition array receive the base address of the array. one more way to create the function as given in the following program snippet.

void prn(int *p,int n)
{
	int i;
	for(i=0;i < n;i++){
    	       printf("%d ",*(p+i));
        }
}  

Searching

Searching means to an element in a collection. It is very critical and most usable problem in computer science.Every person perform searching when he type some initial to search the name in the phone contacts.

Here we discuss about two types of searching

  1. Linear Search
  2. Binary Search

Linear search

In the linear search problem an array is given and an item is given. you have to find the item in the given array. if found then return the index position otherwise indicate that item not found.

The concept behind the linear search process is that match the item with each element starting from the first element if found then return the index position and stop the searching. If item not found till the end of the array then return -1 indicating that item not found. -1 indicated not found because -1 is not an index position in the array. The program snippet given below clarifies the concept. Read the given program carefully and try to understand the concept.

for(i=0;i < n;i++){
    	if(item == arr[i]){
        	printf("Item found at position %d.",i+1);
            break;
        }
    }
    if(i == n)
        printf("Item not found");

In the above program snippet, the control can jump out of the loop by one of the two reasons. one is that item is found and the position of the item gets printed. Observer carefully that i+1 gets printed when the item is found not i because a user doesn't know that array index starts from 0. if the item is found then loop doesn't get completed and i will be less then n so "item not found doesn't get printed.". But if item not found, then loop gets completed and i cross its limit and loops becomes false so at last, i becomes equal to the \n and the message outside the loop "Item not found" gets printed.

One more way to perform this task is given in the following program snippet. The difference is that we have a flag variable, that can be true or false. if item found then it will be true otherwise remains false. Flag variable is a variable which represents some states such as true or false. it one value is considered others is given by program.

found=0;
for(i=0;i < n;i++){
	if(item == arr[i]){
    	found=1;
        break;
    }
}
if(found==1)
	printf("Item found at position %d",i+1);
else
	printf("Item not found");

As given in the above program snippet that a flag variable found is used. if item is found then found=1 and we already assume that found=0 means item not found. Now it is easy to identify that loop gets completed or terminated in half of its execution, for this purpose check the value of found variable. The complete program with function is given below for better understanding.

Program: To demonstrate the linear search

#include<stdio.h>
int linear_search(int arr[],int n,int item) {
	int i;
 	for(i=0;i < n;i++){
 		if(arr[i]==item)
			return i;
		}
	return -1;	
}
int main() {
 	int arr[20],n,i,pos,item;	
 	/*array input*/
 	printf("Enter how many elements: ");
 	scanf("%d",&n);
 
	for(i=0;i < n;i++) {
 		printf("Enter element %d: ",i+1);
 		scanf("%d",&arr[i]);
 	}	
 	printf("Enter the item to search: ");
 	scanf("%d",&item);
 	
 	/*linear search*/
 	
	pos=linear_search(arr,n,item);
 	if(pos!=0)
 		printf("Item found at position %d.",pos+1);
 	else
 		printf("Item not found.");	
 	
 	return 0;
}

Outputs

Enter how many elements: 5
Enter element 1: 10
Enter element 2: 20
Enter element 3: 30
Enter element 4: 40
Enter element 5: 50
Enter the item to search: 30
Item found at position 3.

Program Description

In the above-given program the minimum possible compare is 1 if item found at first position and maximum possible compare are n(size of the array) if item either found at last or not found. So this is not good logic if the array is too large. This logic can work on any sorted or unsorted array.

Program: To demonstrate the binary search

#include<stdio.h>
int binary_search(int arr[],int n,int item) {
	int low,high,mid;
 	low=0;
	high=n-1;
 	while(low <= high) {
 		mid = (low + high) / 2;
 		if(item == arr[mid])
 			return mid;
		else if(item>arr[mid])
 			low=mid+1;
 		else
 			high=mid-1;
 	}	
 	return -1;
}
 
int main() {
 	int n,i,arr[20],item,pos;	
 
	printf("Enter how many elements in array: ");
 	scanf("%d",&n);
 	/*input array*/
 	for(i=0;i < n;i++) {
 		printf("Enter element %d: ",i+1);
 		scanf("%d",&arr[i]);	
 	}
 
	printf("Enter the item to search: ");
	scanf("%d",&item);
 	
 	pos = binary_search(arr,n,item);
 
	if(pos!=-1)
		printf("Item found at position %d.",pos+1);
	else
		printf("Item not found.");
 	
 	return 0;	
}

Output

Enter how many elements in array: 5
Enter element 1: 10
Enter element 2: 20
Enter element 3: 30
Enter element 4: 40
Enter element 5: 50
Enter the item to search: 30
Item found at position 3.

Enter how many elements in array: 5
Enter element 1: 10
Enter element 2: 20
Enter element 3: 30
Enter element 4: 40
Enter element 5: 50
Enter the item to search: 25
Item not found.

Program Description

binary search

Every array is a bounded structure which has its boundary, lower bound and upper bound so, the statement low = 0 put the variable low at lower bound and same high = n - 1 put the variable at upper bound.

Now the statement mid = (low + high) / 2 finds the middle position of array and then check item == arr[mid] test whether item is found at mid, if found then return the mid position and if not found then condition item > arr[mid] check whether item is greater then the middle, if yes the next time we want to continue searching with the upper part of array so set the low = mid + 1 and continue the searching and same if item is less than the mid then we want to continue the searching with the lower part of array so set high = mid - 1 and continue the searching.

The given diagram will help to understand the concept.

Comments

Popular posts from this blog

Overview of Go lang

String in golang

Data Types in Go language

Installing go lang

Creating your first html page

Say Hello world in Go lang

Arrays in Go lang

Program to calculate telephone bill

Decision Making in Go lang