Disclaimer: Some part of the notes here are used verbatim from the book "Fundamentals Of Data Structures in C" by Ellis Horowitz, Sartaj Sahni, and Susan Anderson-Freed.
Ordered Lists
Having data artifacts/objects in some pre-defined order is commonplace. For example
A list of such data artifacts can rightly be called linear list due to its ordering.
To better understand any concept that has a multitude of applications, it is better first expressed in an abstract manner. Thus, we will express a linear list using the following notation:
L = (l1, l2, l3, l4 .... ln), where li is an element in the set L.
There are a variety of operations that are performed on these lists. These operations include:
Arrays
The main memory is organized for access and storage in either row-major or column-major order. This ordering provides for sequential mapping of addresses, i.e. addresses have a numeric order. From a programmer's perspective, numerically-ordered addresses are located next to each other.
It is often that programmers will require to store collection of data items of the same type together, i.e. in a contiguous manner. The structuring/organizing of data elements, which is of the same type, in contiguous memory is called an Array.
In the figure above, it can be seen that the character Q is stored at address 0x100 (hexadecimal) and W E R T and Y are stored contiguously, i.e. they have sequential or linear addressing.
In 'C' programming, an Array is identified using its starting address, data tye and size; all elements in an array must of the same data type. Each individual element can be accessed using an index, where the starting index is ZERO. The code snippet below makes the access of values in an array amply clear.
Image source: The C Programming Language by Kernighan and Ritchie
In the image above, pa is a pointer variable that is initialized with the starting address of array a
int main(){
/*Two ways to initialize array*/
int intArr[10] = {0}; /*initialize all elements to ZERO*/
double doubleArr[10] = {0}; /*initialize all elements to ZERO*/
/*initialize array with multiple values*/
int intArrInitialized[10] = {1,2,3,4,5,6,7,8,9,10};
/*Rewrite values in an array using for loop*/
for(unsigned short idx = 0; idx < 10; idx++){
intArr[idx] = 5 * idx;
doubleArr[idx] = -2.0 * idx;
}
/*print values in an array using for loop*/
for(unsigned short idx = 0; idx < 10; idx++){
printf("intArr[%d] = %d, doubleArr[%d] = %f, intArrInitialized[%d] = %d\n\n",\
idx, intArr[idx], idx, doubleArr[idx], idx, intArrInitialized[idx]);
}
/*print address of elements in array using for loop*/
for(unsigned short idx = 0; idx < 9; idx++){
printf("&intArr[%d] = %p, &doubleArr[%d] = %p,\n\
Bytes between indices for intArr = %u,\n\
Bytes between indices for doubleArr = %u\n\n",\
idx, &intArr[idx], idx, &doubleArr[idx],\
(unsigned int)&intArr[idx + 1] - (unsigned int)&intArr[idx],\
(unsigned int)&doubleArr[idx + 1] - (unsigned int)&doubleArr[idx]);
}
/*Strings in C are created as char array*/
/*There are two ways to initialze char arrays for processing as strings*/
char charArr[6] = {'H','e','l','l','o','\0'};
char string[] = "World"; /**/
printf("Message: %s, %s\n", charArr, string);
}
The numerical order of the indices are mathematically related with the set of addresses that form an array. Accessing the value at a given index equals to calculating the corresponding address by adding the index value to the starting address of the array. For example, the value 'E' can be accessed directly using the operation arr[2], which is enabled by adding 2 to 0x100 - the starting address.
Since working with arrays is essentianlly managing access using addresses, pointers can also be used to access arrays. The code snippet below will make it amply clear.
int main(){
int intArr[5] = {34, 25, 7, -8, 45};
double doubleArr[5] = {2.6, -9.7, 4, 56, 34.2};
/*get the starting address of array using pointers*/
int *ptrArrInt = intArr;
double *ptrArrDouble = doubleArr;
/*print values in an array using pointer arithmetic*/
for(unsigned short idx = 0; idx < 5; idx++){
printf("intArr[%d] = %d\n", idx, *(ptrArrInt + idx));
printf("doubleArr[%d] = %f\n", idx, *(ptrArrDouble + idx));
}
/*Rewrite values in an array
Access next element in an array using increment operator on pointers*/
for(unsigned short idx = 0; idx < 5; idx++){
*intArr = *intArr * -1;
*doubleArr = *doubleArr * -1;
++ptrArrInt; /*point to the next address in the array*/
++ptrArrDouble;
}
/*reinitialize the pointers to address of second element in the array*/
ptrArrInt = intArr + 1;
ptrArrDouble = doubleArr + 1;
/*to point to third element in the array, simply do
ptrArrInt = intArr + 2;
ptrArrDouble = doubleArr + 2;
*/
/*print values in an array using for loop*/
for(unsigned short idx = 0; idx < 4; idx++){
printf("intArr[%d] = %d\n", idx, *ptrArrInt);
printf("doubleArr[%d] = %f\n", idx, *ptrArrDouble);
++ptrArrInt;
++ptrArrDouble;
}
}