確定一個數組是否在另一個數組中包含

如何確定一個數組是否包含在另一個數組中（按元素排序）？我曾在2010 MSVS編寫的程序之下，但也不太清楚如何完成布爾函數來確定一個陣列出現在另一個確定一個數組是否在另一個數組中包含

void isContained(int ar1[], int ar2[]); 


int main(int argc, char** argv) 
{ 
    ifstream fin1("one.txt"); 
    ifstream fin2("two.txt"); 

    int i, j, value1, value2; 
    int arr1[ 10 ]; 
    int arr2[ 10 ]; 

    for (i = 0 ; fin1 >> value1 ; i++) 
    { 
     arr1[ i ] = value1; 
    } 

    for (j = 0 ; fin2 >> value2 ; j++) 
    { 
     arr2[ j ] = value2; 
    } 

    isContained(arr1, arr2); 

    system("PAUSE"); 
} 


void isContained(int ar1[], int ar2[]) 
{ 
    ??? 
}

來源

2011-09-20 Joshua

您可以使用''中的'std :: search'功能。標準庫中有很多有用的功能。您可能需要熟悉這些文檔。 – Blastfurnace

簡單。假設您想檢查ar2是否包含在ar1中。

一個例子：

Ar1: 1 2 3 4 5 6 7 8 9 10 5 2 8 2 4 2 4 6 2 9 1 
Ar2: 2 4 6 2

同時假設你有數組的長度在Ar1_len和Ar2_len

你必須要經過Ar1，找到匹配的Ar2的第一個元素，然後元素從那裏開始，嘗試查看是否所有元素都匹配。如果沒有，你繼續Ar1發現的Ar2

第一元素相匹配的另一要素所以基本上代碼將是這個樣子：

if (Ar2_len == 0) 
    return true; 
for (unsigned int i = 0; i < Ar1_len-(Ar2_len-1); ++i) 
    if (Ar1[i] == Ar2[0]) 
    { 
     bool matches = true; 
     for (unsigned int j = 1; j < Ar2_len; ++j) 
      if (Ar1[i+j] != Ar2[j]) 
      { 
       matches = false; 
       break; 
      } 
     if (matches) 
      return true; 
    }

注意i去Ar1_len-(Ar2_len-1)，因爲如果你太在Ar1（其中有小於Ar2_len元素剩下）的末尾，顯然不可能找到Ar2。

第二個注意事項是，這不是最有效的方法。最有效的方法包括從Ar2構建DFA並使用Ar1作爲其輸入並跟蹤它。如果它達到最終狀態return true。這可能有點複雜，但是如果您有興趣，可以在字符串匹配中查找算法。

最後需要注意的是，此處提供的代碼不適用於複製粘貼。它可能缺乏足夠的錯誤檢查，並且僅僅是爲了給你提供這個想法。

來源

2011-09-20 10:40:16 Shahbaz

注意，條件'Ar1 [i] == Ar2 [0]'是循環條件'Ar1 [i + j] == Ar2 [j]'的'j == 0'情況，可以是很容易融入它。（DRY/SPOT原理，你知道嗎？） – xtofl

...並且循環和它的相等性檢查相當於'std :: mismatch'。 – xtofl

@xtofl你說得對。無論哪種方式都是一樣的。 – Shahbaz

這是不可能的，你給的函數原型。

當傳遞給函數時，數組衰減爲指針，因此函數無法確定數組中有多少個元素。

來源

2011-09-20 10:26:56

它是如果數組終止一個特殊值（0？） – Simon

@Simon當你從用戶讀取數據時，這是不可能的。 –

你所追求的基本上是一個字符串搜索算法（除了在你的情況下你的「字符」是你的數組的整數元素）。

存在多種這樣的算法，參見Wikipedia。

至於你的代碼迄今而言：

你可能想確保你不走過去的數組的末尾你的兩個for循環。
您需要將兩個數組的大小傳遞給isContained（並且其返回類型可能不應該是void）。

來源

2011-09-20 10:27:09 NPE

您可以找到含有陣列，這將使mismatch返回包含數組末尾的位置：

using namespace std; 

template<typename OutIt, typename SeqIt> 
OutIt find_sequence(OutIt outer_begin , OutIt outer_end, 
        SeqIt sequence_begin, SeqIt sequence_end){ 
    assert( 
     distance(outer_begin,outer_end) >= distance(sequence_begin,sequence_end); 

    // limit the possible iterator positions: 
    OutIt outer_limit = outer_begin; 
    advance(outer_limit, distance(sequence_begin, sequence_end)); 

    for(OutIt outer_it = outer_begin; outer_it != outer_limit; ++outer_it) 
    { 
    if(mismatch(sequence_begin, sequence_end, outer_it).first==sequence_end) 
    { 
      return outer_it; 
    } 
    } 
    // none found... 
    return outer_end; 
}

而且使用這樣的：

int values[] = { 1,2,3,4,5, 6 }; 

int pattern[] = { 3,4,5 }; 

int* pFound = find_sequence(values, end(values), pattern, end(pattern)); 
bool bFound = pFound != std::end(values);

來源

2011-09-20 10:43:38 xtofl

可以使用std::search在<algorithm>中搜索模板以搜索另一個序列內的子序列。注意：我修改了你的函數簽名來傳遞數組大小。

bool isContained(int ar1[], int size1, int ar2[], int size2) 
{ 
    return std::search(ar1, ar1 + size1, ar2, ar2 + size2) != (ar1 + size1); 
}

來源

2011-09-20 15:11:00 Blastfurnace

確定一個數組是否在另一個數組中包含

回答

相關問題