2. If each record of a list has, in addition to its information and link fields, a "pred" field, then the list is called a two-way list. The pred field contains a pointer to the preceding record. The first record's pred field contains a null pointer. Write insertion and deletion functions corresponding to those of Section 3.3 for a two-way list.
3. A circular list is a list whose last record's link field contains a pointer to the first list record rather than a null pointer. Write insertion and deletion routines corresponding to those of Section 3.3 for a circular list.
4. Modify the solution to Example 3.1 so it is correct for
a. two-way list
b. A circular list
5. Write a function to interchange the records of a list that are pointed to by p1 and p2.
6. The solution developed for Example 3.1 essentially cycles pointers from one list record to the next. Instead, a solution could cycle information field values from one record to the next. Modify the solution so that it does this and compare the two execution times. What if the information field contains only a pointer to the actual information field value?
7. Consider the three arrays below?/FONT>data, p, and s.
An ordering of the integers in data is specified by p and by s . Arrays p[i] and s[i] point to the predecessor and successor of the integer stored in data[i]. A minus one indicates no predecessor or successor. Assume the first i elements of data, p, and s are properly set, as above, to reflect the usual ordering of integers. Suppose a new integer is placed into data[i+1].
a. If i is 10 and the new integer is 15, what will the new p and s arrays be after they are properly updated to reflect the correct ordering among the eleven integers? The data array, except for 15 being placed in position 10, is to be unchanged.
b. Write a program segment to update p and s after a new integer is placed in data. You might want to assume that first and last point, respectively, to the element of data containing the first and last integers in the ordering.
8. a. What does traverse (Section 3.4) do when process interchanges the record that recordpointer points to with its successor record?
b. Same as Exercise 8(a) except that, in addition, process then sets recordpointer to the link field value of the record to which it points.
9. Write a function to delete all the records from list l1 that also appear on the list 12.
In Exercises 10-13 you must turn traverse of Section 3.4 into a solution to the exercise by defining its functions properly.
10. Write a function to delete all duplicate records from an alphabetical list such as that of Example 3.4.
11. Write a function to insert a new record in front of the record pointed to by ptr. You should not keep track of a predecessor nor traverse the list to find a predecessor. A "trick" is involved here (see Section 3.3.4).
12. This is the same as Example 3.4, but assume the list is implemented as a two-way list.
13. Create a new list that is the same as l except that each record has been duplicated, with the duplicate inserted as the new successor of the record it duplicates.
14. Create a list l that consists of all the records of the list l1 followed by all the records of the list 12.
15. Write a function to print out the number of words for a list such as that of Example 3.2.
16. Write the required functions for traverse of Section 3.4 when list records are stored in dynamic memory and the list is implemented as
a. A two-way list
b. A circular list
17. A hospital has 100 beds. The array records contains records that represent, by floor and bed number, those beds that are not occupied. The first, second, and third elements of a record contain the floor number, bed number, and link value, respectively. How many beds are not occupied and what is the lowest floor with an available bed?
18. Change the appropriate pointers for Exercise 17 so that the records are kept in order by floor and bed number.
19. Show what the arrays floor, bed, and next might have in their entries if the beds list of Exercise 17 were implemented using three corresponding words of these arrays.
20. How would the records array of Exercise 17 change if bed 2 on the fifth floor became occupied?
21. Suppose bed 10 on the sixth floor became empty. Assuming that the records array is used only for the beds list, what changes might be made to it to reflect this new information?
22. This is the same as Exercise 16 except that the list records are stored in an array records .
23. A palindrome is a sequence of characters that reads the same from front to back as from back to front. ABCDDCBA, ABCBA, and NOON are palindromes. Write a function palindrome to return the value true if the list it is called to check represents a palindrome, and the value false otherwise. The list records are stored in dynamic memory.
24. Suppose four records, 13, 7, 1, and 2, were deleted from lists whose records are stored in records of Figure 3.13. Then three records were inserted. If reclaim returns records at the front of availist, depict the availist and records after this processing.
25. Do the same as in Exercise 24, but assume that reclaim returns records at the rear of availist.
26. a. Why isn't it reasonable for avail to delete a record from anywhere on availist except the front or rear?
b. Why isn't it reasonable for reclaim to insert a record anywhere on availist except the front or rear?
27. Suppose a record is deleted from a list stored in records, but reclaim is not invoked to return it to availist. Is it ever possible to reuse the storage relinquished by that record?
28. Suppose records with different lengths are stored in records using the techniques of Chapter 2. The availist contains the available records in arbitrary order. Describe how avail and reclaim might be implemented.
29. This is the same as Exercise 28, except that the availist contains the available records ordered by length.
30. Write a function to create a list whose records are defined by
The input should consist of a sequence of information field values given in the order they should appear in the list. Linkptr points to the next record on the list, and prevptr points to the preceding record on the list.
31. Explain why pointer variables and the functions malloc and free remove the need for the programmer to manage storage for list records.
32. Both the sequential array and list representations for ordered records use arrays. Why are they different?
33. Suppose you are asked to store records that represent an inventory of books that are currently signed out from the library. Assume that frequent requests are made for output that includes the book title and the current borrower in alphabetical order by the borrower's name. Of course, books are frequently taken out and returned. Should a sequential array be used for the records or a list representation? Why?
34. Suppose records are stored using the sequential array implementation. Initially 1,000 records are stored. You are asked to delete every other record, starting with the first. After this deletion you must insert records before every third record, starting with the first record. Find an expression for the total number of shifts of records that must take place to accomplish these insertions and deletions.
35. Do Exercise 34, but instead of assuming a sequential implementation assume a list implementation.
36. Suppose you must access records in the order tenth, first, twelfth, thirtieth, and fiftieth. How much time will the five accesses take with a sequential representation, and how much time will they take with a list representation?
37. Describe a real-life situation in which the sequential array representation of ordered records is clearly more desirable, another in which the list representation is clearly favored, and a third situation that involves trade-offs between the two representations.
38. a. Write the initial and original routines for the array implementation of the perfect shuffle and for the list implementation of the perfect shuffle in Section 3.9.
b. Can original be reduced to checking only the nth card to see if it has returned to the initial configuration?
DATA P S
---------------
0 1 -1 5
1 12 4 6
2 18 6 8
3 4 5 9
4 7 9 1
5 3 0 3
6 12 1 2
7 100 8 -1
8 20 2 7
9 5 3 4
typedef struct node
{whatevertype info;
struct node *linkptr;
struct node *prevptr;
}listnode;