UNIT I : Introduction
DATA STRUCTURES AND ALGORITHMS
KIRTI DIGHOLKAR
UNIT I : Introduction
Introduction to Data Structures: Concept of data, Data object, Data structure,
Concept of Primitive and non-primitive, linear and Nonlinear, static and dynamic,
persistent and ephemeral data structures, Definition of ADT
Analysis of algorithm: Frequency count and its importance in analysis of an
algorithm, Time complexity & Space complexity of an algorithm Big 'O', ‘Ω' and 'Θ'
notations,
Sequential Organization: Single and multidimensional array and address
calculation.
Linked Organization: Concept of linked organization, Singly Linked List, Doubly
Linked List, Circular Linked List (Operations: Create, Display, Search, Insert, Delete).
Case Study: Set Operation, String Operation
Kirti Digholkar
Introduction to Data Structures
Concept of data
Data object
Data structure
Concept of Primitive and non-primitive
linear and Nonlinear
static and dynamic
persistent and ephemeral data structures
Definition of ADT
Kirti Digholkar
Array As List Data Structure
Stack and
Kirti Digholkar
Queue
Further classification of Linear List
Linear
List
Restricted General
List List
Linked
Stack Queue Array
List
Kirti Digholkar
LIST
What is List?
Sequence of any number, name or anything is list
Collection of similar data.
Many applications require multiple data items that
have common characteristics.
Like roll number, account number, Marks, CGPA, Share
price etc…
Kirti Digholkar
Need/ Purpose
Suppose we need to handle 10 numbers.
May be more …..
Where do we store the numbers ? How many variables
we should declare ?
Use 100 variables ?? How to handle them?
Array is a data structure which can represent a collection
of data items which have the same data type
(float/int/char/…)
Kirti Digholkar
Ex: Print numbers in reverse order
4 numbers
3 numbers
int a, b, c, d;
int a, b, c; scanf(“%d”, &a);
scanf(“%d”, &a); scanf(“%d”, &b);
scanf(“%d”, &b); scanf(“%d”, &c);
scanf(“%d”, &c); scanf(“%d”, &d);
printf(“%d ”, c); printf(“%d ”, d);
printf(“%d ”, b); printf(“%d ”, c);
printf(“%d \n”, a); printf(“%d ”, b);
Kirti Digholkar
printf(“%d \n”, a);
1 D Array
Kirti Digholkar
Printing in Reverse Using Arrays
void main()
{
int n, A[100], i;
cout<< “How many numbers to read? “;
cin>> n;
for (i = 0; i < n; ++i)
cin>>A[i];
for (i = n -1; i >= 0; --i)
cout<<A[i];
cout<< “\n”;
}
Kirti Digholkar
Using Arrays
All the data items constituting the group share the same
name
int x[10];
Individual elements are accessed by specifying the index
-------
X is a 10-
X[0] X[1] X[2] element one
X[9] dimensional
array
Kirti Digholkar
Types of Array
1 D Array (One dimensional array) (Sorting)
1 2 3 ………. n
◼2 D array (Two dimensional array) (MATRIX)
Column
r1c1 r1c2 r1c3
Row r2c1 r2c2 r2c3
r3c1 r3c2 r3c3
3 D Array (Three dimensional array)
M D Array (Multi dimensional array)
Kirti Digholkar
Definition of Array :
It defined as a finite sequence of data elements of the homogeneous/
same type.
Integer Array
10 30 40 12 … …. 190
[0] [1] [2] [3] [n] Index
Character Array
‘a’ ’A’ ‘d’ ‘X’ ‘^’ ‘*’ …. ‘H’
[0] [1] [3] [n] Subscript
[2]
Float Array
23.7 12.345 40.11 56.1 … Index/
…. 1.90
Subscript
[0] [1] [2] [3] [n]
Kirti Digholkar
Declaration of Array(C,C++)
◼Any array declaration contains:
➢ the array name,
➢ the element type
➢ and the array size. (+ ve integer constant >0)
➢ type name [size] ;
Examples: Simple declaration in C/C++
• int a[20], b[3],c[7];
• float f[5], c[2];
• char m[4], n[20];
◼int a[4]={1,3,5,2}; , float, b[3]={2.0, 5.5, 3.14};
Initialization
◼char name[4]= {‘E’,’m’,’r’,’e’}; int c[10]={0};
Kirti Digholkar
How is an array stored in memory?
Base
Address
1000
Address of 0th element is called as Base address of the array
Address of A[0] = &A[0] =1000
In C,C++,Java name of the array itself gives the base address of the array
A=&A[0] =1000 //for the array a[10]
Kirti Digholkar
Contiguous memory and Address calculation
Array a contiguous in memory.
int a[10];
1000 1004 1008 10012 1016 1036
10 20 30 40 50 …………………... 100
A[0] A[1] A[2] A[3] A[4] A[9]
1 2 3 4 5 10
Kirti Digholkar
Base Address : 1000
Find the address of A[3]?
address = 1000+3*(sizeof int ) //in c or
C++ 2 bytes for int
= 1000 +3*4
= 1012 // is it the correct ?
A[3] = 1006 //directly calculated from
Kirti Digholkar
base address.
How to read & print the elements of an array?
By reading them one element at a time By printing them one element at a
time
for (j=0; j <25; j++) for (j=0; j <25; j++)
{ {
cin>> a[j]; cout<< a[j] ;
} }
Kirti Digholkar
Examples for practice (1 –D Array)
◼ Read the set of students marks and calculate average of the class and then
check the whose marks are the grater than class average.
◼ Write a program which reads n students marks into 1-D array and then
calculates number of first class, second class and third class.
◼ Find the duplicate numbers in array.
◼ Find whether the elements are in ascending or descending order.
Kirti Digholkar
Using array in Functions
Write a program to accept array elements using functions
#include <iostream> void Accept( int num[10], int n)
using namespace std;
int main() {
{ for (int i = 0; i < n; i++)
int A[10], n; { cout<<“Enter number ” << i;
cout << "Enter 5 natural numbers: cin >> num[i];
"; }
cin>> n;
void Display(int num[10], int n)
Accept(A,n);
{
Display(A,n);
for (int i = 0; i < n; i++)
} { cout<<“Number ”<< i<<“is “<<num[i];
}
Kirti Digholkar
2 D Array
Kirti Digholkar
Declaration of 2D Array
◼Any array declaration contains:
➢ the array name,
➢ the element type
➢ and the array size. (+ ve integer constant >0)
➢ type name [size1] [size2];
Examples: Simple declaration in C/C++
• int a[20][20], b[3][4],c[7][1];
• float f[5][4], c[2][2];
• char m[4][2], n[20][10];
Kirti Digholkar
Initialization of the 2D Array
◼ It is the process of assigning initial values.
◼ Typically declaration and initialization are combined.
◼ Examples:
◼ int a[4][1]={1,3,5,2};
◼ float b[ ][3]={2.0, 5.5, 3.14,2.2,3.4,5.6,67.8,12,34,77.0};
◼ char name[ ][2]= {‘E’,’m’,’r’,’e’};
◼ int arr[2][3] = { 12, 34, 23, 45, 56, 45 } ;
◼ int arr[ ][3] = { 12, 34, 23, 45, 56, 45 }
Kirti Digholkar
Initializing a 2-Dimensional Array
While initializing a 2-D array it is necessary to
int stud[4][2] =
mention the second (column) dimension,
{
whereas the first dimension (row) is optional
{ 1234, 56 },
{ 1212, 33 },
{ 1434, 80 },
int arr[2][ ] = { 12, 34, 23, 45, 56, 45 } ;
{ 1312, 78 } int arr[ ][ ] = { 12, 34, 23, 45, 56, 45 } ;
}; Would never work.
OR
int stud[4][2] = { {12, 4}, {56, 12},{12, 33}, {14,34}} ;
Kirti Digholkar
Declaration of array cont…
• Through # define symbolic constant
• # define n 20
• # define m 10
int arr[n][m]; // array array of size 20.
char b[m][n];
• Without size through initialization.
int a[ ][m]={1,2,3,4};
Kirti Digholkar
Memory Map of a 2-Dimensional Array
•This is because memory doesn’t contain rows and
columns.
•In memory whether it is a one-dimensional or a two-
dimensional array the array elements are stored in
one continuous chain.
Kirti Digholkar
Application of Array :: Matrix data
structure : Memory Representations
1
a11 a12 a13 a14 a11
a12 2
a11
a a a a 3
a21
21 22 23 24 a13
4
a 31
a31 a32 a33 a34 34 a14
a21 5
a12
a22
n rows and m columns 6
a22 a32
i and j are the subscript of element. 7
a23 a13
8
Row-major order a24 a23
a31 9 a 33
Address (aij) = M + (i – 1) * n + j – 1
10
Column-major order a32 11 a14
Address (aij) = M + (j – 1) * m + i – 1 a33 a24
12
a34 a34
Kirti Digholkar Row Major order Column major order
a11 a12 a13
A= a21 a22 a23 Row Major
Column Major
Address Value
Address Value
0 a11
0 a11
1 a12
1 A21
2 a13
2 A12
3 A22 3 a21
4 A13 4 a22
5 a23 5 a23
Kirti Digholkar
row major order
The Location of element A[i, j] can be obtained by evaluating expression:
LOC (A [i, j]) = Base Address + W [M (i) + (j)]
Base Address is the address of first element in the array. 𝑎00 𝑎01 𝑎02 𝑎03
W is the word size. bytes occupied by each element. 𝑎10 𝑎11 𝑎12 𝑎13
𝑎20 𝑎21 𝑎22 𝑎23
N is number of rows in array. 3×4
M is number of columns in array.
Base Address = 2000, W= 2, M=4, N=2, i=1, j=2
LOC (A [i, j])=Base Address + W [M (i) + (j)]
LOC (A[1, 2])=2000 + 2 *[4*(1) + 2]
Kirti Digholkar
=2000 + 2 * [4 + 2] =2000 + 2 * 6 , =2000 + 12 , =2012
Assignment 1 Prerequisite
1. Basics of programming if, else, Loop, Array, Structure,
Functions
2. Class Object.
3. Structure object and related operations like array of structure
copy, delete of structure object.
Kirti Digholkar
Assignment 1
1. Write a program to generate SUM = sqr(1) + sqr(2) + sqr(3) + …+ sqr(N)
2. Palindrome Checking for number and character.
3. Write a C program that reads an integer n and stores the first n
Fibonacci numbers in an array.
4. Use structure for complex number and write a program to include
functions for addition, subtraction, multiplication, and division
5. Use class for student database and write a program to include functions
for addition, display and append .
Kirti Digholkar
