Передача массивов и матриц к функциям как указатели и указатели на указатели в C
Пусть S= any valid sequence of parentheses from n( and n). Теперь любая действительная последовательность S может быть записана как S=X+Y, где
-
X=valid prefix, т.е. если пересечение X слева направо, в любой момент времениnumberof'(' >= numberof')' -
Y=valid suffix, т. е. если пересечение Y справа налево, в любой момент времени,numberof'(' <= numberof')'
Для любого S возможно множество пар X и Y .
В нашем примере: ()(())
`()(())` =`empty_string + ()(())`
= `( + )(())`
= `() + (())`
= `()( + ())`
= `()(( + ))`
= `()(() + )`
= `()(()) + empty_string`
Обратите внимание, что когда X=empty_string, число действительных S из n ( и n ) = число действительного суффикса Y из n ( и n )
Теперь алгоритм будет выглядеть следующим образом: мы начнем с X= empty_string и будем рекурсивно расти X до X=S. В любой момент времени у нас есть два варианта роста X: либо добавьте '(' или append ')'
. Пусть dp[a][b]= number of valid suffixes using a '(' and b ')' given X
nop=num_open_parenthesis_left ncp=num_closed_parenthesis_left
`calculate(nop,ncp)
{
if dp[nop][ncp] is not known
{
i1=calculate(nop-1,ncp); // Case 1: X= X + "("
i2=((nop<ncp)?calculate(nop,ncp-1):0);
/*Case 2: X=X+ ")" if nop>=ncp, then after exhausting 1 ')' nop>ncp, therefore there can be no valid suffix*/
dp[nop][ncp]=i1+i2;
}
return dp[nop][ncp];
}`
Давайте возьмем пример, n = 3, т. е. 3 ( и 3 ) Теперь в самом начале X=empty_string, поэтому
dp[3][3] = число действительных последовательность S с использованием 3 ( и 3 ) = количество действительных суффиксов Y из 3 ( и 3 )
5 ответов
Ну, это, конечно, не хорошо понято под сообществом C как видно путем посматривания ТАК. Волшебство, , все следующее полностью, 100%, эквивалентных :
void foo(int (*array)[10]);
void foo(int array[][10]);
void foo(int array[10][10]);
void foo(int array[42][10]);
очень важно потянуть различие указателя и массива. массив не является указателем . Массив может быть преобразован в указатель на свой первый элемент. Если у Вас есть указатель, у Вас есть это:
--------
| ptr | -------> data
--------
Однако, если у Вас есть массив, у Вас есть это:
---------------------------
| c1 | c2 | c3 | ... | cn |
---------------------------
С указателем, данные в целой другой планете, но связанный с указателем. Массив имеет сами данные. Теперь, многомерный массив является просто массивом массивов. массивы вкладываются в родительский массив. Так, sizeof Вашего массива:
(sizeof(int) * 10) * 10
Это вызвано тем, что у Вас есть 10 массивов, все из которых являются массивами 10 целых чисел. Теперь, если Вы хотите передать тот массив, он преобразовывается. Но к какой? Указатель на его первый элемент. Тип элемента не указатель, но массив. Как следствие Вы передаете указатель на массив 10 интервалов:
int (*)[10] // a pointer to an int[10]
Это ни массив int*, ни int**. Можно спросить, почему массив не передается как int**. Это - потому что компилятор должен знать длину строки. Если Вы сделаете array[1][0], то компилятор обратится к месту sizeof(int) * 10 байты кроме начинания 2 размерных массивов. Это декодирует ту информацию в указателе на тип массива.
Так, Вы имеете к, выбрал среди одного из вышеупомянутых полностью эквивалентных прототипов функции. Естественно, последний просто сбивает с толку. Компилятор просто тихо игнорирует любое число, записанное в самом внешнем размере, если параметр, как объявляют, является массивом. Таким образом, я также не использовал бы предпоследнюю версию. Лучше всего должен использовать первую или вторую версию. То, что важно для запоминания, - то, что C не имеет (реальных) параметров массива ! Параметр будет указателем в конце (указатель для выстраивания в этом случае).
Примечание, как многомерный случай вышеупомянутого подобен вырожденному, одномерному случаю ниже. Все следующие 4 версии полностью эквивалентны:
void foo(int *array);
void foo(int array[]);
void foo(int array[10]);
void foo(int array[42]);
Необходимо определить панель как:
bar( int* matrix )
В C все массивы должны быть переданы как int* (или type_of_element* для других типов).
int ** был бы в порядке, если бы Ваши данные были действительно массивом указателей. int[*data[], например. Это - то, во что Вы входите main(int argc, char *argv[]).
Передача многомерных массивов в C является хитрым предметом. См. этот FAQ.
вопрос спросить состоит в том, как Вы будете использовать bar. Если Вы всегда знаете, что это будет передано 10x10, массив затем переписывает его как
bar(int matrix[10][10]);
, Если Вы хотите справиться с массивами переменных размеров затем, Вам, возможно, придется передать в длинах:
bar(int *matrix, int width, int height);
Проблема состоит в том, что матрица структуры данных [10] [10] является на самом деле не таблицей десяти указателей для выстраивания [10], но это - последовательный массив 100 целых чисел. Надлежащая подпись для панели
bar (int matrix[10][10])
, Если Вы на самом деле хотите представить матрицу с помощью косвенности и иметь интервал ** матрица как тип параметра для панели, затем необходимо выделить его по-другому:
int *matrix[10];
int my_data[100];
int i;
for (i = 0; i < 10; i++) { matrix[i] = &(my_data[i * 10]); }
bar(matrix);
Теперь 'матрица' соответствует интервалу типа **. 'матрица' является массивом десяти указателей, и можно передать ее указателем, следовательно получив второе *.
int **matrix
указал бы, что у Вас есть указатель на указатель на интервал. Это является наиболее часто используемым для указания на указатель на массив указателей (также названный вектором). Это - определенно НЕ случай с
int matrix[10][10]
, который является больше указателя на единственный раздел памяти, измеренной для 10x10 ints. Попытайтесь измениться на:
void bar(int *matrix[])