有没有适合解决这个问题的数据结构？

我有四组数据：有没有适合解决这个问题的数据结构？

我想要做的是给定输入号码，给所有可能的结果。例子可以帮助解释什么，我想做的事：说输入为7，则输出应该是以下几点：

from group 1 
7 2 2 
7 2 3 
7 2 5 
7 2 7 
7 3 2 
7 5 2 
7 6 2 

from group 2 
//nothing 

from group 3 
7 2 

from group 4 
7

然后，添加第二个输入2（所以总投入为7 2）那么结果应该是

from group 1 
7 2 2 
7 2 3 
7 2 5 
7 2 7 

from group 2 
//nothing 

from group 3 
7 2 

from group 4 
//nothing

然后，添加一个第三输入端5（因此总输入为7 2 5），那么结果应该是

from group 1 
7 2 5 

from group 2 
//nothing 

from group 3 
//nothing 

from group 4 
//nothing

这似乎是我需要一个森林（几棵树），对吗？如果是这样，是否有任何良好的C++树实现这个任务的森林，或者我自己更好地手工制作一个？

很多谢谢

来源

2011-08-19 Gob00st

您需要实际描述您正在尝试使用的*算法*。 – Puppy

如果我理解正确，您希望输出包含您的输出的所有行作为前缀，对吗？ – Giorgio

看起来像*前缀树*。在C++标准库中没有一个，但我相信你会在互联网上找到一个好的实现。 –

像来保存数据

std::set<std::vector<int> > data;

现在你可以创建这些每个组一个，如果没有保证项目中的每一组中的数量是相同的，或者如果你知道每个什么组是特定数量的项目，然后将它们全部放在同一组中。

然后使用带有上述data的自定义谓词的std::find_if。在这个谓词中有一个std::vector这是你正在寻找的序列。

struct search_sequence 
{ 
    bool operator()(std::vector<int> const& cVal) const 
    { 
    if (sequence.size() <= cVal.size()) 
     return std::equal(sequence.begin(), sequence.end(), cVal.begin()); 
    return false; 
    } 

    std::vector<int> sequence; 
};

现在有了std::find_if应用此会发现data与搜索顺序启动所有序列。

编辑：要存储在单个实例中，包装矢量，例如

struct group_entry 
{ 
    int id; 
    std::vector<int> data; 

    friend bool operator<(group_entry const& lhs, group_entry const& rhs) 
    { 
    return lhs.id < rhs.id && lhs.data < rhs.data; 
    } 
};

现在你集包含

std::set<group_entry> data;

从所有组将所有数据

修改断言：

struct search_sequence 
{ 
    bool operator()(group_entry const& cVal) const 
    { 
    if (sequence.size() <= cVal.data.size()) 
     return std::equal(sequence.begin(), sequence.end(), cVal.data.begin()); 
    return false; 
    } 

    std::vector<int> sequence; 
};

来源

2011-08-19 15:30:14 Nim

这4组数据并不相同，例如第一和第二组总是有三个元素，第三组总是有两个元素，第四组总是有一个元素。 – Gob00st

@ Gob00st，很好，在这种情况下，每个组都有一个'data'的实例。并且对每个组做'find_if' ... – Nim

我知道在我问这个问题之前，我可以做4组搜索。我只是想知道每次做4次搜索，我可以使用一种数据结构来保存整体数据，每次只搜索一次？ – Gob00st

字符串的数组将会诀窍。每一行都是一个字符串。您可以使用分隔符来装饰线条，以便于搜索，比如“/ 7/2/2 /”而不是“7 2 2”，这样您可以搜索“/ 2”。

我的猜测是你的教授希望你使用更复杂的数据结构。

来源

2011-08-19 15:25:38 Craig

由于深度似乎被固定

std::map<int, std::map<int, std::set<int> > >

会完成这项工作。不知道这是值得的，尽管数据项的数量。在C

来源

2011-08-19 15:32:45 john

A “的树木森林” ++术语将是：

vector<set<string> >

凡在该组中的字符串是 “2 2 6”， “2 2 7” 等

假设你只需要使用前缀，并且所有数字都是一位数字（或零对齐到相同的宽度），则可以使用set::lower_bound和set::upper_bound上的所需前缀实现算法（在本例中，首先是“7”，然后是“7 2”等）。

例子：

void PrintResults(const vector<set<string> >& input, const string& prefix) { 
    for (int i = 0, end(input.size()); i < end; ++i) { 
    cout << "from group " << i + 1 << endl; 
    const set<string>& group_set = input[i]; 
    set<string>::const_iterator low(group_set.lower_bound(prefix)), high(group_set.upper_bound(prefix)); 
    if (low == high) { 
     cout << "//nothing" << endl; 
    } else { 
     for (; low != high; ++low) { 
     cout << *low << endl; 
     } 
    } 
    } 
}

你可以尝试使用这个向量，但没有一个std库版本。

来源

2011-08-19 15:34:16

这里是一个可能的解决方案的草图：

class Group 
{ 
    int id; 

    std::vector<int> values; 
}

使用此类来存储整个组（初始数据），和一个查询的结果（应用一些后的一组内容过滤）。

树使用节点和边构造;每个节点使用一个Group向量来存储该节点的结果。

class Node; 

typedef Node *NodePtr; 

class Edge 
{ 
    NodePtr target; 

    int value; 
}; 

class Node 
{ 
    // Results for each group. Maybe empty for certain groups. 
    // Contains all elements for all groups in the root node. 
    std::vector<Group> results; 

    std::vector<Edge> children; 
};

当您搜索时，您从根开始。为了匹配，例如7 2，您查找通过遍历值为== 7的边达到的根的孩子。然后查看该边的目标节点，然后查找值为== 2的边。当您到达路径的最后一个节点，结果向量中包含结果。

更新当然，你也有构建这样一棵树的问题。你可以使用递归算法来做到这一点。

您从包含所有组和所有列表的根节点开始。然后，为列表的每个第一个元素添加一个带有相应节点和相应结果集的边。

您对每个子节点重复上述步骤，这次查看列表中的第二个元素。等等，直到你不能再延伸树。

来源

2011-08-19 16:18:24 Giorgio

正如其他海报所说，你需要一个前缀树。这里有一个简单的例子，让你开始，假设唯一的字符是0-7。请注意，我放置的安全性很低，数字假设给它的字符串后面都是空格（即使是最后一个），并且结果以相同的方式返回（这很容易）。对于真实的代码，应该涉及更多的安全性。此外，代码是未编译/未经测试的，因此可能有错误。

class number { //create a prefix node type 
    number& operator=(const number& b); //UNDEFINED, NO COPY 
    int endgroup; //if this node is the end of a string, this says which group 
    number* next[8]; // pointers to nodes of the next letter 
public: 
    number() :group(-1) { //constructor 
     for(int i=0; i<8; ++i) 
      next[i] = nullptr; 
    } 
    ~number() { // destructor 
     for(int i=0; i<8; ++i) 
      delete next[i]; 
    } 
    void add(char* numbers, int group) { //add a string to the tree for a group 
     if(next[numbers[0] == '\0') //if the string is completely used, this is an end 
      endgroup = group; 
     else { 
      int index = numbers[0]-'0'; //otherwise, get next letter's node 
      if (next[index] == nullptr) 
       next[index] = new number; //and go there 
      next[index].add(numbers+2, group); //+2 for the space 
     } 
    } 
    void find(char* numbers, 
     std::vector<std::pair<int, std::string>>& out, 
     std::string sofar="") 
    { //find all strings that match 
     if(numbers[0]) { //if there's more letters 
      sofar.append(numbers[0]).append(' '); //keep track of "result" thus far 
      int index = numbers[0]-'0'; //find next letter's node 
      if (next[index] == nullptr) 
       return; //no strings match 
      next[index].find(numbers+2, out, sofar); //go to next letter's node 
     } else { //if there's no more letters, return everything! 
      if (endgroup > -1) //if this is an endpoint, put it in results 
       out.push_back(std::pair<int, std::string>(endgroup, sofar)); 
      for(int i=0; i<8; ++i) { //otherwise, try all subsequent letter combinations 
       if (next[i]) { 
        std::string try(sofar); //keep track of "result" thus far 
        try.append('0'+i).append(' '); 
        next[i].find(numbers, out, try); //try this letter 
       } 
      } 
     } 
    } 
} root; //this is your handle to the tree 

int main() { 
    //group one 
    root.add("2 2 6", 1); 
    root.add("2 2 7", 1); 
    //... 
    //group two 
    root.add("2 2 2", 2); 
    //... 

    std::string pattern; 
    char digit; 
    while(true) { 
     std::cin >> digit; 
     if (digit<'0' || digit > '7') 
      break; 
     pattern.append(digit).append(' '); 
     std::vector<std::pair<int, std::string>> results; 
     root.find(pattern.c_str(), results); 
     for(int g=1; g<4; ++g) { 
      std::cout << "group " << g << "\n"; 
      for(int i=0; i<results.size(); ++i) { 
       if(results.first == g) 
        std::cout << results.second; 
      } 
     } 
    } 
}

来源

2011-08-19 17:03:53

有没有适合解决这个问题的数据结构？

回答

相关问题