创建两个链表的联合

Question

我正在尝试创建一个联合两个链表的函数。我创建了一个函数，它完全按照我想做的做，但是作为一组集合而不是我将在下面提供的节点。

我的限制如下：我可以使用 contains() 和节点 class 访问器和修改器，但除此之外，我不能在联合函数的定义中使用任何函数调用操作必须在不调用任何其他函数来帮助的情况下进行编码。

如能提供任何指导或帮助以走上正轨，我们将不胜感激。

这是我尝试将其编码为链表的函数的数组集版本：

    template <class ItemType>
    ArraySet<ItemType> ArraySet <ItemType> ::setUnion(const ArraySet<ItemType> set2)
    {

        ArraySet<ItemType> unionSet;

        for (int i = 0; i < getCurrentSize(); i++)
        {
            unionSet.add(items[i]);
        }

        for (int i = 0; i < set2.getCurrentSize(); i++)
        {
            unionSet.add(set2.items[i]);
            if (items[i] == set2.items[i])
                unionSet.remove(set2.items[i]);
        }

   
        return unionSet;
    }

这是我的 LinkedSet class:

#ifndef LINKED_SET_
#define LINKED_SET_

#include "SetInterface.h"
#include "Node.h"

namespace cs_set {

    template<class ItemType>
    class LinkedSet : public SetInterface<ItemType>
    {
        private:
            Node<ItemType>* headPtr;
            int itemCount;

            // Returns either a pointer to the node containing a given entry
            // or nullptr if the entry is not in the bag.
            Node<ItemType>* getPointerTo(const ItemType& target) const;
            void clone(const LinkedSet<ItemType>& copyMe);  //Copy function

        public:
            class ItemNotFoundError {};
            class DuplicateItemError {};
            LinkedSet();    //Constructor #Big3
            LinkedSet operator=(const LinkedSet<ItemType>& right);  //Assignment operator
            LinkedSet(const LinkedSet<ItemType>& aSet); //Copy Constructor #Big3
            virtual ~LinkedSet();   //Destructor #Big3
            int getCurrentSize() const;
            bool isEmpty() const;
            void add(const ItemType& newEntry);
            void remove(const ItemType& anEntry);
            void clear();
            bool contains(const ItemType& anEntry) const;
            LinkedSet<ItemType> setUnion(const LinkedSet<ItemType>* set2);
            LinkedSet<ItemType> setIntersection(const LinkedSet<ItemType>* set2);
            LinkedSet<ItemType> setDifference(const LinkedSet<ItemType>* set2);
            //int getFrequencyOf(const ItemType& anEntry) const;
            std::vector<ItemType> toVector() const;
    };
}

#include "LinkedSet.cpp"
#endif

LinkedSet 函数：

#include "Node.h"
#include "LinkedSet.h"
#include <cstddef>

namespace cs_set {

    template<class ItemType>
    LinkedSet<ItemType>::LinkedSet() {
        headPtr = nullptr;
        itemCount = 0;
    }


    template<class ItemType>
    void LinkedSet<ItemType>::clone(const LinkedSet<ItemType>& copyMe) {
        itemCount = copyMe.itemCount;
        Node<ItemType>* origChainPtr = copyMe.headPtr;

        if (origChainPtr == nullptr) {
            headPtr = nullptr;
        }
        else {
            // Copy first node
            headPtr = new Node<ItemType>();
            headPtr->setItem(origChainPtr->getItem());

            // Copy remaining nodes
            Node<ItemType>* newChainPtr = headPtr;
            origChainPtr = origChainPtr->getNext();

            while (origChainPtr != nullptr) {
                // Get next item from original chain
                ItemType nextItem = origChainPtr->getItem();

                // Create a new node containing the next item
                Node<ItemType>* newNodePtr = new Node<ItemType>(nextItem);

                // Link new node to end of new chain
                newChainPtr->setNext(newNodePtr);

                // Advance pointer to new last node
                newChainPtr = newChainPtr->getNext();

                // Advance original-chain pointer
                origChainPtr = origChainPtr->getNext();
            }

            newChainPtr->setNext(nullptr);
        }
    }


    /* BACKUP JUST INCASE I MESS THINGS UP

    template<class ItemType>
    void LinkedSet<ItemType>::clone(const LinkedSet<ItemType>& aSet) {
        itemCount = aSet.itemCount;
        Node<ItemType>* origChainPtr = aSet.headPtr;

        if (origChainPtr == nullptr) {
            headPtr = nullptr;
        } else {
            // Copy first node
            headPtr = new Node<ItemType>();
            headPtr->setItem(origChainPtr->getItem());

            // Copy remaining nodes
            Node<ItemType>* newChainPtr = headPtr;
            origChainPtr = origChainPtr->getNext();

            while (origChainPtr != nullptr) {
                // Get next item from original chain
                ItemType nextItem = origChainPtr->getItem();

                // Create a new node containing the next item
                Node<ItemType>* newNodePtr = new Node<ItemType>(nextItem);

                // Link new node to end of new chain
                newChainPtr->setNext(newNodePtr);

                // Advance pointer to new last node
                newChainPtr = newChainPtr->getNext();

                // Advance original-chain pointer
                origChainPtr = origChainPtr->getNext();
            }

            newChainPtr->setNext(nullptr);
        }
    }

    */



    template<class ItemType>
    LinkedSet<ItemType>::~LinkedSet() {
       clear();
    }





    template<class ItemType>
    bool LinkedSet<ItemType>::isEmpty() const {
        return itemCount == 0;
    }





    template<class ItemType>
    int LinkedSet<ItemType>::getCurrentSize() const {
        return itemCount;
    }





    template<class ItemType>
    void LinkedSet<ItemType>::add(const ItemType& newEntry) {
    
        for (Node<ItemType>* nodePtr = headPtr; nodePtr; nodePtr = nodePtr->getNext())
        {
            if (nodePtr->getItem() == newEntry)
                throw DuplicateItemError();
        } 

        Node<ItemType>* nextNodePtr = new Node<ItemType>();
        nextNodePtr->setItem(newEntry);
        nextNodePtr->setNext(headPtr);

        headPtr = nextNodePtr;          // New node is now first node
        itemCount++;
    }





    template<class ItemType>
    std::vector<ItemType> LinkedSet<ItemType>::toVector() const {
        std::vector<ItemType> setContents;
        Node<ItemType>* curPtr = headPtr;
        while ((curPtr != nullptr)) {
            setContents.push_back(curPtr->getItem());
            curPtr = curPtr->getNext();
        }

        return setContents;
    }





    template<class ItemType>
    void LinkedSet<ItemType>::remove(const ItemType& anEntry) {
        Node<ItemType>* entryNodePtr = getPointerTo(anEntry);
        if (entryNodePtr == nullptr) {
            throw ItemNotFoundError();
        } else {
            // replace data of node to delete with data from first node
            entryNodePtr->setItem(headPtr->getItem());

            // Delete first node
            Node<ItemType>* nodeToDeletePtr = headPtr;
            headPtr = headPtr->getNext();
            delete nodeToDeletePtr;

            itemCount--;
        }
    }





    template<class ItemType>
    void LinkedSet<ItemType>::clear() {
        Node<ItemType>* nodeToDeletePtr = headPtr;
        while (headPtr != nullptr) {
            headPtr = headPtr->getNext();
            delete nodeToDeletePtr;
            nodeToDeletePtr = headPtr;
        }

        headPtr = nullptr;
        itemCount = 0;
    }




    /*
    template<class ItemType>
    int LinkedSet<ItemType>::getFrequencyOf(const ItemType& anEntry) const {
        int frequency = 0;
        int counter = 0;
        Node<ItemType>* curPtr = headPtr;
        while ((curPtr != nullptr) && (counter < itemCount)) {
            if (anEntry == curPtr->getItem()) {
                frequency++;
            }

            counter++;
            curPtr = curPtr->getNext();
        }

        return frequency;
    }

    */



    template<class ItemType>
    bool LinkedSet<ItemType>::contains(const ItemType& anEntry) const {
        return (getPointerTo(anEntry) != nullptr);
    }





    // private
    // Returns either a pointer to the node containing a given entry 
    // or nullptr if the entry is not in the bag.

    template<class ItemType>
    Node<ItemType>* LinkedSet<ItemType>::getPointerTo(const ItemType& anEntry) const {
        bool found = false;
        Node<ItemType>* curPtr = headPtr;

        while (!found && (curPtr != nullptr)) {
            if (anEntry == curPtr->getItem()) {
                found = true;
            } else {
                curPtr = curPtr->getNext();
            }
        }

        return curPtr;
    }

    template <class ItemType>
    LinkedSet<ItemType>  LinkedSet<ItemType>::operator=(const LinkedSet<ItemType>& right) {
        if (this != &right) {
            clear();
            clone(right);
        }
        return *this;
    }

    template<class ItemType>
    LinkedSet<ItemType> ::LinkedSet(const LinkedSet<ItemType>& aSet)
    {
        clone(aSet);
    }

    /* This function is responsible for merging two sets together
    to create one big set by using for loops to add the contents
    of the array sets and also detecting / removing duplicates
    @param set2 used to define the set being used

    @return it returns the merged set

    */

    template <class ItemType>
    LinkedSet<ItemType> LinkedSet <ItemType> ::setUnion(const LinkedSet<ItemType>* set2)
    {

    }

    /*
    This function is responsible for detecting if matching
    values of two sets are detected. For example, if one set
    has {1,2,3) and the second has the same then there are
    three elements that intersect.

    @param set2 used to define the set

    @retunr returns the intersected values
    */

    template <class ItemType>
    LinkedSet<ItemType> LinkedSet<ItemType>::setIntersection(const LinkedSet<ItemType> set2)
    {

    }

    /*
    This function is responsible for detecting values that are present
    in the first set and not the second for example, if set one has values
    (1,2,3,4,5,6,7) and set2 has values (1,2,3) then the difference is
    the elements 1,2,3

    @param set2 used to define the set

    @return returns the differences aka numbers that do not appear in the second set

    */

    template<class ItemType>
    LinkedSet<ItemType> LinkedSet<ItemType>::setDifference(const LinkedSet<ItemType> set2)
    {

    }

}

节点Class:

#ifndef NODE_
#define NODE_

namespace cs_set {

    template<class ItemType>
    class Node {
        private:
           ItemType item;
           Node<ItemType>* next;

        public:
           Node(const ItemType& anItem = ItemType(), Node<ItemType>* nextNodePtr = nullptr);
           void setItem(const ItemType& anItem);
           void setNext(Node<ItemType>* nextNodePtr);
           ItemType getItem() const ;
           Node<ItemType>* getNext() const ;
    };
}

#include "Node.cpp"
#endif

节点Class函数：

#include "Node.h"

namespace cs_set {
    template<class ItemType>
    Node<ItemType>::Node(const ItemType& anItem, Node<ItemType>* nextNodePtr) {
        item = anItem;
        next = nextNodePtr;
    }





    template<class ItemType>
    void Node<ItemType>::setItem(const ItemType& anItem) {
       item = anItem;
    }





    template<class ItemType>
    void Node<ItemType>::setNext(Node<ItemType>* nextNodePtr) {
       next = nextNodePtr;
    }





    template<class ItemType>
    ItemType Node<ItemType>::getItem() const {
       return item;
    }





    template<class ItemType>
    Node<ItemType>* Node<ItemType>::getNext() const {
       return next;
    }
}

设置接口class:

#ifndef SET_INTERFACE
#define SET_INTERFACE

#include <vector>
#include <algorithm>
#include <iterator>

namespace cs_set {
    template<class ItemType>
    class SetInterface
    {
    public:
       /** Gets the current number of entries in this bag.
        @return  The integer number of entries currently in the set. */
       virtual int getCurrentSize() const = 0;

       /** Sees whether this set is empty.
        @return  True if the set is empty, or false if not. */
       virtual bool isEmpty() const = 0;

       /** Adds a new entry to this set.
        @post  If successful, newEntry is stored in the set and
           the count of items in the set has increased by 1.
        @param newEntry  The object to be added as a new entry.
        @return  True if addition was successful, or false if not. */
       virtual void add(const ItemType& newEntry) = 0;

       /** Removes one occurrence of a given entry from this set,
           if possible.
        @post  If successful, anEntry has been removed from the set
           and the count of items in the bag has decreased by 1.
        @param anEntry  The entry to be removed.
        @return  True if removal was successful, or false if not. */
       virtual void remove(const ItemType& anEntry) = 0;

       /** Removes all entries from this set.
        @post  set contains no items, and the count of items is 0. */
       virtual void clear() = 0;

       /** Counts the number of times a given entry appears in this set.
        @param anEntry  The entry to be counted.
        @return  The number of times anEntry appears in the set. */
      // virtual int getFrequencyOf(const ItemType& anEntry) const = 0;

       /** Tests whether this set contains a given entry.
        @param anEntry  The entry to locate.
        @return  True if bag contains anEntry, or false otherwise. */
       virtual bool contains(const ItemType& anEntry) const = 0;

       /** Empties and then fills a given vector with all entries that
           are in this set.
        @return  A vector containing all the entries in the bag. */
       virtual std::vector<ItemType> toVector() const = 0;

       /** Destroys this set and frees its assigned memory. (See C++ Interlude 2.) */
       virtual ~SetInterface() { }
    };
}
#endif

我要实现的输出是：

第 1 组包含：一二三

第 2 组包含：四五六

两个集合的并集是：

一二三四五六

Answer 1

如何统一两个列表有多种选择。

最容易编写代码的解决方案是连接两个列表，然后检查每个元素是否在列表中有另一个相等的元素，如果不是第一个，则将其删除。
一种中间解决方案是连接列表，对组合列表进行排序，然后遍历列表并用元素的一个实例替换连续运行的相等元素。
通常计算上最不复杂的解决方案是使用散列将两个列表转换为一个集合。然后就大功告成了，可以return集合中的元素了。

我想你会选择第 3 种。使用 std 你会做：

template<typename T>
std::list<T> unify(const std::list<T>& a, const std::list<T>& b) {
  std::unordered_set<T> combined_set;
  combined_set.insert(a.begin(),a.end());
  combined_set.insert(b.begin(),b.end());
  std::list<T> result;
  for (auto& element : combined_set) result.push_back(element);
  return result;
}

创建两个链表的联合

Creating a Union of two linked lists

c++

class

pointers

linked-list

adt