Previous Section
 < Free Open Study > 
Next Section


Exercises

  1. Dummy nodes are used to simplify list processing by eliminating some "special case."

    1. What special case is eliminated by a header node in a linear linked list?

    2. What special case is eliminated by a trailer node in a linear linked list?

    3. Would dummy nodes be useful in implementing a linked stack? That is, would their use eliminate a special case?

    4. Would dummy nodes be useful in implementing a linked queue with a pointer to both head and rear elements?

    5. Would dummy nodes be useful in implementing a circular linked queue?

  2. Implement the class constructor, destructor, and copy constructor for the circular linked list class.

  3. If you were going to implement the FIFO Queue ADT as a circular linked list, with the external pointer accessing the "rear" node of the queue, which member functions would you need to change?

  4. Write a member function PrintReverse that prints the elements on a list in reverse order. For instance, for the list X Y Z, list.PrintReverse() would output Z Y X. The list is implemented as a circular list with listData pointing to the first element in the list. You may assume that the list is not empty.

  5. Can you derive a type DLList from the class SpecializedList that has a member function InsertItem that inserts the item into its proper place in the list? If so, derive the class and implement the function. If not, explain why not.

  6. If you were to rewrite the implementation of the Sorted List ADT using a doubly linked list, would you have to change the class definition? If so, how?

  7. Outline the changes to the member functions that would be necessary to implement the Sorted List ADT as a doubly linked list.

  8. Write a member function Copy of the Stack ADT, assuming that the stack named in the parameter list is copied into self.

  9. Write a member function Copy of the Stack ADT, assuming that self is copied into the stack named in the parameter list.

  10. Using the circular doubly linked list below, give the expression corresponding to each of the following descriptions.

    Click To expand

    (For example, the expression for the info member of Node 1, referenced from pointer A, would be A->info.)

    1. The info member of Node 1, referenced from pointer C

    2. The info member of Node 2, referenced from pointer B

    3. The next member of Node 2, referenced from pointer A

    4. The next member of Node 4, referenced from pointer C

    5. Node 1, referenced from pointer B

    6. The back member of Node 4, referenced from pointer C

    7. The back member of Node 1, referenced from pointer A

  11. The text edited by a line editor is represented by a doubly linked list of nodes, each of which contains an 80-column line of text (type LineType). There is one external pointer (type LineType*) to this list, which points to the "current" line in the text being edited. The list has a header node, which contains the string "- - - Top of File - - -" and a trailer node, which contains the string "- - - Bottom of File - - -".

    1. Draw a sketch of this data structure.

    2. Write the type declarations to support this data structure.

    3. Write the class constructor, which sets up the header and trailer nodes.

    4. Code the following operations:

    5. Describe the operations in part (d) in terms of Big-O notation. How could you change the list to make these operations 0(1)?

    6. Code the InsertLine operation, using the following specification:

    7. What other member functions should be included?

  12. Of the three variations of linked lists (circular, with header and trailer nodes, and doubly linked), which would be most appropriate for each of the following applications?

    1. You want to search a list for a key and return the keys of the two elements that come before it and the keys of the two elements that come after it.

    2. A text file contains integer elements, one per line, sorted from smallest to largest. You must read the values from the file and create a sorted linked list containing the values.

    3. A list is short and frequently becomes empty. You want a list that is optimal for inserting an element into the empty list and deleting the last element from the list.

  13. What is the Big-O measure for initializing the free list in the array-based linked implementation? For the functions GetNode and FreeNode?

  14. Use the linked lists contained in the array pictured in Figure 6.19 to answer the following questions:

    1. What elements are in the list pointed to by list1?

    2. What elements are in the list pointed to by list2?

    3. What array positions (indexes) are part of the free space list?

    4. What would the array look like after the deletion of Nell from the first list?

    5. What would the array look like after the insertion of Anne into the second list? Assume that before the insertion the array is as pictured in Figure 6.19.

  15. An array of records (nodes) is used to contain a doubly linked list, with the next and back members indicating the indexes of the linked nodes in each direction.

    1. Show how the array would look after it was initialized to an empty state, with all the nodes linked into the free-space list. (The free-space nodes have to be linked in only one direction.)

      Click To expand
    2. Draw a box-and-arrow picture of a doubly linked list into which the following numbers are inserted into their proper places: 17, 4, 25.

    3. Fill in the contents of the array on the next page after the following numbers are inserted into their proper places in the doubly linked list: 17, 4, 25.

      Click To expand
    4. Show how the array in part (c) would look after 17 is deleted.

      Click To expand
  16. Discuss the changes that would be necessary if more than one digit is stored per node in the LargeInt class.

  17. Distinguish between static and dynamic binding of functions.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)