6.1: Imposing List Structure on Data

So far in this book, records in lists have had information members and link members. These are simple records. The lists themselves have looked like chains of records. Such lists may be used to store the records only or to store them and also impose an ordering on them. This chapter presents complex records, which contain members that are themselves names of lists. The members are called sublist members. Lists composed of such records have more complex structure than chains and are known as complex lists. Several such lists are depicted schematically in Figure 6.1. The following examples illustrate the use of complex lists and show how they provide one means of organizing data to capture certain inherent relations among the list records.

Example 6.1

The accounts list in Figure 6.1(a) consists of three records. The first two are complex, the third simple. The first record points to a sublist consisting of two records; the first of these is complex and the second is simple. Accounts might actually represent three companies' user accounts. The first user account is billed for two distinct computer services, $100 for last month's computing and $75 for this month's software consulting. The second user account owes $200 for the month's computing and $250 for the month's consulting. The third user account has a credit of $46. The X in the sublist member of the complex record "200" means its sublist is null. n

Example 6.2

A programmer asked to simulate a card game with n players might choose to represent the current configuration of the n individual hands by using a list composed of complex records. A typical configuration is shown in Figure 6.1(b) for four poker players. The sublist that makes up each complex record contains all the cards of a particular player's hand, each card represented as a record. Insertions and deletions into an individual hand require insertions and deletions from the appropriate sublist. n

(a) ACCOUNTS List

(b) Poker Hands for n = 4 Players

(c) BOOK List

Figure 6.1 More Complex Lists

(d) List P, a Polynomial Expression

(e) Brokerage Data Base

Example 6.3

A book might be represented as the book list shown in Figure 6.1(c). Records for the individual lines of text would be simple; the records for paragraph, chapter,and page would be complex.

The data processing for word processing or text editing might involve inserting and deleting chapters, paragraphs, or lines. Creating an index for the book would require even more complex processing. This could be done by making a special "dictionary" that lists the key words relevant to the book's topic, then searching the text for all instances of key words. If the book were a computer science text, then the dictionary would include all key technical computer science words. The index could be created by accessing and processing each page. This processing would involve checking the page for occurrences of the key words and keeping track, for each such word in the dictionary, of the pages on which it occurred. (Unfortunately, such automatic indexing creates too large an index and one that may not be very useful, since not every mention of a key term is especially relevant.) n

Example 6.4

A polynomial in x, y, and z may be represented using a list-structure. Suppose the polynomial P(x, y, z) is 3zx5 + 5z3yx + 20. We can write this as

P(x, y, z) = z3(y(x(5))) + z(x5(3)) + 20

This, in turn, can be represented as p of Figure 6.1(d).

(a) General Form of a Record

(b) Main-List Record

(c) Last Record on Main List

Figure 6.2 Records of the List-structure for a Polynomial

Each record of p has four fields, as shown in Figure 6.2(a). A tag field value of 1 indicates that the record is complex, while a tag field of 0 indicates that the record is simple.

Each sublist, including the main list, has a header record and represents a polynomial. The main list, for example, is a polynomial in z composed of three terms. The record (Figure 6.2(b)) on the main list indicates that this term contains z to the power 3 and a coefficient that is pointed to by the pointer in the coeff field. Its successor record is similarly expressed. The last record on the main list (Figure 6.2(c)) is simple, meaning that the value in the coeff field is to be interpreted as a constant. Sublists are interpreted in the same way.n

Example 6.5

Each record on brokerage's main list in Figure 6.1(e) represents a sales representative (a financial advisor) of a brokerage firm. The sublist of each salesperson contains information about each of his or her clients. Each client's sublist is the client's stock portfolio. n

6.1.1 A Definition of List-structures