DATA

STRUCTURES
An Introduction
 Syllabus
Overview of data structure,
Basics of Algorithm Analysis including Running Time Calculations,
Abstract Data Types,
Arrays,
Arrays and Pointers,
Multidimensional Array,
String processing,
General Lists and List ADT,
List manipulations,
Single, Double and circular lists,
Stacks and Stack ADT,
Stack Manipulation, Prefix,
infix and postfix expressions,
recursion,
Queues and Queue ADT,
Queue manipulation
Textbook(s): 1. Richard Gilberg , Behrouz A. Forouzan, “Data Structures: A Pseudocode
Approach with C, 2nd Edition, Cengage Learning, Oct 2004 2. E. Horowitz, S. Sahni, S.
Anderson-Freed, "Fundamentals of Data Structures in C", 2nd Edition, Silicon Press (US),
2007.
2
Basic Terminology
• Data: Data may be a single value or it may be a set of
values.
• Information: Meaningful or Processed data is called
Information.
• Record is a collection of related data item.
• File is a collection of logically related records.
• Entity
• is a person, place, thing, event or concept about which information
is recorded.
• has certain attributes or properties which may be assigned values.
• Attributes gives the characteristics of the entity.
• Entity set: Entities with similar attributes forms an Entity
Set.
• Range is a set of all possible values that could be
assigned to a particular attribute. 3
 Data Structures
• Logical or mathematical model of a particular organization of data
is called a Data Structure.
• Data structures are the building blocks of the program.
• The selection of a particular data structure stresses on following:
• The data structure must be rich enough in structure to reflect the
relationship existing between the data.
• The structure should be so simple that data can be processed effectively
whenever required.

ALGORITHM + DATA STRUCTURE =

PROGRAM

4
Classification of Data Structures

• Data structures are normally divided into two broad categories:

• Primitive data structures
• Basic data structures that are directly operated upon by machine instruction.
• Available in most programming languages as built-in types.
• E.g. int, float, char, pointer
• Non-primitive data structures
• These data structures are a set of homogenous and heterogeneous data
elements stored together.

5
Types of Data Structure

6
Non-primitive data structures

• These are further classified as:

• Linear data structure
• A data structure is said to be linear if its elements forms any sequence
• Non-linear data structure
• Represents data containing hierarchical relationship between elements
e.g. trees, graphs

7
Data Structure Operations

• The choice of data structure depends on the frequency with

which specific operations are performed.
• Operations that can be performed are:
• Traversing
• Searching
• Insertion
• Deletion
• Sorting
• Merging

8
• Traversing
• Accessing each record exactly once so that certain items in the record may
be processed.
• Searching
• Finding the location of the record with a given key value, or finding the
location of all records satisfying one or more conditions.
• Insertion
• Adding a new record to the structure.
• Deletion
• Removing a record from a structure.
• Sorting
• Arranging the records in some logical order
• Merging
• Combining the records in two different sorted files into a single sorted file.

9
 Data types
• Each variable in C has its associated data type.
• Each data type requires different amount of memory.
• Some commonly known basic data types are:
• int
• Used to store an integer
• Requires 2 bytes of memory
• char
• Stores a single character
• Requires one byte of memory
• float
• Used to store decimal numbers with single precision
• double
• Used to store decimal numbers with double precision

10
11
12
13
Algorithm
• An algorithm is a sequence of steps to solve a problem.

• An algorithm can be expressed in English like language, called

Pseudocode.

• There may be more than one algorithms to solve a problem.

• The choice of a particular algorithm depends on the following

considerations:
• Memory requirements (Space complexity)
• Performance requirements (Time Complexity)

14
Complexity of Algorirthms

• Space Complexity
• It is the amount of memory needed to run to completion.
• Time Complexity
• It is the amount of time needed to run to completion

15
Characteristics of an algorithm
An algorithm should have the following characteristics:

• Definiteness/ Unambiguity
• Each step of the algorithm must be clearly and precisely defined and there
should not be any ambiguity.
• Input
• An algorithm must have zero or more but finite number of inputs
• Output
• An algorithm must have one desirable output.
• Finiteness
• An algorithm must always terminate after a finite number of steps in finite
amount of time.
• effectiveness
• An algorithm should be effective.
• Each of the operation to be performed in an algorithm must be sufficiently basic
that it can be done exactly and in a finite length of time
• Independent
• An algorithm should have step-by-step directions, which should 16be
independent of any programming code.
 Algorithmic Notations
• The format for the formal presentation of an algorithm consists of
two parts:
• First part is a paragraph which tells:
• the purpose of the algorithm
• identifies the variables which occur in the algorithm
• lists the input data
• The second part of the algorithm consists of the lists of steps that is to be
executed.

17
An Example Algorithm
A non-empty array DATA with N numerical values is given. Find the
location LOC and the value MAX of the largest element of DATA.

Algorithm: Given a nonempty array DATA with N numerical values,

this algorithm finds the location LOC and the value MAX of the
largest element of DATA. The variable K is used as a counter.

18
Steps, Control, Exit
• The steps of the algorithm are executed one
after the other, beginning with step 1.

• Control may be transferred to step n by the

statement “Go to step n”.

• If several statements appear in the same step,

• e. g. Set K : = 1, LOC : =1 and MAX :
=DATA[1].
• They are executed from left to right.

• The algorithm is completed when the statement

“Exit” is encountered.
• Comments
• Each step may contain a comment in brackets which indicates the main
purpose of the step.
• Variable Names
• Variable names will use capital letters even though lowercase may be
used for these same variables.
• Assignment statements
• These statements will use dots-equal notation :=
• E.g. MAX:=DATA[1]
• Assigns the value of DATA[1] to MAX
• Input and Output
• Data may be read or may be output by means of read and write
statements.
• Read: Variable names
• Write: Messages and/or variable names
• Procedures
• Used for independent algorithmic module (or subalgorithm) which solves a
particular problem

20
Control Structures
• Algorithms mainly uses three types of logic or flow of control such
as:
• Sequence Logic, or sequential flow
• Selection Logic, or conditional flow
• Iteration Logic, or repetitive flow
• Sequential Logic

21
 Selection Logic
• Selecting on out of several alternative modules.
• These are called conditional structures
• End of such statement can be indicated by statement:
[End of If Structure.]

• These structures are divided into three categories:

• Single alternative
• Double alternative
• Multiple alternative

22
• Single Alternative

• Double Alternative

• Multiple Alternative

23
Iteration Logic

• Begins with a Repeat statement

• Followed by a module called body of loop
• End of such statement can be indicated by statement:
[End of loop.]

24
25
Algorithm: Quadratic Equation

26
Complexity of Algorithms

• To measure the efficiency of algorithms, we must have some

criteria.
• Time and Space are the two main measures for the efficiency of
an algorithm i.e.
• Time Complexity
• Space Complexity

27
• The complexity of an algorithm M is the function f(n) which gives
the running time and storage space requirement of the algorithm in
terms of size n of the input data.

• In simple words, the complexity of the algorithm will depend on the

number of statement executed.
• The total number of statements executed will depend on
conditional statements.

28
Example
• E.g.
i=0; // (1 time)
while (i<n) // (n+1 times)
{
printf(“%d”,&i); // (n times)
i=i+1; // (n times)
}

• Total number of executions

= 1+(n+1)+(n)+(n)
= 3n+2

• If we ignore constants, complexity of the order n.

• Hence the complexity,
O(n) //Big-Oh Notation
29
 Finding the complexity
• There are three cases to find the complexity:
• Worst case: maximum value of f(n) for any possible input
• Average case: expected value of f(n).
• Sometimes Best case can also be considered as minimum possible
value of f(n).
• E.g.
• number n1, n2, ……., nk occur with respective probabilities p1, p2, ……., pk.
• Expected or Average value E is given by:
E=n1p1 + n2p2 + ……. + nkpk.

30
Linear Search

31
• The complexity of the searching algorithm is given by the number
C of comparisons between ITEM and DATA[K].

• Worst case
• When ITEM is the last element in the array DATA.
• When ITEM does not exist in the list.
• Then, C(n)=n

• Average case
• It is equally likely to occur at any position in the array.
• The number of comparisons can be any number 1,2,3,….,n
• Each number occurs with probability p=1/n.

32
Rate of Growth: Big O Notation
• Suppose,
• M is an algorithm
• n is the size of input data
• Then, complexity f(n) of M increases as n increases.

33
• Suppose f(n) and g(n) are the functions defined on positive
integers.
• F(n) is bounded by some multiple of g(n) for all n.

• There exists a positive integer n0 and a positive number M such

that for all n>no, we have,
|f(n)| <= M|g(n)|

• Then, f(n) = O(g(n))

• It can be read as “f(n) is of order g(n)”.
• E.g.

34
Omega Notation (Ω)

• The Big-O notation defines an upper bound function g(n) for f(n)
which represents the time/space complexity of the algorithm.
• In Omega notation, the function g(n) defines the lower bound
for function f(n).
• There exists a positive integer n0 and a positive number M such
that for all n>no, we have,
|f(n)| >= M|g(n)|

35
Theta Notation (θ)

• It is used when function f(n) is bounded both from above and

below by the function

36
 Arrays
• An array is a finite set of homogenous data elements.
• Stored in consecutive memory locations.
• The elements of array are referenced respectively by an index set
consisting of n consecutive numbers.

• The number n of elements is called the length or size of the array.

Length=UB-LB+1

Where,
• UB – largest index, called Upper Bound
• LB – smallest index, called Lower bound

Length=UB when LB=1

37
• The elements of array A may be denoted by:
• Subscript notation
A1, A2, A3, ……., An
• Parenthesis notation
A(1), A(2), …… , A(N)
• Bracket notation
A[1], A[2], A[3], …… ,A[N]

• The number K in A[K] is called subscript or index.

• A[K] is called subscripted variable.

38
Representation of Array

Example

39
 Representation of Array in memory
Let LA be a linear array in memory.
LOC(LA[K]) = Base(LA) + w(K-lower bound), where
Base(LA): Starting address of the array in memory.
w: Size of each element in bytes.
K: Position (index) of the element we want to find.
LowerBound: Starting index of the array (usually 0).

Eg: If Base(LA)= 1000,w = Size of each element = 4 byte, Find the

address of LA[3]
Sol) LOC(LA[3])=1000+4(3−0)
LOC(LA[3]) = 1000 + 4(3 - 0)
LOC(LA[3])=1000+4(3)=1000+12
LOC(LA[3]) = 1000 + 4(3) = 1000 + 12= 1012

40
Operations on Arrays

• Traversing
• Accessing or processing (visiting) each element of array exactly once
• Insertion
• To insert an element into array
• Deletion
• To delete element from array
• Searching
• To search any element from the given list
• Sorting
• To sort the given list of elements

41
 Algorithm: Traversing
• LA is a linear array with lower bound LB and upper bound UB. This
algorithm traverses LA applying an operation PROCESS to each
element of LA.

• Alternate algorithm

42
Insertion into Linear Array

43
Deletion into Linear Array

44
Binary search
• By using this technique, element can searched in minimum
possible comparisons.
• This given list of elements should be in sorted order.
• It can be done as follows:
• Find the middle element of the array
• Compare the mid element with an item to search.
• There are three cases:
• If it is the desired element, search is successful.
• If mid is greater than desired item, search only the left half of array.
• Else If mid is less than desired item, search only the right half of array.

• Complexity of Binary Search O(log2n)

45
46
 Two-dimensional Arrays
• A two dimensional m×n array A is a collection of m·n data
elements.
• Each element is specified by a pair of integers (such as J, K),
called subscripts such that
1 ≤ J ≤ m and 1≤K≤n
• It is denoted by
• AJ,K or A[J,K]

• Two dimensional arrays are called matrix

arrays.

47
Two-dimensional array

48
Representation of 2-D array in memory

49
• Following formula can be applied to locate a particular address:
• Column major order
• LOC(A[J,K]) = Base(A) + w(M(K-1)+(J-1))
• Row major order
• LOC(A[J,K]) = Base(A) + w(N(J-1)+(K-1))

50
Example

51
Bubble Sort

52
Selection Sort

53
Insertion Sort

54
Complexity of Insertion Sort
• Worst Case
• When array A is in reverse order
• (k-1) comparisons

• Average Case
• Approximately (k-1)/2 comparisons

55
 Multi-dimensional Arrays
• A multi-dimensional or n-dimensional array m1×m2×……..×mn array
B is a collection of m1·m2·……..·mn data elements.
• Each element is specified by a list of n integers (such as K1, K2,
….., Kn), called subscripts such that
1 ≤ K1 ≤ m1, 1 ≤ K2 ≤ m2, ………, 1 ≤ Kn ≤ mn
• It is denoted by
• B K , K , ….., K or B[K1, K2, ….., Kn]
1 2 n

56
Multi-dimensional Arrays

• Length Li can be calculated as

Li = upper bound – lower bound + 1
• For a given subscript Ki, effective index Ei of Li is the number of
indices preceding Ki in the index set.
Ei = Ki - lower bound

57
58
• Column major order

• Row major order

59
An Example:

60
Recursion
• Recursion is a process in which a function calls itself with an
argument.

• A recursive procedure must have following two properties:

• There must be certain criteria, called base criteria, for which the procedure
does not call itself.
• Each time the procedure calls itself, it must be closer to the base criteria.
• A recursive procedure with these two properties is said to be well
defined.

• It is of two types:
• Direct recursion
• When a function class itself
• Indirect recursion
• When two functions calls one another mutually.

61
62
 Factorial Function
• The product of positive integers from 1 to n is called “n factorial”
denoted by n!
n!=1·2·3·……(n-2) ·(n-1) ·n
or, n!=n· (n-1)!

• Formal Definition (Factorial function)

• If n=0, then n!=1
• If n>0, then n!=n· (n-1)!

63
Algorithm: Factorial Function

64
Fibonacci Sequence

• Fibonacci sequence is as follows:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……………..
• Here,
F0=0 and F1=1
• Each succeeding term is the sum of two preceding terms

• Formal Definition:
• If n=0 or n=1, then Fn=n
• If n>1, then Fn=Fn-2 + Fn-1

65
Algorithm: Fibonacci Sequence

66
Example

67
68
69