有沒有適合解決這個問題的數據結構？

Question

我有四組數據：

//group 1 
2 2 6 
2 2 7 
2 3 5 
2 3 6 
2 3 7 

3 2 5 
3 2 6 
3 2 7 
3 3 4 
3 3 5 
3 3 6 
3 3 7 
... 
... 
7 2 2 
7 2 3 
7 2 5 
7 2 7 
7 3 2 
7 5 2 
7 6 2 

//group 2 
2 2 2 
2 2 3 
2 2 4 
2 2 5 
2 3 2 
2 3 3 

3 3 2 
3 3 3 
3 4 2 
... 
... 

5 2 2 

//group 3 
2 4 
2 5 

3 3 
3 4 
3 5 
3 6 
... 
... 
7 2 

//group 4 
6 
7 
8 

我想要做的是給定輸入號碼，給所有可能的結果。 例子可以幫助解釋什麼，我想做的事： 說輸入爲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++樹實現這個任務的森林，或者我自己更好地手工製作一個？

很多謝謝

Answer 1

像來保存數據

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; 
}; 

Answer 2

字符串的數組將會訣竅。每一行都是一個字符串。您可以使用分隔符來裝飾線條，以便於搜索，比如「/ 7/2/2 /」而不是「7 2 2」，這樣您可以搜索「/ 2」。

我的猜測是你的教授希望你使用更復雜的數據結構。

Answer 3

由於深度似乎被固定

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

會完成這項工作。不知道這是值得的，儘管數據項的數量。在C

Answer 4

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庫版本。

Answer 5

這裏是一個可能的解決方案的草圖：

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的邊。當您到達路徑的最後一個節點，結果向量中包含結果。

更新 當然，你也有構建這樣一棵樹的問題。你可以使用遞歸算法來做到這一點。

您從包含所有組和所有列表的根節點開始。然後，爲列表的每個第一個元素添加一個帶有相應節點和相應結果集的邊。

您對每個子節點重複上述步驟，這次查看列表中的第二個元素。等等，直到你不能再延伸樹。

Answer 6

正如其他海報所說，你需要一個前綴樹。這裏有一個簡單的例子，讓你開始，假設唯一的字符是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; 
      } 
     } 
    } 
}