了解递归函数中的数组和指针

Question

我必须编写一个递归函数，该函数将检查两个相同大小的给定数组是否具有相同的元素，但它们的顺序可能不同。

我认为最优雅的解决方案是对两个数组进行排序，然后比较每个元素，但我不知道在一个递归函数中对两个数组进行排序的方法。

所以我有另一个想法，使用线性搜索，取 array1 的最后一个元素并在 array2 中搜索它，如果它在那里，使用 shiftback 函数，将所有元素移到该元素前面(在 array2 中(并返回 true，如果未找到返回 false。这将经历所有级别的递归。

但它不起作用，我在调试器中看到，在满足递归的停止条件很久之后，数组突然变成了 1 个元素。

从我读到的内容来看，将数组作为指针传递是不明智的，但它能解决这个问题吗？ 到底是怎么做到的？

这是代码，它有据可查：

注意：我无法使用库函数。

#include <iostream>
using namespace std;
bool sameelem(int A1[], int A2[], int len);
void shiftback(int a[], int len, int i);
bool lsearchandshift(int a[], int len, int key);
void main()
{
    int arr[7] = { 1, -2, 3, 4, -1, 6, -7 };
    int arr2[7] = { 1, -2, 3, 3, -1, 6, -7 };
    cout << sameelem(arr, arr2, 7);
}
bool sameelem(int A1[], int A2[], int len){
    ///pick an element from arr1, if it appears in arr2 cut both out using shiftback
    ///if it doesn't appear rerturn false, false should go thorugh all levels till the end
    //end: if true check last two elements, if false return false
    if (size==0)return true;
    else{
        sameelem(Arr1, Arr2, len - 1);
        return (lsearchandshift(Arr2, size, Arr1[size - 1]));//if the last element from Arr1 is in Arr2 this will be true
    }
}

//linear search function, will return 0 if key isn't found, otherwise will 'kill' that element using shiftback function and return 1
bool lsearchandshift(int a[], int len, int key){
    int i;
    bool found = false;
    for (i = 0; i < len && found==false; i++)//if found will turn true and stop searching
    {
        if (a[i] == key){
            found = true;
            shiftback(a, len, i);
        }
    }
    return found;
}
//array shifting backward function
//len has to be logical size, array's physical size has to be larger than entered logical size
void shiftback(int a[], int len, int i){
//i is the index which will be moved one place forward to i+1 along with all the other elements
    int j;
    for (j = i; j < len; j++)
    {
        a[j] = a[j+1];
    }
    //return a[len-1];
}

Answer 1

唯一调用自己的函数是 haveSameElems ：

bool haveSameElems(int Arr1[], int Arr2[], int size)
{
  ///pick an element from arr1, if it appears in arr2 cut both out using shiftback
  ///if it doesn't appear rerturn false, false should go thorugh all levels till the end
  //end: if true check last two elements, if false return false
  if (size==0)return true;
  else{
    haveSameElems(Arr1, Arr2, size - 1);
    return (lsearchandshift(Arr2, size, Arr1[size - 1]));//if the last element from Arr1 is 
in Arr2 this will be true
  }
}

请注意，它不使用递归调用的返回值。因此，递归调用可能会返回false而调用函数永远不会知道它。

您可以轻松解决此问题：

if(!haveSameElems(Arr1, Arr2, size - 1))
  return(false);

在这段代码和编写它的方法中，还有很大的改进空间，但这足以让你继续前进。

Answer 2

以此供您参考：-

bool isSame(int *p, int *q, int n)
{
    if( n == -1 )
        return true;
    if ( *p != *q )
        return false;
    else
        isSame(++p, ++q, --n);
}
int main()
{
    int arr1[] = {1,2,3,2,4,5};
    int arr2[] = {2,1,5,2,3,4};
    //check if two arrays have different number of elements...
    //If yes then just jump past 4-5 lines...
    std::sort(arr1, arr1 + sizeof(arr1)/sizeof(arr1[0]));  <<< You can build your own
    std::sort(arr2, arr2 + sizeof(arr2)/sizeof(arr2[0]));  <<< sort.
    if( isSame(arr1, arr2, 6) )
        cout << "Arrays are same" << endl;
    else
        cout << "Arrays are different" << endl;
}

在这些算法中，首先对数组进行排序比对未排序的数组进行处理几乎总是更好的。另一个好处是，一旦你看到不匹配，你就停止了进一步的移动。