Если размер строки матрицы известен, а неизвестно только количество строк, можно по-
ступить так: ввести новый тип данных – строка матрицы. Когда количество строк станет известно, с помощью оператора new выделяем массив таких данных.
typedef int row10[10]; // новы тип: массив из 10 элементов
Main()
{
int N;
row10 *A; // указатель на массив (матрица)
printf ("Введите число строк ");
scanf ("%d", &N);
A = new row10[N]; // выделить память на N строк
A[0][1] = 25; // используем матрицу, как обычно
printf("%d", A[2][3]);
Delete A; // освобождаем память
}
Неизвестный размер строки
Пусть размеры матрицы M и N заранее неизвестны и определяются в ходе работы про-
граммы. Тогда можно предложить следующий способ выделения памяти под новую матрицу.
Поскольку матрицу можно рассматривать как массив из строк-массивов, объявим M указателей и выделим на каждый из них область памяти для одномерного массива размером N (то есть, на одну строку). Сами эти указатели тоже надо представить в виде динамического массива. Определив требуемые размеры матрицы, мы выделяем сначала динамический массив указателей, а потом на каждый указатель – место для одной строки.
|
|
typedef int *pInt; // новый тип данных: указатель на целое
Main()
{
intM, N, i;
pInt *A; // указатель на указатель
// ввод M и N
A = new pInt[M]; // выделить память под массив указателей
for (i = 0; i < M; i ++) // цикл по всем указателям
A[i] = new int[N]; // выделяем память на строку i
// работаем с матрицей A, как обычно
for (i = 0; i < M; i ++) // освобождаем память для всех строк
delete A[i];
Delete A; // освобождаем массив указателей
}
В рассмотренном выше случае на каждую строку выделяется свой участок памяти. Можно поступить иначе: сначала выделим область памяти сразу на всю матрицы и запишем ее адрес в A[0]. Затем расставим указатели так, чтобы A[1] указывал на N+1 - ый элемент с начала блока(начало строки 1), A[2] – на 2N+1 - ый (начало строки 2) и т.д. Таким образом, в памяти выделяется всего два блока – массив указателей и сама матрица.
typedef int *pInt;
Main()
{
int M, N, i;
pInt *A; // указательнауказатель
// ввод M и N
A = new pInt[M]; // память на массив указателей
A[0] = new int [M*N]; // память для матрицы
for (i = 1; i < M; i ++) // расставляем указатели
A[i] = A[i-1] + N;
// работаем с матрицей
delete A[0]; // освобождаем матрицу
Delete A; // освобождаем указатели
}
Рекурсия
Что такое рекурсия?
Рекурсивные объекты
Всем известна сказка, которая начинается словами «У попа была собака...». Это бесконеч-
ное предложение будем называть сказкой о попе и собаке. Как же нам определить его строго математически? Оказывается, это можно сделать примерно так:
Как видите, частью этой сказки является сама сказка. Так мы пришли к понятию рекурсии. Еще один пример – картинка, содержащая свое изображение.
|
|
Рекурсия – это определение объекта через самого себя.
С помощью рекурсии в математике определяются многие бесконечные множества, например множество натуральных чисел. Действительно, можно задать их так:
Натуральное число.
1) 1 - натуральное число.
2) Число, следующее за натуральным – натуральное.
Понятие факториала n!=1·2·3·…·(n-1) ·n также можно задать рекурсивно:
Факториал.
1) 0! = 1 (так условно принято).
2) n! = n*(n-1)!