IMPLEMENTING ARRAY AS AN ABSTRACT DATA TYPE (ADT):-
In this post we will see how to implement arrays as abstract data type.
Let’s say
we name out abstract data type as “NewArray” to store integer data types.
Which will
have properties like:-
- int totalSize
- int usedSize
- int *ptr
we will
also have some set of operations which we could perform with our ADT NewArray
like:-
- showIndex() : to display all the elements of the array
- setValue() : to set a value at the end
- insertAtIndex() : to insert a value at at index
- deleteAtIndex() : to delete a value at an index
now we will implement this step by using structures in C language:-
// structure for array ADT:
struct NewArray
{
// properties
int totalSize; // to store total size (max size) of the array
int usedSize; // to store the used size of the array
int *ptr; // pointer for dynamic memory allocation of array
};
Now lets define a function to create an array and initialize values for its total size
and used size.
/* function to create array which sets values of
total size, used size, and dynamically allocates memory of ptr */
void createArray(struct NewArray *array, int total)
{
array->totalSize = total;
array->usedSize = 0; // used size will be zero whlile creation as array is empty
array->ptr = (int *)malloc(total * sizeof(int));
}
This function is created so that we can set values of total size used size and dynamically
allocate memory of size total size * size of integer data type. This is done
using malloc function.
Calling the above function:-
createArray(&arr, val);
here we have passed the address of arr, total size = val1
where val is taken from user like this:-
where val is taken from user like this:-
printf("Enter total size in integer : ");
int val;
scanf("%d", &val);
Now lets create a function that can set value at the end.
// to set value at the end
int setValue(struct NewArray *array, int value)
{
// check if array is full or not
// if not full the continue with adding value
// else display msg and exit by returning 0
if (array->usedSize < array->totalSize)
{
array->ptr[array->usedSize] = value;
array->usedSize++;
return 1;
}
else
{
printf("\n!!! Array is full cannot add value\n");
return 0;
}
}
Here we have made a function of int type which has structure of array and an integer value as the parameters:-
We would first check whether array is not full upto its max size to add more elements , if its full we will give a message and return 0.
Else if it has some space or if its empty then we will continue setting “value” at the last position of the array whch is the usedSize.
Next we will create a function that can insert value any index specified by user starting from 0 upto the used index.
But before that we will have to make function which will check if the index given by user is within the range of
0 and the used size of the array lets name the function inRange()
// func to check if index is within correct range
int inRange(struct NewArray *array, int index)
{
if (index >= 0 && index <= array->usedSize)
{
return 1;
}
else
{
return 0;
}
}
Now continuing with our insertAtIndex() function:-
// to insert value at an index
int insertAtIndex(struct NewArray *array, int value, int index)
{
// check if array is full or not
// if not full the continue with adding value
// else display msg and exit by returning 0
if (inRange(array, index))
{
if (array->usedSize < array->totalSize) // to check if array is not full
{
for (int i = array->usedSize - 1; i >= index; i--)
{
array->ptr[i + 1] = array->ptr[i];
}
array->usedSize++;
array->ptr[index] = value;
return 1;
}
else
{
printf("\n!!! Array is full cannot add value\n");
return 0;
}
return 1;
}
else
{
printf("\n!!! Index %d is out of valid range 0 to %d\n", index, array->usedSize);
return 0;
}
}
Here we have first checked if index is within the allowed range if not then simply return 0, if we are in proper range then first we need to create space for the insertion, so we shift the elements to the right using that for loop, we then increment the used size ad the size has been increased now.
Then we add the value at out desired index and we are done.
We will now make a function to delete at an index.
// to delete value at an index
int deleteAtIndex(struct NewArray *array, int index)
{
if (inRange(array, index))
{
// to delete element at an index we need to shift all elements at the right to the left
for (int i = index + 1; i < array->usedSize; i++)
{
array->ptr[i - 1] = array->ptr[i];
}
array->usedSize--; // decremented used size as one element was deleted
array->ptr[array->usedSize] = NULL;
return 1;
}
else
{
printf("\n!!! Index %d is out of valid range 0 to %d\n", index, array->usedSize);
return 0;
}
}
We checked index using the inRange function and shifted elements to the right from index where we have to delete the element. Since we have copied the last element to the second last index, we now need to set the value of last index to be NULL; once we are done with that simple decrement the used size as one element has been reduced.
let's make a function to see value at an index, function will be called showAtIndex()
let's make a function to see value at an index, function will be called showAtIndex()
// see val at Index
int showAtIndex(struct NewArray *array, int index)
{
if (index >= 0 && index <= array->usedSize-1)
{
printf("\nvalue at %d is %d\n", index, array->ptr[index]);
return 1;
}
else
{
printf("\nindex %d out of range !!! \n", index);
return 0;
}
}
We again check if the index is within the range 0 to last index (here last index = used
size - 1) . if it is correct then we will print that value in the array at the given index otherwise return 0 and give the required message.
Here is the complete program:-
#include <stdio.h>
#include <stdlib.h>
/*
properties :
int totalSize;
int usedSize;
int *ptr;
operations :
showAtIndex() : to display all the elements of the array
setValue() : to set a value at the end
insertAtIndex() : to set a value at an index
deleteAlIndex() : to delete value at an index
*/
// structure for array ADT:
struct NewArray
{
// properties
int totalSize; // to store total size (max size) of the array
int usedSize; // to store the used size of the array
int *ptr; // pointer for dynamic memory allocation of array
};
/* function to create array which sets values of
total size, used size, and dynamically allocates memory of ptr */
void createArray(struct NewArray *array, int total)
{
array->totalSize = total;
array->usedSize = 0; // used size will be zero whlile creation as array is empty
array->ptr = (int *)malloc(total * sizeof(int));
}
// see val at an index
int showAtIndex(struct NewArray *array, int index)
{
if (index >= 0 && index <= array->usedSize-1)
{
printf("\nvalue at %d is %d\n", index, array->ptr[index]);
return 1;
}
else
{
printf("\nindex %d out of range !!! \n", index);
return 0;
}
}
// to set value at the end
int setValue(struct NewArray *array, int value)
{
// check if array is full or not
// if not full the continue with adding value
// else display msg and exit by returning 0
if (array->usedSize < array->totalSize)
{
array->ptr[array->usedSize] = value;
array->usedSize++;
return 1;
}
else
{
printf("\n!!! Array is full cannot add value\n");
return 0;
}
}
// func to check if index is within correct range
int inRange(struct NewArray *array, int index)
{
if (index >= 0 && index <= array->usedSize)
{
return 1;
}
else
{
return 0;
}
}
// to insert value at an index
int insertAtIndex(struct NewArray *array, int value, int index)
{
// check if array is full or not
// if not full the continue with adding value
// else display msg and exit by returning 0
if (inRange(array, index))
{
if (array->usedSize < array->totalSize) // to check if array is not full
{
for (int i = array->usedSize - 1; i >= index; i--)
{
array->ptr[i + 1] = array->ptr[i];
}
array->usedSize++;
array->ptr[index] = value;
return 1;
}
else
{
printf("\n!!! Array is full cannot add value\n");
return 0;
}
return 1;
}
else
{
printf("\n!!! Index %d is out of valid range 0 to %d\n", index, array->usedSize);
return 0;
}
}
// to delete value at an index
int deleteAtIndex(struct NewArray *array, int index)
{
if (inRange(array, index))
{
// to delete element at an index we need to shift all elements at the right to the left
for (int i = index + 1; i < array->usedSize; i++)
{
array->ptr[i - 1] = array->ptr[i];
}
array->usedSize--; // decremented used size as one element was deleted
array->ptr[array->usedSize] = NULL;
return 1;
}
else
{
printf("\n!!! Index %d is out of valid range 0 to %d\n", index, array->usedSize);
return 0;
}
}
int main(int argc, char const *argv[])
{
// now NewArray is our custom data type we can create a variable of this data type
// lets name it arr
printf("Enter total size in integer : ");
int val;
scanf("%d", &val);
struct NewArray arr;
createArray(&arr, val);
insertAtIndex(&arr, 5, 0);
insertAtIndex(&arr, 7, 1);
insertAtIndex(&arr, 4, 2);
insertAtIndex(&arr, 9, 3);
deleteAtIndex(&arr, 2);
showAtIndex(&arr, 0);
showAtIndex(&arr, 1);
showAtIndex(&arr, 2);
showAtIndex(&arr, 3);
showAtIndex(&arr, 4);
return 0;
}
Output:-
){kind=link}
0 Comments