Mastering Algorithms with C
by Kyle Loudon

The following errata were *corrected* in the 8/05 reprint:

Here's a key to the markup:

        [page-number]: serious technical mistake
        {page-number}: minor technical mistake
        <page-number>: important language/formatting problem
        (page-number): language change or minor formatting problem



<363> Under "Related Topics", another related topic HAS BEEN ADDED before
 "Error Approximation". The new topic READS AS FOLLOWS:

	Numerical Representation in Computers

The representation of numbers in computers is finite. Consequently, computers
are limited in the way they can work with certain types of numbers, such as
those that are extremely small or large. An understanding of these limitations
is important before undertaking most serious work in numerical analysis. This
chapter assumes an understanding of these limitations.



{503} middle of page, after the sentence:
        The straddle test determines the orientation of p3 relative to
        p2 and of p4 relative to p2 with respect to p1.

The following HAS BEEN ADDED:
        It then determines the orientation of [p1] relative to [p4] and of
        [p2] relative to [p4] with respect to [p3].

Note that [ ] above indicates an item in constant width italic font.


ALSO the sentence that begins:
        If the orientations are different, or if either orientation is 0...

NOW READS:
        If the orientations of the points in either computation are
        different or 0, the straddle test succeeds, and the algorithm returns
        that the line segments intersect; otherwise, the line segments do not
        intersect.



{277}  last line on the page;
The line that reads:
	set_init(&adjlist->adjacent, graph->match, graph->destroy);

NOW READS:
	set_init(&adjlist->adjacent, graph->match, NULL);


**AUTHOR'S RESPONSE

It is important to note that when inserting an edge into a graph, the data2 
parameter of graph_ins_edge must have *its own* storage allocated for it. For 
example, data2 cannot share storage with a vertex passed to graph_ins_vertex 
at some earlier time. For example, to create the graph below, we should do 
something like the following:

        Graph:
        ---------
        a -> b
	b
        ---------

        data2 = (char *)malloc(2);
        strcpy(data2, "b");
        graph_ins_vertex(&graph, data2);

        data1 = (char *)malloc(2);
        strcpy(data1, "a");
        graph_ins_vertex(&graph, data1);

        data2 = (char *)malloc(2);
        strcpy(data2, "b");
        graph_ins_edge(&graph, data1, data2);

Note that before the call to graph_ins_edge, we allocate new storage for 
data2. This is because inside of graph_ins_vertex, set_init initializes each 
new adjacency list with graph->destroy, which will be called once for each 
vertex in the adjacency list when the graph is destroyed. Since every vertex 
also appears in the list of AdjList structures, without its own storage each 
vertex will be destroyed more than once. One solution is to set the destroy 
parameter of set_init to NULL. However, this alternative poses problems in the
form of consistency issues. The important thing to remember, therefore, is 
simply this: Before any piece of data is inserted into a data structure, it 
must have *its own* storage allocated for it. (Notice that it is perfectly 
acceptable in the call to graph_ins_edge, however, not to allocate new storage
for data1 because data1 is used only to look up in which adjacency list data2 
will be inserted; in other words, the graph does not have a pointer to data1 
once the operation completes.