Data Structures
ARRAYS
1. An array is a type of linear data structure that is defined as a collection of elements
with same data types.
All the data items of an array are stored in consecutive memory locations.
The data items of an array are of same type and each data items can be
accessed usingthe same name but different index value.
4. They exist in both single dimension and multiple dimensions.
An array is a set of pairs, <index, value >, such that each index has a value
associatedwith it.
Ex: <index, value>
< 0 , 25 > list[0]=25
< 1 , 15 > list[1]=15
< 2 , 20 > list[2]=20
< 3 , 17 > list[3]=17
< 4 , 35 > list[4]=35
Here, list is the name of array. By using, list [0] to list [4] the data items in list
can beaccessed.
Implementation:
When the complier encounters an array declaration, list[5], it allocates five
consecutivememory locations. Each memory is enough large to hold a single
integer.
The address of first element of an array is called Base Address. Ex: For
list[5] theaddress of list[0] is called the base address.
If the memory address of list[i] need to compute by the compiler, then the size of
the
int would get by sizeof (int), then memory address of list[i] is as follows:
list[i] = α + i * sizeof (int)
Where, α is base address.
Mr. Dhanraj Suresh Kiwde Page 1
Data Structures
Representation of Linear Arrays in Memory
1. Arrays are represented as a collection of buckets where each bucket stores
one element.
2. These buckets are indexed from '0' to 'n-1', where n is the size of that
particular array.
3. For example, an array with size 10 will have buckets indexed from 0 to 9.
4. This indexing will be similar for the multidimensional arrays as well.
5. If it is a 2-dimensional array, it will have sub-buckets in each bucket.
6. It will be indexed as array_name[m][n], where m and n are the sizes of each
level in the array.
As per the above illustration, following are the important points to be
considered.
Index starts with 0.
Array length is 9 which mean it can store 9 elements.
Each element can be accessed via its index.
For example, we can fetch an element at index 6 as 23.
Operations on Linear Arrays:
1. The basic operations in the Arrays are insertion, deletion, searching, display,
traverse, and update.
2. These operations are usually performed to either modify the data in the array
or to report the status of the array.
Mr. Dhanraj Suresh Kiwde Page 2
Data Structures
Following are the basic operations supported by an array.
Traverse − print all the array elements one by one.
Insertion − Adds an element at the given index.
Deletion − Deletes an element at the given index.
Search − Searches an element using the given index or by the value.
Update − Updates an element at the given index.
Display − Displays the contents of the array.
Traversing linear array
Array is a container which can hold a fix number of items and these
items should be of the same type.
Traverse − print all the array elements one by one.
Or process the each element one by one.
Let LA be a collection of data elements stored in the memory of the
computer.
Suppose we want to print the content of each element of LA or suppose we
want to count the number of elements of LA with given property.
This can be accomplished by traversing LA, that is, by accessing and
processing (frequently called visiting) each element of an exactly once.
Algorithm
Step 1 : [Initialization] Set K : = LB
Step 2 : Repeat Step 3 and Step 4 while K < = UB
step 3 : [ processing ] Process the LA[K] element
Step 4 : [ Increment the counter ] K := K + 1
[ End of the loop of step 2 ]
Step 5: Exit .
(Here LB is lower Bound and UB is Upper Bound LA [ ] is linear array)
// Program to take 5 values from the user and store them in an array
// Print the elements stored in the array
Mr. Dhanraj Suresh Kiwde Page 3
Data Structures
#include <stdio.h>
void main() {
int values[5];
printf("Enter 5 integers: ");
// taking input and storing it in an array
for(int i = 0; i <= 4; i++) {
scanf("%d", &values[i]);
}
printf("Displaying integers: ");
// printing elements of the array
for(int i = 0; i <= 4; i++) {
printf("%d\n", values[i]);
}
getch();
}
Output
Enter 5 integers: 1
-3
34
0
3
Displaying integers: 1
-3
34
0
3
Here, we have used a for loop to take five inputs and store them in an array.
Then, these elements are printed using another for loop.
Mr. Dhanraj Suresh Kiwde Page 4