Передать массив по значению функции в C/C++
В этом посте мы обсудим, как передать массив по значению в функцию на C/C++.
Мы знаем, что аргументы функции по умолчанию передаются по значению в C. Однако массивы в C не могут быть переданы функции по значению, и мы можем изменить содержимое массива из вызываемой функции. Это связано с тем, что в функцию передается не массив, а копия указателя на его адрес в памяти. Итак, когда мы передаем массив в функцию, это будет распадаться на указатель независимо от того, объявлен ли параметр как int[] или нет.
Однако несколько трюков позволяют нам передавать массив по значению в C/C++.
1. Использование структур в C
Идея состоит в том, чтобы обернуть массив составным типом данных, таким как структуры в C. Это работает, поскольку структуры передаются в функцию по значению и не распадаются на указатели. В C++ мы можем использовать class.
Передача массива в функцию, подсчет длины массива по указателю
- В С++ массивы можно инициализировать следующим образом:
int arr[] = ; // длина массива определяется после инициализацииКак следствие, его можно передать в функцию таким же способом:
void func(int arr[])< //your code >void func(int* arr) < //your code >int arr[5] = ;Мы привыкли обращаться к элементам массива по индексам, но попробуйте скомпилировать и запустить следующие строки:
int main()< int arr[5] = ; cout void func(int* arr, int length)< //your code >Но в ряде задач длина входного массива может быть неизвестной. На этот случай тоже есть решение, мы можем анализировать данные, которые поступили в функцию по указателю, например:
int len(int* arr)
Крайне важно понять критерий по которому мы будем оценивать содержимое. В противном случае, можно получить не совсем то, что ожидалось.
Arduino.ru
Передача массива в функцию без указания размерности
- Войдите на сайт для отправки комментариев
14 ответов [Последнее сообщение]
Пт, 02/10/2015 - 14:18
Зарегистрирован: 11.07.2014
Задача состоит в следующем: Нужно передать одномерный массив в функцию таким образом, чтобы функция сама определяла размерность массива. Предполагается, что размерность передаваемых массивов может быть разной и на момент написания программы не будет известна, или известна, но чтобы не париться указывая второй аргумент функции.
Уважаемые господа, помогите решить этот вопрос. Заранее знаю что это возможно.
- Войдите на сайт для отправки комментариев
Пт, 02/10/2015 - 14:40
Зарегистрирован: 09.10.2013
В языке С нельзя передать весь массив как аргумент функции. Однако можно передать указатель на массив, т.е. имя массива без индекса. Например, в представленной программе в func1() передается указатель на массив i:
int main(void)
int i[10];
Если в функцию передается указатель на одномерный массив, то в самой функции его можно объявить одним из трех вариантов: как указатель, как массив определенного размера и как массив без определенного размера. Например, чтобы функция func1() получила доступ к значениям, хранящимся в массиве i, она может быть объявлена как
void func1(int *x) /* указатель */
/* . */
>
или как
void func1(int x[10]) /* массив определенного размера */
/* . */
>
и наконец как
void func1(int x[]) /* массив без определенного размера */
/* . */
>
Эти три объявления тождественны, потому что каждое из них сообщает компилятору одно и то же: в функцию будет передан указатель на переменную целого типа. В первом объявлении используется указатель, во втором — стандартное объявление массива. В последнем примере измененная форма объявления массива сообщает компилятору, что в функцию будет передан массив неопределенной длины. Как видно, длина массива не имеет для функции никакого значения, потому что в С проверка границ массива не выполняется. Эту функцию можно объявить даже так:
void func1(int x[32])
/* . */
>
И при этом программа будет выполнена правильно, потому что компилятор не создает массив из 32 элементов, а только подготавливает функцию к приему указателя.
- Войдите на сайт для отправки комментариев
Как передать ссылку на массив в функцию c
передаю массив в функцию:
получаю 1.
почему я получаю 1, а не 5?
что нужно сделать, чтоб функция работала правильно?
И ещё: как правильно объявить функцию, которая должна возвращать массив, длина которого заранее не известна?
Re: разъясните ситуацию с передачей массива в функцию:
| От: | WolfHound |
| Дата: | 20.08.03 19:00 |
| Оценка: |
Здравствуйте, spectre, Вы писали:
S>И ещё: как правильно объявить функцию, которая должна возвращать массив, длина которого заранее не известна?
templateclass T, int N> int arr_len(T(&arr)[N]) < return N; >Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: разъясните ситуацию с передачей массива в функцию:
| От: | Linuxoid |
| Дата: | 20.08.03 19:06 |
| Оценка: |
Здравствуйте, spectre, Вы писали:
S>передаю массив в функцию:
S>int a[]=;
S>fun(a);
S>int fun(int ar[])
S>
S>получаю 1.
S>почему я получаю 1, а не 5?
S>что нужно сделать, чтоб функция работала правильно?
Потому что ar — укзатель на int. На 32-х разрядных платформах
sizeof (int *) == sizeof (int) == 4; 4/4 == 1
Тебе нужно объявить функцию так:
int fun (int * arr, int arr_size) < // . >и в качестве второго аргумента передавать размер массива.
S>И ещё: как правильно объявить функцию, которая должна возвращать массив, длина которого заранее не известна?
int* fun (int *size) < *size = random (1000); return ((int *)malloc (rnd_size * sizeof (int)); >Re: разъясните ситуацию с передачей массива в функцию:
| От: | Андрей Тарасевич |
| Дата: | 20.08.03 20:30 |
| Оценка: |
Здравствуйте, spectre, Вы писали:
S>передаю массив в функцию:
S>int a[]=;
S>fun(a);
S>int fun(int ar[])
S>
S>получаю 1.
S>почему я получаю 1, а не 5?
Потому что объявление 'int ar[]' в списке параметров функции эквивалентно объявлению 'int* ar'. Это указатель, а не массив.
S>что нужно сделать, чтоб функция работала правильно?
Она и так работает правильно. Вопрос в том, что именно ты хочешь получить.
Как ты хочешь передать массив в функцию? По значению? По ссылке (указателю)? Всегда ли массив будет одного размера?
S>И ещё: как правильно объявить функцию, которая должна возвращать массив, длина которого заранее не известна?
Функции в С++ не могут возвращать массив, независимо от того известна его длина или нет. Работай через параметры.
Best regards,
Андрей Тарасевич
Re: разъясните ситуацию с передачей массива в функцию:
| От: | LaptevVV | |
| Дата: | 21.08.03 06:51 | |
| Оценка: | 3 (1) | |
Здравствуйте, spectre, Вы писали:
S>передаю массив в функцию:
S>int a[]=;
S>fun(a);
S>int fun(int ar[])
S>
S>получаю 1.
S>почему я получаю 1, а не 5?
S>что нужно сделать, чтоб функция работала правильно?
S>И ещё: как правильно объявить функцию, которая должна возвращать массив, длина которого заранее не известна?
Почитайте вот это
Реализуем эти задачи в виде функций, параметром которых будет массив. Заодно и разберемся с нюансами передачи массива в качестве параметра. Итак, для начала напишем функцию, вычисляющую сумму массива вещественных чисел. Нам, как обычно, требуется написать универсальную функцию, поэтому она должна работать для массивов любой длины. Заголовок такой функции выглядит так:
double Summa (double array[], int n)
По правилам языка С++ (которые в этом случае унаследованы от С), функция, получающая массив в качестве параметра, «не знает», сколько элементов в этом массиве. Попробуем, однако, вычислить количество элементов массива, используя для этого операцию sizeof, как выше мы вычисляли количество элементов массива month. Тогда наша функция выглядит следующим образом:
double Summa (double array[])
< unsigned long n = sizeof(array)/sizeof(double);
double s = 0; for(int i = 0; i < n; ++i) s+=array[i];
return s;
>
Далее напишем main и вызовем нашу функцию.
int main()
< double v[10] = ;
cout return 0;
>
Однако результат получается неожиданный — ноль! Такой результат может получиться только в двух случаях: либо массив содержит только нулевые значения, либо цикл в функции не выполняется ни разу, и функция возвращает первоначальное значение переменной s, равное нулю. Первый вариант сразу отпадает, второй вариант может сработать, если переменная n — количество элементов массива — равна нулю. Выполняем программу по шагам с заходом в функцию и выясняем, что это действительно так. Для исследования работы программы и функции добавим операторы cout, которые покажут нам длину массива в основной программе и в функции.
double Summa (double array[])
< cout unsigned long n = sizeof(array)/sizeof(double);
double s = 0; for(int i = 0; i < n; ++i) s+=array[i];
return s;
>
int main()
< double v[10] = ;
cout cout return 0;
>
Программа, как и положено, выводит число 80 = sizeof(double)*10. А вот функция выводит число 4. Теперь понятно, почему получается ноль в результате: целое деление 4/sizeof(double) равно 0, цикл не выполняется ни разу, и функция возвращает ноль.
Однако это может означать только одно: сам массив в функцию не попадает. Таким образом, массив в функцию передается не по значению, а каким-то другим способом. Но и не по ссылке, так как массивы были реализованы еще в С, а ссылок в С не было. Остается только один вариант из приведенных в начале главы 2 — массив передается по указателю. С указателями мы разберемся позже, а сейчас исправим нашу функцию, чтобы она вычисляла правильное значение (листинг 3.2).
Листинг 3.2. Сумма массива
double Summa (double array[], int n)
< double s = 0;
for(int i = 0; i < n; ++i) s+=array[i];
return s;
>
Проверка показывает, что функция работает совершенно правильно, если правильно задано количество элементов. Более того, функция получилась даже универсальнее, чем мы изначально задумывали: с помощью этой функции мы можем вычислить «хвостовые» суммы, начиная с любого элемента массива. Нам надо только правильно задать конструкцию, с какого элемента начинать считать. Мы не можем написать обычное выражение с индексом в скобках, например, v[5] — это значение пятого элемента массива, а не обозначение «хвоста» массива, начиная с 5-го элемента. В С++ это можно сделать, прибавив номер элемента к имени массива.
int main()
< double v[10] = ;
cout cout cout return 0;
>
Таким образом, мы еще раз убеждаемся, что массив-параметр передается в функцию не по ссылке — со ссылкой такой фокус проделать невозможно. Вместо номера элемента-константы мы даже можем задавать произвольное выражение, например
int main()
< int i = 3; const int ten = 10;
double v[ten] = ;
cout return 0;
>
Главное, чтобы значение этого выражения не было отрицательным, или больше количества элементов массива — тогда последствия непредсказуемы. Так как С++ не может проверить правильность этого выражения, то вся ответственность ложится на программиста. Например, никаких сообщений ни при трансляции, ни при выполнении не выдается, если программист напишет такой вызов
cout Однако совершенно очевидно, что это серьезная ошибка, которую программисты обычно называют «вылет за границу».
«Вылет» за границу массива — одна из самых распространенных ошибок при программировании обработки массивов. А такое происходит достаточно часто, если количество элементов задается не явно, а вычисляется, как в нашем примере, и передается функции как переменная. При работе с массивами программист совершенно не защищен от ошибок. Именно это послужило одной из причин разработки стандартной библиотеки, в которую вошли более «умные» контейнеры.
В главе 1 мы говорили о том, что программа, выполняющая больше того, что запланировано — ошибочна. Однако в программе вычисления таблицы умножения (см. листинг 1.2) мы могли проверить наши данные и отвергнуть ошибочные. Совершенно иная картина наблюдается сейчас: у нас нет средств проверить соответствие «начала отсчета» и количества элементов. Так устроен язык С++, унаследовавший эту особенность от С. Поэтому неожиданная унивесальность сама по себе не является ошибкой, но порождает массу проблем, связанных с «вылетом» за границы массива.
Аналогично пишутся и другие функции, например, поиск заданного значения в массиве (листинг 3.3). Функция должна возвращать номер найденного элемента. Если элемента в массиве нет, то возвращается -1.
Листинг 3.3. Поиск элемента в массиве
int FindNumber(double Number, double array[], int n)
< for(int i = 0; i < n; ++i)
if (array[i]==Number) return i;
return -1;
>
Функция также прекрасно работает, если параметры передаются правильные. Как и для функции суммирования массива (см. листинг 3.2), в этом случае мы тоже имеем возможность искать заданное число в «хвосте» массива, например
double pi = 3.141592653;
int k = FindNumber(pi, v+3, n-3);
Вообще-то существует один вариант передачи массива в качестве параметра, когда можно не указывать количество элементов: необходимо в качестве параметра объявить ссылку на массив. Продемонстрируем эту возможность на примере той же функции Summa (листинг 3.4).
Листинг 3.4. Параметр-ссылка на массив
const int n = 10;
double Summa (double (&array)[n])
< double s = 0;
for(int i = 0; i < n; ++i) s+=array[i];
return s;
>
Скобки вокруг имени параметра-массива указывать обязательно, без них программа не транслируется. К сожалению, такой способ не позволяет написать универсальную подпрограмму для обработки массива произвольного размера. В этом случае и тип, и количество элементов массива фиксировано и должно указываеться при объявлении. Поэтому в функцию при вызове допускается передавать массивы только указанного размера. Мы объявили глобальную константу и использовали ее в объявлении параметра-массива.
При вызове такой функции мы уже не можем посчитать «хвостовые» суммы,
cout cout так как со ссылками арифметические вычисления запрещены — программа просто не транслируется.
Оператор typedef позволяет прояснить ситуацию с передачей ссылки. Для массивов этот оператор имеет нестандартный синтаксис
typedef тип ИМЯ [количество];
ИМЯ — это имя нового типа. Его можно использовать для объявлений массивов заданного типа и размера. Количество должно быть константным выражением. Таким образом, у нас в программе могут встречаться такие объявления:
typedef double DoubleArray [10];
DoubleArray a;
Теперь заголовок функции Summa мы можем задать так
double Summa (DoubleArray &a) //--эквивалентно листингу 3.4
Для компилятора такой заголовок абсолютно идентичен прописанному нами ранее в листинге 3.4. В этом случае в теле функции мы обязаны использовать константу — количество элементов при организации цикла вычислений — переменную компилятор не пропустит.
Попытки использовать это имя для возврата массива
DoubleArray Summa(DoubleArray &a)
так же не проходят — компилятор тут же обнаруживает «обман».
Если мы случайно или намеренно не укажем ссылку в параметре, то нарвемся на очередной «риф» обширного моря С++.
double Summa(DoubleArray a)
Синтаксических ошибок в таком объявлении не наблюдается. Может показаться, что таким образом массив передается «по значению». Однако такая запись является грубой ошибкой. В этом случае считается, что массив передается по указателю. А это означает, что надо передавать количество элементов, иначе результат вычислений непредсказуем.
И наконец, что произойдет, если у нас в программе объявлена и та и другая функция, то есть мы перегружаем функцию Summa:
double Summa (DoubleArray &a) ;
double Summa (DoubleArray a) ;
Определения транслируются без ошибок. Однако при вызове функции возможны «аварийные ситуации» вплоть до отказа компилятора «выдать готовый продукт», то есть работающую программу.
cout cout cout Первый оператор является двусмысленным: компилятор не может решить, какая функция вызывается. Остальные работают по варианту без ссылки, так как ссылки не могут участвовать в арифметических выражениях. А так как в данном случае количество элементов не передается, то программа либо вообще не будет работать, либо посчитает неверную сумму.
Так как для копирования одного массива в другой требуется цикл, будет полезным реализовать эту операцию в виде функции. Более того, мы напишем шаблон функции, чтобы можно было копировать массивы любого числового типа (листинг 3.5).
Листинг 3.5. Копирование массивов
template < typename T >
void Copy(const T a[], T b[], int n)
< for (int i = 0; i < n; ++i) b[i] = a[i]; >
Замечание
Чтобы этот пример заработал в системе Borland C++ 3.1, необходимо ключевое слово typename заменить на слово class.
Мы прописали в списке параметров два массива — один массив описан как константный, а второй — нет. Дело в том, что у нас нет возможности возвратить массив как результат функции — если массив не попадает в функцию, то и возвратить функция массив не может. Поэтому нам нужен один входной массив и один выходной. Мы и задокументировали в прототипе входной массив как константный, а выходной — нет. Без const по прототипу трудно сообразить, что куда пересылается. Проверяем нашу функцию для массивов двух типов: int и double.
int main ()
< int i;
int v[10] = ;
int w[10] = ;
for(i = 0; i cout Copy(w,v,10); // w -> v
for(i = 0; i <10; ++i) cout << v[i] <<' '; cout double v1[10] = ;
double w1[10] = ;
for(i = 0; i <10; ++i) cout << v1[i] <<' '; cout Copy(w1,v1,10); // w1 -> v1
for(i = 0; i <10; ++i) cout << v1[i] <<' '; cout return 0;
>
Программа выводит на экран
0 0 0 0 0 0 0 0 0 0 -- пустой массив v типа int
1 2 3 4 5 6 7 8 9 10 -- копия v 0 0 0 0 0 0 0 0 0 0 -- пустой массив v1 типа double
1.1 2.1 3.1 4 5 6 7 8 9 10.1 -- копия v1 Таким образом, если мы не прописываем слово const, то такой массив можно свободно модифицировать в теле функции. Этот пример наглядно демонстрирует, что передача массива по указателю очень похожа на передачу параметра по ссылке, но нам нет нужды указывать символ & при объявлении параметра-массива.
Теперь мы легко можем написать функцию, модифицирующую аргумент-массив некоторым заданным образом, например, умножает все элементы на 2 (листинг 3.6).
Листинг 3.6. Умножение массива на 2
template < typename T >
void Mult2(T array[], int n)
< for (int i = 0; i < n; ++i) array[i] *= 2;
>
Мы опять написали шаблон, чтобы иметь возможность оперировать с числовыми массивами любого типа.
При обработке массивов начинающий программист часто «наступает на одни и те же грабли». Обычно приходится выполнять некоторую операцию над всеми элементами массива, например, поделить на некоторое значение. Программист пишет функцию, в которой, для пущей универсальности, решает передавать это значение в качестве параметра: «делить — так делить».
void Divide(double array[], int n, double m)
< for (int i = 0; i < n; ++i) array[i] /= m; >
Никакого «криминала» в определениии не наблюдается. И в самом деле, любой их вызовов
double w[10] = ;
Divide(w, 10, 2);
Divide(w, 10, 3);
Divide(w, 10, 7.543);
проблем не вызывает — все работает именно так, как и задумывал программист. Где же ошибка? Вот она:
Divide(w, 10, w[5]);
Никаких сообщений об ошибках, естественно, не возникает. Однако результат работы функции совершенно не тот, на который рассчитывал программист: очевидно, требовалось поделить все элементы массива на пятый элемент. Сам пятый элемент должен получить значение 1. Однако если мы выведем массив w на экран после вызова функции Divide, то увидим, что первые четыре элемента совершенно правильно поделены на пятый, сам пятый элемент равен 1. А вот после него все элементы остались без изменения. «Собака зарыта» именно в пятом элементе. После того, как цикл выполнит деление для этого элемента, его значение станет равно 1, и дальше производится деление на единицу!
Операция деления не является в данном случае особой — точно такая же ошибка возникает и при сложении, вычитании и умножении. Дело в аргументе, который является элементом массива. Подобного рода проблемы возникают, например, при программировании метода Гаусса для решения системы линейных уравнений — там нужно делить все элементы строки матрицы на главный элемент, который тоже содержится в матрице.
Индексы как параметры
Одним из распространенных приемов при работе с одномерными массивами является передача в качестве параметров начального и конечного индекса элементов. Особенно такой прием распространен в рекурсивных функциях (см. главу 8), однако и простых циклических программах довольно часто применяется. Такой способ обработки имеет дополнительные удобства: мы сможем обрабатывать любую последовательность элементов исходного массива, явно указывая индексы первого и последнего.
Кроме того, есть ряд традиционных задач обработки массивов, которые при таком способе передачи параметров решаются значительно проще, чем при указании длины массива. Одной такой классической задачей является быстрая сортировка, второй — двоичный поиск в отсортированном по возрастанию массиве. Обеим задачам посвящено огромное количество работ, некоторые из которых приведены в списке литературы [ ], однако нас интресует в данном случае не теория, а чисто практический вопрос передачи параметров.
Для определенности будем считать, что массив – целого типа. Как массив, так и искомое число, очевидно, должны передаваться функции как параметры. Функция должна вычислять индекс середины некоторого сегмента исходного массива. Поэтому в качестве параметров лучше передавать начальный и конечный индекс сегмента. Таким образом, заголовок функции выглядит следующим образом:
int BinarySearch(int a[], int begin, int end, int v)
где begin и end – начальный и конечный индекс элементов сегмента массива, а v – искомое число. Возвращать такая функция будет номер искомого элемента, если он есть в массиве, или –1, если элементав массиве нет. Таким образом, функция выглядит так (листинг 3.7).
Листинг 3.7. Двоичный поиск в массиве
int BinarySearch(const int a[], int begin, int end, int v)
< while (end >= begin)
< int m = (begin+end)/2; //--середина последовательности
if (v == a[m]) return m;
if (v < a[m]) end = m-1; //--«идем налево»
else begin = m+1; //--«идем направо»
>
return –1; //--в массиве нет элемента
>
Поскольку данная функция не изменяет элементы массива, то мы явно указываем этот факт, прописывая в заголовке слово const. Попробуйте написать двоичный поиск с параметром-количеством элементов – это не такая простая задача! Нам все равно придется некоторым образом моделировать обрабатываемую половину массива. А в данной функции это делается легко и просто изменением заданных в качестве параметров границ массива.
Теперь нам осталось только написать сортировку массива по возрастанию. Опять не будем вдаваться в теорию, а просто напишем шаблон для сортировки любых числовых массивов. Используем один из простых методов — сортировку выбором.
Идея этого метода заключается в том, что в массиве выбирается минимальный элемент, потом из оставшихся — опять минимальный, и так далее. Можно помещать очередной выбранный элемент исходного массива на соответствующее место в массив-результат. Однако сортировки разрабатывались в те далекие времена, когда памяти у компьютеров было очень мало, использовать два массива просто не было физической возможности. Поэтому сортировки традиционно пишутся таким образом, чтобы сортировать массив «на месте», не используя дополнительных массивов.
Таким образом, очередной выбранный минимальный элемент должен переставляться с очередным элементом того же массива: первый минимум переставляется с первым элементом, затем из оставшихся опять выбирается минимальный и переставляется со вторым, и так далее.
Результата-числа у функции нет — это «процедура». Таким образом, наш шаблон сортировки выглядит так (листинг 3.8).
Листинг 3.8. Сортировка массива методом выбора
template < typename T>
void SortArray(T a[], int n)
< for(int i = 0; i < n-1; ++i)
< T min = a[i];
for(int j = i+1, k = i; j < n; ++j)
if (a[j]
a[k] = a[i]; // -- обмен
a[i] = min; // -- элементов
>
>
Несколько необычно выглядит обмен элементов — всего два присваивания. В главе 2 мы писали функцию обмена (см. листинг 2.7), и там требовалось три оператора присваивания и временная переменная. В данном случае мы при обмене используем переменную min, в которой уже записан k-й элемент массива, являющийся минимальным значением.
Проверка функции
double w1[10] = ;
for(i = 0; i <10; ++i) cout << w1[i] <<' '; cout SortArray(w1, 10);
for(i = 0; i <10; ++i) cout << w1[i] <<' '; cout показывает,
9 8 7 6 5 4 3 2 1 10.1 -- до сортировки
1 2 3 4 5 6 7 8 9 10.1 -- после сортировки
что она работает совершенно правильно. Так же, как и во всех предыдущих функциях, мы имеем возможность сортировать только «хвост» массива.
Напишем второй вариант той же сортировки, но параметрами будут индексы первого и последнего элемента массива. Вместо индекса последнего элемента будем задавать номер на 1 больше — так оказывается удобнее проверять условие окончания. Кроме того, такой вариант позволяет нам осуществить проверку правильности задания границ передаваемого массива. Совершенно очевидно, что первый индекс должен быть меньше второго, по крайней мере, на 1, а сами индексы не могут быть меньше нуля. К сожалению, и в таком варианте мы не можем гарантировать отсутствие «вылета» за границы массива. Однако возможность хоть какой-то проверки параметров говорит в пользу такого метода. Поэтому, если параметры неверные, функция будет возвращать -1, а если все задано верно, то ноль (листинг 3.9).
Листинг 3.9. Сортировка с параметрами-индексами
template < typename T>
int SortArray(T a[], int first, int last)
< if ((last for(int i = first; i < last-1; ++i)
< T min = a[i];
for(int j = i+1, k = i; j < last; ++j)
if (a[j]
a[k] = a[i]; a[i] = min;
>
return 0;
>
Как видите, мы просто перегрузили шаблон. Проверка его на массиве целого типа
int w[10] = ;
for(i = 0; i <10; ++i) cout << w[i] <<' '; cout SortArray(w, 0, 10);
for(i = 0; i <10; ++i) cout << w[i] <<' '; cout показывает
10 2 3 9 8 6 5 7 4 1 -- до сортировки
1 2 3 4 5 6 7 8 9 10 -- после сортировки
что все работает совершенно правильно. В таком варианте мы получаем возможность сортировать любую последовательность элементов в массиве.
Параметры-массивы в форме указателя
Выше мы говорили о том, что массивы передаются в функцию по указателю. Более того, при разработке языка С авторы приняли гениальное решение: само имя массива является указателем. Это, с одной стороны, позволило избавиться от многих проблем, которые были характерны для других языков программирования того времени. С другой стороны, это повлекло за собой множество следствий, в частности, разрешение арифметических операций с указателями. Мы уже видели примеры использования этих возможностей на примере функции Summa (см. листинг 3.2)., когда смогли вычислять сумму «хвоста» массива.
Можно было бы написать более общий вариант функции Summa, если передавать в качестве параметров имя массива и два индекса, как в функции BinarySearch (см. листинг 3.7). В таком варианте мы могли бы, по крайней мере, проверять правильность задания начального и конечного индекса. Однако было бы совсем хорошо, если бы для любого массива А мы могли бы писать такие вызовы функции суммирования:
Summa(A, A+10);
Summa(A+3, A+8);
Summa(A+5, A+(n-7));
Первый вызов означает сумму первых 10 элементов массива. Второй, очевидно, — сумма 5 элементов, начиная с A[3] и до A[8]. Если n обозначает длину массива, то третий вызов означает суммирование элементов массива А, начиная с А[5] и до А[n7] — седьмой элемент от конца массива.
Как видим, такая функция суммирования является универсальной и не получает лишних параметров — только то, что действительно нужно для работы.
Мы можем написать подобную функцию, если используем способ задания параметров-массивов в форме указателей. Передача параметра-массива в форме указателя выглядит так:
тип *имя
Звездочка и показывает, что это не простой параметр, а параметр-указатель. При использовании указателей для обработки массивов в функцию обычно передают два параметра-указателя: начало и конец обрабатываемой последовательности. Но при этом имя массива в формальных параметрах не задается — оно фигурирует только при вызове. Напишем теперь шаблон функции суммирования (листинг 3.10).
Листинг 3.10. Шаблон функции суммирования
template
T Summa(T *begin, T *end)
< T sum = 0;
if (begin < end) // если параметры корректны
< for(;begin < end; ++begin)
sum+=*begin; // звездочка обязательна.
>
return sum;
>
Здесь надо отметить важные особенности, которые мы наблюдаем в теле шаблона. Как видим, с указателями можно выполнять разные операции, например, сравнивать их между собой, и эти операции не являются операциями с элементами массива. При входе в функцию должно выполняться условие begin Почему именно begin Summa(A, A+10);
Если в массиве 10 элементов, то А+10 — это после последнего элемента массива. Такой способ задания фактического параметра упрощает жизнь программисту и является естественным в С и С++.
Далее, начальное значение в операторе цикла не присваивается, предполагается, что begin — это оно и есть. Кроме того, в операторе цикла выполняется арифметическая операция с указателем.
И самое важное — при суммировании мы прописали при указателе звездочку. Очевидно, при этом предполагается, что *begin имеет такой же тип T, как и sum. Это действительно так, что мы и наблюдаем в заголовке.
Чтобы разобраться в некоторых нюансах, напишем шаблон последовательного поиска заданного элемента в массиве (см. листинг 3.3). В качестве параметров нам очевидно нужно искомое число, а массив, в котором надо его искать, зададим парой указателей. Возвращать функция тоже будет указатель на искомый элемент. Зачем возвращать указатель, если мы можем вернуть и сам элемент? Дело в том, что элемент в массиве может отсутствовать, поэтому функция должна сигнализировать о такой ситуации. При возврате непосредственно элемента массива мы должны иметь дополнительный булевский параметр, передаваемый по ссылке, куда и нужно записывать результат поиска. А возврат указателя позволит нам обойтись без этого параметра: если элемент не найден, то функция возвращает ноль — можно присваивать указателю значение ноль, и это не является присвоением нуля элементу массива. Таким образом, заголовок нашего шаблона выглядит так.
template < class T >
T *Find(T number, T *begin, T *end)
В шаблоне мы напишем такой же цикл, как и в шаблоне суммирования, заменив только тело цикла (листинг 3.11).
Листинг 3.11. Поиск в массиве по указателю
template < class T >
T *Find(T number, T *begin, T *end)
< if (begin < end) // если параметры корректны
< for(;begin < end; ++begin)
if (*begin == number) return begin; // -- если нашли
>
return 0; // -- не нашли или параметры неправильные
>
Вызов такой функции может быть такой
double w[10] = ;
double *p = Find(6.0, w, w+10);
На месте параметра-указателя begin мы написали имя массива, а на месте end — имя массива + количество элементов. Этот прием совершенно стандартный и широко используется в различных алгоритмах стандартной библиотеки STL. Для возвращаемого значения в заголовке мы прописали звездочку, так как функция возвращает не значение, а указатель. Интересно, что и при выводе найденного значения на экран звездочку тоже необходимо прописывать.
cout << *p То же самое нужно делать непосредственно при вызове функции
cout Почему это необходимо делать, мы разберемся при детальном изучении указателей в главе 7.
Параметр-массив по умолчанию
Параметру-массиву можно присвоить значение по умолчанию. Однако синтаксис инициализации массива в списке параметров не допускается. Такую запись
void f(int a[] = )
компилятор не пропустит. Однако можно присвоить начальные значения элементам массива, используя функцию, возвращающую указатель. Рассмотрим следующий пример (листинг 3.13).
Листинг 3.13. Присвоение значений по умолчанию массиву
double a[10] = ;
double* P(double array[], int n)< return array; >
void T(int n = 10, double d[] = P(a, 10))
< for(int i = 0; i < n; ++i)
cout >
Мы прописали массив а глобально, чтобы задать его параметром в функции Р, которая вызывается для заполнения параметра-массива уже в функции Т. Вызов таким образом определенной функции может быть таким:
double b[10] = ;
T(); cout T(6, b); cout В первом случае функция Т обрабатывает массив а, во втором — явно заданный массив b.
Многомерные массивы
Как уже было сказано выше, многомерный массив в С++ рассматривается как одномерный, элементами которого являются массивы. Так как массив — это набор однотипных элементов, массивы-элементы многомерного массива все должны быть одного типа и размера. Проясняет ситуацию использование оператора typedef
typedef float array [10]; // array — массив из 10 float
array m[10]; // массив из 10 массивов float[10]
Ограничений на количество измерений не накладывается — все зависит от реализации. Однако обычно двумерный массив объявляется более традиционным способом, например:
int a[10][10];
Как и другие переменные, многомерный массив можно инициализировать
int A[3][3] = < , >;
Мы объявили массив из 3-х элементов, каждый элемент является массивом из 3 целых. Элемент A[0] получил значение , элемент A[1] равен , остальные элементы все равны 0.
Элементы одномерного массива располагаются в памяти последовательно: A[0], A[1],A[2]. Это значит, что двумерный массив расположен в памяти по строкам. На рисунке 3.1 показано, как размешщается массив A.
A[0] A[1] A[2]
1 2 3 2 3 0 0 0 0
A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2] A[2][0] A[2][1] A[2][2]
Рис. 3.1. Размещение в памяти массива A[3][3]
Инициализацию многомерного массива можно выполнить и «одномерным способом.
int A[3][3] = < 1,2,3,2,3 >;
Это объявление эквивалентно предыдущему. Как обычно, можно не указывать количество элементов, но только в самых левых скобках, например
int A[][3] = < , >;
В данном случае считается, что массив А состоит из двух элементов (см. рис.3.2), каждый из которых является массивом из 3 целых. При инициализации А[0] заполняется полностью, а в A[1] заносится только два числа, а третий элемент обнуляется.
A[0] A[1]
1 2 3 2 3 0
A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2]
Рис. 3.2. Размещение в памяти массива A[][3]
Как многомерные массивы–параметры передаются в функции, рассмотрим в главе 7.
Массивы и указатели
Для всех встроенных типов в С и С++ существуют константы соответствующих видов. Указатели — тоже встроенный тип, поэтому встает вопрос о том, как представить в языке константу-указатель. И, как мы уже упоминали в третьей главе, создатели С приняли решение считать имя массива такой константой. Пусть у нас в программе объявлен массив и указатель
int a[10];
int *p;
Тогда присвоить адрес массива переменной-указателю можно одним из следующих совершенно равноправных способов
p = &a[0];
p = &a;
p = a;
С указателями разрешены арифметические действия, поэтому после одного из таких присваиваний выражение p+i означает адрес i-го элемента массива. Обратите внимание, что i — это номер элемента массива, а не количество байт. Транслятор правильно вычисляет адрес соответствующего байта, умножая i на sizeof(тип). Значение i-го элемента можно получить, применив уже известную нам операцию разыменования
*(p+i)
Скобки поставлены, поскольку приоритет операции разыменования * больше приоритета операции сложения +. Эта запись эквивалентна записи p[i] и имеет смысл a[i]. Так же, как и a[i], выражение *(p+i) можно использовать и слева, и справа от знака присваивания.
Выражение *p+i имеет совершенно другой смысл: а[0]+i. Так как имя массива тоже является указателем, его тоже можно использовать в таких выражениях, например *(a+i), что означает a[i]. Только надо помнить, что имя массива — это все-таки константа, а константе нельзя присвоить другое значение (в данном случае значением является адрес другой переменной).
Если указатель p указывает на элемент массива, то операция инкремента p++ или ++p «передвинет» указатель на следующий элемент массива: к указателю прибавляется sizeof(тип) байтов. Пусть, например, указатель p указывает на 5-й элемент массива. Тогда выражения
*p++ //-1
(*p)++ //-2
*(p++) //-3
имеют, как обычно, совершенно разный смысл:
1. выдать значение 5-го элемента массива и «передвинуть» указатель;
2. увеличить значение 5-го элемента массива;
3. «передвинуть» указатель и выдать значение 6-го элемента массива.
Как вы уже поняли, к указателю всегда можно добавить выражение целого типа или отнять (аналогично тому, как мы это делали с итераторами в главе 5). Однако операции умножения и деления с указателями не допускаются. Складывать два указателя тоже нельзя. А вот разность указателей — это важная операция. Мы уже использовали эту операцию при написании функции findStr (см. листинг 3.18). Пусть у нас в программе есть следующие объявления:
int a[10]; int *p1 = &a[1]; int *p2 = &a[8];
Тогда оператор вывода
cout << p2-p1 выведет на экран число 7 — количество элементов массива между a[1] и a[8].
Многомерные массивы как параметры
В главе 3 мы рассматривали различные способы передачи одномерных параметров-массивов. С многомерными массивами все значительно сложнее, поскольку требуется уже не одна размерность, а несколько. Кроме того, необходимо помнить, что в C++ все массивы считаются одномерными и интерпретируются как “массив массивов массивов . ”. Поэтому, вообще говоря, неопределенной может быть только одна размерность, а остальные должны быть зафиксированы на момент обращения. Это создает некоторые трудности при программировании функций для работы, например, с матрицами.
Рассмотрим следующий простой пример. Пусть требуется написать функцию вывода на экран квадратной матрицы. Передаваемый массив двумерный, хотя для передачи размерности требуется один параметр. Очевидное решение просто недопустимо в языке C++ — транслятор выдаст сообщение, что размер массива не определен или равен нулю (листинг 7.19).
Листинг 7.19. Неправильный параметр — двумерный массив
void PrintMatrix(int m[][], int n)
< float x;
for(int i=0; i < for(int j=i+1; jcout >
>
Можно конечно зафиксировать одно измерение – количество элементов в строке, — оставляя второе – количество строк — пустым, но, очевидно, такое решение не является удовлетворительным, хотя и будет работать. Причем выражение, определяющее количество элементов в строке матрицы должно быть только константным. Это означает, что нельзя задавать параметр в виде int m[][n] или в виде int m[][f()]. В приведенном ниже прототипе функции в качестве второго измерения указано число 10. Тело функции не изменяется, поэтому мы его опустим.
void PrintMatrix(int m[][10], int n);
Однако фиксация только второго размера не имеет никакого смысла, поскольку все равно такая функция сможет работать только с массивами 10х10. Проще зафиксировать оба измерения и написать функцию для конкретного массива. Аналогично при указании формального параметра в виде ссылки на массив необходимо зафиксировать оба измерения. Но тогда, как мы уже знаем, можно не задавать параметр – количество строк матрицы.
void PrintMatrix(int (&m)[10][10]);
Конечно, в каждой конкретной программе матрицы имеют конкретные размеры и можно обойтись указанными способами. Однако иногда требуется написать универсальную программу, например, умножения матриц. Указав вместо конкретных размеров поименованные константы, мы до некоторой степени решаем проблему, однако такой способ, несомненно, не удовлетворяет истинного программиста. Радикальным решением этой проблемы было бы использование механизма классов для представления матриц как объектов. Без применения классов обработка многомерных массивов основана на использовании указателей. Обычно используют вспомогательные массивы указателей (на массивы). Рассмотрим реализацию программы транспонирования матриц с использованием массива указателей (листинг 7.20).
Листинг 7.20. Параметр — двумерный массив как массив указателей
void PrintMatrix(int *m[], int n)
< float x;
for(int i=0; i < for(int j=i+1; jcout >
>
Тело функции не изменилось. В качестве параметра-массива указан одномерный массив указателей. Однако в вызывающей программе придется организовать все эти дополнительные массивы указателей. Главная программа может выглядеть следующим образом:
int main(void)
< int t[ ][4] = < , // -- инициализация матрицы
,
,
>;
int *pt[4] = <(int *)&t[0], // -- массив указателей
(int *)&t[1],
(int *)&t[2],
(int *)&t[3]>;
// -- что-то делаем
PrintMatrix(pt,4);
// -- дальнейшая обработка
return 0;
>
Инициализацию указателей можно выполнять и в цикле. Обратите внимание, что при инициализации массива указателей приходится явным образом прописывать преобразование адреса строки к типу указателя pt – без этого преобразования программа в Visual C++ 6 просто не транслируется.
Конечно, этот прием позволяет выходить из положения, но он не слишком хорош для больших массивов: расходуется много памяти на указатели. Да и прописывать явно инициализацию массива указателей не слишком удобно. Поэтому этот прием чаще применяется для динамических массивов указателей. Однако в этом случае мы должны передавать в функцию не массив указателей, а указатель на указатель.
void PrintMatrix(int **m, int n);
В теле функции опять ничего не меняется. Естественно, запрошенную память необходимо потом где-то возвращать системе.
Применение массивов указателей является приемлемым решением для массивов небольших размерностей – двумерных, трехмерных. Однако с увеличением количества измерений все значительно усложняется. Кроме того, на присвоение адресов требуется некоторое время. Поэтому Б.Страудструп [] (а вслед за ним и В.Подбельский []) рекомендуют «обманывать» компилятор, «подсовывая» ему вместо двумерного (многомерного) массива одномерный. Прием основан на том, что в памяти элементы массива размещаются подряд, без пропусков и построчно: сначала элементы первой строки, затем второй и так далее. Правильное моделирование произвольного двумерного массива одномерным выглядит так (листинг 7.21).
Листинг 7.21. Двумерный массив как одномерный
void PrintMatrix(int *M, int n, int m) // — простой указатель
< for (int i=0; i < for (int j=0; jcout cout >
>
int main(void)
< const int n = 4;
int t[n][n] = < ,
,
,
>;
int *p = &t[0][0]; // -- адрес первого элемента массива
PrintMatrix(p,n,n);
return 0;
>
В функцию передается простой указатель, которому в главной программе присваивается адрес первого элемента двумерного массива. В функции выполняются вложенные циклы, чтобы расположить на экране элементы в виде матрицы. Обратите внимание, что выражение [i*m+j] является именно тем, которое генерирует компилятор при трансляции программы для доступа к элементам двумерного массива.
Как указано выше, двумерный массив символов фактически используется как одномерный массив строк, поскольку в качестве параметра передается массив (одномерный!) указателей на строки. Интересно, что для параметра-массива указателей можно использовать то же соглашение, которое принято для строк: последний элемент массива указателей должен иметь нулевое значение. Тогда отпадает необходимость передавать длину массива. Следующий пример в Visual C++ 6 работает абсолютно корректно (листинг 7.24).
Листинг 7.24. Передача массива указателей без количества элементов
void PrintArrayString(char *m[]) // -- нет количества элементов
< int i=0;
while(m[i]) // --пока указатель не нулевой
< cout
>
int main(void)
< char *s[] = // -- массив строк
< "First","Second","Three",0 // нулевой указатель!
>;
PrintArrayString(s); // -- вызов функции
return 0;
>
Если вас смущает условие в операторе цикла, можно прописать явную проверку:
while(m[i]==0)
Этот же прием может использоваться не только для строк, но и для любых двумерных (или многомерных) массивов. Этим приемом не пользуются, видимо, исходя из соображений якобы «неэффективности». Может показаться, что слишком неэффективно расходуется память, так как требуется лишний «пустой» указатель. Однако в настоящее время самый «большой» указатель занимает всего 4 байта, поэтому для любого массива из нескольких десятков (не говоря уже о сотнях и тысячах) элементов этот довод не актуален. Особенно, если размер элемента массива значительно превосходит размер указателя. Ещё одна потенциальная «неэффективность» — в косвенном обращении к объекту через указатель. Однако в наше время «повсеместной косвенности» (COM-технология, паттерны проектирования и т.п.) этот довод также нельзя считать существенным.
Функции и динамические массивы
Поскольку имя массива является указателем, при вызове функции разрешается в качестве параметра задавать динамический массив с помощью оператора new. Размер массива практически неограничен – мы можем забыть о проблемах нехватки памяти как в системе Visual C++ 6, так и в системе Borland C++ 5. Но и в этом случае нужно указывать количество элементов массива отдельным параметром. Попытки вычислить это количество, используя операцию sizeof, ни к чему хорошему не приводят (листинг 7.25).
Листинг 7.25. Параметр — динамический массив
int ff(int m) < return m; >//-- функция для задания размера массива
int* f(int n, int *a)
< int m = sizeof(a)/sizeof(int); //-- «вычисление» количества
return a;
>
int main(void)
< int k = 3;
int *p = f(k, new int [ff(k)]); // -- динамический массив как параметр
delete []p; // — возврат памяти
return 0;
>
Результат выражения sizeof(a)/sizeof(int) равен 1, поскольку в числителе стоит не размер массива, а размер указателя. Поэтому даже в случае динамических массивов приходится задавать количество элементов как параметр. Ничего не меняется, если вместо int *a указать int a[] – программа остается корректной, но переменная m по-прежнему равна единице. Не изменяют ситуацию ни выражение sizeof(*a)/sizeof(int), ни даже выражение sizeof(a[n])/sizeof(int) – значение m по-прежнему равно 1.
Единственным вариантом параметра, при котором выражение sizeof(a)/sizeof(int) выдает истинную длину массива, является ссылка на массив (аналогичная, например, такой int (&a)[10]), но при этом, как мы уже знаем, приходится прописывать явное количество элементов прямо при объявлении. Кроме того, по ссылке невозможно передать динамический массив.
Необходимо подчеркнуть, что функция, получающая динамический массив в качестве параметра, обязана возвращать указатель, иначе возникает утечка памяти
Если останутся вопросы — задавайте.