Pune Vidyarthi Griha’s
COLLEGE OF ENGINEERING,
NASHIK – 3.
“Linear Data Structure using
Squential Organization”
By
Prof. Anand N. Gharu
(Assistant Professor)
PVGCOE Computer Dept.
10 July 2019
.1
SEQUENTIAL
ORGANIZATION
• Definition :
“In computer science, sequential access means that a group of
elements (such as data in a memory array or a disk file or on magnetic
tape data storage) is accessed in a predetermined, ordered
sequence.Sequential access is sometimes the only way of accessing
the data, for example if it is on a tape.”
PROF. ANAND GHARU
2
Lnear Data Structure sng Sequential
Organization
• Definition :
“The data structure where data items are organized sequentially
or linearly one after another is called as Linear Data
Structure”
A linear data structuretraverses the data elements
sequentially, in which only one data element can directly
be reached. Ex: Arrays, Linked Lists.
PROF. ANAND GHARU3
Array
• Definition :
❖“An array is a finite ordered collection of homogeneous
data elements which provides direct access (or random
access)to any of its elements.
❖An array as a data structure is defined as a set of pairs
(index,value) such that with each index a value is associated.
• index — indicates the location of an element in an array.
• value - indicates the actual value of that data element.
❖Declaration of an array in ‘C++’:
• int Array_A[20];
”
PROF. ANAND GHARU4
Array
• Array Representation
• Arrays can be declared in various ways in different languages. For
illustration, let's take C array declaration.
• 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.
PROF. ANAND GHARU5
Array
• Array Representation
• Index starts with 0.
• Array length is 10 which means it can store 10 elements. • Each
element can be accessed via its index. For example, we can fetch an
element at index 6 as 9.
• Basic Operations
• 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. PROF. ANAND GHARU6
Memory Representation and Calculation
X(Base)
X+1
X+2
X+(n-1)
Array A
Fig 2.1 Memory Representation
PROF. ANAND GHARU 77
ADDRESS CALCULATION
❖The address of the ith element is calculated by the following
formula
(Base address) + (offset of the ith element from base
address)
Here, base address is the address of the first element
where array storage starts.
2
PROF. ANAND GHARU 8 8
Abstract Data Type
• ADT is useful tool for specifying the logical properties of
a data type.
• A data type is a collection of values & the set of
operations on the values.
• ADT refers to the mathematical concept that defines the
data type.
• ADT is not concerned with implementation but is useful
in making use of data type.
ADT for an array
• Arrays are stored in consecutive set of memory
locations.
• Array can be thought of as set of index and values. •
For each index which is defined there is a value
associated with that index.
• There are two operations permitted on array data
structure .retrieve and store
ADT for an array
• CREATE()-produces empty array.
• RETRIVE(array,index)->value
Takes as input array and index and either returns
appropriate value or an error.
• STORE(array,index,value)-array used to enter new index
value pairs.
Introduction to arrays
Representation and analysis
Type variable_name[size]
Operations with arrays:
Copy
Delete
Insert
Search
Sort
Merging of
sorting
arrays.
Copy operation
• #include <stdio.h>
•
• int main()
•{
• int a[100],b[100] position, c n;
•
• printf("Enter number of elements in array\n");
• scanf("%d", &n);
•
• printf("Enter %d elements\n", n);
•
• for ( c = 0 ; c < n ; c++ )
• scanf("%d", &a[c]);
• printf("Enter %d elements\n", n);
•
• for( c = 0 ; c < n - 1 ; c++ )
• printf("%d\n", a[c]);
• //Coping the element of array a to b
• for( c = 0 ; c < n - 1 ; c++ )
•{
• b[c]=a[c];
•}
•}
•
• return 0;
Output •
• • Enter number of
elements in array -4
•
• Enter 4 elements
•
1
•2
•3
•4
• displaying array a
•1
•2
•3
•4
• displaying array b
•1
•2
•3
•4
Delete operation
• #include <stdio.h>
•
• int main()
•{
• int array[100], position, i, n;
•
• printf("Enter number of elements in array\n");
• scanf("%d", &n);
•
• printf("Enter %d elements\n", n);
•
• for ( i = 0 ; i < n ; i++ )
• scanf("%d", &array[i]);
•
• printf("Enter the location where you wish to delete element\n"); •
scanf("%d", &position);
•
• for ( i = position ; i < n; i++ )
o {
• array[i] = array[i+1];
•}
• printf("Resultant array is\n");
•
• for( i = 0 ; i < n-1 ; i++ )
• printf("%d\n", array[i]);
• return 0;
•}
Delete operation
Inserting an
element #include <stdio.h>
int main()
{
int array[100], position, i, n, value;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d elements\n", n);
for (i= 0;i< n; i++)
scanf("%d", &array[i]);
printf("Enter the location where you wish to insert an element\n");
scanf("%d", &position);
printf("Enter the value to insert\n");
scanf("%d", &value);
for (i = n - 1; i >= position ; i--)
array[i+1] = array[i];
array[position] = value;
printf("Resultant array is\n");
for (i= 0; i <= n; i++)
printf("%d\n", array[i]);
return 0;
Inserting an element
Sort an array
Int a[10]={5,4,3,2,1}
for(i=0;i<n-1;i++)
{
for(j=0;j<=n-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
everse array
#include <stdio.h>
int main() {
int array[100], n, i, temp, end;
scanf("%d", &n);
end = n - 1;
for (i = 0; i < n; i++) {
scanf("%d", &array[i]);
}
for (i= 0; < n/2; i++)
{
temp = array[i];
array[i] = array[end];
array[end] = temp;
end--;
}
printf("Reversed array elements are:\n");
for ( i= 0; i < n; i++) {
printf("%d\n", array[i]);
}
return 0;
}
Sort element
using array int
a[10]={5,4,3,2,1}
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
Two-
dimensional Arrays
in C
• multidimensional array is the two-
dimensional array
• type arrayName [ x ][ y ];
Two-
dimensional Arrays
in C
m-no of rows
n-no of columns
Printf(“\n Enter the rows and
columns”); Scanf(%d %d”,&m,&n);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
Printf(“\n Enter the value
of(%d)(%d)=“,i,j); Scanf(“%d”,&a[i][j]);
}
}
for(i=0;i<m;i++
){
Printf(“\n”);
for(j=0;j<n;j++)
{
printf(“%d”,&a[i][j])
;}
}
ARRAY AS AN ADT
❖Formally ADT is a collection of domain, operations,and
axioms (or rules)
❖For defining an array as an ADT, we have to define its very
basic operations or functions that can be performed on it ❖
The basic operations of arrays are creation of an array,
storing an element, accessing an element, and traversing
the array
PROF. ANAND GHARU 26
2
6
❖List of operation on Array :-
❖1. Inserting an element into an array
❖2. deleting element from array
❖3. searching an element from array
❖4. sorting the array element
PROF. ANAND GHARU
27 27
N -dimensional Arrays
PROF. ANAND GHARU 28
PROF. ANAND GHARU 29
Row-Major representation of 2Darray
PROF. ANAND GHARU 30
A[0][m2][m3] A[1][m2][m3] A[i][m2][m3]
A[m1-1][m2]
(i*m2*m3) elements
Three dimensions row-majorarrangement
PROF. ANAND GHARU 31
❖The address of A[i][j][k] is computedas
❖Addrof A[i][j][k] = X + i * m2 * m3 + j * m3 + k
❖By generalizing this we get the address of A[i1][i2][i3] … [ in] in n
dimensional array A[m1][m2][m3]. ….[ mn ]
❖Consider the address of A [0][0][0]…..[0] is X then the address of A
[i][0][0]….[0] = X + (i1 * m2 * m3 * - - -- - * mn ) and
❖Address of A [i1][i2] …. [0] = X + (i1 * m2 * m3 * - -- - *mn ) + (i2 * m3
* m4 *--- * mn)
❖Continuing in a similar way, address of A[i1][i2][i3]- - - -[ in] willbe
❖Address of A[i1][i2][i3]----[ in] = X + (i1 * m2 * m3 * - - -- - * mn) + (i2
* m3 * m4 *--- - - * mn )+(i3 * m4 * m5--- * mn + (i4 * m5 * m6-- - - - *
mn +…….+ in =
PROF. ANAND GHARU 32
x-rrays
#include <stdio.h>
int main ()
{
int a[10],i,size;
printf(“\nhow many no of elements u want to scan”);
scanf(“%d”,&size);
printf(“\nEnter the elements in the array”);
for(i=0;i<size;i++)
{
scanf(“%d”,&a[i]);
} //end for
for(i=0;i<size;i++)
{
printf(“The array is %d”,a[i]); //Displaying Array } //end for
return 0;
Output will be 1
2
3
4
5
Multi- dimensional
Arrays in C
• type
name[size1][size2]...[sizeN];
Two-
dimensional Arrays
in C
• multidimensional array is the two-dimensional array
• type arrayName [ x ][ y ];
Two-
dimensional Arrays in
C
HOW TO INITIALIZE 2-D
ARRAY IN PROGRAM •
Initializing Two-Dimensional Arrays
int a[3][4] = { {0, 1, 2, 3} , /*
initializers for {4, 5, 6, 7} ,
{8, 9, 10, 11} /* initializers for row
/* initializers for row indexed by 2 */
};
• Accessing Two- Dimensional Array
Elements int val = a[2][3];
Three-
dimensional Arrays
in C
• For example, the following declaration creates a three
dimensional integer array −
• Ex-int threedim[5][10][4];
THE CLASS ARRAY
❖Arrays support various operations such as traversal,
sorting, searching, insertion, deletion, merging,
block movement, etc.
Insertion of an element into an array
Deleting anelement
Memory Representation of Two-DimensionalArrays
PROF. ANAND GHARU 4141
❖Row-major Representation ❖
Column-major Representation
Columns
Col1 col2 ....
coln
:::
Rows R1 R2
Am1 Am2 ....
Amn
m*n
Rm
A11 A12 .... A1n
A11 A12 .... A1n Matrix M =
1 2 3 4 5 6 7 8 9 10 11
12
PROF. ANAND
G
H
A
R
U
4
2
42
Row-major
representation
PROF. ANAND
GHARU 43
Row-major
representation
❖In row-
major representation, the elements of Matrix are stored row-
wise, i.e., elements of 1st row, 2nd row, 3rd row, and so on till
mth row
1 2 3 4 5 6 7 8 9 10 11 12
(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3)
Row1 Row2 Row3
PROF. ANAND GHARU 44
Row 0 Row 1
Row
major
arrangement
Row0
Row1
Memory Location
Row m-1 Row m-1
Row-major arrangement in memory , in row major representation PROF. ANAND
GHARU 45
❖The address of the element of the ith rowand the jth column for matrix of
size m x n can be calculated as:
Addr(A[i][j]) = Base Address+ Offset = Base Address + (number of
rows placed before ith row * size of row) * (Size of Element) +
(number of elements placed before in jth element in ith row)* size
of element
❖As row indexing starts from 0, i indicate number of rows before the
ith row hereand similarly for j.
For Element Size = 1 the address is
Address of A[i][j]= Base + (i * n ) +j
PROF. ANAND GHARU 46
❖In general,
Addr[i][j] = ((i–LB1) * (UB2 – LB2 + 1) * size) + ((j– LB2) * size)
❖where number of rows placed before ith row = (i –LB1) ❖
where LB1 is the lower bound of the firstdimension.
Size of row = (number of elements in row) * (size of
element)Memory Locations
The number of elements in arow = (UB2 – LB2 + 1)
❖where UB2 and LB2 are upper and lower bounds of
the second dimension.
PROF. ANAND GHARU 47
Column-major
representation
❖In column-major
representation m × n elements of two- dimensional array A are stored as one
single rowof columns.
❖The elements are stored in the memory as a sequence as first the
elements of column 1, then elements of column 2 and so on till elements of
column n
PROF. ANAND GHARU 48
Column-major
arrangement
Col
0
col1 col2 Col
…
n-1
Col 1
Col 2 Memory Location
Column-major arrangement in memory , in column major representation PROF.
ANAND GHARU 49
❖The address of A[i][j] is computedas
❖ Addr(A[i][j]) = Base Address+ Offset= Base Address + (number of
columns placed before jth column * size of column) * (Size of
Element) + (number of elements placed before in ith element in ith
row)* size of element
❖For Element_Size = 1 the addressis
❖Address of A[i][j] for column major arrangement = Base + (j *
m)+I
❖In general, for column-major arrangement; address of the
element of the jth row and the jth column therefore is ❖Addr
(A[i][j] = ((j – LB2) * (UB1 – LB1 + 1) * size) + ((i –LB1) * size)
PROF. ANAND GHARU 50
Example 2.1: Consider an integer array, int A[3][4] inC++. If
the base address is 1050, find the address of the element A[2]
[3] with row-major and column-majorrepresentation of the
array.
For C++, lower bound of index is 0 and we have m=3, n=4,
and Base= 1050. Let us compute address of element A [2][3]
using the address computationformula
1. Row-Major Representation:
Address of A [2][3] = Base + (i * n ) +j
= 1050 + (2 * 4) + 3
= 1061
PROF. ANAND GHARU 51
1 2 3 4 5 6 7 8 9 10 11 12
(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3)
Row1 Row2 Row3
Row-Major Representation of 2-D
array
PROF. ANAND GHARU 52
2. Column-Major Representation:
Address of A [2][3] = Base + (j * m ) +i
= 1050 + (3 * 3) + 2
= 1050 + 11
= 1061
Here the address of the element is same because it is the
last member of last row and lastcolumn.
PROF. ANAND GHARU 53
1 2 3 4 5 6 7 8 9 10 11 12
(0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) (0,3) (1,3) (2,3)
Col 1 Col 2 Col 3 Col 4
Column-Major Representation of 2-D
array
PROF. ANAND GHARU 54
Characteristics of array
❖An array is a finite ordered collection of homogeneous data
elements.
❖In array, successive elements of list are stored at a fixed
distance apart.
❖Array is defined as set of pairs-( index and value).
❖Array allows random access to any element
❖In array, insertion and deletion of element in between
positions
• requires data movement.
❖Array provides static allocation, which means space allocation
done once during compile time, can not be changed run time.
PROF. ANAND GHARU
55 55
Advantage of Array Data
Structure ❖Arrays permit efficient random access
in constanttime 0(1). ❖Arrays are most appropriate for
storing a fixed amount of data
and also for high frequency of data retrievals as data can
be accessed directly.
❖Wherever there is a direct mapping between the
elements and there positions, arrays are the most
suitable data structures. ❖Ordered lists such as
polynomials are most efficiently handled using arrays.
❖Arrays are useful to form the basis for several more
complex data structures, such as heaps, and hash tables
and can be
used to represent strings, stacks andqueues.
PROF. ANAND GHARU
56 56
Disadvantage of Array Data
Structure
❖Arrays provide static memory management. Hence
during execution the size can neither be grown nor
shrunk. ❖Array is inefficient when often data is to
inserted or deleted as inserting and deleting an element
in array needs a lot of data movement.
❖Hence array is inefficient for the applications, which
very often need insert and delete operations in between.
PROF. ANAND GHARU
57 57
Applications of Arrays
❖Although useful in their own right, arrays also form the basis
for several more complex data structures, such as heaps, hash
tables and can be used to represent strings, stacks and queues.
❖All these applications benefit from the compactness and
direct access benefits of arrays.
❖Two-dimensional data when represented as Matrix and
matrix operations.
PROF. ANAND GHARU
58 58
CONCEPT OF ORDERED LIST
❖Ordered list is the most common and frequently used data
object
❖Linear elements of an ordered list are related with each other
in a particular order or sequence
❖Following are some examples of theordered list.
❖1, 3,5,7,9,11,13,15
❖January, February, March, April, May, June, July,
August, September,
❖October, November, December
❖Red, Blue, Green, Black, Yellow
PROF. ANAND GHARU 59
❖There are many basic operations that can be
performed on
the ordered list
as follows:
⮚Finding the length of the list
⮚Traverse the list from left to right or from
right to left
⮚Access the ith element in thelist
⮚Update (Overwrite) the value of
the ith
position
⮚Insert an element at the ith location
⮚Delete an element at the ith position
PROF. ANAND GHARU 60
SINGLE VARIABLE
POLYNOMIAL
PROF. ANAND GHARU 61
Single
Variable Polynomial
❖Representation Using Arrays
❖Array of Structures
❖Polynomial Evaluation
❖Polynomial Addition
❖Multiplication of TwoPolynomials
PROF. ANAND GHARU 62
Polynomial
Representation on array
PROF. ANAND GHARU 63
Polynomial
Representaiton
PROF. ANAND
GHARU 64
❖Polynomial as an ADT, the basic operations are as
follows:
❖Creation of a polynomial
❖Addition of two polynomials
❖Subtraction of two polynomials
❖Multiplication of two polynomials
❖Polynomial evaluation
PROF. ANAND GHARU 65
Polynomial by using Array
PROF. ANAND GHARU 66
Polynomial by using Array
PROF. ANAND GHARU 67
❖Structure is better than array for Polynomial:
❖Such representation by an array is both time and space efficient when
polynomial is not a sparse one such as polynomial P(x) of degree 3 where
P(x)= 3x3+x2–2x+5.
❖But when polynomial is sparse such as in worst case a polynomial as A(x)=
x99 + 78 for degree of n =100, then only two locations out of 101 would be
used.
❖ In such cases it is better to store polynomial as pairs of coefficient and
exponent. We may go for two different arrays for each or a structure having
two members as two arrays for each of coeff. and Exp or an array of
structure that consists of two data members coefficient and exponent.
PROF. ANAND GHARU 68
Polynomial by using
structure
❖Let us go for structure having two data members coefficient
and exponent and itsarray.
PROF. ANAND GHARU 69
SPARSE MATRIX
❖In many situations, matrix size is very large but out of it,
most of the elements are zeros (not necessarily always zeros).
❖And only a small fraction of the matrix is actually used. A
matrix o such type is called a sparse matrix,
PROF. ANAND GHARU 70
SPARSE
MATRIX
PROF. ANAND GHARU 71
Sparse Logical Matrix
PROF. ANAND GHARU 72
Sparse matrix and its representation PROF.
ANAND GHARU 73
Transpose
Of Sparse Matrix
❖Simple Transpose
❖Fast Transpose
PROF. ANAND GHARU 74
Transpose
Of Sparse Matrix
PROF. ANAND GHARU 75
Transpose Of Sparse
Matrix
Time complexity of manual
technique is O(mn).
PROF. ANAND GHARU 77
Sparse matrix
transpose
PROF. ANAND GHARU 78
Simple Sparse
matrixtranspose
❖Time complexity will be O (n. T)
= O (n . mn)
2
= O (mn )
which is worst than the conventional transposewith
time complexity O (mn)
PROF. ANAND GHARU 79
Fast Sparse matrix
transpose
❖In worst case, i.e. T= m ×
n (non-zero elements) the magnitude becomes O (n +mn) = O
(mn) which is the same as 2-D transpose
❖Howeverthe constant factor associated with fast transpose
is quite high
❖When T is sufficiently small, compared to its maximum of m
. n, fast transpose will workfaster
PROF. ANAND GHARU 80
