CHAPTER - 9

DATASTRUCTURES - ARRAYS

What is a data structure?

A data structure is a particular way of
storing and organizing data in a
computer so that it can be used
efficiently. Different kinds of data
structures are suited to different kinds of
applications, and some are highly
specialized to specific tasks. Simple
Data Structure These data structures
are normally built from primitive data
types like integers, floats, characters.
For example arrays and structure.
Compound Data Structure Simple data
structures can be combined in various
ways to form more complex structure
called compound structures. Linked
Lists, Stack, Queues and Trees are
examples of compound data structure.
Operations on Data
structures
• Insertion - Addition of a new data element
in a data structure
• Deletion - Removal of a data element
from a data structure
• Searching - Searching for a particular
data element in a data structure
• Traversal - Processing all the elements in
a data structure
• Sorting - Arranging data elements of a
data structure in a specified order
• Merging - Combining elements of two
similar data structures to form a new one

Searching methods in
array
• Linear Search In this method each element of the

array is compared with the number to be searched

in linear order (from first to last) and when the

number is matched the position and the index is

displayed.
#include<iostream.h> #include<conio.h> int

LinearSearch(int A[ ],int size, int item) {

int i; for(i=0; i<size; i++) { if(A[i] == item)

return i; } return -1; }

int main() { element to be
clrscr(); int searched: "; cin>>item;
A[50],i,size,item,pos; pos=LinearSearch(A,siz
cout<<"Enter the size of e,item);
the array: "; cin>>size; if(pos==-1)
cout<<"\nEnter the
cout<<"\nElement not
elements of the
found"; else
array\n"; for(i=0; i<size;
cout<<"Element found
i++)
at index
cin>>A[i]; cout<<"\nThe
"<<pos<<" and
array elements are\n";
position"<<pos+1;
for(i=0; i<size; i++)
getch();
cout<<A[i]<<" ";
return 0; }
cout<<"\nEnter the
• Binary Search Binary search algorithm is
applicable for already sorted array only. In
this algorithm, to search for the given item
from the sorted array (in ascending order),
the item is compared with the middle
element of the array. If the middle element
is equal to the item then index of the middle
element is returned, otherwise, if item is
less than the middle item then the item is
present in first half segment of the array
(i.e. between 0 to middle-1), so the next
iteration will continue for first half only, if the
item is larger than the middle element then
the item is present in second half of the
array (i.e. between middle+1 to size -1), so
the next iteration will continue for second
half segment of the array only. The same
process continues until either the item is
found (search successful) or the segment is
reduced to the single element and still the
item is not found (search unsuccessful).
#include<iostream.h> pos=BinarySearch(A,size,item);
if(pos==-1)
#include<conio.h> int
BinarySearch(int A[],int size, cout<<"\nElement not found"; else
int item) { cout<<"Element found at index

int first,mid,last; first=0; "<<pos<<" and position "<<pos+1;

getch(); return 0; }
last=size-1; while(first<=last) {
mid=(first+last)/2; if(A[mid] ==
item)
Selection
return mid; else
if(A[mid]<item)
Sort
first=mid+1; else
#include<iostream.h>
if(A[mid]>item) #include<conio.h> void
last=mid-1; } return -1; } Selection_Sort(int A[], int size) {
int main() { int small,pos,temp,i,j,k; for(i=0;
clrscr(); int A[50],i,size,item,pos; i<size-1; i++) {
cout<<"Enter the size of the array: small = A[i]; pos = i; for(j=i+1;
"; cin>>size; cout<<"\nEnter the j<size; j++) {
elements of the array\n"; for(i=0; if(A[j] < small) { small = A[j]; pos =
i<size; i++) j; } } temp = A[i]; A[i] = A[pos];
cin>>A[i]; cout<<"\nThe array A[pos] = temp; cout<<"\nArray
elements are\n"; for(i=0; i<size; after pass "<<i+1<<": "; for(k=0;
i++) k<size; k++)
cout<<A[k]<<" "; } }
cout<<A[i]<<" "; cout<<"\nEnter
int main() { clrscr();
the element to be
int A[10],size,i; cout<<"How many
searched: "; cin>>item;
 "<<i<<": "; for(k=0; k<size; k++)
elements dou you want to create
cout<<A[k]<<" "; } }
array with: "; cin>>size; int main() {
cout<<endl<<"Enter the array
clrscr(); int A[10],size,i,item;
elements"<<endl; for(i=0; i<size; cout<<"How many elements do
i++) you
cin>>A[i]; cout<<endl<<"Original want to create array with: ";
array is"<<endl; for(i=0; i<size; cin>>size; cout<<endl<<"Enter
i++) the array
cout<<A[i]<<" "; Selection_Sort(A, elements"<<endl; for(i=0;
size); cout<<endl<<"Array after i<size; i++)

sorting "<<endl; for(i=0; i<size; cin>>A[i];

i++)
cout<<endl<<"Original array
cout<<A[i]<<" "; getch(); return 0; } is"<<endl; for(i=0; i<size; i++)
cout<<A[i]<<" ";
Insertion Insertion_Sort(A,size);
cout<<endl<<"Array after

Sort sorting”
<<endl; for(i=0; i<size; i++)
cout<<A[i]<<" "; getch(); return
#include<iostream.h> 0; }
#include<conio.h> void
Insertion_Sort(int A[], int size) {
int i,j,k,min; for(i=1; i<size; i++) {
Bubble sort
min = A[i]; j = i-1; while(j>=0 && #include<iostream.h>
A[j]>min) { #include<conio.h> void
A[j+1] = A[j]; j--; } A[j+1] = min; Bubble_Sort(int A[], int size) {
cout<<"\nArray after pass int temp,i,j,k; for(i=0; i<size; i++)
{ the array elements"<<endl;
for(j=0; j<(size-1)-i; j++) { for(i=0; i<size; i++)
if(A[j] > A[j+1]) { cin>>A[i];
temp = A[j]; A[j] = A[j+1]; A[j+1] cout<<endl<<"Original array
= temp; } } cout<<"\nArray after is"<<endl;
pass for(i=0; i<size; i++)
"<<i+1<<": "; for(k=0; k<size; cout<<A[i]<<" ";
k++) Bubble_Sort(A,size);
cout<<A[k]<<" "; } } cout<<endl<<"Array after
int main() { sorting "<<endl;
clrscr(); int A[10],size,i,item; for(i=0; i<size; i++)
cout<<"How many elements cout<<A[i]<<" "; getch(); return
dou you want to create array 0; }
with: ";
cin>>size; cout<<endl<<"Enter

Merging of two arrays

#include<iostream.h> void merge_array(int[],int[],int,int,int[]); int main() {
int a[10],b[10],c[20],m,n,i; cout<<"Enter the size of the first array: "; cin>>m;
cout<<endl<<"Enter the size of the second array: ";
cin>>n; cout<<endl<<"Enter the elements of the 1st array"<<endl;
for(i=0;i<m;i++) cin>>a[i]; cout<<endl<<"Enter the elements of the 2nd
array"<<endl;
for(i=0;i<n;i++) cin>>b[i]; merge_array(a,b,m,n,c); cout<<endl<<"The
merged array is"<<endl; for(i=0;i<(m+n);i++) cout<<c[i]<<" "; return 0; }
Here, first in ascending and second in ascending order
and the merged array also in ascending order
void merge_array(int a[],int b[],int m,int n,int c[]) {
int i=0,j=0,k=0;
while(i<m&&j<n)
{
if(a[i]<=b[j]) {

c[k]=a[i]; k++; i++; } else

{
c[k]=b[j]; k++; j++; } }
if(i>m-1)
{
while(j<=n-1) {

c[k]=b[j]; k++; j++; } } if(j>n-1)

{ while(i<=m-1) {
c[k]=a[i]; k++; i++; } } }

Two-Dimensional Arrays
• A 2D array is an array which is stored in
the form of matrix.
• There are two ways of implementing 2-D
array in the memory ▫ Row Major
Implementation ▫ Column major implementation
Row major
implementation

Address of A[i][j]= B+ W [C(i-

lr) + (j- lc)] where B – Base address
of the array W – Width of the array
C- No. of columns of the original
array
lr – Lowest row index lc – Lowest
column index

Column major
implementation
 Address of A[i][j]= B+ W [R(j-
lc) + (i- lr)] where B – Base address
of the array W – Width of the array
R- No. of rows of the original array
lr – Lowest row index lc – Lowest
column index
Practice Questions
Q:

Q: