Previous Section
 < Free Open Study > 
Next Section


Chapter 6

    1. The special case of changing the external list pointer when a node is added to or deleted from the beginning of the list.

    2. The check for the end of the list is eliminated from the search function.

    3. No. Popping and pushing always change the external pointer.

    4. Yes. The special cases of adding a new node to an empty queue and removing the last node from a queue can be eliminated with dummy nodes.

    5. The special case of changing the external list pointer when a node is added to an empty list or when the last node is deleted from the list leaving it empty.

  1. The member functions Enqueue and Dequeue would have to be changed.

  2. template<class ItemType>
    void SortedType<ItemType>::PrintReverse() const
    // Pre:  List is not empty.
    // Post: List is printed in reverse order.
    {
    NodeType<ItemType>* location = listData;
    StackType<ItmType> stack;
    ItemType item;
    do {
    stack.Push(location->info);
    location = location->next; } while (location != listData): while (!stack.IsEmpty()) {
    stack.Pop(item);
    std::cout << item << end1; } }
    
  3. The class SpecializedList provides no way to directly access the items within the list, so a derived class could not insert items into the list. The only accessing mechanisms provided are insertion at the beginning and insertion at the end.

  4. No, the class definition would not have to be changed. Only the definition of NodeType would have to be changed.

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

    template <class ItemType>
    void StackType<ItemType>::Copy(StackType<ItemType>& anotherStack)
    {
      NodeType<ItemType>* ptr1;
      NodeType<ItemType>* ptr2;
    
      if (topPtr == NULL)
        anotherStack.topPtr = NULL;
      else
      {
        anotherStack.topPtr = new NodeType<ItemType>;
        anotherStack.topPtr->info = topPtr->info;
        ptrl = topPtr->next;
        ptr2 = anotherStack.topPtr;
        while (ptr1 != NULL)
        {
          ptr2->next = new NodeType<ItemType>;
          ptr2 = ptr2->next;
          ptr2->info = ptr1->info;
          ptrl = ptr1->next;
        }
        ptr2->next = NULL;
      }
    }
    
    1. Doubly linked

    2. Circular

    3. List with header and trailer

  1. Initialization has O(N) complexity, where N is the size of the array of records; GetNode and FreeNode have O(1) complexity.

    1. Click To expand


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