2. Draw pictures, similar to p of Figure 6.1(d), for the polynomials
z2(y2(x(8))) + z(y(3x)) + y(x) + 18 and x3yz + 2xz + y2xz3
3. Give a recursive definition for a chain.
4. Why do the two definitions of list-structures not allow more than one pointer to a record, or loops, to occur in a list-structure?
5. Why does a null ptr and an empty stack indicate the end of the traversal of a list-structure?
6. What will be in the stack when record 20 of formula (Figure 6.4) is accessed?
7. Simulate the execution of the iterative implementation of traverse on p of Figure 6.1(d).
8. Simulate the execution of the recursive implementation of traverse on p of Figure 6.1(d).
9. Give an example of a list containing loops for which the traversal functions fail because they do not terminate.
10. a. Write a process function to turn the iterative traversal into a program that prints the number of sublists of a list-structure.
b. Will your solution also work for the recursive traversal?
11. a. Write a function to return a pointer to the record of a list-structure that has the maximum information field value.
b. Modify your solution to return a pointer to a list. The list should contain pointers to all records whose information field value coincides with the maximum value.
12. Give an algorithm to determine whether two list-structures whose records have the same format are identical.
13. Modify your solution to Exercise 12 so that the algorithm determines whether the two list-structures have the same "structure," independent of the information values stored.
14. Each complex record of a list-structure has a field pointing to the record's sublist. The sublist is composed of a main list (composed of the chain of records linked by their link fields). Suppose each complex record of a list-structure also has a field called number that contains the number of records on the complex records sublist. Write a process function to turn the traverse functions into a program to insert a record after the record whose information field value is value. The program must, of course, also correctly update the number field for the appropriate sublist.
15. Write a function to implement evaluate (Example 6.9).
16. Modify your solution to Exercise 15 so that it outputs the evaluation of each operation as it occurs.
17. Modify your solution to Exercise 16 so that it prints out an appropriate message, such as "too many operands for the operator PS of the sublist of record 7" or "missing operands for the operator PS of the sublist of record 7," whenever the list-structure does not represent a valid arithmetic expression.
18. Assume that p points to a record of Example 6.9 containing an operator or operand. Suppose ptr points to a record of a sublist after which the record pointed to by p is to be inserted. It is to be inserted as the first record of a sublist if it is an operator, and as the next record on the sublist if it is an operand. Write an insertion function to accomplish this. For example, suppose the list-structure, ls, is currently:
If ptr points to DIFF, and the record pointed to by p contains PS, then after insertion ls will be
If the record pointed to by p contained 432.713, then after insertion ls would have been
19. Insertion and deletion of records in list-structures is similar to their insertion and deletion in chains. However, the deletion of a sublist has ramifications for the reclaim function of Chapter 3. Discuss these, and explain how they might be resolved by modifying the definition of reclaim or by increasing the responsibility of the programmer. In either case, the idea is to be sure all unused records are returned to availist.
20. Modify paragraphinsert (Example 6.8) so that all deleted records are returned to the availist.
21. Let ptr and pv point, respectively, to a record of a list-structure and to its preceding record. Write a function to delete the record pointed to by ptr if it is simple, and to replace it with the list-structure to which it points if it is complex. For example, consider the following list-structure.
If ptr points to 17, then the function produces
If ptr points to the complex record following 17, then the function produces
22. Give an implementation of next and sublist of the function traverse (Section 6.2.1) for each declaration of the polynomial p.
23. Give a declaration for the records of Example 6.8 using dynamic memory and write implementations for all the functions of traverse and process that depend on this implementation.
24. Draw a picture, corresponding to Table 6.2, for the complete input data (31 names) of Example 6.11.
25. Modify the answer to Exercise 24 to reflect the lists of children being kept as circular lists.
26. Show the complete situation in the arrays of your solution to Exercise 24 after the input below is processed.
27. Show the complete situation after the input of Exercise 26 is processed, when circular lists are used for the lists of children.
28. Suppose the records of Example 6.11 were to be kept in alphabetical order by the name in the name field. What would the arrays look like after all the input data were processed?
29. How does the algorithm for updating the information base given another input record (p. 287) have to be modified if inputs are allowed for which one or more field values are unknown?
30. Write two functions for Example 6.11, children(person) and brothers(person). They should print out the names of all children and all brothers of person, respectively. Simulate the behavior of the functions on the data of the example.
31. Modify your solutions to Exercise 30 so that the functions will work on circular lists of children.
32. Suppose the nametable is implemented as a list. How will your solutions to Exercises 30 and 31 be modified?
33. Write an algorithm to print out the names of individuals who were born before 1900. How much time will your algorithm take?
34. Can you find a way to implement the information system so that a faster solution can be obtained for Exercise 33? If you find a faster solution, then determine how its update time will compare to that for Exercise 33.
35. Write a detailed description for a routine that will delete an individual record and its nametable entry from the system. This implies that all relevant pointers will be properly modified and that storage will be reclaimed.
JOHANN 0AMBROSIUS BACH M 2/22/1695 CHRISTOPH BACH
MARIA MAGDALENA GRABLER