Список параметров в рекурсивных вызовах (C)

Question

Я разрабатываю рекурсивный алгоритм:

int f(int[] a, int[] b){
----changing a here
----changing b here
f(a,b)
----writing a here
----writing b here
}

Я знаю, что все массивы являются указателями, поэтому этот код должен быть проблематичным. Он запишет окончательные значения a и b после завершения всех рекурсивных вызовов. Я не хочу, чтобы это случилось.

Что я должен сделать, чтобы передать этот массив рекурсивным вызовам как обычный "проход по значению"?

PS: массивы могут быть динамически размещены или изменены в размере и т. Д. В любом месте рекурсивных вызовов.

Answer 1

Я предполагаю, что int f(int[] a, int[] b) является опечаткой: оно должно быть int f(int a[], int b[]).

Прежде всего, массивы и указатели отличаются . При многих обстоятельствах имя массива «распадается» на указатель на его первый элемент, но не всегда. В противном случае sizeof a для массива a не будет работать.

Во-вторых, давайте на минуту проигнорируем рекурсию. Давайте также упростим прототип функции:

int g(int *a);

(я изменил int a[] на int *a, потому что в этом контексте имя массива эквивалентно указателю.)

Теперь вы говорите, что можете «динамически размещать или изменять размер» массива в вызове функции. Поскольку все передается по значению в C , динамическое выделение или изменение размера a внутри g() не может быть видимым вызывающей стороной: вызывающая сторона все равно будет иметь старое значение a. Но что более важно, если «оригинальный» тип a был массивом, то есть вызывающий код имел такой код:

int data[SIZE];
g(data);

тогда попытка изменить размер data в g() плохая, потому что параметр, указанный в вызове, не был динамически выделен для начала. Вы можете только динамически изменить размер чего-либо, что было результатом malloc(), calloc() или realloc().

Итак, есть две проблемы даже с этим простым определением:

• Если g() должен динамически изменять размер памяти, на которую указывает адрес, который ему дан, значение должно быть получено из динамического выделения, а не массива,
• После исправления этого, так как g() хочет иметь возможность сигнализировать об изменении вызывающей стороне, вам нужно передать указатель на то, что необходимо изменить. Итак, прототип g() становится: int g(int **a);.

Надеюсь, вышеизложенное поможет вам начать. Если вы расскажете нам больше о своем алгоритме, в частности о том, что вы подразумеваете под «изменением» и «написанием», вы получите лучшие ответы.

Редактировать : ответить на ваш вопрос в комментарии:

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

Если вы выделили что-то до вызова, он никогда не был массивом для начала. Он может быть проиндексирован как массив, но это не главное. Так что, может быть, вас здесь смущает терминология?

... когда моя новая функция меняет указанное значение, то это значение изменяется и у вызывающего абонента.

Указанное значение изменено, да.

Я не хочу, чтобы это было так, поэтому мне нужна копия указанного значения в новой функции, чтобы неизмененное значение моего исходного указателя не изменилось. теперь я ясно?

Теперь стало понятнее, но тогда возникает больше вопросов:

• Если вы собираетесь динамически размещать или изменять размер данных при каждом вызове функции, как вы собираетесь возвращать эти новые указатели? Ты не можешь А это значит, что у тебя утечка памяти. Если только вы не free() данные в самой (рекурсивно вызванной) функции.
• Как бы вы изменили размер указателя? Возможно, вам не удастся узнать размер указанных данных, если вы не используете значение часового.

Вы используете функцию для итеративного решения головоломки или проблемы? Вы free() вводите свои данные при каждом вызове функции? Если вы можете сказать нам, что именно вы пытаетесь сделать?

Answer 2

Все массивы , а не указатели.

См. Эти:

http://c -faq.com / aryptr / practdiff.html

http://c -faq.com / aryptr / aryptrequiv.html

http://c -faq.com / aryptr / ptrkindofary.html - именно этот

Answer 3

Предполагая, что вы хотите, чтобы порядок вывода был таким же, как и в оригинале, если вы не хотите, чтобы внешний вызов видел изменения в ваших массивах, внесенных в рекурсивный вызов, вам необходимо их скопировать. Самый простой способ - это разместить их в стеке, а затем скопировать из аргумента memcopy, хотя это приведет к SO, если он станет слишком большим. Второй самый простой способ - найти и освободить их. Вы, вероятно, должны будете также передать размер массива. Вы не можете передавать массивы по значению в стеке в C.

Answer 4

Учитывая требования:

int f(int[] a, int[] b){
----changing a here
----changing b here
f(a,b)
----writing a here
----writing b here
}

Что я должен сделать, чтобы передать этот массив рекурсивным вызовам как обычный "проход по значению"?

PS: массивы могут быть динамически размещены или изменены в размере и т. Д. В любом месте рекурсивных вызовов.

Код в f () либо авторизован для внесения изменений в массивы (как сейчас), либо он не авторизован для внесения изменений. Если он авторизован для внесения изменений, то вам ничего не нужно делать, кроме как беспокоиться о том, не утратите ли вы память, если используете динамическое распределение.

Если код не авторизован для изменения массивов, то он должен будет делать копии массивов. Вы можете предотвратить случайное изменение кода кодом, включив соответствующие квалификаторы const:

int f(const int *a, const int *b) { ... }

Обратите внимание, что вы не можете передавать массивы по значению в C. Вы можете попросить вызывающего абонента передать изменяемую копию - или вы можете сделать так, чтобы получатель (вызываемый?) Сделал копию; один или другой должен будет сделать это, так что если получатель собирается вносить изменения, когда это не нужно.

Answer 5

Самый простой и безопасный вариант - передать указатель и размер . Допустим, вы работаете над чем-то вроде быстрой сортировки:

void sort_range( int* ptr, size_t count )
{
    size_t pivot;

    assert( ptr ); /* make sure we have memory */

    if ( count < 2 ) return; /* terminate recursion */

    pivot = partition( count ); /* select a pivot */

    assert( pivot < count ); /* make sure we don't overrun the buffer */

    sort_range( ptr, pivot ); /* sort left part */
    sort_range( ptr + pivot, count - pivot ); /* sort right part */

    merge( ptr, count, pivot ); /* merge ranges */
}

Всегда помните о размере блока памяти, с которым вы работаете. К сожалению, С не облегчает, поэтому вам нужно выработать привычку проверять диапазоны памяти.

Answer 6

Ваш вопрос не очень понятен, но я читаю:

У вас есть рекурсивный алгоритм, который работает с двумя массивами, выделенными для кучи. Возможно, что один из рекурсивных вызовов должен будет перераспределить массивы, и поэтому, когда он вернется на следующий уровень вверх, старые указатели больше не будут действительными. Вы хотите знать, как «передавать массивы по значению», чтобы избежать этого.

Во-первых, вы не можете передать массив по значению в C. Период. Массивы всегда передаются в виде указателей на первый элемент, и пути к этому нет.

Во-вторых, ответом всегда является другой уровень косвенности. :)

Чтобы решить проблему необходимости перераспределения массивов во время рекурсивного вызова, нужно, чтобы функция взяла два указателя на указатель (int**), где *a дает адрес указатель на первый элемент массива A, а (*a)[n] дает n-й элемент массива. Таким образом, вы можете перераспределить массив в соответствии с вашим сердцем (изменяя значение *a), но само значение a всегда остается неизменным. Делая это, экземпляры функции, расположенные дальше по стеку вызовов, будут автоматически наследовать перераспределения, сделанные рекурсивными вызовами, поскольку значение указателя (*a) указателя (a), которое они передали рекурсивному вызову изменен, чтобы отразить новое местоположение фактических данных.

, например

int f(int** a, int** b)
{

  /* Do stuff on arrays using (*a)[n] and (*b)[n] */

  if (some_condition) {
     /* Time to reallocate */
     *a = realloc(*a, new_size);
     *b = realloc(*b, new_size);
  }

  /* Do stuff on arrays using (*a)[n] and (*b)[n] */

  f(a, b);  /* Recursive call */

  /* Do more stuff using (*a)[n] and (*b)[n] */
  /* a and b are still valid pointers, even though *a and *b might point somewhere new */

 return foo;
}

void use_f(void)
{
   int* a = malloc(starting_size);
   int* b = malloc(starting_size);

   f(&a, &b);
}

Answer 7

Просто напечатайте их до , передав их на следующий уровень рекурсии.