Data Structures using C++

COURSE OBJECTIVES:

• To impart the basic concepts of data structure
• To understand the concepts about linear and non linear data structures
• To understand basic concepts and implementation about stacks, queues, arrays, lists, trees and graphs

LEARNING OUTCOMES:

After the completion of the course, students will be able to –

• To introduce the concepts of Abstract data Type, data structure, performance measurement, time and space complexities of algorithms.
• To discuss the implementation linear data structures such as stacks, queues and lists and their applications.
• To discuss the implementation of different non linear data structures such as trees and graphs.
• To introduce various search data structures such as hashing, binary search trees and b-trees.
• To introduce various internal sorting techniques and analyze their time complexities.

SYLLABUS

Unit I

Concept of Structured data – Data structure definition, Different types and classification of data structures, Arrays – Memory allocation and implementation of arrays in memory, array operations, Applications – sparse matrix representation and operations, polynomials representation and addition, Concept of search and sort – linear search, binary search, selection sort, insertion sort, quick sort.

Unit II

Stacks – Concepts, organization and operations on stacks using arrays (static), examples, Applications – Conversion of infix to postfix and infix to prefix, postfix evaluation, subprogram calls and execution, Multiple stacks representation. Queues – Concepts, organization and operations on queues, examples. Circular queue – limitations of linear queue, organization and operations on circular queue. Double ended queue, Priority queue.

Unit III

Linked list: Concept of dynamic data structures, linked list, types of linked list, linked list using pointers, insertion and deletion examples, circular linked list, doubly linked lists Applications- linked stacks and queues, memory management basic concepts, garbage collection.

Unit IV

Trees – Concept of recursion, trees, tree terminology, binary trees, representation of binary trees, strictly binary trees, complete binary tree, extended binary trees, creation and operations on binary tree, binary search trees, Creation of binary search tree, tree traversing methods – examples, binary tree representation of expressions.

Unit V

File – Definition, Operations on file (sequential), File organizations – sequential, Indexed sequential, random files, linked organization, inverted files, cellular partitioning, hashing – hash tables, hashing functions, collisions, collision resolving methods.