Передача массивов в функции
При использовании в качестве параметра функции массива в функцию передается указатель на его первый элемент, а не копия всего массива. т.е. массив всегда передается по адресу. (Следует помнить, что в языке С имена массивов без индекса – это указатели на нулевой элемент массива.) Параметр должен иметь тип, совместимый с указателем, т.е. элементами массива.
Т.к. работаем с указателями, то информация о количестве элементов массива теряется, и следует передавать его размерность через отдельный параметр (в случае массива символов, то есть строки, ее фактическую длину можно определить по положению нуль-символа):
Имеется три способа объявления параметра, предназначенного для получения указателя на массив.
Во-первых, он может быть объявлен как массив, как показано ниже:
#include <stdio.h>
void vivod(int num[10], int n);
int main(void)
{
int t[10], i;
for(i=0; i<10; i++) t[i]=i;
vivod (t,10);
return 0;
}
void vivod (int num[10])
// void display(int num[],int n)
// void display(int *num,int n)
{
int i;
for(i=0; i<n; i++) printf(“%d “, num[i]);
}
Все, приведенные выше, три способа объявления параметра приводят к одинаковому результату – указателю.
При использовании массива в качестве аргумента функции происходит передача в функцию его адреса. Это позволяет непосредственно из вызываемой функции изменять значения объектов, определённых в вызывающей функции.
Пример Даны два одномерных массива. Вывести упорядоченные массивы , и упорядоченный массив, объединенный из элементов двух массивов
#include<stdio.h>
#include<conio.h>
void input(float *,int );
void sort(float *,int );
void output(float *,int );
main()
{
int i,j,k,n1,n2;
printf("Vv n1 and n2:");
scanf("%d%d",&n1,&n2);
float *a=new float[n1];
float *b=new float[n2];
float *c=new float[n1+n2];
input(a,n1);
input(b,n2);
sort(a,n1);
sort(b,n2);
output(a,n1);
output(b,n2);
for (i=j=k=0;i<n1+n2;i++)
if((a[j]<=b[k]||k>=n2)&&j<n1) {c[i]=a[j];j++;}
else {c[i]=b[k];k++;}
output(c,n1+n2);
getche();
return 0;
}
void input(float *a,int n )
{
int i;
for(i=0;i<n;i++)
{printf("Vv %3d element:",i+1);
scanf("%f",&a[i]);
}
}
void sort(float *a,int n)
{
int i,j;
float tmp;
for(i=1;i<n;i++)
{tmp=a[i];
for(j=i-1;j>=0;j--)
{if(tmp>a[j]) break;
a[j+1]=a[j];
}
a[j+1]=tmp;
} }
void output(float *a,int n)
{int i;
for(i=0;i<n;i++)
printf("%.3f ",a[i]);
printf("\n");
}
Передача многомерных массивов в функции
При передаче многомерных массивов, как и для одномерных, все размерности должны передаваться в качестве параметров.
Существует несколько способов передачи многом. массивов в функцию:
1. С помощью указателя. Синтаксис объявление и определения функции такой же как и при передачи одномерных массивов. При вызове функции передаётся адрес первого элемента массива. Внутри функции массив интерпретируется как одномерный, а его индекс пересчитывается в программе.
В приведенном ниже примере с помощью функции находится максимальный элемент, а также их расположение в двух двумерных массивов. Размерность массива b известна на этапе компиляции, под массив а память выделяется динамически:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void out_matr(float *a,int nstr, int nstb);
float max(float *a, int nstr, int nstb, int &n, int &m);
int main(){
float b[3][3] = {{2, 2,5}, {4,0, 7},{3,2,6}};
int n1,m1;
n1=m1=0;
printf("B:\n");
out_matr(&b[0][0],3,3);
printf("Max B = %f ", max(&b[0][0], 3, 3,n1,m1));
printf("in %d str and %d stb\n",n1+1,m1+1);
int i, j, nstr, nstb;
printf("Введите количество строк и столбцов: \n");
scanf("%d%d", &nstr, &nstb);
float *a = new float[nstb*nstr];
for (i = 0; i<nstr; i++)
for (j = 0; j<nstb; j++)
a[i * nstb + j]=-10+20*float(rand())/RAND_MAX;
printf("A:\n");
out_matr(a,nstr,nstb);
printf("Max B = %f ", max(a, nstr, nstb,n1,m1),n1+1,m1+1);
printf("in %d str and %d stb\n", n1+1,m1+1);
return 0;}
void out_matr( float *a,int nstr, int nstb)
{int i, j;
for (i=0;i<nstr;i++)
{for (j=0;j<nstb;j++)
printf("%5.2f ",a[i*nstb+j]);
printf("\n");
}}
float max(float *a, int nstr, int nstb, int &n, int &m)
{int i, j;
float s=a[0];
n=m=0;
for (i=0;i<nstr;i++)
for (j=0;j<nstb;j++)
if (a[i*nstb+j]>s)
{s= a[i*nstb+j]; n=i;m=j;}
return s;}
2 способ. используется для того чтобы работать с двумерным массивом естественным образом. В этом случае в определении функции применяется указатель на указатель(см. динамич. многом. массивы.)
Задача. Найти произведение матриц.
#include <stdio.h>
#include <conio.h>
void in_matr(int **a,int nstr,int nstb);
void out_matr(int **a,int nstr,int nstb);
void proizv(int **a, int **b,int **c, int , int ,int);
int main(){
int i, j, n, m,k;
printf("Введите количество строк и столбцов: \n");
scanf("%d%d", &n, &m);
int **a = new int*[n];
for (i = 0; i<n; i++) a[i] = new int [m];
in_matr(a,n,m);
printf("Введите количество столбцов(строк =%d): \n",m);
scanf("%d", &k);
int **b=new int *[m];
for (i = 0; i<m; i++) b[i] = new int [k];
int **c=new int *[n];
for (i = 0; i<n; i++) c[i] = new int [k];
in_matr(b,m,k);
printf("A:\n");
out_matr(a,n,m);
printf("B:\n");
out_matr(b,m,k);
proizv(a,b,c,n,m,k);
printf("A*B:\n");
out_matr(c,n,k);
getche();
return 0;}
void in_matr(int **a,int nstr,int nstb)
{ int i,j;
for (i = 0; i<nstr; i++)
for (j = 0; j<nstb; j++)
scanf("%d", &a[i][j]);
}
void out_matr(int **a,int nstr,int nstb)
{ int i,j;
for (i = 0; i<nstr; i++)
{for (j = 0; j<nstb; j++)
printf("%d ", a[i][j]);
printf("\n");}
}
void proizv(int **a, int **b,int **c, int n, int m,int l)
{int i, j,k, s=0;
for (i=0;i<n;i++)
for (j=0;j<l;j++)
{c[i][j]=0;
for(k=0;k<m;k++)
c[i][j]+=a[i][k]*b[k][j];
}}
В этом случае память выделяется в два этапа: сначала под столбец указателей на строки матрицы, а затем в цикле под каждую строку, как показано на рис. 1.10. Освобождение памяти должно выполняться в обратном порядке.
Шаблоны функций
Многие алгоритмы не зависят от типов данных, с которыми они работают (классический пример — сортировка). Естественно желание параметризовать алгоритм таким образом, чтобы его можно было использовать для различных типов данных.
В C++ есть мощное средство параметризации — шаблоны. С помощью шаблона функции можно определить алгоритм, который будет применяться к данным различных типов, а конкретный тип данных передается функции в виде параметра на этапе компиляции. Компилятор автоматически генерирует правильный код, соответствующий переданному типу. Таким образом, создается функция, которая автоматически перегружает сама себя и при этом не содержит накладных расходов, связанных с параметризацией.
Формат простейшей функции-шаблона:
template <c1ass Type> заголовок
{
/* тело функции */ }
Вместо слова Type может использоваться произвольное имя.
В общем случае шаблон функции может содержать несколько параметров, каждый из которых может быть не только типом, но и просто переменной, например:
template<c1ass A. class В, int C> void f(){ ... } ' ^
Например, функция, сортирующая методом выбора (он был рассмотрен на с. 59) массив из п элементов любого типа, в виде шаблона может выглядеть так:
#include<iostream.h>
template <class Type> void sort_vybor(Type *b, int n);
int main()
{
const int n=20;
int i, b[n];
for (i= 0; i<n-1; i++) cin>>b[i];
sort_vybor(b, n);
for (i= 0; i<п-1; i++) cout<<b[i]<<’ ‘;
cout<<’\n’;
double a[]={3,2,5,1,7};
sort_vybor(a, 5);
for (i= 0; i<n-1; i++) cout<<a[i]<<’ ‘;
cout<<’\n’;
return 0;
}
template <class Type> void sort_vybor(Type *b. int n)
{
Type а; //буферная переменная для обмена элементов
for (int i= 0; i<п-1; i++)
{ int imin = i;
for (int j = i + 1;j<n; j++)
if (b[j] < b[imin]) imin= j;
a=b[i]; b[i]=b[imin]; b[imin]=a
}
}
Передача имен функций в качестве параметров
Функцию можно вызвать через указатель на нее. Для этого объявляется указатель соответствующего типа и ему с помощью операции взятия адреса присваивается адрес функции:
void f(int а ){ /* j */ } // определение функции void (*pf)(int): // указатель на функцию
pf = &f: /'/' указателю присваивается адрес функции
// (можно написать pf = f:) pf(10); // функция f вызывается через указатель pf
// (можно написать (*pf)(10) )
#include <stdio.h>
#include <conio.h>
#include <math.h>
double trig(int a,double (*fun)(double));
int main(void)
{
int alfa;
double (*p) (double);
p = sin; /* получение адреса функции sin() */
scanf("%d",&alfa);
printf("sin=%lf",trig(alfa,p));
printf("cos=%lf",trig(alfa,cos));
getch();
return 0;
}
double trig(int a,double (*fun)(double))
{
return (*fun)(a*M_PI/180);
}
Можно объявлять массивы указателей на функции (это может быть полезно, например, при реализации меню):
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
void enter(void), del(void), review(void), quit(void);
int menu(void);
void (*options[])(void) = {
enter,
del,
review,
quit
};
int main(void)
{
int i;
i = menu(); /* получение выбора пользователя */
(*options[i])(); /* выполнение */
return 0;
}
int menu(void)
{
char ch;
do {
printf(“1. Ввод\n”);
printf(“2. Удаление\n”);
printf(“3. Просмотр\n”);
printf(“4. Выход\n”);
printf(“Сделай выбор: “);
ch = getche();
printf(“\n”);
} while();
return ch-49; /* преобразование к целочисленному эквиваленту */
}
void enter(void)
{
printf(“Это ввод.”);
}
void del(void)
{
printf(“Это удаление”);
}
void review(void)
{
printf(“Это просмотр”);
}
void quit(void)
{
printf(“Это выход”);
exit(0);
}
Программа работает следующим образом. Сначала выводится меню и пользователь вводит число, соответствующее его выбору. Поскольку введенное число представлено в ASCII-коде, то необходимо вычесть число 49 (ASCII-код цифры 0) для получения двоичного числа. Данное значение затем возвращается в main() и используется как индекс массива options – массива указателей на функцию. После чего вызывается необходимая функция.
Тип указателя и тип функции, которая вызывается посредством этого указателя, должны совпадать в точности.
Рекурсивные функции
Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций.
Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции.
int a()
{.....a().....}
Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже считаются рекурсивными.
Например:
a(){.....b().....}
b(){.....c().....}
c(){.....a().....} .
Все функции a,b,c являются рекурсивными, так как при вызове одной из них, осуществляется вызов других и самой себя.
. Если функция вызывает себя, в стеке создается копия значений ее параметров, как и при вызове обычной функции, после чего управление передается первому исполняемому оператору функции. При повторном вызове этот процесс повторяется. Ясно, что для завершения вычислений каждая рекурсивная функция должна содержать хотя бы одну нерекурсивную ветвь алгоритма, заканчивающуюся оператором возврата. При завершении функции соответствующая часть стека освобождается, и управление передается вызывающей функции, выполнение которой продолжается с точки, следующей за рекурсивным вызовом.
Числа Фибоначи f0=1
f1=1
fk=fk-1+fk-2
Простым примером рекурсии является функция factr(), вычисляющая факториал целого числа. Факториал числа N есть произведение целых чисел от 1 до N. Для вычисления факториала следует число п умножить на факториал числа п-1.Известно также что 0!=1 и 1!=1
/* Вычисление факториала числа */
int fact(int n) /* нерекурсивно */
{ int t, answer;
answer = 1;
for(t=1; t<=n; t++)
answer = answer*t;
return answer;
}
/* Вычисление факториала числа */
long factr(int n) /* рекурсивно */
{
if(n==1 || n==0)) return 1;
return fact(n-1)*n;
}
long factr(int n) /* рекурсивно */
{
return (n>1)?fact(n-1)*n:1;
}
При написании рекурсивных функций следует использовать оператор if, чтобы заставить функцию вернуться без рекурсивного вызова. Если это не сделать, то, однажды вызвав функцию, выйти из нее будет невозможно.
Достоинством рекурсии является компактная запись, а недостатками — расход времени и памяти на повторные вызовы функции и передачу ей копий параметров, и, главное, опасность переполнения стека.
Прімер. Программа упорядочивания по возрастания чисел методом быстрой сортировки, предложенной Хоар в 1961 г
Метод быстрой сортировки состоит в следующем:
Средний(один из средних) элемент принимается за эталонный и элементы последовательности меньшие эталонного перемещаются в левую часть, а большие – в правую. затем процесс повторяется для каждой из этих частей и будет завершен, когда в рассматриваемых частях останется по одному элементу. Данный метод сортировки является рекурсивным и самым эффективным
Метод быстрой сортировки. В массиве выбирается элемент относительно которого ведётся сортировка, как правило это средний элемент a[k]. Сначала перебираются все элементы расположенные слева от a[k], начиная с первого, до элемента большего либо равного по значению a[i]>=a[k]. После этого перебираются все элементы расположенные справа от a[k], начиная с последнего, до элемента меньшего либо равного по значению a[j]<=a[k]. Элементы a[i] и a[j] меняются местами. Эта процедура продолжается до тех пор, пока выполняется условие i<j. Если же это условие не выполняется то массив разбивается на два новых массива и все действия повторяются до тех пор, пока новый массив содержит не менее двух элементов.
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void quicksort(int *a,int l,int r);
int main ()
{const int n=10;
int a[n],i;
randomize();
for(i=0;i<n;i++)
{a[i]=random(50);
cout<<a[i]<<" ";
}
quicksort(a,0,n-1);
cout<<"\nPosle\n";
for(i=0;i<n;i++)
cout<<a[i]<<" ";
getche();
}
void quicksort(int *a,int l,int r)
{
int i,j;
int buf,p;
if(l<r)
{p=a[(l+r)/2];
i=l;
j=r;
do
{while(a[i]<p) i++;
while(a[j]>p) j--;
if(i<=j)
{buf=a[i];
a[i]=a[j];
a[j]=buf;
i++;
j--;
}
} while(i<j);
quicksort(a,l,j);
quicksort(a,i,r);
}
}
Параметры со значениями по умолчанию
Чтобы упростить вызов функции, в ее заголовке можно указать значения параметров по умолчанию. Эти параметры должны быть последними в списке и могут опускаться при вызове функции Синтаксис для параметров функции по умолчанию подобен синтаксису для инициализации переменных:
Тип имя=значение
В С++ требуется выполнение след. правил для использования Параметров по умолчанию.
когда назначается параметр по умолчанию какому-либо параметру, то д. назначаться параметры по умолчанию всем последующим параметрам.
принимаемые по умолчанию параметры делят список на 2 части: первая – не содержит значений, вторая – содержит;
чтобы использовать значение параметр по умолчанию в качестве фактич.параметра следует опустить фактич.параметр на месте, соответствующего формальн. параметру при вызове функций.
. Если при вызове параметр опущен, должны быть опущены и все параметры, стоящие за ним
double kor(double a, double n=2.0)
{return pow(a,1./n);}
при вызове
y=kor(64,3);
y=kor(64);