确定一个数组是否在另一个数组中包含

如何确定一个数组是否包含在另一个数组中（按元素排序）？我曾在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

确定一个数组是否在另一个数组中包含

回答

相关问题