Document Text Contents
Page 1
DATA STRUCTURES WITH C
(Common to CSE & ISE)
Subject Code: 10CS35 I.A. Marks : 25
Hours/Week : 04 Exam Hours: 03
Total Hours : 52 Exam Marks: 100
PART – A
UNIT - 1 8 Hours
BASIC CONCEPTS: Pointers and Dynamic Memory Allocation, Algorithm Specification, Data Abstraction,
Performance Analysis, Performance Measurement
UNIT - 2 6 Hours
ARRAYS and STRUCTURES: Arrays, Dynamically Allocated Arrays, Structures and Unions, Polynomials,
Sparse Matrices, Representation of Multidimensional Arrays
UNIT - 3 6 Hours
STACKS AND QUEUES: Stacks, Stacks Using Dynamic Arrays, Queues, Circular Queues Using Dynamic
Arrays, Evaluation of Expressions, Multiple Stacks and Queues.
UNIT - 4 6 Hours
LINKED LISTS: Singly Linked lists and Chains, Representing Chains in C, Linked Stacks and Queues,
Polynomials, Additional List operations, Sparse Matrices, Doubly Linked Lists
PART - B
UNIT - 5 6 Hours
TREES – 1: Introduction, Binary Trees, Binary Tree Traversals, Threaded Binary Trees, Heaps.
UNIT - 6 6 Hours
TREES – 2, GRAPHS: Binary Search Trees, Selection Trees, Forests, Representation of Disjoint Sets, Counting
Binary Trees, The Graph Abstract Data Type.
UNIT - 7 6 Hours
PRIORITY QUEUES Single- and Double-Ended Priority Queues, Leftist Trees, Binomial Heaps, Fibonacci
Heaps, Pairing Heaps.
UNIT - 8 8 Hours
EFFICIENT BINARY SEARCH TREES: Optimal Binary Search Trees, AVL Trees, Red-Black Trees, Splay
Trees.
Text Book:
1. Horowitz, Sahni, Anderson-Freed: Fundamentals of Data Structures in C, 2nd Edition, University Press,
2007.
(Chapters 1, 2.1 to 2.6, 3, 4, 5.1 to 5.3, 5.5 to 5.11, 6.1, 9.1 to 9.5, 10)
Page 2
TABLE OF CONTENTS
UNIT 1: BASIC CONCETPS 1-12
UNIT 2: ARRAYS & STRUCTURES 13-26
UNIT 3: STACKS & QUEUES 27-36
UNIT 5: TREES 37-50
UNIT 6: TREES(CONT.) & GRAPHS 51-62
Page 32
DATA STRUCTURES WITH C
The place where your greatest fears live is also the place where your greatest growth lies.
30
QUEUES
• This is an ordered-list in which insertions & deletions take place at different ends (Figure 3.4).
• The end at which new elements are added is called the rear &
the end from which old elements are deleted is called the front.
• Since first element inserted into a queue is first element removed, queues are known as FIFO lists.
structure Queue is
objects: a finite ordered list with zero or more elements.
functions:
for all queue Queue, item element, max_ queue_ size positive integer
Queue CreateQ(max_queue_size) ::=
create an empty queue whose maximum size is max_queue_size
Boolean IsFullQ(queue, max_queue_size) ::=
if(number of elements in queue == max_queue_size)
return TRUE
else
return FALSE
Queue AddQ(queue, item) ::=
if (IsFullQ(queue))
queue_full
else
insert item at rear of queue and return queue
Boolean IsEmptyQ(queue) ::=
if (queue ==CreateQ(max_queue_size))
return TRUE
else
return FALSE
Element DeleteQ(queue) ::=
if (IsEmptyQ(queue))
return
else
remove and return the item at front of queue
ADT 3.2: Abstract data type Queue
• The CreateQ() function can be implemented as follows
Queue CreateQ(maxQueueSize)::=
#define MAX_QUEUE_SIZE 100
struct element
{
int key;
};
element queue[MAX_QUEUE_SIZE];
int rear=-1;
int front=-1;
Boolean IsEmptyQ(queue)::= front==rear;
Boolean IsFullQ(queue)::= rear=MAX_QUEUE_SIZE-1;
void addq(int rear, element item)
{
if (rear == MAX_QUEUE_SIZE_1)
{
queue_full( );
return;
}
queue [++rear] = item;
}
element deleteq(int front, int rear)
{
if ( front == rear)
return queue_empty( );
return queue [++ front];
}
Program 3.5: Add to a queue Program 3.6: Delete from a queue
Page 33
DATA STRUCTURES WITH C
The law of attraction says that we attract into our life that which we focus on.
31
JOB SCHEDULING
• Queues are used for the creation of a job-queue by an operating-system (Figure 3.5).
• If operating-system does not use, then the jobs are processed in the order they enter the system.
CIRCULAR QUEUE
• In a circular-queue, the elements are arranged implicitly in a circle (Figure 3.7).
• When the array is viewed as a circle, each array position has a next and a previous position.
void addq(int front, int rear, element item)
{
rear = (rear +1) % MAX_QUEUE_SIZE;
if (front == rear) /* reset rear and print error */
return;
queue[rear] = item;
}
Program 3.7: Add to a circular queue
element deleteq(int front, int rear)
{
element item;
if (front == rear)
return queue_empty( ); /* queue_empty returns an error key */
front = (front+1) % MAX_QUEUE_SIZE;
return queue[front];
}
Program 3.8: Delete from a circular queue
Page 63
DATA STRUCTURES WITH C
You can expect only that which you inspect.
61
GRAPH REPRESENTATIONS
• Three commonly used representations are:
1) Adjacency matrices,
2) Adjacency lists and
3) Adjacency multilists
Adjacency Matrix
• Let G=(V,E) be a graph with n vertices, n>=1.
• The adjacency matrix of G is a two-dimensional n*n array( say a) with the property that a[i][j]=1 iff
the edge (i,j) is in E(G). a[i][j]=0 if there is no such edge in G (Figure 6.7).
• The space needed to represent a graph using its adjacency matrix is n
2
bits.
• About half this space can be saved in the case of undirected graphs by storing only the upper or
lower triangle of the matrix.
Figure 6.7 Adjacency matrices
Adjacency Lists
• The n rows of the adjacency matrix are represented as n chains.
• There is one chain for each vertex in G.
• The data field of a chain node stores the index of an adjacent vertex (Figure 6.8).
• For an undirected graph with n vertices and e edges, this representation requires an array of size n
and 2e chain nodes.
Figure 6.8 adjacency lists
Page 64
DATA STRUCTURES WITH C
Failure reawakens us to who we really are & to what we truly want, & it shakes us out of our complacency.
62
Adjacency Multilists
• Each edge (u,v) is represented by two entries, one on the list for u and the other on the list for v.
• The new node structure is
Figure 6.12:Adjacency multilists for G1
DATA STRUCTURES WITH C
(Common to CSE & ISE)
Subject Code: 10CS35 I.A. Marks : 25
Hours/Week : 04 Exam Hours: 03
Total Hours : 52 Exam Marks: 100
PART – A
UNIT - 1 8 Hours
BASIC CONCEPTS: Pointers and Dynamic Memory Allocation, Algorithm Specification, Data Abstraction,
Performance Analysis, Performance Measurement
UNIT - 2 6 Hours
ARRAYS and STRUCTURES: Arrays, Dynamically Allocated Arrays, Structures and Unions, Polynomials,
Sparse Matrices, Representation of Multidimensional Arrays
UNIT - 3 6 Hours
STACKS AND QUEUES: Stacks, Stacks Using Dynamic Arrays, Queues, Circular Queues Using Dynamic
Arrays, Evaluation of Expressions, Multiple Stacks and Queues.
UNIT - 4 6 Hours
LINKED LISTS: Singly Linked lists and Chains, Representing Chains in C, Linked Stacks and Queues,
Polynomials, Additional List operations, Sparse Matrices, Doubly Linked Lists
PART - B
UNIT - 5 6 Hours
TREES – 1: Introduction, Binary Trees, Binary Tree Traversals, Threaded Binary Trees, Heaps.
UNIT - 6 6 Hours
TREES – 2, GRAPHS: Binary Search Trees, Selection Trees, Forests, Representation of Disjoint Sets, Counting
Binary Trees, The Graph Abstract Data Type.
UNIT - 7 6 Hours
PRIORITY QUEUES Single- and Double-Ended Priority Queues, Leftist Trees, Binomial Heaps, Fibonacci
Heaps, Pairing Heaps.
UNIT - 8 8 Hours
EFFICIENT BINARY SEARCH TREES: Optimal Binary Search Trees, AVL Trees, Red-Black Trees, Splay
Trees.
Text Book:
1. Horowitz, Sahni, Anderson-Freed: Fundamentals of Data Structures in C, 2nd Edition, University Press,
2007.
(Chapters 1, 2.1 to 2.6, 3, 4, 5.1 to 5.3, 5.5 to 5.11, 6.1, 9.1 to 9.5, 10)
Page 2
TABLE OF CONTENTS
UNIT 1: BASIC CONCETPS 1-12
UNIT 2: ARRAYS & STRUCTURES 13-26
UNIT 3: STACKS & QUEUES 27-36
UNIT 5: TREES 37-50
UNIT 6: TREES(CONT.) & GRAPHS 51-62
Page 32
DATA STRUCTURES WITH C
The place where your greatest fears live is also the place where your greatest growth lies.
30
QUEUES
• This is an ordered-list in which insertions & deletions take place at different ends (Figure 3.4).
• The end at which new elements are added is called the rear &
the end from which old elements are deleted is called the front.
• Since first element inserted into a queue is first element removed, queues are known as FIFO lists.
structure Queue is
objects: a finite ordered list with zero or more elements.
functions:
for all queue Queue, item element, max_ queue_ size positive integer
Queue CreateQ(max_queue_size) ::=
create an empty queue whose maximum size is max_queue_size
Boolean IsFullQ(queue, max_queue_size) ::=
if(number of elements in queue == max_queue_size)
return TRUE
else
return FALSE
Queue AddQ(queue, item) ::=
if (IsFullQ(queue))
queue_full
else
insert item at rear of queue and return queue
Boolean IsEmptyQ(queue) ::=
if (queue ==CreateQ(max_queue_size))
return TRUE
else
return FALSE
Element DeleteQ(queue) ::=
if (IsEmptyQ(queue))
return
else
remove and return the item at front of queue
ADT 3.2: Abstract data type Queue
• The CreateQ() function can be implemented as follows
Queue CreateQ(maxQueueSize)::=
#define MAX_QUEUE_SIZE 100
struct element
{
int key;
};
element queue[MAX_QUEUE_SIZE];
int rear=-1;
int front=-1;
Boolean IsEmptyQ(queue)::= front==rear;
Boolean IsFullQ(queue)::= rear=MAX_QUEUE_SIZE-1;
void addq(int rear, element item)
{
if (rear == MAX_QUEUE_SIZE_1)
{
queue_full( );
return;
}
queue [++rear] = item;
}
element deleteq(int front, int rear)
{
if ( front == rear)
return queue_empty( );
return queue [++ front];
}
Program 3.5: Add to a queue Program 3.6: Delete from a queue
Page 33
DATA STRUCTURES WITH C
The law of attraction says that we attract into our life that which we focus on.
31
JOB SCHEDULING
• Queues are used for the creation of a job-queue by an operating-system (Figure 3.5).
• If operating-system does not use, then the jobs are processed in the order they enter the system.
CIRCULAR QUEUE
• In a circular-queue, the elements are arranged implicitly in a circle (Figure 3.7).
• When the array is viewed as a circle, each array position has a next and a previous position.
void addq(int front, int rear, element item)
{
rear = (rear +1) % MAX_QUEUE_SIZE;
if (front == rear) /* reset rear and print error */
return;
queue[rear] = item;
}
Program 3.7: Add to a circular queue
element deleteq(int front, int rear)
{
element item;
if (front == rear)
return queue_empty( ); /* queue_empty returns an error key */
front = (front+1) % MAX_QUEUE_SIZE;
return queue[front];
}
Program 3.8: Delete from a circular queue
Page 63
DATA STRUCTURES WITH C
You can expect only that which you inspect.
61
GRAPH REPRESENTATIONS
• Three commonly used representations are:
1) Adjacency matrices,
2) Adjacency lists and
3) Adjacency multilists
Adjacency Matrix
• Let G=(V,E) be a graph with n vertices, n>=1.
• The adjacency matrix of G is a two-dimensional n*n array( say a) with the property that a[i][j]=1 iff
the edge (i,j) is in E(G). a[i][j]=0 if there is no such edge in G (Figure 6.7).
• The space needed to represent a graph using its adjacency matrix is n
2
bits.
• About half this space can be saved in the case of undirected graphs by storing only the upper or
lower triangle of the matrix.
Figure 6.7 Adjacency matrices
Adjacency Lists
• The n rows of the adjacency matrix are represented as n chains.
• There is one chain for each vertex in G.
• The data field of a chain node stores the index of an adjacent vertex (Figure 6.8).
• For an undirected graph with n vertices and e edges, this representation requires an array of size n
and 2e chain nodes.
Figure 6.8 adjacency lists
Page 64
DATA STRUCTURES WITH C
Failure reawakens us to who we really are & to what we truly want, & it shakes us out of our complacency.
62
Adjacency Multilists
• Each edge (u,v) is represented by two entries, one on the list for u and the other on the list for v.
• The new node structure is
Figure 6.12:Adjacency multilists for G1
