Advanced C and C Programming

Advanced C & C++ Programming Comprehensive University Study Guide Data Structures · Complex Algorithms · Modern OOP · STL Root C DS Alg C++ OOP STL From Procedural Mastery to Object-Oriented Software Engineering

Advanced C & C++ Programming Contents 1 1. Advanced Non-Linear Data Structures 2 1.1 Binary Search Trees (BST) & Balancing . . . . . . . . . . . . . . . . . . . 2 1.1.1 Mathematical Problem: Tree Degeneration . . . . . . . . . . . 2 1.2 Heaps and Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 2. Tries and Advanced Hashing 4 2.1 Tries (Prefix Trees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Hash Tables Deep Dive . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.1 Handling Collisions: Chaining vs. Open Addressing . . . . . . 5 3 3. Range Queries & Disjoint Sets 6 3.1 Segment Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 Disjoint Sets (Union-Find) & Path Compression . . . . . . . . . . . . . 6 4 4. Graph Theory & Traversals 8 4.1 Graph Representation Comparison . . . . . . . . . . . . . . . . . . . . 8 4.2 Breadth-First Search (BFS) Simulation . . . . . . . . . . . . . . . . . . . 8 5 5. Shortest Paths & Spanning Trees 10 5.1 Dijkstra’s Shortest Path Algorithm . . . . . . . . . . . . . . . . . . . . . 10 5.2 Bellman-Ford Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.3 Minimu

Advanced C & C++ Programming 1 1. ADVANCED NON-LINEAR DATA STRUCTURES 1 1. Advanced Non-Linear Data Structures While the intermediate syllabus covered linear structures (arrays, linked lists, stacks), advanced university algorithms rely heavily on non-linear data structures to bypass the O(n) limitations of sequential searches. 1.1 Binary Search Trees (BST) & Balancing A Binary Search Tree (BST) enforces a strict property: for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger. Analogy: The Telephone Directory Imagine looking for ”Smith” in a phone book. You do not read sequentially from page 1. You open the exact middle. If you see ”Miller”, you mathematically know ”Smith” must be in the right half. You discard the entire left half instantly and repeat. A BST models this exact physical process in memory, allowing you to discard half the remaining data at every step, yielding O(log2 n) search time. 1.1.1 Mathematical Problem: Tree Degeneration If you insert pre-sorted data into a standard BST (e.g., 10, 20, 30, 40), it physically degen- erates into a Linked List. The mathematical height of the tree becomes h = n instead of h =