Download VTU 3RD SEM CSE DATA STRUCTURES WITH C NOTES 10CS35 PDF

TitleVTU 3RD SEM CSE DATA STRUCTURES WITH C NOTES 10CS35
TagsPointer (Computer Programming) C (Programming Language) Data Type Queue (Abstract Data Type) Time Complexity
File Size3.7 MB
Total Pages64
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

Similer Documents