CAPE Computer Science Unit 2
Abstract Data Types (ADTs) and
Implementation
Dynamic Memory Allocation and Linked
Lists
Presentation Linear Data Structures: Stacks and
Overview Queues
Non-Linear Data Structures: Binary
Search Trees
Searching and Sorting Algorithms
File Handling in C
Understanding Abstract Data Types (ADTs)
• An ADT is a theoretical model that defines a data type by its behavior from the
user's perspective.
• Focuses on 'what' the data does rather than 'how' it is implemented.
• Encapsulation: Users interact with the ADT through a specific interface
(functions/methods).
• Examples include Stacks, Queues, and Lists.
Linked Lists: Dynamic Data Structures
• A collection of nodes where each node contains data and a pointer to the next
node.
• Dynamic Memory: Uses 'malloc()' and 'free()' in C to allocate memory at
runtime.
• Advantages: Efficient insertion and deletion compared to arrays.
• Singly Linked vs. Doubly Linked lists.
Stacks: Last-In, First-Out (LIFO)
• A linear structure where elements are added and removed from the same end
(the top).
• Core Operations:
• Push: Add an item to the top.
• Pop: Remove the top item.
• Peek: View the top item without removing it.
• Used in function call management and expression evaluation.
Queues: First-In, First-Out (FIFO)
• A linear structure where elements are added at the rear and removed from the
front.
• Standard Operations: Enqueue (add) and Dequeue (remove).
• Circular Queues: Optimize memory by reusing empty spaces at the beginning
of the array.
• Applications: Printer spooling and CPU scheduling.
Binary Search Trees (BST)
• A hierarchical structure where each node has at most two children.
• BST Property: Left child < Parent < Right child.
• Traversal Methods:
• In-order: Results in sorted data.
• Pre-order and Post-order for structural processing.
Essential Sorting Algorithms
• Bubble Sort: Repeatedly steps through the list, compares adjacent elements
and swaps them.
• Selection Sort: Repeatedly finds the minimum element and moves it to the
beginning.
• Insertion Sort: Builds the final sorted array one item at a time by 'inserting'
values.
• Advanced sorts: Quick Sort and Merge Sort (Divide and Conquer).
Searching: Linear vs. Binary
• Linear Search: Checks every element until the target is found. Works on
unsorted data.
• Binary Search: Repeatedly divides a sorted search interval in half. O(log n)
efficiency.
• Criteria for Binary Search: The list MUST be sorted beforehand.
File Handling in C
• Files allow for data persistence across program executions.
• Key Functions:
• fopen(): Opens a file in read (r), write (w), or append (a) mode.
• fprintf() / fscanf(): For reading and writing formatted data.
• fclose(): Essential for preventing data loss and memory leaks.