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

Question

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

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

所以我有另一个想法，使用线性搜索，获取数组1的最后一个元素并在数组2中搜索它，如果它在那里，使用移位函数，移动该元素前面的所有元素（在数组2中）并返回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

拿这个给你参考：-

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

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

Answer 2

唯一调用自己的函数是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
  }
}

请注意，is不使用递归调用的返回值。因此递归调用可能返回＜code＞false＜/code＞并且调用函数永远不会知道它。

您可以轻松解决此问题：

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

这段代码和你编写它的方法还有很大的改进空间，但是这已经足够让你前进了。