TAOCP 6.1 Exercise 2

Let $P$ be a pointer to a record, with $FIRST$ pointing to the first record and the last record linked to the sentinel $A$.

taocpmathematicsalgorithmsvolume-3simple

Section 6.1: Sequential Searching

Exercise 2. [15] [15] Restate the steps of Algorithm S, using linked-memory notation instead of subscript notation. (If P points to a record in the table, assume that KEY(P) is the key, INFO(P) is the associated information, and LINK(P) is a pointer to the next record. Assume also that FIRST points to the first record, and that the last record points to A.)

Verified: yes
Solve time: 1m

Solution

Let $P$ be a pointer to a record, with $FIRST$ pointing to the first record and the last record linked to the sentinel $A$. The sequential search is expressed directly in linked-memory form by replacing subscript advancement with pointer following.

Algorithm $S'$ (Sequential search in linked representation).

$S1.$ Set $P \leftarrow FIRST$.

$S2.$ If $P = A$, go to failure.

$S3.$ If $K = KEY(P)$, go to success.

$S4.$ Set $P \leftarrow LINK(P)$ and return to $S2$.

At the label success, the instruction $LDA\ INFO(P)$ places the associated information of the matching record into the accumulator, exactly as in the array version where $INFO+ i$ is accessed upon finding $K = K_i$.

At the label failure, the algorithm terminates with the conclusion that the search key does not appear in the table. This corresponds to reaching the sentinel $A$ without encountering equality, so the traversal has visited every record in the linked list in order and exhausted all links.

This completes the reformulation of Algorithm $S$ in linked-memory notation. ∎