Java Reference
In-Depth Information
root
x1
−
−
x4
+
+
y1
−
+
y3
z1
z2
+
+
+
a1
+
a2
+
Figure12.4
Linked representation for the pure list of Figure 12.1. The first field
in each link node stores a tag bit. If the tag bit stores “+,” then the data field stores
an atom. If the tag bit stores “,” then the data field stores a pointer to a sublist.
ROOT
B
C
D
A
Figure12.5
LISP-like linked representation for the cyclic multilist of Fig-
ure 12.3. Each link node stores two pointers. A pointer either points to an atom,
or to another link node. Link nodes are represented by two boxes, and atoms by
circles.
implementation can easily support reentrant and cyclic lists, because non-atoms
can point to any other node.
12.2
Matrix Representations
Sometimes we need to represent a large, two-dimensional matrix where many of
the elements have a value of zero. One example is the lower triangular matrix that
results from solving systems of simultaneous equations. A lower triangular matrix
stores zero values at all positions [r, c] such that r < c, as shown in Figure 12.6(a).
Thus, the upper-right triangle of the matrix is always zero. Another example is
representing undirected graphs in an adjacency matrix (see Project 11.2). Because
all edges between Vertices i and j go in both directions, there is no need to store
both. Instead we can just store one edge going from the higher-indexed vertex to
