Как написать определение функции для этого прототипа

Question

Я написал прототип для клиентской функции под названием "mergeLists", которая объединяет два отсортированных списка в третий отсортированный список:

template <class Item Type>
void mergeList (const SortedList < ItemType> & list1,
                       const SortedList < ItemType > & list2,
                       SortedList < ItemType > & result);

Он использует отсортированный класс SortedList:

#ifndef SORTEDLIST_H
#define SORTEDLIST_H
#include <iostream>
#include <cstdlib>   // Needed for the exit function
using namespace std;

const int MAX_LENGTH = 100; // Maximum number of components

template <class ItemType> // You may also choose to use
                          // typedef statement
class SortedList
{
public:
    // Constructor
    SortedList();
    // Post: Empty list has been created. length has been set to zero.

    // Knowledge responsibilities
    int getLength() const;
    // Post: Returns the length of the list
    bool isEmpty() const;
    // Post: Returns true if list is empty; false otherwise
    bool isFull() const;
    // Post: Returns true if list is full; false otherwise
    bool isInList(const ItemType& item) const;
    // Post: Returns true if item is int the list; false otherwise
    int binarySearch(const ItemType& item) const;
    // Function to search the list for a given item using binary 
    // search algorithm.
    // Post: If item is found, returns the index in the array where
    // item is found; otherwise, return -1.

    // Action Responsibilities
    void resetList();
    // Post: The list becomes empty. length has been set to zero.
    void insert(const ItemType& item);
    // Function to insert item to the list. However, first 
    // the list is searched to see whether the item to be inserted is
    // already in the list.
    // Pre: The list items are sorted in ascending order.
    // Post: item is in the list and list items are sorted in ascending
    // order. If item is added, length++; if the list is already full or
    // item is already in the list, an appropriate message is displayed.
    void remove(const ItemType& item);
    // Function to remove item from the list. 
    // Pre: The list items are sorted in ascending order.
    // Post: If item is found in the list, it is removed from the list
    // and length is decremented by one. The list items remain sorted in
    // ascending order.

    // Overloaded [] operator declaration.  
        // This function returns a reference to the element in the 
    // array indexed by index.               
    ItemType& operator[](const int& index);

private:
    ItemType list[MAX_LENGTH]; // array to hold the list elements
    int length;                // to store the length of the list
};


//**********************************************************
template <class ItemType>
SortedList<ItemType>::SortedList()
{
    length = 0;
}

//**********************************************************
template <class ItemType>
int SortedList<ItemType>::getLength() const
{
    return length;
}

//**********************************************************
template <class ItemType>
bool SortedList<ItemType>::isEmpty() const
{
    return (length == 0);
}

//**********************************************************
template <class ItemType>
bool SortedList<ItemType>::isFull() const
{
    return (length == MAX_LENGTH);
}

//**********************************************************
template <class ItemType>
bool SortedList<ItemType>::isInList(const ItemType& item) const
{
    int loc;
    loc = binarySearch(item);
    if (loc != -1)
        return true;
    else
        return false;
}

//**********************************************************
template <class ItemType>
int SortedList<ItemType>::binarySearch(const ItemType& item) const
{
    int first = 0;      // lower bound on list
    int last = length - 1;  // upper bound on list
    int middle;             // middle index
    bool found = false;

    while (last >= first && !found )
    {
        middle = (first + last ) / 2;
        if (item < list[middle])
            // item is not in list[middle..last]
            last = middle - 1;
        else if (item > list[middle])
            // item is not in list[first..middle]
            first = middle + 1;
        else
            // item == list[middle]
            found = true;
    }
    if (found)
        return middle;
    else 
        return -1;
}   

//**********************************************************
template <class ItemType>
void SortedList<ItemType>::resetList()
{
    length = 0;
}

//**********************************************************
template <class ItemType>
void SortedList<ItemType>::insert(const ItemType& item)
{
    int loc = length - 1; // the index for the inserted item
    if (length == MAX_LENGTH)  // check if the list is full
        cout << "Cannot insert in a full list." << endl;
    else if (binarySearch(item) != -1) // check if item is in list
        cout << "The item is already in the list. "
              << "No duplicates are allowed." << endl;
    else
    {
        // Search for insertion point beginning at the end. Items
        // are compared and shifted until insertion place is found.
        while (loc >= 0 && item < list[loc])
        {
            list[loc + 1] = list[loc];
            loc--;      
        }
        list[loc + 1] = item; // insert item
        length++;
    }
}

//*********************************************************
template <class ItemType>
void SortedList<ItemType>::remove(const ItemType& item)
{
    int loc;
    loc = binarySearch(item);
    if (loc == -1) // check if item is in list
        cout << "The item is not in the list. "
             << "Cannot delete a non-existing item." << endl;
    else
    {
        // Shift list[(loc+1)..length-1] up one position
        for (int index = loc + 1; index < length; index++)
            list[index - 1] = list[index];
        length--;           
    }
}

//**********************************************************
template <class ItemType>
ItemType& SortedList<ItemType>::operator[](const int& index)
{
   if (index < 0 || index >= length)
    {
        cout << "ERROR: Index out of range.\n";
        exit(EXIT_FAILURE);
    }

   return list[index];
}

#endif

Предварительные условия функции: list1 и list2 были инициализированы и отсортированы; list1 и list2 не имеют общих элементов. Постусловиями являются: результат представляет собой отсортированный список, который содержит все элементы из list1 и list2. Я хочу написать определение функции для mergeLists, используя этот класс SortedList, но я не уверен, как это сделать.

Я думаю, что это начнется примерно так:

SortedList <ItemType> & mergeList ( )

Answer 1

Декларация должна быть такой:

template <class ItemType>
void mergeList (const SortedList < ItemType> & list1,
                       const SortedList < ItemType > & list2,
                       SortedList < ItemType > & result);

Затем внутри списка вам нужно сделать:

• Выберите элемент по индексу i1 от list1,
• Выберите элемент по индексу i2 от list2,

Вставьте нижнюю из двух в resultи увеличивать соответствующий i1 или же i2,

Когда вы дойдете до конца любого списка, вставьте остальные элементы другого списка. Возможно, вам придется заботиться о дубликатах (если дублирование не разрешено, в том случае, если значение из list1 такой же, как в list2, то вы не должны вставлять оба).