A priority queue in C is a queue where the element served next is the one with the highest priority, not the one that arrived first. Operating system schedulers, Dijkstra’s algorithm, event simulators, and heap sort are all built on it. The textbook way to implement one efficiently is a binary max-heap: a complete binary …
Exercise 4-4. Add commands to print the top element of the stack without popping it, to duplicate it, and to swap the top two elements. Add a command to clear the stack. Four new commands, each operating directly on the stack array. None requires new data structures — just index arithmetic on val[] and sp. …
Exercise 4-3. Given the basic framework, it’s straightforward to extend the calculator. Add the modulus (%) operator and provisions for negative numbers. This exercise extends the RPN desk calculator from K&R Section 4.3. Two independent additions: Modulus operator % — pop two operands, cast to int, apply %, push result. Floating-point modulus is mathematically well-defined …
Exercise 4-2. Extend atof to handle scientific notation of the form 123.45e-6 where a floating-point number may be followed by e or E and an optionally signed exponent. The K&R atof in Section 4.2 handles sign, integer part, and fractional part. Scientific notation adds a third stage: after the mantissa, look for e or E, …
Kruskal’s algorithm finds the minimum spanning tree (MST) of a weighted, connected, undirected graph — the cheapest possible set of edges that connects every vertex with no cycles. It’s the classic greedy approach: sort all edges by weight, then keep taking the cheapest edge that doesn’t form a cycle. Road networks, electrical wiring, and network …
Exercise 4-1. Write the function strindex(s,t) that returns the position of the rightmost occurrence of t in s, or -1 if there is none. The K&R strindex in Section 4.1 returns the leftmost match by scanning left-to-right and returning at the first hit. For the rightmost match there are two symmetric approaches: scan right-to-left and …