Project 5

IUP Computer Science
CO 310 Fall 1983

Assignment #5

For sometime, information has been collected about the Devo family. This information is to be used to make a psychological study of two generations of Devos. Some of the information is kept in file 310DEVO.COMPSCI, but it is not well organized. The information is about family relationships and deaths in the family. The records in the file are in the following form.

     Character position       Contents
     ------------------       --------------------------
          1 - 10              Family member name A  (FMA)
         12 - 18              Relationship; one of CHILD, SPOUSE,
                                   SIBLING, or DEATH
         20 - 21              'OF'
         24 - 33              Family member name B  (FMB)

As examples, consider the following records.

          DOLORES    SIBLING OF  DELVIN
          ELVIS      CHILD   OF  DAWN
                     DEATH   OF  EDGAR

Notice that if the record is a death, there is no FMA (it is blank).

Your task is to write a program to read the records in the 310DEVO.COMPSCI file and to form a linked list based on the relationships expressed in the records. The linked list should use nodes of the form

The program should form a linked list that looks something like the following. The actual list for the Devo family will not look exactly like this example.

In this list, the family members in the first generation are on the top level and their children (the second generation) are on the second level. Each of the second level sublists represents the children of one of the first generation Devos.

For second generation Devos, the child link will always be null; however, some of these Devos may be married. Members of the first generation may or may not be married, and may or may not have children.

After the program has formed the linked list, it should print out the family members in the following form, beginning with the head of the Devo family and his/her children.

>
     1    1st Generation Name      Spouse name
     2    Child Name               Spouse name
     2    Child Name               Spouse name
          .     .                  .      .
          .     .                  .      .
     1    1st Generation Name      Spouse name
     2    Child Name               Spouse name
          .     .                  .      .

If there is no spouse, that field should be left blank. Devos that have been deleted must not be printed.

Suggestions on how to build the linked list

1. Plan to read the relationship records one at a time and search pieces of the linked list for FMA and/or FMB. Based upon what the relationship is and whether or not FMA and FMB are found you can determine the action necessary. (A table that follows indicates specifics.)

2. Set up an array of family piece pointers. Because the records in the file are not well ordered, you will have several disconnected pieces of the family as you are going along, but by the end, it should form a single list as shown before.

3. Pay attention to the guarantees given at the end. They will eliminate some difficult cases and make the task easier.

4. If you wish, you may use nodes in a form other than the specified one. Also, you may make the whole linked list or portions of it circular and/or doubly linked. You may use header nodes if you find them convenient.

The following table indicates the specific actions your program should take in most situations. These situations relate to whether or not FMA and FMB are found during the searches in suggestion #1.

     Which Found         Action
     -----------         -----------------------------------
     FMA and FMB         Can happen only when the relationship
                         is CHILD OF.  Make the connection.


     FMA only            Get a node for FMB and make the 
                         connection.  Can't happen for SPOUSE OF.


     FMB only            For DEATH OF, delete node for FMB.
                         For SPOUSE OF, fill in spouse field.
                         For others, get node for FMA and make
                         the connection.


     Neither             For SPOUSE OF, get a node and fill in.
                         For others, get 2 nodes and make the
                         connection.

GUARANTEES

1. There are no contradictory relationship records.

2. Everyone in the Devo family has a unique name.

3. A DEATH OF record will occur only after that family member is in the list somewhere.

4. A death will occur only for people who are not married and have no children. Thus, that person's node can safely be deleted.

5. The first relationship record has the head of the family in the FMB field.

6. No SIBLING OF record will occur in which both FMA and FMB have appeared in previous records.