 |
Задачи для решения на тему «вложенные циклы (вычисление суммы ряда)»
|
|
|
|
Вычислить и вывести на экран в виде таблицы значения функции, заданной с помощью ряда Тейлора, на интервале от хнач до хкон с шагом dx с точностью ε. Таблицу снабдить заголовком и шапкой. Каждая строка таблицы должна содержать значение аргумента, значение функции и количество просуммированных членов ряда.
Вариант 1
Вариант 2
Вариант 3
Вариант 4
Вариант 5
Вариант 6
Вариант 7
Вариант 8
Вариант 9
Вариант 10
Вариант 11
Вариант 12
Вариант 13
Вариант 14
Вариант 15
Вариант 16
Вариант 17
Вариант 18
Вариант 19
Вариант 20
7 Указатели и массивы
7.1 Указатели
Когда компилятор обрабатывает оператор определения переменной, например, int i=10;, он выделяет память в соответствии с типом (int) и инициализирует ее указанным значением (10). Все обращения в программе к переменной по ее имени (i) заменяются компилятором на адрес области памяти, в которой хранится значение переменной. Программист может определить собственные переменные для хранения адресов областей памяти. Такие переменные называются указателями.
Итак, указатели предназначены для хранения адресов областей памяти. В С++ различают три вида указателей - указатели на объект, на функцию и на void, отличающиеся свойствами и набором допустимых операций. Указатель не является самостоятельным типом, он всегда связан с каким-либо другим конкретным типом.
Указатель на функцию содержит адрес в сегменте кода, по которому располагается исполняемый код функции, то есть адрес, по которому передается управление при вызове функции. Указатели на функции используются для косвенного вызова функции (не через ее имя, а через обращение к переменной, хранящей ее адрес), а также для передачи имени функции в другую функцию в качестве параметра. Указатель функции имеет тип «указатель функции, возвращающей значение заданного типа и имеющей аргументы заданного типа»:
|
|
|
тип (*имя) (список_типов_аргументов);
Например, объявление:
int (*fun) (double, double);
задает указатель с именем fun на функцию, возвращающую значение типа int и имеющую два аргумента типа double.
Указатель на объект содержит адрес области памяти, в которой хранятся данные определенного типа (основного или составного). Простейшее объявление указателя на объект (в дальнейшем называемого просто указателем) имеет вид: тип *имя;, где тип может быть любым, кроме ссылки и битового поля, причем тип может быть к этому моменту только объявлен, но еще не определен (следовательно, в структуре, например, может присутствовать указатель на структуру того же типа).
Звездочка относится непосредственно к имени, поэтому для того, чтобы объявить несколько указателей, требуется ставить ее перед именем каждого из них. Например, в операторе
int *а, b, *с;
описываются два указателя на целое с именами а и с, а также целая переменная b.
Размер указателя зависит от модели памяти. Можно определить указатель на указатель и т. д.
Указатель на void применяется в тех случаях, когда конкретный тип объекта, адрес которого требуется хранить, не определен (например, если в одной и той же переменной в разные моменты времени требуется хранить адреса объектов различных типов).
Указателю на void можно присвоить значение указателя любого типа, а также сравнивать его с любыми указателями, но перед выполнением каких-либо действий с областью памяти, на которую он ссылается, требуется преобразовать его к конкретному типу явным образом.
Указатель может быть константой или переменной, а также указывать на константу или переменную. Рассмотрим примеры:
|
|
|
int i; // целая переменная
const int ci = 1; // целая константа
int * pi; // указатель на целую переменную
const int * pci; // указатель на целую константу
int * const ср = &i; // указатель-константа на целую переменную
const int * const срс = &ci; // указатель-константа на целую константу
Как видно из примеров, модификатор const, находящийся между именем указателя и звездочкой, относится к самому указателю и запрещает его изменение, a const слева от звездочки задает постоянство значения, на которое он указывает. Для инициализации указателей использована операция получения адреса &.
Величины типа указатель подчиняются общим правилам определения области действия, видимости и времени жизни.
Инициализация указателей
Указатели чаще всего используют при работе с динамической памятью, называемой некоторыми эстетами кучей (перевод с английского языка слова heap). Это свободная память, в которой можно во время выполнения программы выделять место в соответствии с потребностями. Доступ к выделенным участкам динамической памяти, называемым динамическими переменными, производится только через указатели. Время жизни динамических переменных - от точки создания до конца программы или до явного освобождения памяти. В С++ используется два способа работы с динамической памятью. Первый использует семейство функций malloc и достался в наследство от С, второй использует операции new и delete.
При определении указателя надо стремиться выполнить его инициализацию, то есть присвоение начального значения. Непреднамеренное использование неинициализированных указателей - распространенный источник ошибок в программах. Инициализатор записывается после имени указателя либо в круглых скобках, либо после знака равенства.
Существуют следующие способы инициализации указателя:
1 Присваивание указателю адреса существующего объекта:
- с помощью операции получения адреса:
int а = 5; // целая переменная
int * р = &а; //в указатель записывается адрес а
int * р (&а); //то же самое другим способом
- с помощью значения другого инициализированного указателя: int * r = р;
- с помощью имени массива или функции, которые трактуются как адрес:
int b[10]; // массив
int * t = b; // присваивание адреса начала массива
void f(int а){ /*... */ } // определение функции
|
|
|
void (*pf)(int); // указатель на функцию
pf = f; // присваивание адреса функции
2 Присваивание указателю адреса области памяти в явном виде:
char* vp = (char *)0хВ8000000;
Здесь 0хВ8000000 - шестнадцатеричная константа, (char *) - операция приведения типа: константа преобразуется к типу «указатель на char».
3 Присваивание пустого значения:
int* rulez = 0;
4 Выделение участка динамической памяти и присваивание ее адреса указателю:
- с помощью операции new:
int * n = new int; // 1
int * m = new int (10); // 2
int * q = new int [10]; // 3
- с помощью функции mallос ( для того чтобы использовать malloc, требуется подключить к программе заголовочный файл <malloc.h>):
int * u = (int *)malloc(sizeof(int)); // 4
В операторе 1 операция new выполняет выделение достаточного для размещения величины типа int участка динамической памяти и записывает адрес начала этого участка в переменную n. Память под саму переменную n (размера, достаточного для размещения указателя) выделяется на этапе компиляции.
В операторе 2, кроме описанных выше действий, производится инициализация выделенной динамической памяти значением 10.
В операторе 3 операция new выполняет выделение памяти под 10 величин типа int (массива из 10 элементов) и записывает адрес начала этого участка в переменную q, которая может трактоваться как имя массива. Через имя можно обращаться к любому элементу массива.
Если память выделить не удалось, по стандарту должно порождаться исключение bad_alloc. Старые версии компиляторов могут возвращать 0.
В операторе 4 делается то же самое, что и в операторе 1, но с помощью функции выделения памяти malloc, унаследованной из библиотеки С. В функцию передается один параметр - количество выделяемой памяти в байтах. Конструкция (int*) используется для приведения типа указателя, возвращаемого функцией, к требуемому типу. Если память выделить не удалось, функция возвращает 0.
Операцию new использовать предпочтительнее, чем функцию malloc, особенно при работе с объектами.
Освобождение памяти, выделенной с помощью операции new, должно выполняться с помощью delete, а памяти, выделенной функцией malloc, – посредством функции free. При этом переменная-указатель сохраняется и может инициализироваться повторно. Приведенные выше динамические переменные уничтожаются следующим образом:
|
|
|
delete n; delete m; delete [] q; free (u);
Если память выделялась с помощью new[], для освобождения памяти необходимо применять delete[]. Размерность массива при этом не указывается. Если квадратных скобок нет, то никакого сообщения об ошибке не выдается, но помечен как свободный будет только первый элемент массива, а остальные окажутся недоступны для дальнейших операций. Такие ячейки памяти называются мусором.
С помощью комбинаций звездочек, круглых и квадратных скобок можно описывать составные типы и указатели на составные типы, например, в операторе int *(*р[10])(); объявляется массив из 10 указателей на функции без параметров, возвращающих указатели на int.
По умолчанию квадратные и круглые скобки имеют одинаковый приоритет, больший, чем звездочка, и рассматриваются слева направо. Для изменения порядка рассмотрения используются круглые скобки.
При интерпретации сложных описаний необходимо придерживаться правила «изнутри наружу»:
- если справа от имени имеются квадратные скобки, это массив, если скобки круглые - это функция;
- если слева есть звездочка, это указатель на проинтерпретированную ранее конструкцию;
- если справа встречается закрывающая круглая скобка, необходимо применить приведенные выше правила внутри скобок, а затем переходить наружу;
- в последнюю очередь интерпретируется спецификатор типа.
Для приведенного выше описания порядок интерпретации указан цифрами:
int *(*р[10])():
5 4 2 1 3 // порядок интерпретации описания
Операции с указателями
С указателями можно выполнять следующие операции: разадресация, или косвенное обращение к объекту (*), присваивание, сложение с константой, вычитание, инкремент (++), декремент (--), сравнение, приведение типов. При работе с указателями часто используется операция получения адреса (&).
Операция разадресации, или разыменования, предназначена для доступа к величине, адрес которой хранится в указателе. Эту операцию можно использовать как для получения, так и для изменения значения величины (если она не объявлена как константа):
char а; // переменная типа char
char * р = new char; /* выделение памяти под указатель и под динамическую переменную типа char */
*р = 'Ю'; а = *р; // присваивание значения обеим переменным
Арифметические операции с указателями (сложение с константой, вычитание, инкремент и декремент) автоматически учитывают размер типа величин, адресуемых указателями. Эти операции применимы только к указателям одного типа и имеют смысл в основном при работе со структурами данных, последовательно размещенными в памяти, например, с массивами.
|
|
|
Инкремент перемещает указатель к следующему элементу массива, декремент - к предыдущему. Фактически значение указателя изменяется на величину sizeof (тип). Если указатель на определенный тип увеличивается или уменьшается на константу, его значение изменяется на величину этой константы, умноженную на размер объекта данного типа, например:
short * р = new short [5];
р++; // значение р увеличивается на 2
long * q = new long [5];
q++: // значение q увеличивается на 4
Разность двух указателей - это разность их значений, деленная на размер типа в байтах (в применении к массивам разность указателей, например, на третий и шестой элементы равна 3).Суммирование двух указателей не допускается.
При записи выражений с указателями следует обращать внимание на приоритеты операций. В качестве примера рассмотрим последовательность действий, заданную в операторе
*р++ = 10;
Операции разадресации и инкремента имеют одинаковый приоритет и выполняются справа налево, но, поскольку инкремент постфиксный, он выполняется после выполнения операции присваивания. Таким образом, сначала по адресу, записанному в указателе р, будет записано значение 10, а затем указатель будет увеличен на количество байт, соответствующее его типу. То же самое можно записать подробнее:
*р = 10; р++;
Выражение (*р)++, напротив, инкрементирует значение, на которое ссылается указатель.
Унарная операция получения адреса & применима к величинам, имеющим имя и размещенным в оперативной памяти. Таким образом, нельзя получить адрес скалярного выражения, неименованной константы или регистровой переменной. Примеры операции приводились выше.
7.2 Ссылки
Ссылка представляет собой синоним имени, указанного при инициализации ссылки. Ссылку можно рассматривать как указатель, который всегда разыменовывается. Формат объявления ссылки:
тип & имя;
где тип - это тип величины, на которую указывает ссылка;
& - оператор ссылки, означающий, что следующее за ним имя является именем переменной ссылочного типа, например:
int kol;
int & pal = kol; // ссылка pal - альтернативное имя для kol
const char & CR = '\n'; // ссылка на константу
Ссылки применяются чаще всего в качестве параметров функций и типов возвращаемых функциями значений. Ссылки позволяют использовать в функциях переменные, передаваемые по адресу, без операции разадресации, что улучшает читаемость программы.
Ссылка, в отличие от указателя, не занимает дополнительного пространства в памяти и является просто другим именем величины. Операция над ссылкой приводит к изменению величины, на которую она ссылается.
7.3 Массивы
При использовании простых переменных каждой области памяти для хранения данных соответствует свое имя. Если с группой величин одинакового типа требуется выполнять однообразные действия, им дают одно имя, а различают по порядковому номеру. Это позволяет компактно записывать множество операций с помощью циклов. Конечная именованная последовательность однотипных величин называется массивом. Описание массива в программе отличается от описания простой переменной наличием после имени квадратных скобок, в которых задается количество элементов массива (размерность):
float а [10]; // описание массива из 10 вещественных чисел
Элементы массива нумеруются с нуля. Инициализирующие значения для массивов записываются в фигурных скобках. Значения элементам присваиваются по порядку. Если элементов в массиве больше, чем инициализаторов, элементы, для которых значения не указаны, обнуляются:
int b[5] = {3, 2, 1}; // b[0]=3, b[1]=2, b[2]=1, b[3]=0, b[4]=0
Размерность массива вместе с типом его элементов определяет объем памяти, необходимый для размещения массива, которое выполняется на этапе компиляции, поэтому размерность может быть задана только целой положительной константой или константным выражением. Если при описании массива не указана размерность, должен присутствовать инициализатор, в этом случае компилятор выделит память по количеству инициализирующих значений.
Для доступа к элементу массива после его имени указывается номер элемента (индекс) в квадратных скобках. В следующем примере подсчитывается сумма элементов массива.
#include <iostream.h>
int main(){
const int n = 10;
int i, sum;
int marks[n] = {3, 4, 5, 4, 4};
for (i = 0, sum = 0; i<n; i++) sum += marks[i];
cout «"Сумма элементов: " «sum;
return 0;
}
Пример. Сортировка целочисленного массива методом выбора. Алгоритм состоит в том, что выбирается наименьший элемент массива и меняется местами с первым элементом, затем рассматриваются элементы, начиная со второго, и наименьший из них меняется местами со вторым элементом, и так далее n-1 раз (при последнем проходе цикла при необходимости меняются местами предпоследний и последний элементы массива).
#include <iostream.h>
int main(){
const int n = 20; // количество элементов массива
int b[n]; // описание массива
int i;
for (i = 0; i<n; i++) cin» b[i]; // ввод массива
for (i =0; i<n-1; i++){ // n-1 раз ищем наименьший элемент
// принимаем за наименьший первый из рассматриваемых элементов:
int imin = i;
// поиск номера минимального элемента из неупорядоченных:
for (int j = i + 1; j<n; j++)
// если нашли меньший элемент, запоминаем его номер:
if (b[j] < b[imin]) imin = j;
int a = b[i]; // обмен элементов
b[i] = b[imin]; // с номерами
b[imin] = a; // i и imin
}
// вывод упорядоченного массива:
for (i = 0; i<n; i++) cout «b[i] «' ';
return 0;
}
Идентификатор массива является константным указателем на его нулевой элемент. Например, для массива из предыдущего листинга имя b - это то же самое, что &b[0], а к i-му элементу массива можно обратиться, используя выражение *(b+i). Можно описать указатель, присвоить ему адрес начала массива и работать с массивом через указатель. Следующий фрагмент программы копирует все элементы массива a в массив b:
int а[100], b[100];
int *ра = а; // или int *р = &а[0]:
int *pb = b;
for(int i = 0; i<100; i++)
*pb++ = *pa++; // или pb[i] = pa[i];
Динамические массивы создают с помощью операции new, при этом необходимо указать тип и размерность, например:
int n = 100;
float *р = new float [n];
В этой строке создается переменная-указатель на float, в динамической памяти отводится непрерывная область, достаточная для размещения 100 элементов вещественного типа, и адрес ее начала записывается в указатель р. Динамические массивы нельзя при создании инициализировать, и они не обнуляются.
Преимущество динамических массивов состоит в том, что размерность может быть переменной, то есть объем памяти, выделяемой под массив, определяется на этапе выполнения программы. Доступ к элементам динамического массива осуществляется точно так же, как к статическим, например, к элементу номер 5 приведенного выше массива можно обратиться как р[5] или *(р+5).
Память, зарезервированная под динамический массив с помощью new [], должна освобождаться оператором delete []. Размерность массива в операции delete не указывается, но квадратные скобки обязательны.
Многомерные массивы задаются указанием каждого измерения в квадратных скобках, например, оператор
int matr [6][8];
задает описание двумерного массива из 6 строк и 8 столбцов. В памяти такой массив располагается в последовательных ячейках построчно. Многомерные массивы размещаются так, что при переходе к следующему элементу быстрее всего изменяется последний индекс. Для доступа к элементу многомерного массива указываются все его индексы, например, matr[i][j], или более экзотическим способом: *(matr[i]+j) или *(*(matr+i)+j). Это возможно, поскольку matr[i] является адресом начала i-й строки массива.
При инициализации многомерного массива он представляется либо как массив из массивов, при этом каждый массив заключается в свои фигурные скобки (в этом случае левую размерность при описании можно не указывать), либо задается общий список элементов в том порядке, в котором элементы располагаются в памяти:
int mass2 [][2] - { {1, 1}, {0, 2}, {1, 0} };
int mass2 [3][2] = {1, 1, 0, 2, 1, 0};
Пример. Программа определяет в целочисленной матрице номер строки, которая содержит наибольшее количество элементов, равных нулю.
#include <stdio.h>
int main(){
const int nstr = 4, nstb = 5; // размерности массива
int b[nstr][nstb]; // описание массива
int i, j;
for (i = 0; i<nstr; i++) // ввод массива
for (j = 0; j<nstb; j++) scanf("%d", &b[i][j]);
int istr = -1, MaxKol = 0;
for (i = 0; i<nstr; i++){ // просмотр массива по строкам
int Kol = 0:
for (j = 0; j<nstb; j++) if (b[i][j] = 0)Kol++;
if (Kol > MaxKol){istr = i; MaxKol = Kol;}
}
printf("Исходный массив:\n");
for (i = 0; i<nstr; i++){
for (j = 0; j<nstb; j++)
printf("%d", b[i][j]);
printf("\n");}
if (istr == -1) printf("Нулевых элементов нет");
else printf("Номер строки: %d", istr);
return 0;
}
Номер искомой строки хранится в переменной istr, количество нулевых элементов в текущей (i-й) строке - в переменной Kol, максимальное количество нулевых элементов - в переменной MaxKol. Массив просматривается по строкам, в каждой из них подсчитывается количество нулевых элементов (обратите внимание, что переменная Kol обнуляется перед просмотром каждой строки). Наибольшее количество и номер соответствующей строки запоминаются.
Для создания динамического многомерного массива необходимо указать в операции new все его размерности (самая левая размерность может быть переменной), например:
int nstr = 5;
int ** m = (int **) new int [nstr][10];
Более универсальный и безопасный способ выделения памяти под двумерный массив, когда обе его размерности задаются на этапе выполнения программы, приведен ниже:
int nstr, nstb;
cout «" Введите количество строк и столбцов:";
cin» nstr» nstb;
int **a = new int *[nstr]; // 1
for(int i = 0; i<nstr; i++) // 2
a[i] = new int [nstb]; // 3
В операторе 1 объявляется переменная типа «указатель на указатель на int» и выделяется память под массив указателей на строки массива (количество строк - nstr). В операторе 2 организуется цикл для выделения памяти под каждую строку массива. В операторе 3 каждому элементу массива указателей на строки присваивается адрес начала участка памяти, выделенного под строку двумерного массива. Каждая строка состоит из nstb элементов типа int (рисунок 7.1).
Освобождение памяти из-под массива с любым количеством измерений выполняется с помощью операции delete []. Указатель на константу удалить нельзя.
Рисунок 7.1 - Выделение памяти под двумерный массив
Для правильной интерпретации объявлений полезно запомнить мнемоническое правило: «суффикс привязан крепче префикса». Если при описании переменной используются одновременно префикс * (указатель) и суффикс [] (массив), то переменная интерпретируется как массив указателей, а не указатель на массив: int * р[10]; - массив из 10 указателей на int.
|
|
|
