Указатели C возвращаются к старому адресу в рекурсии

Question

Указатели C возвращаются к старому адресу в рекурсии

Существует 3 связанных списка, 2 из которых (headX и headY) приведены в порядке убывания, и задача функций состоит в том, чтобы отсортировать их в один список (headZ).

По какой-то причине алгоритм работает нормально, но когда он завершен и он возвращается через рекурсию, 3 указателя возвращаются к своим старым значениям, когда они возвращаются через рекурсию.

void SortedMergeRecur(Node* headX, Node* headY, Node* headZ)
{
if (headX == NULL && headY == NULL)
return;

else if (headX == NULL && headY != NULL)
{
if (headZ == 0)
{
headZ = headY;
headY = headY->link;
headZ->link = NULL;
}
else
{
headZ->link = headY;
headY = headY->link;
headZ = headZ->link;
headZ->link = NULL;
}

SortedMergeRecur(headX, headY, headZ);
}

else if (headX != NULL && headY == NULL)
{
if (headZ == 0)
{
headZ = headX;
headX = headX->link;
headZ->link = NULL;
}
else
{
headZ->link = headX;
headX = headX->link;
headZ = headZ->link;
headZ->link = NULL;
}

SortedMergeRecur(headX, headY, headZ);
}

if (headX != NULL && headY != NULL)
{
if (headX->data > headY->data)
{
if (headZ == NULL)
{
headZ = headY;
headY = headY->link;
headZ->link = NULL;
}
else
{
headZ->link = headY;
headY = headY->link;
headZ = headZ->link;
headZ->link = NULL;
}
}
else
{
if (headZ == NULL)
{
headZ = headX;
headX = headX->link;
headZ->link = NULL;
}
else
{
headZ->link = headX;
headX = headX->link;
headZ = headZ->link;
headZ->link = NULL;
}
}
SortedMergeRecur(headX, headY, headZ);
}
}

Я знаю, что некоторые части этого могут быть упрощены (например, добавление всего списка, если headX или headY равны нулю), но я написал это так, потому что думал, что это может решить проблему, чего не произошло ….

2

c++recursion tail-recursion

Решение

Другие решения

Если вы хотите изменить параметры и оставить эти изменения вне функции, вам нужно передать их по ссылке — например,

void SortedMergeRecur(Node*& headX, Node* headY, Node* headZ)
//                         |
//                 pass by reference

Если вы измените headX внутри функции изменения будут сохраняться после ее возврата. Изменения в headY а также headZ не будет, потому что они передаются по значению.

1

Помните, что в C, аргументы всегда передаются по значению, никогда по ссылке.

Когда вы передаете указатель на функцию, такую как

  void SortedMergeRecur(Node* headX, Node* headY, Node* headZ)

если вы измените (т.е. установите) аргумент формального указателя headX внутри тела вашего SortedMergeRecur фактический аргумент указателя, используемый в вызове, не затрагивается.

Если вы хотите повлиять на них в теле функции, чтобы их настройки передавались вызывающей стороне, объявите формальные указатели на указатели, например

  void SortedMergeRecur(Node** pheadX, Node** pheadY, Node** pheadZ)

затем установите внутри тела:

   *pheadY = (*pheadY)->link;

В C ++ вы можете иметь формальные аргументы, передаваемые по ссылке с &

1

Источник

Accepted Answer

Указатели копируются по значению так же, как переменные:

void test(int x)
{
x = 5;
}
int y = 3;
test(y);
//y is 3

Та же идея:

void test(int* x, int* y)
{
x = y;
}
int a = 5; int b = 6;
int* x = &a;
int* y = &b;
test(x, y);
//x is still &a and y is still &b

Если вы хотите изменить указатели, вы должны передать указатели указателю:

void test(int** x, int *y)
{
*x = y;
}
int a = 5; int b = 6;
int* x = &a;
int* y = &b;
test(&x, y);
//x is now &b and y is still &b
//(note that a and b are still 5 and 6, respectively)

Поскольку вы используете C ++, другой вариант — передать по ссылке:

void test(int*& x, int *y)
{
x = y;
}
int a = 5; int b = 6;
int* x = &a;
int* y = &b;
test(x, y);
//x is now &b and y is still &b
//(note that a and b are still 5 and 6, respectively)

3