# Data Structures Using C laboratory examples Ten independent programs illustrate the algorithms used in the ebook. Each contains its own `main`, boundary-case checks and a short demonstration. They use the C11 standard library only. ## Build and run From this directory: ```sh cc -std=c11 -Wall -Wextra -Werror -pedantic arrays_search.c -o /tmp/arrays_search /tmp/arrays_search ``` Replace the filename to run another example. To compile every example and compare its exact output with the checked-in expectations: ```sh ../tests/run_c_examples.sh ``` Where supported, run AddressSanitizer and UndefinedBehaviorSanitizer: ```sh SANITIZE=1 ../tests/run_c_examples.sh ``` Some sandboxed environments cannot run LeakSanitizer. For those environments only: ```sh ASAN_OPTIONS=detect_leaks=0 SANITIZE=1 ../tests/run_c_examples.sh ``` Assertions are the test harness. **Do not compile these demonstrations with `-DNDEBUG`**: some test calls occur inside `assert`. For a production library, move operations outside assertions and provide a separate test harness. ## Contracts and limits All pointer arguments must point to valid objects or buffers with the documented size. These are teaching programs, not general-purpose libraries. A returned `false` reports an operation that cannot be performed; output arguments are unchanged on failure. Allocation failures leave existing structures intact. | File | What it demonstrates | Contract and limitations | | --- | --- | --- | | `arrays_search.c` | Positional insertion and deletion; linear search; first-match binary search | Array storage has at least `cap` slots and logical length never exceeds capacity. Deletion receives a valid logical length. Search returns `n` when absent. Binary search requires nondecreasing input. | | `sorting.c` | Bubble with early exit, selection, insertion, merge, quick and Shell sorts | Bubble, insertion and merge are stable in the shown forms; selection, quick and Shell are generally unstable. Shell uses halving gaps and has quadratic worst-case time. Merge sort needs a separate temporary buffer of at least `n` integers. Quicksort uses a last-element pivot and can take quadratic time and linear recursion depth. Lab arrays are small. | | `stack_queue.c` | Array stack and circular queue | Capacity is four. Zero-initialize state. Stack `size` and queue `size` remain between zero and capacity; queue `front` remains a valid index. Queue uses an explicit count, so every slot is usable. | | `linked_list.c` | Prepend, find, first-match removal and cleanup | `head` owns an acyclic list. `find` returns a borrowed pointer that becomes invalid if that node is removed. `clear` resets the head to `NULL`. | | `bst.c` | Insertion, lookup and three depth-first traversals | Duplicate keys are ignored. Traversal output has space for all nodes, with count initialized to zero. Recursive traversals and cleanup can exhaust the call stack on very deep trees. No balancing or deletion is implemented. | | `graph_traversal.c` | BFS and recursive DFS using an adjacency matrix | At most six vertices, labelled `0` through `n-1`. Output has six slots. Neighbours are visited in increasing label order. A traversal covers only the start vertex's reachable component. | | `file_records.c` | Formatted text record write/read using `tmpfile` | Temporary file is removed on close. Names are single whitespace-free tokens of at most 23 bytes; marks are stored to one decimal place. This is a controlled round-trip example, not a parser for untrusted files. No binary struct serialization or external file overwrite. | | `linked_stack_queue.c` | Linked stack and queue operations and cleanup | Zero-initialize pointers. Each structure exclusively owns its nodes. Queue resets both pointers after removing its final node. Allocation failure does not mutate the structure. | | `avl.c` | AVL insertion with LL, RR, LR and RL rotations | Duplicate keys are ignored; empty height is zero. The caller initializes the allocation-status flag to `true` and checks it after insertion. No AVL deletion is implemented. Validation and traversal buffers in the test are sized for the test sequences. | | `hashing.c` | Integer set with linear probing and tombstone deletion | Fixed capacity seven; no resizing. Duplicate insertion succeeds without adding an entry. A full table rejects a new key. Probing is bounded by capacity, including when all slots are tombstones. | ## Exact demonstration output ### Arrays and search ```text After deletion: 10 20 40 50 arrays/search tests passed ``` ### Sorting ```text Sorted: 1 2 3 4 5 6 sorting tests passed ``` ### Stack and queue ```text Stack: 4 3 2 1 Queue after wraparound: 3 4 5 6 stack/queue tests passed ``` ### Linked list ```text List: 20 40 linked-list tests passed ``` ### Binary search tree ```text Inorder: 10 20 30 40 50 60 70 Preorder: 40 20 10 30 60 50 70 Postorder: 10 30 20 50 70 60 40 BST tests passed ``` ### Graph traversals ```text BFS: 0 1 2 3 4 DFS: 0 1 3 2 4 graph tests passed ``` ### Hashing ```text Collision chain: 10 at 3, 31 at 4, 24 at 5 hashing tests passed ``` ### File records ```text 101 Asha 84.5 102 Ravi 91.0 file-record tests passed ``` ### Linked stack and queue ```text Linked stack: 3 2 1 Linked queue: 1 2 3 linked stack/queue tests passed ``` ### AVL insertion ```text LL, RR, LR and RL rotation tests passed AVL inorder: 10 20 30 45 75 80 100 120 125 130 150 200 AVL tests passed ``` ## C++ comparison appendix `inversions.cpp` is deliberately separate from the C11 labs. It uses C++17 `std::array` and stream output to count pairs `(i,j)` for which `i < j` and `a[i] > a[j]`. The input `{8,4,2,1}` has six inversions. This direct pair-counting method takes Θ(n²) time and Θ(1) extra space beyond the fixed input array. It is a fixed demonstration, not an input-reading utility or optimized merge-sort inversion counter. ```sh c++ -std=c++17 -Wall -Wextra -Werror -pedantic inversions.cpp -o /tmp/inversions /tmp/inversions ../tests/run_cpp_example.sh ``` Expected output: ```text Inversions: 6 ``` Use the separate C++ runner; the C runner intentionally compiles only `.c` files using C11. For sanitizer checking, use `SANITIZE=1` with the C++ runner (and `ASAN_OPTIONS=detect_leaks=0` only where LeakSanitizer is unavailable).