Array (1-D)
We will explain the concept of arrays using an analogy. Consider a situation in which we have 20 students in a class and we have been asked to write a program that reads and prints the marks of all the 20 students. In this program, we will need 20 integer variables with different names.
Now to read the values of these 20 variables, we must have 20 read statements. Similarly, to print the value of these variables, we need 20 write statements. If it is just a matter of 20 variables, then it might be acceptable for the user to follow this approach. But would it be possible to follow this approach if we have to read and print the marks of students of entire college or entire university then answer is no, definitely not! we need a data structure
known as array.
We need a data structure known as array. These data elements have the same data type. The elements of the array are stored in consecutive memory locations and are referenced by an index (also known as the subscript). The subscript is an ordinal number which is used to identify an element of the array.
Declaration Of Array
Every variable must be declared before it is used. The same concept holds true for arrays. An array must be declared before being used. Declaring an array
means specifying the following:
1) Data type — the kind of values it can store, for example, int , char , float , double .
2) Name — to identify the array.
3) Size — the maximum number of values that the array can hold.
Syntax: int marks[10];
In most of Programming language array index starts from 0. The first element will be stored in marks[0]. second element in marks[1] , and so on. Therefore, the last element, that is the 10th element, will be stored in marks[9]. Note that 0, 1, 2, 3 written within square brackets are the subscripts.
Storing related data items in a single array enables the programmers to develop concise and efficient programs. But there is no single function that can operate on all the elements of an array. To access all the elements, we must use a loop. That is, we can access all the elements of an array by varying the value of the subscript into the array. But note that the subscript must be an integral value or an expression that evaluates to an integral value.
Example:
//sum of an array
int i, marks[10], sum=0;
for(i= ;i<1 ;i++)
sum+=marks[i];
Calculating the Address of Array Elements
You must be wondering how C gets to know where an individual element of an array is located in the memory. The answer is that the array name is a symbolic reference to the address of the first byte of the array. When we use the array name, we are actually referring to the first byte of the array. When we use the array name, we are actually referring to the first byte of the array.
The subscript or the index represents the offset from the beginning of the array to the element being referenced. That is, with just the array name and the index, C can calculate the address of any element in the array.
Since an array stores all its data elements in consecutive memory locations, storing just the base address, that is the address of the first element in the array, is sufficient. The address of other data elements can simply be calculated using the base address. The formula to perform this calculation is
Address of data element, A[k] = BA(A) + w(k-lower_bound)
where BA(A) = Base Address of A, w is the size of one element in memory,
k is the index of the element of which we have to calculate the address.
Example:
Given an array int marks[] = {99,67,78,56,88,90,34,85} , calculate the address of marks[4] if the base address = 1000.
We know that storing an integer value requires 2 bytes,
marks[4] = 1000 + 2(4–0)
= 1000 + 2(4) = 1008
OPERATIONS ON ARRAYS
There are a number of operations that can be preformed on arrays. These operations include:
1) Traversing an array
2) Inserting an element in an array
3) Searching an element in an array
4) Deleting an element from an array
5) Merging two arrays
6) Sorting an array in ascending or descending order
1) Traversing an Array
Traversing an array means accessing each and every element of the array for a specific purpose. Traversing the data elements of an array A can include printing every element, counting the total number of elements, or performing any process on these elements. Since, array is a linear data structure (because all its elements form a sequence), traversing its elements is very simple and straightforward.
2) Inserting an Element in an Array
If an element has to be inserted at the end of an existing array, then the task of insertion is quite simple. We just have to add 1 to the upper_bound and assign the value. Here, we assume that existing array the memory space allocated for the array is still available.
Algorithm to Insert an Element in the Middle of an Array
The algorithm INSERT will be declared as INSERT (A, N, POS, VAL) . The arguments are
(a) A , the array in which the element has to be inserted
(b) N , the number of elements in the array
(c) POS , the position at which the element has to be inserted
(d) VAL , the value that has to be inserted
3) Searching an element in an array
For Searching an element in array we have two approaches
1) Linear Search (Sequential Search)
2) Binary Search
4) Deleting an Element from an Array
Deleting an element from an array means removing a data element from an already existing array. If the element has to be deleted from the end of the existing array, then the task of deletion is quite simple. We just have to subtract 1 from the upper_bound . Figure 3.15 shows an algorithm to delete
an element from the end of an array.
Algorithm to delete an element from the middle of an array
The algorithm DELETE will be declared as DELETE(A, N, POS). The arguments are:
(a) The array from which the element has to be deleted.
(b) N , the number of elements in the array.
(c) POS , the position from which the element has to be deleted.
5) Merging two arrays
Merging two arrays in a third array means first copying the contents of the first array into the third array and then copying the contents of the second array into the third array. Hence, the merged array contains the contents of the first array followed by the contents of the second array.
If the arrays are unsorted, then merging the arrays is very simple, as one just needs to copy the contents of one array into another. But merging is not a trivial task when the two arrays are sorted and the merged array also needs to be sorted. Let us first discuss the merge operation on unsorted arrays.
When two array are sorted and merged array also needs to be sorted then we need to check that which element is small and increment its pointer.
Step 1 : i=0, j=0, k = 0, a[n1], b[n2], c[n1 + n2]
Step 2 : Repeat step 3 and step 4 while k < n1 + n2
Step 3: if a[i]<b[j] then c[k] = a[i]; i++; k++;
Step 4 : else c[k] = b[j] then c[k] = b[j]; j++; k++;
Here, i is used for indexing array a, j is used for indexing b and k is used for indexing array c. Now we want to merge array a and array b of size n1 and n2 respectively. At a time of assigning, we will check and smaller value will be assigned to array c and pointer of c and array from value is copied both ill be incremented.
Conclusion
Array is the simplest linear data structure and used in many problems and we can also pass array as an argument.
We can also create array of more than 1 dimension. That is topic for my next blog. I hope you enjoyed and learnt something from this blog.
