Array and Abstract Data Types in Data Structure

ADTs or abstract data types are the ways of classifying data structures by providing a minimal expected interface and some set of methods. It is very similar to when we make a blueprint before actually getting into doing some job, be it constructing a computer or a building. The blueprint comprises all the minimum required logistics and the roadmap to pursuing the job.

Static and Dynamic Arrays:

  • Static arrays – Size cannot be changed
  • Dynamic arrays – Size can be changed

Memory Representations of Array:

  • Elements in an array are stored in contiguous memory locations.
  • Elements in an array can be accessed using the base address in constant time → O (1).
  • Although changing the size of an array is not possible, one can always reallocate it to some bigger memory location. Therefore resizing in an array is a costly operation.
Operations on Array
  • Insertion
  • Deletion
  • Traversal
Source Code

#include <stdio.h>

// Array Traversal - Printing all elements of array
void ArrayTraversal(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%dth element : %d\n", i + 1, arr[i]);
}
}

// Array Insertion - Adding elements in array
int ArrayInsertion(int arr[], int size, int capacity, int index, int element)
{
if (index > size || index < 0)
{
printf("Please enter valid index...");
}

else if (size == capacity)
{
printf("HouseFull !!!");
}
else
{
if (index == size)
{
arr[index] = element;
}
else
{
for (int i = size - 1; i >= index; i--)
{
arr[i + 1] = arr[i];
}
arr[index] = element;
size++;
}
}
return (size);
}

// Array Deletion - Deleting elements from array
int ArrayDeletion(int arr[], int size, int capacity, int index)
{
if (index < 0 || index > size)
{
printf("Invalid Index...\n");
}
else
{
if (index == size)
{
size--;
}
else
{
for (int i = index; i < size; i++)
{
arr[i - 1] = arr[i];
}
size--;
}
}
return (size);
}

int main()
{
/* code */
int arr[10] = {1, 45, 23, 34, 6, 39, 79, 100};
int capacity = sizeof(arr) / sizeof(int);
int size = 8;

printf("Array before Insertion : \n");
ArrayTraversal(arr, size);
size = ArrayInsertion(arr, size, capacity, 3, 25);

printf("\nArray After Insertion : \n");
ArrayTraversal(arr, size);

printf("Array before Deletion : \n");
ArrayTraversal(arr, size);
size = ArrayDeletion(arr, size, capacity, 3);
size = ArrayDeletion(arr, size, capacity, 8);

printf("\nArray After Deletion : \n");
ArrayTraversal(arr, size);

return 0;
}

Output

Array before Insertion :
1th element : 1
2th element : 45
3th element : 23
4th element : 34
5th element : 6
6th element : 39
7th element : 79
8th element : 100

Array After Insertion :
1th element : 1
2th element : 45
3th element : 23
4th element : 25
5th element : 34
6th element : 6
7th element : 39
8th element : 79
9th element : 100

Array before Deletion :
1th element : 1
2th element : 45
3th element : 23
4th element : 25
5th element : 34
6th element : 6
7th element : 39
8th element : 79
9th element : 100

Array After Deletion :
1th element : 1
2th element : 45
3th element : 25
4th element : 34
5th element : 6
6th element : 39
7th element : 79

Comments

Post a Comment

Popular posts from this blog

Searching Algorithms in Data Structure

Searching is a process of retriving or locating or finding information matching with some specific value. In data structure there are two types of searching. Linear or sequencial search Binary search   Linear or Sequencial Search It is a simplest form of searching and can be applied for sequencial storage such as array, stack, queue, linked list. Algorithm Linear/Sequencial Search Step 1: Start Step 2: Set 0 to i Step 3: Read and store value to search in val Step 4: if a(i) = val, print value is found at (i+1) position and go to step 8 Step 5: Set i to i + 1 Step 6: If i is less than n then, go to Step 4 Step 7: Print element not found Step 8: Stop n - size of array a - array val - value to be searched in array Source Code #include <stdio.h> #include <conio.h> #include <stdlib.h> int main() { int n; printf("Enter the size of array : "); scanf("%d", &n); int arr[n]; for...
Read more

Sorting Algorithms in Data Structure

Sorting is a process of arranging information either in ascending or in descending order of key values. In data structures there are techniques available to sort the data. Types of sorting algorithms Bubble sort Insertion sort Selection sort Quick sort Radix sort Merge sort   1. Bubble Sort It is one of the simplest & popular sorting method. The basic idea of this sorting is that in each pass we have to compare a successive pair of element i.e. a[i] & a[i+1]. Interchange these two values, if they are not place in proper order. Place the element in it's correct position in each pass. In first pass largest element is shifted at bottom. In second pass second largest will be shifted to the second last position & so on. Thus to sort n values n-1 passes are required. Algorithm Bubble Sort Step 1: Start Step 2: Set 1 to pass Step 3: Set o to i Step 4: if a[i]> a[i+1] then, Swap a[i] & a[i+1] Step 5: Add I to i. Step 6: If i...
Read more

Circular Linked List

Image
I n a Circular Linked List the first and the last elements are adjacent. A linked list can be made circular by storing the address of the first node in the next field of the last node. In a circular linked list, last node is connected back to the first node. In some applications, it is convenient to use circular linked list. A queue data structure can be implemented using a circular linked list, with a single pointer "rear" as the front node can be accessed through the rear node. Implementation of Circular Linked List Circular Linked List Creation and Traversal Algorithm for traversing a circular list is slightly different than the same algorithm for a singly linked list because "NULL" is not encountered. Source Code (Circular Linked List Creation and Traversal) #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; void CircularLinkedListTraversal(stru...
Read more