1

好的，所以我记下了这段代码。

包接口

#ifndef BAGINTERFACE_H
#define    BAGINTERFACE_H

#include <vector>
#include <algorithm>

template<class ItemType>
class BagInterface
{
    public:

    virtual int getCurrentSize() const = 0;
    virtual bool isEmpty() const = 0;
    virtual bool add(const ItemType& newEntry) = 0;
    virtual bool remove(const ItemType& anEntry) = 0;
    virtual void clear() = 0;
    virtual int getFrequencyOf(const ItemType& anEntry) const = 0;
    virtual bool contains(const ItemType& anEntry) const = 0;
    virtual std::vector<ItemType> toVector() const = 0;
}; 

#endif    /* BAGINTERFACE_H */

袋子 #ifndef BAG_H #define BAG_H

#include "BagInterface.h"

template <class ItemType>
class Bag: public BagInterface<ItemType>
{

public:

    int getCurrentSize() const { return v.size(); }
    bool isEmpty() const { return v.empty(); }
    bool add(const ItemType& newEntry) { v.push_back(newEntry); return true; }
    bool remove(const ItemType& anEntry) { std::remove(v.begin(), v.end(), anEntry); return true; }
    void clear() { v.clear(); }
    int getFrequencyOf(const ItemType& anEntry) const { return std::count(v.begin(), v.end(), anEntry); }
    bool contains(const ItemType& anEntry) const { return true; }
    std::vector<ItemType> toVector() const { return v; }

private:

  std::vector<ItemType> v;

};

#endif    /* BAG_H */

和我的实际程序 main.cpp

#include <iostream> // For cout and cin
#include <string> // For string objects
#include "Bag.h" // For ADT bag
using namespace std;
int main()
{
string clubs[] = { "Joker", "Ace", "Two", "Three",
"Four", "Five", "Six", "Seven",
"Eight", "Nine", "Ten", "Jack",
"Queen", "King" };
// Create our bag to hold cards
Bag<string> grabBag;
Bag<string> dumpBag;

grabBag.add(clubs[1]);
grabBag.add(clubs[2]);
grabBag.add(clubs[4]);
grabBag.add(clubs[8]);
grabBag.add(clubs[10]);
grabBag.add(clubs[12]);

dumpBag.add(clubs[3]);
dumpBag.add(clubs[5]);
dumpBag.add(clubs[7]);
dumpBag.add(clubs[9]);
dumpBag.add(clubs[10]);
dumpBag.add(clubs[12]);

Bag<string> Itersection(Bag<string> bagToCompare){


    return grabBag;
}


return 0;
}; // end main

我试图找到两个袋子的交集，这将是一个新袋子，其中包含两个原始袋子中出现的条目。所以基本上我需要设计并指定一个方法交集，它作为一个新包返回接收对方法的调用的包和作为方法的一个参数的包的交集。假设 bag1 和 bag2 是袋子；bag1 包含字符串 a 、 b 和 c ；bag2 包含字符串 b 、 b 、 d 和 e 。表达式 bag1.intersection(bag2) 返回一个只包含字符串 b 的包。

我已经制作了两个包进行比较，但我不太确定如何设计交叉方法。

任何帮助都会很棒。谢谢你。

4

3 回答 3

1

由于枚举包中项目的唯一方法是使用toVector，因此您需要遍历toVector其中一个输入包的 。对于每个项目，在任一输入包中获取该项目的最小频率，并确保输出包包含具有该频率的项目。由于toVector可能重复包含相同的项目，您必须检查输出包以查看它是否已包含您正在考虑的项目。

我跟不上 C++11 的速度，所以我会用一种老式的方式来做这件事：

template<class T>
Bag<T> intersection(BagInterface<T> const &a, BagInterface<T> const &b) {
    Bag<T> c;
    std::vector<T> aItems = a.toVector();
    for (int i = 0; i < aItems.size(); ++i) {
        T const &item = aItems[i];
        int needed = std::min(a.getFrequencyOf(item), b.getFrequencyOf(item));
        int lacking = needed - c.getFrequencyOf(item);
        for ( ; lacking > 0; --lacking) {
            c.add(item);
        }
    }
    return c;
}
于 2013-09-17T05:23:05.517 回答
0

std::set_intersection from <algorithm> does this for sorted input ranges:

vector<int> as { 1, 2, 3 };
vector<int> bs { 2, 3, 4 };
vector<int> cs;

set_intersection(
    begin(as), end(as),
    begin(bs), end(bs),
    back_inserter(cs)
);

// 2 3
for (const auto c : cs)
    cout << c << ' ';

It works by looping over the input ranges until at least one is exhausted, copying those elements from one range that appear in the other, according to the strict weak ordering imposed by operator<:

while (first1 != last1 && first2 != last2) {
    if (*first1 < *first2) {
        ++first1;
    } else {
        if (!(*first2 < *first1)) {
            *output++ = *first1++;
        }
        ++first2;
    }
}
return output;
于 2013-09-17T07:19:15.113 回答
0

尝试对俱乐部使用枚举。您可以使用字符串，但字符串比较很棘手。

enum ClubsType { 
    Joker, 
    Ace, 
    Two, 
    Three, 
    Four, 
    Five, 
    Six, 
    Seven, 
    Eight, 
    Nine, 
    Ten, 
    Jack, 
    Queen, 
    King,
    ClubsTypeSize
}

Bag<ClubsType> Intersection(const Bag<ClubsType>& other) {
    set<ClubsType> common;
    int n = v.size();
    for (int i=0;i<n;i++) {
        common.insert(v[i]);
    }
    otherAsVector = other.toVector();
    n = otherAsVector.size();
    for (int i=0;i<n;i++) {
        common.insert(otherAsVector[i]);
    }
    Bag<ClubsType> result;
    for (set<ClubsType>::iterator it = common.begin(); it!=common.end();++it) {
        result.add(*it);
    }
    return result;
}
于 2013-09-17T06:44:08.053 回答