Data Structure Using C

Dr. Nachiket Tapas

Scheme

Course Course End Semester Class Test Teacher

Subject Code Exam Assessment
Data A000272 100 20 20
Structure (022)
Using C
Data A000291 40 - 20
Structure (022)
Using C
Lab
Exams
There can be surprise quizzes during the lectures.
There will be an End Semester Exam (ESE) for 100 Marks.
There will be two class tests before the ESE each for 20 marks.
Syllabus
● FUNDAMENTAL CONCEPTS

Introduction to Data Structures: Data, Data Objects, Data Types ,Abstract Data
Type (ADT) and data structures, Concepts of static and dynamic, linear and
nonlinear data structures.
Introduction to Algorithms: Definition and Characteristics of an algorithm.
Algorithm design tools – flowcharts and pseudo code, notations – algorithm
header, purpose, conditions and selection, loops, procedures and sub-algorithms.
Program development: Analysis, Design, Coding, Testing and Verification.
Contd.
● LINEAR DATA STRUCTURES USING SEQUENTIAL ORGANIZATION, SEARCHING AND
SORTING

Concept of sequential organization, arrays as ADT, Storage representation of array, Matrix

operations using arrays,

String operations (Length, Concatenation, Copy, Palindrome, Reverse, Compare, Substring) without
using library functions,

Searching: linear and binary search algorithms.

Sorting: General concepts–Bubble sort, Insertion sort, Selection sort, Heap sort, Merge sort, Quick
sort.
Contd.
● ALGORITHM ANALYSIS AND ALGORITHM DESIGN STRATEGIES

Algorithm Analysis: Time Complexity–Bigoh ‘O’, Omega ‘Ω’, Theta ‘θ’,

Best, Average and Worst case analysis: binary search, quick sort, merge sort,
insertion sort.

Algorithmic Strategies: Divide and Conquer (quick sort and Tower of

Hanoi),Backtracking(n-queens problem), greedy (job scheduling), dynamic
programming, branch and bound.
Contd.
● LISTS

List as ADT, Concept of linked organization of data against linked list.

Singly linked list, doubly linked list, circular linked list.

Representation & manipulations of polynomials/sets using linked lists.

Dynamic memory management. Representation of sparse matrix. Addition and

transpose of sparse matrix
Contd.
● STACKS AND QUEUES

Stack and queue as ADT. Operations on stack and queue. Implementations using
arrays and dynamic memory allocation. Application of stack for expression
evaluation, expression conversion. Recursion and stacks
Contd.
● TREES AND GRAPHS

Basic terminology. Binary trees and its representation. Binary tree traversals
(recursive and non-recursive) and various operations. Insertion and deletion of
nodes in binary search tree.

Representation of graphs using adjacency matrix, adjacency list. Implementation of

algorithms for traversals; implementing Kruskal's, Prim's algorithms. Single source
shortest paths using Dijkstra’s algorithm.

Applications of graphs and trees.

Labs
In each lab you will be given few problems to solve
● You need to prepare the practical file with solution to problems.

● You must work on your own.

● Discussion is allowed, but sharing of code in any form is NOT permitted.

Front Page Index Page

Textbooks
Y. Langsam, M. Augenstin and A. Tannenbaum, “Data Structures using C”, Pearson Education Asia,
First Edition, 2002, ISBN 978-81-317-0229-1.

E.Horowitz, S.Sahni, S.Anderson Freed,“Fundamentals of Data Structures in C”,Second Edition,

University Press, ISBN 978-81-7371-605-8

C, Prentice Hall of India, Second Edition, ISBN81-203-0596-5

Ellis Horowitz, S. Sahni, D. Mehta “Fundamentals of Data Structures in C++”, Galgotia Book Source,
New Delhi.

Jean-Paul Tremblay, Paul. G. Soresan, “An introduction to data structures with Applications”, Tata
Mc- Graw Hill International Editions, 2nd edition 1984,ISBN-0-07-462471-7.
Course Objective
To teach how to design a new user defined, efficient, data types array, stack, queue, list,
tree, graph, etc. abstract data types and reusable code using object based design
techniques.

To demonstrate good programming practices, coding standards, modular programming,

procedural and object-based way of thinking.

To emphasize the design aspects of a new data structure for solving any real life problems.

To lay strong emphasis on time complexity analysis techniques and algorithm design
techniques.
Let’s Begin
Algorithm
● A formula or set of steps for solving a particular problem.
● To be an algorithm, a set of rules must be unambiguous and have a clear
stopping point.
● Algorithm can be defined as: “A sequence of activities to be processed for get
ting desired output from a given input.”
Properties
● Finiteness
● Definiteness
● Input
● Output
● Effectiveness
Finiteness
● An algorithm must always terminate after a finite number of steps.
● It means after every step one reaches closer to solution of the problem and
after a finite number of steps algorithm reaches to the solution.
Definiteness
● Each step of algorithm must be precisely defined.
● Also the actions must be defined unambiguously for each activity in the
algorithm.
Input
● Any operation you perform need some beginning value/quantities associated with
different activities in the operation.
● So the value/quantities are given to the algorithm before it begins.
Output
● One always expects output/result (expected value/quantities) in terms of
output from an algorithm.
● The result may be obtained at different stages of the algorithm.
● If some result is from the intermediate stage of the operation then it is known
as intermediate result and result obtained at the end of algorithm is known as
end result.
● The output is expected value/quantities always have a specified relation to
the inputs.
Effectiveness
● Algorithms to be developed/written using basic operations.
● Actually operations should be basic, so that even they can in principle be
done exactly and in a finite amount of time by a person, by using paper and
pencil only.
Problem-1
● Write an algorithm to print “Hello World”
Problem-1
● Write an algorithm to print “Hello World”

Step 1: Start
Step 2: Print “Good Morning‟
Step 3: Stop
Problem-2
● Write an algorithm to find area of a rectangle.
Problem-2
● Write an algorithm to find area of a rectangle.

Step 1: Start
Step 2: Take length and breadth and
store them as L and B?
Step 3: Multiply by L and B and store it
in area
Step 4: Print area
Step 5: Stop
Problem 3
● Write an algorithm to check whether she/he is eligible to vote? (more than or
equal to 18 years old).
Problem 3
● Write an algorithm to check whether she/he is eligible to vote? (more than or
equal to 18 years old).

Step 1: Start
Step 2: Take age and store it in age
Step 3: Check age value, if age >= 18 then go to step 4 else step 5
Step 4: Print “Eligible to vote” and go to
step 6
Step 5: Print “Not eligible to vote”
Step 6: Stop
Problem 4
● Write an algorithm to check whether given number is +ve, -ve or zero.
Problem 4
● Write an algorithm to check whether given number is +ve, -ve or zero.

Step 1: Start
Step 2: Take any number and store it in n.
Step 3: Check n value, if n > 0 then go to
step 5 else go to step 4
Step 4: Check n value, if n < 0 then go to
step 6 else go to step 7
Step 5: Print “Given number is +ve”and go
to step 8
Step 6: Print “Given number is -ve” and go
to step 8
Step 7: Print “Given number is zero”
Problem 5
● Program to find the factorial of a number
Problem 5
● Program to find the factorial of a number

Step 1: Start.
Step 2: Initialize variables.
Step 3: Check FOR condition.
Step 4: If the condition is true, then go to step 5 otherwise go to step 7.
Step 5: f = f * i.
Step 6: Go to step 3.
Step 7: Print value of factorial.
Step 8: Stop.
Algorithm vs Program vs Data Structure
● An Algorithm is an outline, the essence of a computational procedure, step-
by-step instructions.
● A Program is an implementation of an algorithm in some programming
language.
● A Data Structure is an organization of data needed to solve the problem.
Example: Algorithm
matrixMultiply(A, B):
Assume dimension of A is (m x n), dimension of B is (p x q)
Begin
if n is not same as p, then exit
otherwise define C matrix as (m x q)
for i in range 0 to m - 1, do
for j in range 0 to q – 1, do
for k in range 0 to p, do
C[i, j] = C[i, j] + (A[i, k] * A[k, j])
done
done
done
End
Contd: Program
#include<stdio.h>
#include<stdlib.h>
int main(){
int a[10][10],b[10][10],mul[10][10],r,c,i,j,k;
// row and column input, Input matrix 1, Input matrix 2
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
mul[i][j]=0;
for(k=0;k<c;k++)
{
mul[i][j]+=a[i][k]*b[k][j];
}
}
}
// Remaining code
}
Data Structure
● In the matrix multiplication problem, we used two dimensional array to
represent the matrix. This makes the machine representation closer to the
mathematical representation of the matrix.
Algorithmic Problem

Specification
Specification Algori of Output as
?
of Input thm function of
Input

There can be infinite number of input instances satisfying the specification.

Ex – You can select any random two matrices for multiplication. There dimensions
can be different, their elements can be different.

Algorithm defines actions on the input instance.

Algorithms in Ordinary Life?
An algorithm is a familiar concept: cooking recipes are almost algorithms! (not
quite precise enough for a computer)

Write an algorithm for temperature conversion.

Algorithm
● Start ● Start
● Initialize F=0, C=0 ● Initialize F=0, C=0
● Read C ● Read F
● F = (1.8*C) + 32 ● C = (F-32) * 5 / 9.0
● Print or display F ● Print or display C
● Stop ● Stop
Problems
● Write an algorithm that exchanges the value of two variables: x and y. The output
must be: the value of variable y will become the value of variable x, and vice versa.
● Design an algorithm to find the circumference of a circle. Use the formula: C=2πr,
where π is approximately equivalent 3.1416.
● Write an algorithm to compute the radius of a circle given the area. Derive your
formula from the given equation: A=πr², then display the output.
Data vs Data Object vs Data Type
● Data:
○ 1,2,3,4...
○ a,b,c,d,...
○ A,B,C,D,...
○ ...

int a; //Variable declaration

● Data Object (int a)

○ name : a
○ address : 101101
○ data type: int
ADT (Abstract Data Type): What and Why?
● Now there might be a situation when we need operations for our user-defined data
type which have to be defined.
● To simplify the process of solving problems, we can create data structures along with
their operations, and such data structures that are not in-built are known as Abstract
Data Type (ADT).
● The definition of ADT only mentions what operations are to be performed but not
how these operations will be implemented. It does not specify how data will be
organized in memory and what algorithms will be used for implementing the
operations. It is called “abstract” because it gives an implementation-independent
view.
Array
● An array is a collection of data items stored at contiguous memory locations.
● The idea is to store multiple items of the same type together.
● This makes it easier to calculate the position of each element by simply adding an
offset to a base value, i.e., the memory location of the first element of the array
(generally denoted by the name of the array).
Linked List
● Like arrays, Linked List is a linear data structure.
● Unlike arrays, linked list elements are not stored at a contiguous location; the
elements are linked using pointers.
Stack
● Stack is a linear data structure which follows a particular order in which the
operations are performed.
● The order may be LIFO(Last In First Out) or FILO(First In Last Out). In stack, all
insertion and deletion are permitted at only one end of the list.
Operations
1. push() – Insert an element at one end of the stack called top.
2. pop() – Remove and return the element at the top of the stack, if it is not empty.
3. peek() or Top() – Return the element at the top of the stack without removing it, if
the stack is not empty.
4. size() – Return the number of elements in the stack.
5. isEmpty() – Return true if the stack is empty, otherwise return false.
6. isFull() – Return true if the stack is full, otherwise return false.
Queue
● Like Stack, Queue is a linear structure which follows a particular order in which the
operations are performed.
● The order is First In First Out (FIFO).
● In the queue, items are inserted at one end and deleted from the other end.
● A good example of the queue is any queue of consumers for a resource where the
consumer that came first is served first.
Operations
• Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an
Overflow condition.
• Dequeue: Removes an item from the queue. The items are popped in the same order
in which they are pushed. If the queue is empty, then it is said to be an Underflow
condition.
• Front: Get the front item from the queue.
• Rear: Get the last item from the queue.
Binary Tree
● Unlike Arrays, Linked Lists, Stack and queues, which are linear data structures, trees
are hierarchical data structures.
● A binary tree is a tree data structure in which each node has at most two children,
which are referred to as the left child and the right child.
● It is implemented mainly using Links.
● A Binary Tree is represented by a pointer to the topmost node in the tree. If the tree is
empty, then the value of root is NULL.
Binary Search Tree
● In Binary Search Tree is a Binary Tree with the following additional properties:
○ The left subtree of a node contains only nodes with keys less than the node’s key.
○ The right subtree of a node contains only nodes with keys greater than the node’s key.
○ The left and right subtree each must also be a binary search tree.
Heap
● A Heap is a special Tree-based data structure in which the tree is a complete binary
tree.
● Generally, Heaps can be of two types:
○ Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at
all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
○ Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present
at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree.
Hashing Data Structure
● Hashing is an important Data Structure which is designed to use a special function
called the Hash function which is used to map a given value with a particular key for
faster access of elements.
● The efficiency of mapping depends on the efficiency of the hash function used.
● Let a hash function H(x) maps the value x at the index x%10 in an Array. For
example, if the list of values is [11, 12, 13, 14, 15] it will be stored at positions {1, 2,
3, 4, 5} in the array or Hash table respectively.
Trie
● Trie is an efficient information reTrieval data structure.
● Using Trie, search complexities can be brought to an optimal limit (key length).
● Why?
1. With Trie, we can insert and find strings in O(L) time where L represent the length of a
single word. This is obviously faster than BST. This is also faster than Hashing because
of the ways it is implemented. We do not need to compute any hash function. No
collision handling is required (like we do in open addressing and separate chaining)
2. Another advantage of Trie is, we can easily print all words in alphabetical order which is
not easily possible with hashing.
3. We can efficiently do prefix search (or auto-complete) with Trie.
Example
Phases of program development
● Problem Definition.
● Problem Analysis.
● Algorithm Development.
● Coding & Documentation.
● Testing & Debugging.
● Maintenance.
Problem Definition
● Here, we define the problem statement and decide the boundaries of the
problem.
● In this phase, we need to understand what is the problem statement, what is
our requirement and what is the output of the problem solution.
● All these are included in the first phase of program development life cycle.
Problem Analysis
● Here, we determine the requirements like variables, functions, etc. to solve
the problem.
● It means that we gather the required resources to solve the problem, which
are defined in the problem definition phase.
● Here, we also determine the bounds of the solution.
Algorithm Development
● Here, we develop a step-by-step procedure that is used to solve the problem
by using the specification given in the previous phase.
● It is very important phase for the program development.
● We write the solution in step-by-step statements.
Coding & Documentation
● Here, we use a programming language to write or implement the actual
programming instructions for the steps defined in the previous phase.
● We construct the actual program in this phase.
● We write the program to solve the given problem by using the programming
languages like C, C++, Java, etc.
Testing & Debugging
● In this phase, we check whether the written code in the previous step is
solving the specified problem or not.
● This means, we try to test the program whether it is solving the problem for
various input data values or not.
● We also test if it is providing the desired output or not.
Maintenance
● In this phase, we make the enhancements. Therefore, the solution is used by
the end-user.
● If the user gets any problem or wants any enhancement, then we need to
repeat all these phases from the starting, so that the encountered problem is
solved or enhancement is added.
Thank You!!