|
80 |
|
|
|
|
is given in Figure 4.10.
Each sublist in this structure has
associated with it a record containing only two pointers.
(We
can assume that Di is really a pointer to document Di.)
The function of the pointers should be clear from the diagram.
The
main thing to note, however, is that the record associated with a list
does not contain any identifying information.
A modification of the implementation of a list structure like this which makes it resemble a set of ring structures is to make the right hand pointer of the last element of a sublist point back to the head of the sublist. Each sublist has become effectively a ring structure. We now have what is commonly called a threaded list (see Figure 4.11). The representation I have given is a slight oversimplification in that we need to flag which elements are data elements (giving access to the documents Di) and which elements are just pointer elements. The major advantage associated with a threaded list is that it can be traversed without the aid of a stack. Normally when traversing a conventional list structure the return addresses are stacked, whereas in the threaded list they have been incorporated in the data structure.
One disadvantage associated with the use of list and ring structures for representing classifications is that they can only be entered at the 'top'. An additional index giving entry to the structure at each of the data elements increases the update speed considerably.
Another modification of the simple list representation has been studied extensively by Stanfel[21,22] and Patt[23]. The individual elements |
|
|
80 |
|
|
|