How are the collections of individual records and of nametable records created originally? Suppose you have already dealt with the first hundred records and that the situation in memory accurately reflects all the information they contain. That is, the two collections are correct and as complete as possible, given this input. You now attempt to input the next record, the one hundred first. Recall that the
input consists of the individual's name, sex, birthdate, father's name, and mother's name. Input data for John Smith would appear as
JOHN SMITH M 1/2/79 GEORGE SMITH ALICE RICKARD
The program should check the record for validity (input validation). If valid, the two collections in memory must be updated to reflect the new information. Then the program should read the next record, and so on until there are no more to enter. An important component of the solution is an update function, which will create and add new records to the collections when necessary and enter new values into the proper fields. It must function as follows.
It is possible that one or more of the three names in the name fields of the newly input record are already in the nametable, with individual records having been created for them. For instance, the father's name might have been dealt with earlier when it appeared in the name field of another record. Assume first that each distinct name appearing in any field of the previously processed records has been entered into the nametable and has had an individual record created for it. Thus the nametable entry for each of these distinct names has the correct name in its name field, and a pointer in its recordptr field to its corresponding individual record. This individual record also has a pointer in its name field back to the record in the nametable it represents. Some fields of the individual record may not yet have been filled with appropriate information.
We cannot, however, assume that any name in the new input record has been seen before. Suppose John Smith is in the name field of the new record. Search the nametable to see if there is an entry for John Smith. If there is, remember where it is by placing a pointer to it in nt_ptr and then copy the pointer in the recordptr field into a variable ir_nptr. Then ir_nptr reveals where the individual record is that corresponds to John Smith. Nt_ptr is a pointer to John Smith's nametable record, and ir_nptr is a pointer to John Smith's individual record. Ir_nptr will be used later when we have to update John Smith's individual record. If there is no entry for John Smith in the nametable, you know that there is not yet an individual record created for John Smith. Create such a record, and also create an entry in the nametable corresponding to it. Store John Smith's name and a pointer to his corresponding record in the recordptr field of the nametable entry. Also place a copy of the pointer to this entry in the nameptr field of the individual record. Then copy the pointer to the individual record into ir_nptr.
At this point, whether or not information on John Smith was already in the system, both an entry in the nametable and an individual record for him exist. The nametable record is completely filled in, and the individual record has at least its nameptr field filled in. Also, ir_nptr points to the individual record.
We would follow the same process for John Smith's father and mother, creating the following four pointers.
ir_fptr
A pointer to the individual record representing John Smith's father
ir_mptr
A pointer to the individual record representing John Smith's mother
nt_fptr
A pointer to the nametable entry for John Smith's father
nt_mptr
A pointer to the nametable entry for John Smith's mother
How do we now complete the update properly? That is, which individual records and nametable entries must be modified, and how are the modifications done?
Consider the individual record for John Smith. The sex and birthdate fields can easily be filled in, as well as the fnameptr field, copying nt_fptr into it.The same can be done for mnameptr.
Now the individual record for the father of John Smith must be updated. Fill in the sex field (you know he is male). There is no additional information on his birthdate. (It may already be known. Why?) John Smith's record must be added to the list of children of his father. Assuming that the children are not kept in any special order, add his record at the front of the list. This requires copying the childrenlist pointer of his father's record into the siblingptr of John Smith's record, and then copying the pointer in ir_nptr into the childrenlist field of his father. This implies that whenever individual records are created, they must have their childrenlist and siblingptr fields set to null.
The mother's record can be treated similarly, except we may simply copy the father's childrenlist pointer (or ir_nptr) into her childrenlist field. This completes the update, which consisted of a search of the nametable and the updating of pointers in nine fields after the nametable entries and individual records were created. These nine fields were
fnameptr, mnameptr, sex, birthdate, siblingptr梖or the individual record of John Smith
sex, childrenlist?/FONT>for the individual record of George Smith and Alice Rickard, the father and mother
Example 6.11
Let us now trace this process with some data and show how the records would appear. Suppose the input data so far consisted of the information shown in Table 6.1, and suppose that we use different arrays to hold the individual records and the nametable entries. (Later, in Chapters 8 and 9, more appropriate implementations for collections such as nametable are introduced.) The situation in memory will then be as shown in Table 6.2. n
The next input is
Since none of these names appears in the nametable, an entry in the nametable and an individual record must be created for each of the names.
After this has been done, the new nametable entries, individual records, and saved pointers will appear as shown in Figure 6.8(a). Updating the nine fields of the individual records yields the result shown in Figure 6.8(b).
The next input is
Johann S. Bach and Maria Bach already appear in the nametable and have individual records. An entry in the nametable and an individual record must, however, be created for Carl Bach.
When this has been completed, the nametable entries, i`ndividual records, and saved pointers related to this input appear as in Figure 6.8(c). Updating the nine fields of the individual records yields the result shown in Figure 6.8(d). The time required to complete an update is the constant time for the pointer manipulations plus the time to search the nametable.
The following is an algorithm for updating the information base given another input record.
1. Search the nametable.
a. Create entries in the nametable and create individual records for any of the three input names not present in nametable.
b. Set their recordptr and nameptr fields.
c. Set their childrenlist and siblingptr fields to null.
d. Set nt_ptr, nt_fptr, nt_mptr, ir_nptr, ir_fptr, and ir_mptr.
2. Update the following fields of the individual record pointed to by ir_nptr:
sex to input sex
birthdate to input birthdate
fnameptr to nt_fptr
mnameptr to nt_mptr
3. Update:
sex.fptr (the sex field of the record pointed to by ir_fptr) to m
siblingptr.ir_nptr to childrenlist.ir_fptr
childrenlist.ir_fptr to ir_nptr
sex.ir_mptr to f
childrenlist.ir_mptr to ir_nptr
JOHN SMITH M 1/2/79 GEORGE SMITH ALICE RICKARD
Table 6.1 Input Data for Example 6.11
Name Sex Birthdate Fathersname Mothersname
-----------------------------------------------------------------------------
Albert Einstein M 3/14/1879 Hermann Einstein Paulina Koch
Leo Tolstoy M 9/9/1828 Nikolai Tolstoy Marie Volkronskii
George Eliot F 11/22/1819 Robert Evans Christina Pearson
Margaret Truman F 2/17/1924 Harry Truman Bess Truman
Wilhelm Bach M 11/22/1710 Johann S. Bach Maria Bach
Jimmy Carter M 10/1/1924 James Earl Carter Lillian Carter
Sir Isaac Newton M 12/25/1642 Isaac Newton Hannah Newton
Harry Truman M 5/8/1884 John Truman Martha Young
Billy Carter M 3/29/1937 James Earl Carter Lillian Carter
Johann S. Bach M 3/21/1685 Johann Ambrosius Bach Elizabeth L鋗merhirt
Johann Gottfried
Bach M 5/11/1715 Johann S. Bach Maria Bach
Table 6.2 The nametable and Individual Records (for Example 6.11) after Initial Input Data Are Processed
Nametable Individual
Records Records
Name Recordptr Nameptr Fnameptr Mnameptr Siblingptr Childrenlist Sex Birthdate
---------------------------------------------------------------------------------------------------------------
1 Albert Einstein 1 1 1 2 3 0 0 M 03141879
2 Hermann Einstein 2 2 2 0 1 M
3 Paulina Koch 3 3 3 0 1 F
4 Leo Tolstoy 4 4 4 5 6 0 0 M 09091828
5 Nikolai Tolstoy 5 5 5 0 4 M
6 Marie Volkronskii 6 6 6 0 4 F
7 George Eliot 7 7 7 8 9 0 0 F 11221819
8 Robert Evans 8 8 8 0 7 M
9 Christina Pearson 9 9 9 0 7 F
10 Margaret Truman 10 10 10 11 12 0 0 F 02171924
11 Harry Truman 11 11 11 0 10 M
12 Bess Truman 12 12 12 0 10 F
13 Wilhelm Bach 13 13 13 14 15 0 0 M 11221710
14 Johann S. Bach 14 14 14 25 26 0 27 M 03211685
15 Maria Bach 15 15 15 0 27 F
16 Jimmy Carter 16 16 16 17 18 0 0 M 10011924
17 James Earl Carter 17 17 17 0 16 M
18 Lilian Carter 18 18 18 0 16 F
19 Sir Isaac Newton 19 19 19 20 21 0 0 M 12251642
20 Isaac Newton 20 20 20 0 19 M
21 Hannah Newton 21 21 21 0 19 F
22 John Truman 22 22 22 11 M
23 Martha Young 23 23 23 11 F
24 Billy Carter 24 24 24 17 18 16 0 M 03291937
25 Johann Ambrosius Bach 25 25 25 0 14 M
26 Elizabeth L鋗merhirt 26 26 26 0 14 F
27 Johann Gottfried Bach 27 27 27 14 15 13 0 M 05111715
(a) With Three New Entries
(b) Updated
(c) With One Additional Entry
(d) Updated Again
Figure 6.8 Nametable and Individual Records with Saved Pointers
CARL BACH M 3/8/1714 JOHANN S. BACH MARIA BACH