BCA : III
BCA-S202T: Data Structure using C and C++
Poorva Sanjay Sabnis.
Assistant Professor-I
Unit 1 : Introduction to Data Structures
Characteristics of data structures
• Linear or non-linear: This characteristic describes whether the data items are
arranged in chronological sequence, such as with an array, or in an unordered
sequence, such as with a graph.
• Homogeneous or non-homogeneous: This characteristic describes whether all data
items in a given repository are of the same type or of various types.
• Static or dynamic: This characteristic describes how the data structures are
compiled. Static data structures have fixed sizes, structures and memory locations at
compile time. Dynamic data structures have sizes, structures and memory locations
that can shrink or expand depending on the use.
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Classification of Data Structures
Data structures can be classified as-
• Simple data structure
• Compound data structure
• Linear data structure
• Non-linear data structure
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Linear data structures
• Linear data structures can be constructed as a continuous arrangement of data elements
in the memory. It can be constructed by using array data type. In the linear Data Structures
the relationship of adjacency is maintained between the data elements.
• Types of linear data structures : 1) Array
2) Stack
3) Queue
4) Linked Lists
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Definition of Array
• Array is a data structure that represents a collection of the same types of data.
• Array is a container which can hold a fix number of items and these items
should be of the same type. Most of the data structures make use of arrays to
implement their algorithms.
• Following are the important terms to understand the concept of Array.
1) Element − Each item stored in an array is called an element.
2) Index − Each location of an element in an array has a numerical index,
which is used to identify the element.
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Array Representation
• Arrays can be declared in various ways in different languages. For illustration,
let's take C array declaration.
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Array Representation
• Arrays can be declared in various ways in different languages. For illustration,
let's take C array declaration.
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Array Representation
• Arrays can be declared in various ways in different languages. For illustration,
let's take C array declaration.
• As per the above illustration, following are the important points to be
considered.
1) Index starts with 0.
2) Array length is 10 which means it can store 10 elements.
3) Each element can be accessed via its index.
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Operations on Array
Following are the basic operations supported by an array.
• Traverse − print all the array elements one by one.
• Insertion − Adds an element at the given index.
• Deletion − Deletes an element at the given index.
• Search − Searches an element using the given index or by the value.
• Update − Updates an element at the given index.
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Creating Array
arrayName = new datatype[arraySize];
Example:
myList = new double[10];
myList[0] references the first element in the array.
myList[9] references the last element in the array.
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Traverse Operation
This operation is to traverse through the elements of an array.
Example:
Following program traverses and prints the elements of an array:
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Traverse Operation
When we compile and execute the above program, it produces the following
result −
Output:
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Insertion Operation
• Insert operation is to insert one or more data elements into an array. Based
on the requirement, a new element can be added at the beginning, end, or
any given index of array.
• Here, we see a practical implementation of insertion operation, where we
add data at the end of the array −
BCA-S202T: DS
Insertion Operation
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++)
{ printf("LA[%d] = %d \n", i, LA[i]); }
n = n + 1;
while( j >= k) { LA[j+1] = LA[j];
j = j - 1; }
LA[k] = item;
printf("The array elements after insertion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]); }
}
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Insertion Operation
Output:
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Deletion Operation
Deletion refers to removing an existing element from the array and
reorganizing all elements of an array.
Algorithm:
Consider LA is a linear array with N elements and K is a positive integer such
that K<=N. Following is the algorithm to delete an element available at the Kth
position of LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
BCA-S202T: DS
Deletion Operation
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); }
j = k;
while( j < n) { LA[j-1] = LA[j];
j = j + 1; }
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Deletion Operation
Output:
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Search Operation
You can perform a search for an array element based on its value or its index.
Algorithm:
Consider LA is a linear array with N elements and K is a positive integer such
that K<=N. Following is the algorithm to find an element with a value of ITEM
using sequential search.
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
BCA-S202T: DS
Search Operation
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); }
while( j < n){
if( LA[j] == item ) { break; }
j = j + 1;
}
printf("Found element %d at position %d\n", item, j+1);
}
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Search Operation
When we compile and execute the above program, it produces the following
result −
The original array éléments are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Update Operation
Update operation refers to updating an existing element from the array at a
given index.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such
that K<=N. Following is the algorithm to update an element available at the
Kth position of LA.
1. Start
2. Set LA[K-1] = ITEM
3. Stop
BCA-S202T: DS
Update Operation
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
LA[k-1] = item;
printf("The array elements after updation :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
BCA-S202T: DS
Unit 1 : Introduction to Data Structures
Update Operation
When we compile and execute the above program, it produces the following result
Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8
BCA-S202T: DS
