| VTU NOTES | |
|---|---|
|
Subject code |
21CS32 |
|
Semester |
3rd |
Introduction: Data Structures, Classifications (Primitive & Non-Primitive), Data structure operations (Traversing, inserting, deleting, searching, and sorting). Review of Arrays.
Structures: Array of structures Self-Referential Structures. Dynamic Memory Allocation Functions. Representation of Linear Arrays in Memory, dynamically allocated arrays and Multidimensional Arrays. Demonstration of representation of Polynomials and Sparse Matrices with arrays.
Stacks: Definition, Stack Operations, Array Representation of Stacks, Stacks using Dynamic Arrays. Different representation of expression. Stack Applications: Infix to postfix conversion, Infix to prefix conversion, evaluation of postfix expression, recursion.
Queues: Definition, Array Representation of Queues, Queue Operations, Circular Queues, Queues and Circular queues using Dynamic arrays, Dequeues, Priority Queues.
Linked Lists: Definition, and classification of linked lists. Representation of different types of linked lists in Memory, Traversing, Insertion, Deletion, Searching, Sorting, and Concatenation Operations on Singly linked list, Doubly Linked lists, Circular linked lists, and header linked lists. Linked Stacks and Queues. Applications of Linked lists – Polynomials, Sparse matrix representation. Programming Examples.
Trees 1: Terminologies, Binary Trees, Properties of Binary trees, Array and linked Representation of Binary Trees, Binary Tree Traversals – Inorder, postorder, preorder; Threaded binary trees, Binary Search Trees – Definition, Insertion, Deletion, Traversal, and Searching operation on Binary search tree. Application of Trees-Evaluation of Expression.
Trees 2: AVL tree, Red-black tree, Splay tree, B-tree.
Graphs: Definitions, Terminologies, Matrix and Adjacency List Representation of Graphs, Traversal methods: Breadth First Search and Depth FirstSearch.
Hashing: Hash Table organizations, Hashing Functions, Static and Dynamic Hashing.