Я определил базовую структуру списка и простой insert
функция и search
функция. Код ниже:
////////////////////////////////////////////////
typedef struct list
{
int item;
struct list *next;
}List;
////////////////////////////////////////////////
List * search_list(List * l, int i)
{
if(NULL == l)
return(NULL);
if(i == l->item)
return l;
else
return search_list(l->next, i);
}
////////////////////////////////////////////////
void insert_list(List ** l, int i)
{
List * p = new List();
p->item = i;
p->next = *l;
*l = p;
}
Мой основной цикл для его проверки выглядит так:
int main(int, char* argv[])
{
List * mylist = new List();
for(int i = 0; i < 8000; i++)
{
insert_list(&mylist,i);
}
int val = 2000;
List * s = search_list(mylist, val);
return 0;
}
когда val
4000, программа завершает нормально. Но когда val
равно 2000, то есть 2000 индексов далее вниз по списку, Visual Studio завершается переполнением стека.
Количество рекурсивных вызовов в search_list()
вызывая переполнение стека? Как я могу избавиться от этой ошибки?
Рекурсивные алгоритмы должны использоваться только в том случае, если глубина строго ограничена или алгоритм имеет не более O (logN) сложность. Если это не так, то вы всегда переполнение стека рисков. Ваш не соответствует требованию сложности, это O (N).
Visual Studio не помогает избежать сбоев при запуске вашей программы с настройками сборки Debug по умолчанию. Во-первых, оптимизация хвостовой рекурсии не включена, для этого требуются параметры сборки выпуска, чтобы оптимизатор был включен. Для другого, функция «Правка + Продолжить» выделяет кучу дополнительный пространство стека для функции. Это доступно, если вы добавляете локальную переменную в функцию во время отладки.
Вы можете легко отключить это. Project + Properties, C / C ++, General, измените настройку формата отладочной информации на «Program Database (/ Zi)». Ваша программа больше не будет зависать.
Ваш компилятор должен был сказать вам одну вещь: этот рекурсивный вызов search_list ничего не возвращает. Разве вы не получили предупреждение об этом? И использование рекурсии здесь действительно плохая идея, лучше замените ее каким-то циклом. Одна из причин, конечно, — чрезмерное использование стека, другая — отладка отстой с такой рекурсией.
Помимо вашей ошибки переполнения стека, вы должны проверить следующее. Вы не инициализируете значения первого выделенного List
экземпляр в main()
указал mylist
,
List * mylist = new List();
То, что делает ваш текущий код, передает «пустой» List
экземпляр при первом вызове, который может иметь недопустимый next
значение. Это будет твой последний List
экземпляр в связанном списке.
Вы должны сделать это вместо этого:
List * mylist = NULL;
Это заверит вас в прошлом List
Экземпляр в списке имеет next
с NULL
значение.