Previous Section
 < Free Open Study > 
Next Section


Chapter 3

    1. bool IsThere(ItemType item) const;
      
    2. bool UnsortedType::IsThere(ItemType item)
      {
        bool moreToSearch;
        int location = 0;
        found = false;
      
        moreToSearch = (location < length);
        while (moreToSearch && !found)
        {
          switch (item.ComparedTo(info[location]))
          {
            case LESS    :
            case GREATER : location++;
                           moreToSearch = (location < length);
                           break;
            case EQUAL   : found = true;
                           break;
          }
        }
        return found;
      }
      
    3. O(N), where N is the number of items in the list.

  1. The specification and prototype are identical for the unsorted and sorted versions. Only the algorithm used to implement the search differs. Because the values in the list are sorted by key in Exercise 2, the binary search can be used to look for item. The binary search has O(log2N) complexity in contrast to the O(N) linear search that must be used in an unsorted list.

    1. bool IsThere(ItemType item, UnsortedType list)
      {
        ItemType item2;
        int counter = 1;
        bool found = false;
      
        list.ResetList();
        int length = list.LengthIs();
        while (counter <= length && !found)
        {
          list.GetNextItem(item2);
          if (item.ComparedTo(item2) == EQUAL)
            found = true;
          counter++;
        }
        return found;
      }
      

      or

      bool IsThere(ItemType item, UnsortedType list)
      {
        bool found;
      
        list.RetrieveItem(item, found);
        return found;
      }
      
    2. Both of these functions are O(N). The first is quite obviously; the second lets RetrieveItem, which is O(N), do the search.

    3. The member function has direct access to the array where the items are stored; the client has to use the class access functions to retrieve each item in turn or call the member function RetrieveItem. The order of IsThere is the same in both cases, but the overhead included with the constant is greater in the client version because of the extra function calls.

    1. void MergeLists(SortedType list1 , SortedType list2,
         SortedType& result);
      
    2. void MergeLists(SortedType list1, SortedType list2,
         SortedType& result)
      {
        int length1;
        int length2;
        int counter1 = 1;
        int counter2 = 1;
        ItemType item1;
        ItemType item2;
      
        length1 = list1.LengthIs();
        length2 = list2.LengthIs();
        list1.ResetList();
        list2.ResetList();
        list1.GetNextItem(item1);
        list2.GetNextItem(item2);
        result.MakeEmpty();
      
        while (counter1 <= length1 && counter2 <= length2)
          switch (item1.ComparedTo(item2))
          {
            case LESS   : result.InsertItem(item1);
                          if (counter1 < length1)
                            list1.GetNextItem(item1);
                          counter1++;
                          break;
            case GREATER: result.InsertItem(item2);
                          if (counter2 < length2)
                            list2.GetNextItem(item2);
                          counter2++;
                          break;
          }
        for (; counter1 <= length1; counter1++)
        {
          result.InsertItem(item1);
          if (counter1 < length1)
            list1.GetNextItem(item1);
        }
        for (; counter2 <= length2; counter2++)
        {
          result.InsertItem(item2);
          if (counter2 < length2)
            list2.GetNextItem(item2);
        }
      }
      
    3. Because the lists that are being merged are sorted, the complexity is O(N) times the complexity of the InsertItem operation.

    1. void UnsortedType::DeleteItem(ItemType item)
      {
      {
        int location = 0;
        bool found = false;
      
        while (!found && location < length)
        {
          if (item.ComparedTo(info[location]) == EQUAL)
            found = true;
          else
            location++;
        }
        if (found)
        {
          info[location] = info[length - 1];
          length--;
        }
      }
      
      
    2. void UnsortedType::DeleteItem(ItemType item)
      {
        int location = 0;
      
        while (location < length)
        {
          if (item.ComparedTo(info[location]) == EQUAL)
          {
            info[location] = info[length - 1];
            length--;
          }
          else
            location++;
        }
      }
      
    1. Same as Exercise 9(a).

    2. void SortedType::DeleteItem(ItemType item)
      {
        int location = 0;
        bool found = false;
      
        while (!found && location < length)
        {
          if (item.ComparedTo(info[location]) == EQUAL)
            found = true;
          else
            location++;
        }
        for (int index = location + 1; index < length; index++)
          info[index - 1] = info[index];
        length--;
      }
      
      
    3. Same as Exercise 9(c).

    4. void SortedType::DeleteItem(ItemType item)
      {
        int location = 0;
      
        while (location < length)
        {
          if (item.ComparedTo(info[location]) == EQUAL)
          {
            for (int index = location + 1; index < length; index++)
              info[index - 1] = info[index];
            length--;
          }
          else
            location++;
        }
      }
      
    1. Adding the function Head to the class UnsortedType would be easy because the last item inserted into the list is immediately accessible: info [length - 1].

    2. Adding the function Head to the class SortedType would be almost impossible. A separate unsorted list would have to be kept to implement this function.

  1. The advantage of having DeleteItem maintain the original order is being able to determine the original order. The specifications for UnsortedType indicate nothing about order, so adding this requirement defines a different ADT.

  2. None of the changes in Exercises 9 and 10 change the Big-O notation from that discussed in the chapter. Each of the delete operations still has order O(N).



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