##### 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