Hello people! How are you?
In this lesson we would be performing insertion, deletion and traversal in an array. These are pretty straight forward data structure operations which I do not think you guys would have much difficulty in understanding. Hence lets get started!
Traversal
Let A be the collection of data elements stored in the memory of computer. Suppose we want to print the contents of each element of A or suppose we want to count the number of elements of A with a given property. This can be achieved by traversing A, that is, by accessing and processing each element of A exactly once.
The following algorithm traverses a linear array LA. The simplicity of algorithm comes from the fact that LA is a linear structure. Other linear structures such as linked lists can also be easily traversed. On the other hand, the traversal of non-linear data structures such as trees and graphs is considerably more complicated.
Algorithm: Traversal of a Linear Array
Here LA is a linear array with lower bound LB and upper bound UB. This algorithm traverses LA applying an operation PROCESS to each element of LA.
1. Set K:=LB [Initialize counter]
2. Repeat steps 3 and 4 while K<= UB
3. Apply PROCESS to LA[K]. [Visit element]
4. Set K:=K+1 [Increase counter,]
[End of Step 2 Loop]
5. Exit.
Insertion & Deletion
Let A be a collection of data elements in the memory of computer. "Inserting" refers to the operation of adding another element to the collection A, and "Deleting" refers to the operation of removing one of the elements from A. This section discusses inserting and deleting when A is the linear array.
Inserting an element at the "end" of the linear array can be easily done provided the memory space allocated for the array is large enough to accommodate the additional element. On the other hand, suppose we need to insert an element in the middle of the array, then, on the average, half of the elements must be moved upwards to new locations to accommodate the new element and keep the order of the other elements.
Similarly, deleting an element at the "end" of an array presents no difficulties, but deleting an element somewhere in the middle of an array would require that each subsequent element be moved one location downwards in order to "fill" up the array.
Algorithm: Insertion in a Linear Array
Here LA is a linear array with N elements and K is a positive integer such that K<=N. This algorithm inserts an element ITEM into the Kth position in LA.
INSERT(LA, N, K, ITEM)
1. Set J:=N. [Initialize counter]
2. Repeat steps 3 & 4 while J>=K.
3. Set LA[J+1]:=LA[J] [Move Jth element upwards]
4. Set J:=J-1. [Decrease counter]
[End of Step 2 Loop]
5. Set LA[K] := ITEM. [Insert element]
6. Set N:=N+1 [Reset N]
7. Exit.
Algorithm: Deletion in a Linear Array
Here LA is a linear array with N elements and K is a positive integer such that K<=N. This algorithm deletes the Kth element from the LA.
DELETE(LA, N, K, ITEM)
1. Set ITEM:=LA[K].
2. Repeat for J=K to N-1.
Set LA[J]:=LA[J+1] [Move J+1st element upward.]
[End of Step 2 Loop.]
3. Set N:=N-1. [Reset the number N of elements in LA.]
4. Exit.
Now that we have completed the theoretical analysis of all the three operations, let us have a look at the code for the three operations!
//Shubham Mehta, Write a program to perform insertion, deletion and traversal on an array.
#include <stdio.h>
#include <conio.h>
void main()
{
int i, choice1, no, arr[500], choice2, operation, index, dummy;
clrscr();
printf("%s", "Please enter the appropriate code: \n\nEnter 1 for Traversal\nEnter 2 for Insertion\nEnter 3 for Deletion\n\nYour Choice: ");
scanf("%d", &choice1);
printf("%s", "\nPlease enter the number of elements you want to enter in your array: ");
scanf("%d", &no);
printf("%s", "\nPlease enter the elements of the array: \n\n");
for(i=1; i<=no; i++)
scanf("%d", &arr[i]);
if(choice1==1)
{
printf("%s", "\n\nPerforming Traversal\n\n");
printf("%s", "Which Operation do you want to perform with the array? (Enter the respective code)\nEnter 1 for Addition\nEnter 2 for Subtraction\nEnter 3 for Multiplication\nEnter 4 for Division\n\nYour Choice: ");
scanf("%d", &choice2);
if(choice2==1)
{
printf("Enter the number to be added: ");
scanf("%d", &operation);
printf("%s", "\n\nHence the revised array is: \n");
for(i=1; i<=no; i++)
{
arr[i]=arr[i]+operation;
printf("%d\n", arr[i]);
}
}
else if(choice2==2)
{
printf("Enter the number to be subtracted: ");
scanf("%d", &operation);
printf("%s", "\n\nHence the revised array is: \n");
for(i=1; i<=no; i++)
{
arr[i]=arr[i]-operation;
printf("%d\n", arr[i]);
}
}
else if(choice2==3)
{
printf("Enter the number to be multiplied: ");
scanf("%d", &operation);
printf("%s", "\n\nHence the revised array is: \n");
for(i=1; i<=no; i++)
{
arr[i]=arr[i]*operation;
printf("%d\n", arr[i]);
}
}
else if(choice2==4)
{
printf("Enter the number to be divided by: ");
scanf("%d", &operation);
printf("%s", "\n\nHence the revised array is: \n");
for(i=1; i<=no; i++)
{
arr[i]=arr[i]/operation;
printf("%d\n", arr[i]);
}
}
else
{
printf("%s", "Wrong choice entered, exiting!");
}
}
else if(choice1==2)
{
printf("%s", "\n\nPerforming insertion\n\n");
printf("%s", "Enter the element you want to insert: ");
scanf("%d", &operation);
printf("%s%d%s", "\nEnter the index you want to enter this number at (smaller than or equal to ", no, "): ");
scanf("%d", &index);
for(i=(no+1); i>index; i--)
{
dummy=arr[i];
arr[i]=arr[i-1];
arr[i-1]=dummy;
}
arr[i]=operation;
no++;
printf("%s", "\n\nHence the revised array is: \n\n");
for(i=1; i<=no; i++)
printf("%d\n", arr[i]);
}
else if(choice1==3)
{
printf("%s", "\n\nPerforming deletion\n\n");
printf("Enter the index at which you want to delete (smaller than equal to ", no, "): ");
scanf("%d", &index);
for(i=index; i<=no; i++)
arr[i]=arr[i+1];
no--;
printf("%s", "\n\nHence the revised array is: \n\n");
for(i=1; i<=no; i++)
printf("%d\n", arr[i]);
}
else
{
printf("Wrong choice entered, exiting!");
}
getch();
}
And with this we finish our analysis of three of the data structure operations on linear arrays. Stay tuned for even more operations like searching and sorting. Take care :)
Output kaha hai
ReplyDelete