我有一个学校分配,要求我创建一个递归的二叉搜索函数。我不允许更改函数签名。我对指针的经验不是最好的,我认为我的问题就在那里。我得到了一个堆栈流,但我真的不明白的方式
bool contains(const int* pBegin, const int* pEnd, int x)
{
int length = pEnd - pBegin;//gives me the length of the array
const int* pMid = pBegin + (length / 2);
if(length == 1)
{
if(*pMid != x)
return false;
return true;
}
else if(x < *pMid)
return contains(pBegin, pMid-1, x);
else
return contains(pMid, pEnd, x);
}
void main(){
setlocale(LC_ALL, "swedish");
int arr[10];
for(int i = 0; i < 10; ++i)
arr[i] = i;
bool find = contains(&arr[0], &arr[10], 3);//arr[10] points to the index after the array!
cout <<"found = "<< find << endl;
system("pause");
}
有人可以向我解释我做错了什么,以及我如何以更好的方式做到这一点吗?
堆栈溢出是由于太深的递归造成的。你的数组不太可能大到真正成为一个问题,所以你所拥有的是无限递归......contains() 不断调用自己,但无法检测到这一点。
看看这是怎么可能的,并添加断言。
您的代码假设 pend> pBegin
您的代码无法处理这种可能性。
#include <assert.h>
bool contains( ... )
{
assert(pBegin > pEnd);
...
现在,如果此假设不正确,它将中止。
(ppending> pBegin)为假有两种可能性,即"<"或"=="。在这两种情况下,您的代码会做什么?
下面剧透..
<块引用类>长度可以为零,并且不进行处理。
块引用类>