- •Часть 2
- •Содержание
- •Задание № Доп-1. Обработка двухмерных динамических массивов. Функции пользователя
- •Особенности применения указателей
- •Связь указателей с массивами
- •Декларация многомерного массива:
- •Указатели на указатели
- •Динамическое размещение данных
- •Минимальный набор действий, необходимых для динамического размещения одномерного массива действительных чисел размером n:
- •Минимальный набор действий, необходимых для динамического размещения двухмерного массива действительных чисел размером nm:
- •Задание №1. Рекурсивные функции
- •1.1. Краткие теоретические сведения
- •1.2. Пример выполнения задания
- •1.2.1. Реализация задания в оконном приложении
- •1.2.2. Реализация задания в консольном приложении
- •1.3. Индивидуальные задания
- •Задание №2. Динамическая структура стек
- •2.1. Краткие теоретические сведения
- •2.2. Пример выполнения задания
- •2.2.1. Реализация задания в оконном приложении
- •2.2.2. Реализация задания в консольном приложении
- •2.3. Индивидуальные задания
- •Задание №3. Динамическая структура очередь
- •3.1. Краткие теоретические сведения
- •Создание первого элемента
- •Добавление элемента
- •Просмотр списка
- •Алгоритм удаления элемента в списке по ключу
- •3.2. Пример выполнения задания
- •3.2.1. Реализация задания в оконном приложении
- •3.2.2. Реализация задания в консольном приложении
- •3.3. Индивидуальные задания
- •Задание №4. Обратная польская запись
- •4.1. Краткие теоретические сведения
- •4.2. Пример выполнения задания
- •4.3. Индивидуальные задания
- •Задание №5. Нелинейные списки
- •5.1. Краткие теоретические сведения
- •Функция просмотра элементов дерева
- •Функция освобождения памяти, занятой деревом
- •5.2. Пример выполнения задания
- •5.3. Индивидуальные задания
- •Задание №6. Алгоритмы поиска корней уравнений
- •6.1. Краткие теоретические сведения
- •Метод простой итерации
- •Метод Ньютона (метод касательных)
- •Метод секущих
- •Метод Вегстейна
- •Метод деления отрезка пополам
- •6.2. Пример выполнения задания
- •6.3. Индивидуальные задания
- •Задание №7. Аппроксимация функций
- •7.1. Краткие теоретические сведения
- •Интерполяционный многочлен Ньютона
- •Линейная и квадратичная интерполяции
- •Интерполяционный многочлен Лагранжа
- •7.2. Пример выполнения задания
- •7.3. Индивидуальные задания
- •Задание №8. Алгоритмы вычисления интегралов
- •8.1. Краткие теоретические сведения
- •Формула средних
- •Формула трапеций
- •Формула Симпсона
- •8.2. Пример выполнения задания
- •8.3. Индивидуальные задания
- •Задание №9. Алгоритмы поиска и сортировки в массивах
- •9.1. Краткие теоретические сведения
- •9.1.1. Алгоритмы поиска
- •Функция поиска всех элементов целочисленного динамического массива а размера n, равных значению х, может иметь следующий вид:
- •Функция поиска одного значения х в целочисленном динамическом массиве а размера n может иметь следующий вид:
- •Else // Вывод сообщения, что элемент не найден
- •9.1.2. Алгоритмы сортировки
- •Функция сортировки элементов целочисленного динамического массива а размера n может иметь следующий вид:
- •Функция сортировки элементов целочисленного динамического массива а размера n может иметь следующий вид:
- •Рекурсивная функция сортировки элементов целочисленного динамического массива а размера n может иметь следующий вид (begin – первый элемент массива, end – последний элемент массива):
- •9.2. Индивидуальные задания
- •Литература
- •Учебное издание
- •Часть 2
- •220013, Минск, п. Бровки, 6
Динамическое размещение данных
Для создания массивов с переменной размерностью используется динамическое размещение данных, декларируемых указателями.
Для работы с динамической памятью используются стандартные функции библиотеки alloc.h:
void *malloc(size) и void *calloc(n, size) – выделяют блок памяти размером size и nsize байт соответственно; возвращают указатель на выделенную область, при ошибке – значение NULL;
void free(bf); – освобождает ранее выделенную память с адресом bf.
Другим, более предпочтительным подходом к динамическому распределению памяти является использование операций языка С++ new и delete.
Операция new возвращает адрес ОП, отведенной под динамически размещенный объект, при ошибке – NULL, а операция delete освобождает память.
Минимальный набор действий, необходимых для динамического размещения одномерного массива действительных чисел размером n:
double *а;
. . .
а = new double[n]; // Захват памяти для n элементов
. . .
delete []а; // Освобождение памяти
Минимальный набор действий, необходимых для динамического размещения двухмерного массива действительных чисел размером nm:
int i, n, m; // n, m – размеры массива
double **a;
a = new double *[n]; // Захват памяти под указатели
for(i=0; i<n; i++)
a[i] = new double [m]; // и под элементы
. . .
for(i=0; i<n; i++) delete []a[i]; // Освобождение памяти
delete []a;
Для освобождения памяти, занятой массивами большой размерности, в современных компиляторах достаточно выполнить следующее действие (для предыдущего примера)
delete []a;
Функции пользователя
Подпрограмма – это именованная и определенным образом оформленная группа операторов, вызываемая по мере необходимости.
В языке С++ в качестве подпрограмм используют функции, которые должны быть декларированы до их первого использования. Предварительное описание функции называется прототипом, который обычно размещается в начале программы (*.cpp) либо в заголовочном файле (*.h) и сообщает компилятору о том, что далее в программе будет приведен ее полный текст, т.е. реализация.
Описание прототипа имеет следующий вид:
тип_результата ID_функции (список типов параметров);
а определение функции имеет следующую структуру:
тип_результата ID_функции (список параметров)
{
код функции
return результат;
}
Результат возвращается из функции в точку вызова при помощи оператора return и преобразуется к типу, указанному в заголовке функции. Если тип функции не указан, то по умолчанию устанавливается тип int, если же функция не возвращает результата, то следует указать пустой тип void. Список параметров состоит из перечня типов и ID параметров, разделенных запятыми.
Из функции можно передать только одно значение, при необходимости возвратить несколько – в списке параметров используют указатели.
Пример реализации функции, определяющей наименьшее из двух целых чисел:
int Min_x_y(int x, int y) {
return (x<y) ? x : y;
}
Вызов функции имеет следующий формат:
ID_функции(список аргументов);
где в качестве аргументов можно использовать константы, переменные, выражения (их значения перед вызовом функции будут компилятором определены). Аргументы списка вызова должны совпадать со списком параметров вызываемой функции по количеству и порядку следования параметров, а типы аргументов при передаче будут преобразованы к указанным в функции типам параметров.
Вызов предыдущей функции может иметь вид: min = Min_x_y(a, b);
Область действия переменных
Область действия переменной – это правила, которые устанавливают, какие данные доступны из текущего места программы, и определяют переменные двух типов: глобальные и локальные.
Глобальные переменные объявляются вне какой-либо функции и могут быть использованы в любом месте программы, но перед их первым использованием они должны быть объявлены и инициализированы. Область действия глобальных переменных – вся программа с момента их объявления. При объявлении глобальные переменные обнуляются.
Область действия локальных переменных – это блоки, где они объявлены. К локальным относятся и формальные параметры в заголовке функций пользователя с бластью действия – кодом функции. При выходе из блока значения локальных переменных теряются.
В языке С каждая переменная принадлежит одному из четырех классов памяти – автоматической (auto), внешней (extern), статической (static) и регистровой (register). Тип памяти указывается перед спецификацией типа, например, register int a; или static double b; По умолчанию устанавливается класс auto и переменные размещаются в стеке.
Доп-1.2. Пример выполнения задания
В целочисленном двухмерном динамическом массиве (матрице) размером NМ найти сумму четных элементов и их количество. Ввод исходных данных (размеры массива и его элементы) и вывод результатов выполнить в основной функции. Решение поставленной задачи оформить в фунции пользователя.
Текст программы может иметь следующий вид:
#include <iostream.h>
#include <conio.h>
int Fun_Sum_Kol(int, int, int**, int*); // Описание прототипа функции
void main()
{
int **a, i, j, n, m, sum, kol;
cout << "\t Input N, M : ";
cin >> n >> m;
a = new int*[n]; // Захват памяти под указатели
for(i=0; i<n;i++)
a[i] = new int[m]; // Захват памяти под элементы
cout <<"\n Input A" << endl;
for(i=0; i<n; i++)
for(j=0; j<m; j++){
cout << "\t a[" << i+1 << "][" << j+1 << "] = ";
cin >> a[i][j];
}
cout <<"\n Matrix A:" << endl;
for(i=0; i<n; i++) {
for(j=0; j<m; j++)
cout << "\t" << a[i][j];
cout << endl;
}
// Обращение к функции с указанием фактических аргументов
sum = Fun_Sum_Kol(n, m, a, &kol);
cout << "\n Kol-vo = " << kol << "\t Summa = " << sum << endl;
delete []a; // Освобождение памяти
cout << "\n\t Delete !" << endl;
cout << " Press any key ... " << endl;
getch();
}
/* Реализация описанной выше функции, в заголовке которой указаны формальные параметры, идентификаторы которых обрабатываются в ее коде */
int Fun_Sum_Kol(int a, int b, int **x, int *k)
{
int i, j, s = 0;
*k = 0;
for(i=0; i<a;i++)
for(j=0; j<b;j++)
if(x[i][j] % 2 ==0){
(*k)++; // Скобки обязательны
s += x[i][j];
}
return s;
}
Обратите внимание на то, что из функции мы должны получить два скалярных результата – посчитанные сумму и количество четных чисел. С помощью оператора return мы возвращаем первое значение (сумму), а второе значение мы передаем в точку вызова с помощью указателя (адреса): при обращении к функции в качестве четвертого параметра передаем адрес &kol, а в функции используем «содержимое, находящееся по указанному адресу» *k ( * – операция разадресации).
При вводе значений элементов массивов в одной строке через пробелы должен получиться следующий результат:
Доп-1.3. Индивидуальные задания
В двухмерном целочисленном массиве (размеры массива N, M и значения его элементов вводить с клавиатуры) найти указанное значение.
Массив в памяти разместить динамически (с использованием операций new и delete), ввод исходных данных и вывод полученных результатов выполнить в основной функции, а решение задачи оформить в виде отдельной функции пользователя. Не использовать глобальных переменных.
1. Найти сумму элементов, расположенных на главной диагонали.
2. Найти произведение элементов, расположенных на главной диагонали.
3. Найти максимальный элемент и поменять его с первым элементом.
4. Найти минимальный элемент и поменять его с первым элементом.
5. Найти максимальный элемент и поменять его с последним элементом.
6. Найти минимальный элемент и поменять его с последним элементом.
7. Найти количество отрицательных и положительных элементов массива.
8. Найти количество 0-й и 1-ц в массиве, а также сумму единиц.
9. Найти число элементов массива, больших T (вводится с клавиатуры) и просуммировать эти элементы.
10. Найти число элементов массива > T и их произведение.
11. Найти число элементов массива < T* и их сумму.
12. Найти число элементов массива < T* и перемножить эти элементы.
13. Найти число элементов массива = T* и сложить эти элементы.
14. Найти число элементов массива = T* и перемножить эти элементы.
15. Найти максимальный элемент среди лежащих ниже главной диагонали.
16. Найти минимальный элемент среди лежащих выше главной диагонали.