Now that we have built the collections, how do we answer questions about family relationships?
Example 6.12
How do we determine who the children of John Smith are? Search the nametable for John Smith. If the name is not there, print an appropriate message. If it is there, follow the pointer to John Smith's individual record. Traverse his list of children and count the number of records on it, or output the individual names. In any case, ignoring the search of nametable, the time required is proportional to the length of the answer?/FONT>that is, it is proportional to the number of children of John Smith. n
Example 6.13
How do we find all the uncles of John Smith? Search the nametable, and follow its pointer to the record for John Smith. Then, follow the fnameptr pointer to the entry in the nametable for his father and follow its recordptr back to the father's record. Do this again for the father to get to the grandfather's record. Once we have the grandfather's record we can traverse his children's list to find the uncles on John Smith's father's side. Repeat the process for John Smith's mother to find the uncles on her side. n
Simply following the sibling pointer of the father's record doesn't work, because the traversal may have begun in the middle of this sibling list. To ensure starting at the beginning of the sibling list, it is best to use the children's list of the grandfather's record. If the sibling lists were circular, this would not be necessary; it would suffice to traverse the grandfather's list of children (John Smith's father's siblings) and then output the name of each male. The same processing must be done for John Smith's mother, to output all his uncles on his mother's side.
The total time, again ignoring the nametable search, is proportional to the answer, the number of uncles. Excluding the nametable search, this is certainly close to the minimal time that would be desirable. You will see in the chapters on searching and sorting how long it would take to search the nametable!