DATA STRUCTURES USING C [CSIT124]

LECTURE NOTES
MODULE- I
ARRAY

By Dr. Nancy Girdhar

 In this session we will talk… ASET

• Course outline and overview

– What is your ideas on Data Structures
– What are we going to study
– Why we will study this
– What are we going to learn
• Quizzes and assignments
• And about you all………

2
 Before we Start….. ASET

• Email: [email protected]

• Google Classroom Codes:

X Batch_Lab: v5t3ftw

Y Batch_Lab: tugcd3b

Theory_Lectures: dogxhmu
3
 Course Content
Module 1: Introduction to Data Structures

Module 2: Stacks and Queues

Module 3: Programming with Linked Lists

Module 4: Trees

Module 5: Searching and Sorting

Module 6: Graph and their Applications

 Module I : Introduction to Data Structures
• Definition, Types. Algorithm design, Complexity, Time-Space
Tradeoffs. Use of pointers in data structures.

• Array Definition and Analysis, Representation of Linear Arrays in

Memory, Traversing of Linear Arrays, Insertion And Deletion, Single
Dimensional Arrays, Two Dimensional Arrays, Multidimensional
Arrays, Function Associated with Arrays, Character String in C,
Character String Operations, Arrays as parameters, Implementing One
Dimensional Array, Sparse matrix.
 Contents to be Covered​

 Definition of Array
 Representation of Array in Memory
 Operations on array
 Address calculation for data stored in an array in 1D and 2D

6
 Abstract Data Type

• An abstract data type (ADT) is defined by its behavior from the

point of view of a user, which refers to a set of data values and
associated operations that are specified accurately,
independent of any particular implementation.

• With an ADT, we know what a specific data type can do, but
how it actually does it is hidden (Simply hiding the
implementation).
Data Structure : Array
9

Definitions
What is an Array?
Array is a data structure used to store homogeneous elements at contiguous
locations.

• A one-dimensional (1 D) array is a structured collection of components (often

called array elements) that can be accessed individually by specifying the
position of a component with a single index value.

• The syntax for creating a one-dimensional array:

<data type> <array name>[size];
e.g., int a[6];
 Data Structure - Arrays
• Array is a container which can hold fix number of items and these
items should be of same type.

• Important terms
• Element − each item stored in an array is called an element.
• Index − each location of an element in an array has a numerical
index which is used to identify the element.
 Array Representation
Index starts with 0
Array length is 10

Basic Operations
• Traverse − print all the array elements one by one.
• Insertion − add an element at given index.
• Deletion − delete an element at given index.
• Update − update an element at given index.
• Searching − search an element using given index or by value.
• Sorting – Arranging in Ascending or descending order
 1-D Arrays

Note: Size of an array must be provided before storing data.

 Array Initialization
• In C, it's possible to initialize an array during declaration.

For example,
/* declare and initialize and array*/

int x[6] = {19, 10};

 1-D Array
• If an array has a size 𝒏, we can store 𝒖𝒑𝒕𝒐 𝒏 number of elements in the array.
• However, what will happen if we store less than n number of elements.

For example,
/*store only 3 elements in the array*/
int x[6] = {19, 10, 8};

• Here, the array x has a size of 6. However, we have initialized it with only 3 elements.

• In such cases, random values (Garbage) is assigned to the remaining places.

 Operations on Arrays
1) Traversing an Array:
 2) Insertion in an Array
Step 1:

Find proper place to insert new element

Step 2:

Shift elements to the right to make room for new element

Step 3:

Insert new element

 3) Deletion in an Array

Step 1:
Find element to delete

Step 2:
Shift elements to the left to fill the gap

Step 3:
Decrease No. of elements in array by 1
4) Search in Array (Linear Search)
 Array Operations: Time Complexity
• Let size of array be 𝑛.
• Accessing Time: O(1) [This is possible because elements are stored at contiguous
locations]

• Search Time: O(n) for Sequential/Linear Search

O(log n) for Binary Search [If Array is sorted]

• Insertion Time: O(n) [The worst case occurs when insertion happens at the
Beginning of an array and requires shifting all of the elements]

• Deletion Time: O(n) [The worst case occurs when deletion happens at the
Beginning of an array and requires shifting all of the elements]
 2D Array (Matrix)
• The syntax for creating a two-dimensional array is:

<data type> <array name>[size of Dim1][size of Dim2];

e.g., int a[6][4];
21

Initializing a 2D Array
/* declare and initialize a 2D array*/

int a[3][2]; = { {19, 10},

{18, 17},
{9,15} };
 Storing 2D Arrays into Memory

There are two main techniques of storing 2D array

elements into memory:

1. Row Major ordering

3 4 5 2 8 4 1 4 5

3 4 5 2. Column Major ordering

2 8 4
a[2][3]
1 4 5
3 2 1 4 8 4 5 4 5
Calculating the Address of the random element of a 2D array

• By Row Major Order

Address(a[i][j]) = Base Address + (i * N + j) * size

Base_Address = 2000, W= 2, N=4, M=2, i=1, j=2

LOC (A [i, j]) = Base_Address + W* [N* (i) + (j)]

LOC (A[1, 2]) = 2000 + 2 *[4*(1) + 2]
= 2000 + 2 * [4 + 2]
= 2000 + 2 * 6
= 2000 + 12
= 2012
 Calculating the Address of the random element of a 2D array

• By Column Major Order

Address(a[i][j]) = ((j * M) + i) * size +Base Address

Base_Address = 2000, W= 2, N=4, M=2, i=1, j=2

LOC (A [i, j]) = Base_Address + W* [M* (j) + (i)]

LOC (A[1, 2]) = 2000 + 2 *[2*(2) + 1]
= 2000 + 2 * [4 + 1]
= 2000 + 2 * 5
= 2000 + 10
= 2010
N-D Arrays
 Sparse Matrix
 In computer programming, a matrix can be 1 0 0 0
defined with a 2-dimensional array. 0 0 5 0
0 0 0 1
 Any array with 'm' rows and 'n' columns 0 0 0 8
0 2 0 0
represents a 𝑚 ∗ 𝑛 matrix.
1 0 0 0
𝟔∗𝟒
Sparse Matrix
 There may be a situation in which a matrix (No. of zeros > No. of non-zeros)
contains more number of ZERO values than
NON-ZERO values. Such matrix is known as
Sparse Matrix.
 Sparse Matrix Representations

 Triplet Representation  Linked Representation

 Triplet Representation
 In this representation, we consider only non- zero values along with
their row and column index values.
 In this representation, the 0th row stores total rows, total columns and
total non-zero values in the matrix.
 For example, consider a matrix of size 5 ∗ 6 containing 6 number of non-
zero values. This matrix can be represented as shown

0 1 2 3 4 5

0
1
2
3
3
4
 0 1 2 3 4 5

0
1
2
3
3
4

 In above example matrix, there are only 6 non-zero elements ( those are 9, 8,
4, 2, 5 & 2) and matrix size is 5 ∗ 6.
 Here, the first row in the right side table is filled with values 5, 6 & 6 which
indicates that it is a sparse matrix with 5 rows, 6 columns & 6 non-zero
values.
 Second row is filled with 0, 4, & 9 which indicates the value in the matrix at
0th row, 4th column is 9. In the same way the remaining non-zero values also
follows the similar pattern.
 Linked List Representation
In linked list, each node has four fields. These four fields are defined as:

 Row: Index of row, where non-zero element is located.

 Column: Index of column, where non-zero element is located.
 Value: Value of the non zero element located at index – (row, column).
 Next node: Address of the next node
Linked Representation
 Linked Representation of Sparse Matrix in Memory
 We use Linked List data structure to represent a sparse matrix.
 In this linked list, we use two different nodes namely Header node and
Element node.
 Header node consists of three fields and Element node consists of five
fields as shown
Linked Representation of Sparse Matrix in Memory
Linked Representation of Sparse Matrix in Memory

 In above representation, H0, H1,...,H4 indicates the header nodes which are
used to represent indexes.

 Remaining nodes are used to represent non-zero elements in the matrix,

except the very first node which is used to represent abstract information
of the sparse matrix (i.e., it is a matrix of 4 ∗ 5 with 6 non-zero elements).

 In this representation, in each row and column, the last node right field
points to it's respective header node.
 Strength and Weakness of Arrays

Strength Weakness
Random Access possible (Fast Search Time) Slow Insertion/ Deletion Time
Less memory needed per element Fixed size once declared
Better cache locality Inefficient memory allocation/
utilization
 LetsTest
Draw the Sparse matrix for the following matrix using
Triplet representation
 LetsTest
Draw the Sparse matrix for the following matrix using
Triplet representation
 Fill up the table

Algorithm Best case Average case Worst case

Linear Search
O(1) O(n) O(n)

Binary Search O(1) O(logn) O(logn)

Bubble Sort O(n^2)

O(n) O(n^2)

Insertion Sort O(n) O(n^2) O(n^2)

Work for you….
1. Find the Serial no. of the person having phone number say “1234”
with the help of a telephone directory. Since telephone directory is
sorted by name not by numbers, we have to go through each and
every number of the directory.

2. A Library has list of books. Each book has unique id. The data base
has the book id in sorted order. Department has given the students
the book id rather the author name. Write a program to help the
students to search whether the particular book is available in the
library or not.
 Self Reading

• Go through some examples of how to create 1D and 2D arrays.

• Try to perform operations on 2D array:

1) Traversal
2) Search for an element
3) Update an element
 References
Textbooks: ​
•Yashwant Kanetkar,”Data Structure using C”, BPB Publication, 5th Edition ,2011
•A.Tannenbaum,Y. Lanhgsam and A.J. Augenstein ,” Data Structures Using C And C++ “,Prentice Hall of India,2nd
Edition,2009.
•Jean-Paul Tremblay, P.G Sorenson, “An Introduction to Data Structures with applications”, Mcgraw-Hill ,2nd Edition
,1984.

​Reference Book: ​
•Robert L Kruse, “Data Structure and Program Design in C”, Prentice Hall (1991).
•Noel Kalicharan ,“Data Structure in C” ,Ist Edition Create space publisher, 2008.
•Mark Allen Weiss,“Data Structure and algorithm Analysis in C”,2nd Edition AddisonWesley,1996.
•E. Balagurusamy, “Problem Solving through C language”, TMH publication, Fourth Edition, 2008.
•R.S Salaria ,“Data Structures & Algorithms using C”,Khanna Publication,4th Edition,2009
•E.Horowitz and S.Sahni,”Fundamentals of Data Structures in C “,2nd Edition, Universities Press,2008.
​

41
Thank you !