Skip to main content

2. ADTs and Array

 

Abstract Data Types and Array

  • ADTs or abstract data types are the ways of classifying data structures by providing a minimal expected interface and some set of methods.
  • ADT gives us the blueprint to implement the data structures.
  • Abstract Data Types = Minimal required functionality + Operations

  • An array is used to store elements of the same data type in contiguous memory location.
  • Elements in an array can be accessed using the base address in constant time.
  • Although changing the size of an array is not possible, we can reallocate it to some bigger memory location.

  • An array ADT holds the collection of given elements accessible by their index.

struct MyArray
{
    int TotalSize;
    int UsedSize;
    int *BaseAddress;
};

Minimal Required Functionality

We have three basic functionalities of an array:

  • TotalSize: This stores the maximum size of the array.
  • UsedSize: This stores the used size of the array.
  • *BaseAddress: A pointer variable which contains address of first element of the array.
void createArray(struct MyArray *a, int usize)
{
    (*a).TotalSize = usize+10;
    (*a).UsedSize = usize;
    (*a).BaseAddress = (int *)malloc((usize+10) * sizeof(int));
}

Operations

We can perform a lot of different operations on the array we created.

  1. Insertion: Inserting an element in the array.
  2. Deletion: Deleting an element from the array.
  3. Merging and Sorting: Merging two arrays to form a single array and then organizing the array in a specific order.
  4. Linear Search: Finding the position of an element in the array by comparing each element.
  5. Sorting: Arranging the array in ascending or descending order.
  6. Binary Search: Finding the position of an element in the array by dividing into halves.
  7. Traversing: Visiting all the elements of the array by processing each index exactly once.

Algorithm to Insert an Element in an Array

We assume A is an one-dimensional array with N elements. The maximum number of elements it can store is defined by MAX. The index be new inserting element be index and new element be value.

  1. START
  2. If N = MAX or index < min_index_of_array or index > N + 1
    print "Insertion not possible"
  3. Else
    1. Set N = N + 1
    2. Set j = N
    3. Repeat setps 3.iv. and 3.v. till j ≥ index
    4. Set A[j+1] = A[j]
    5. Set j = j - 1
    6. A[index] = value
  4. END
void insertion(struct MyArray *a)
{
    int j, position, value;
    printf("\t\tEnter position of element to be inserted: ");
    scanf("%d", &position);
    if ((position > (*a).UsedSize + 1) || (position < 0) || ((*a).UsedSize > (*a).TotalSize))
        printf("\t\tInsertiion not possible.");
    else
    {
        printf("\t\tEnter value of element to be inserted: ");
        scanf("%d", &value);
        (*a).UsedSize++;
        for (j = (*a).UsedSize; j >= position - 1; j--)
            (*a).BaseAddress[j + 1] = (*a).BaseAddress[j];
        (*a).BaseAddress[position - 1] = value;
    }
}

Algorithm to Delete an Element from an Array

We assume A is an one-dimensional array with N elements. The index of deleting element be index.

  1. START
  2. If index > N or index < min_index_of_array
    print "Deletion not possible"
  3. Else
    1. Set j = index
    2. Repeat steps 3.iii. and 3.iv. till j ≤ N
    3. Set A[j] = A[j+1]
    4. Set j = j + 1
    5. Set N = N - 1;
  4. END
void deletion(struct MyArray *a)
{
    int j, position;
    printf("\t\tEnter position of element to be deleted: ");
    scanf("%d", &position);
    if ((position > (*a).UsedSize) || (position < 0))
        printf("\t\tDeletion not possible.");
    else
    {
        for (j = position - 1; j < (*a).UsedSize; j++)
            (*a).BaseAddress[j] = (*a).BaseAddress[j + 1];
        (*a).UsedSize--;
    }
}

Algorithm to Merge an Array into another Array

We assume A and B be two one-dimensional arrays with N and M elements respectively.

  1. START
  2. Set j = min_index_of_array
  3. Repeat steps 4. and 5. till j < N
  4. Set A[N+j] = B[j]
  5. Set j = j + 1
  6. Set N = N + M
  7. END
void merging(struct MyArray *a, struct MyArray *b)
{
    for (int j = 0; j < (*b).UsedSize; j++)
        (*a).BaseAddress[(*a).UsedSize + j] = (*b).BaseAddress[j];
    (*a).UsedSize += (*b).UsedSize;
}

Algorithm for Linear Search in an Array

We assume A is an one-dimensional array with N elements. Let item be the element to be searched in the array.

  1. START
  2. Set k = 0
  3. Set j = min_index_of_array
  4. Repeat steps 5 and 6 till j < N
  5. If A[j] == item
    print "item founded at index j"
    Set k = k + 1
  6. Set j = j + 1
  7. If k == 0
    print "item not founded"
  8. END
void linear(struct MyArray *a)
{
    int j, k = 0, item;
    printf("\t\tEnter element to be searched: ");
    scanf("%d", &item);
    for (j = 0; j < (*a).UsedSize; j++)
    {
        if ((*a).BaseAddress[j] == item)
        {
            printf("\t\t%d is founded at position %d.", item, j + 1);
            k++;
        }
    }
    if (k == 0)
        printf("\t\t%d is not founded.", item);
}

Algorithm for Insertion Sorting in Ascending order

We assume A is an one-dimensional array with N elements.

  1. START
  2. Set i = min_index_of_array + 1
  3. Repeat steps 4, 5, 6, 7, 8 and 9 till i < N
  4. Set temp = A[i]
  5. Set k = i - 1
  6. Repeat steps 7and 8 till k ≥ 0 and temp ≤ A[k]
  7. Set A[k+1] = A[k]
  8. Set k = k - 1;
  9. Set A[k+1] = temp;
  10. END
void sorting(struct MyArray *a)
{
    int i, temp, k;
    for (i = 1; i < (*a).UsedSize; i++)
    {
        temp = (*a).BaseAddress[i];
        k = i - 1;
        while (k >= 0 && temp <= (*a).BaseAddress[k])
        {
            (*a).BaseAddress[k + 1] = (*a).BaseAddress[k];
            k--;
        }
        (*a).BaseAddress[k + 1] = temp;
    }
}

Algorithm for Binary Search in an Array

We assume A is an one-dimensional ascending order sorted array with N elements. Let item be the element to be searched in the array.

  1. START
  2. Set beg = 0
  3. Set end = N
  4. Set j = 0
  5. Repeat steps 6, 7, 8 and 9 till beg ≤ end
  6. Set mid = (beg + end)/2
  7. If A[mid] == item
    print "item founded at position mid"
    Set j = j + 1
    Break the loop
  8. Else if A[mid] < item
    Set beg = mid + 1
  9. Else
    Set end = mid - 1
  10. If j == 0
    print "item not founded"
  11. END
void binary(struct MyArray *a)
{
    int beg = 0, end = (*a).UsedSize, mid, j = 0, item;
    printf("\n\t\tEnter element to be searched: ");
    scanf("%d", &item);
    while (beg <= end)
    {
        mid = (beg + end) / 2;
        if ((*a).BaseAddress[mid] == item)
        {
            printf("\t\t%d is founded at position %d.", item, mid + 1);
            j++;
            break;
        }
        else if ((*a).BaseAddress[mid] < item)
            beg = mid + 1;
        else
            end = mid - 1;
    }
    if (j == 0)
        printf("\t\t%d not founded.", item);
}

Program to traverse the Array elements

void display(struct MyArray *a)
{
    printf("\t\t\tPrinting the array...\n\t\t\t");
    for (int i = 0; i < (*a).UsedSize; i++)
    {
        printf("%d ", (*a).BaseAddress[i]);
    }
}

Comments

Post a Comment