Структуры и алгоритмы компьютерной обработки данных
10. Лекция: Массивы: одномерные массивы: версия для печати и PDA В лекции рассматриваются понятие и виды массивов в языках программирования, определение, объявление, инициализация, способы генерации и вывод одномерных массивов, расположение в памяти элементов массивов, связь между указателями и массивами.
Цель лекции: изучить понятия, особенности внутреннего представления, способов генерации и вывода одномерных массивов, научиться выполнять объявление, инициализацию, генерацию и вывод массивов при решении задач на языке C++.
В программировании часто возникают задачи, связанные с обработкой больших объемов данных. Для того, чтобы весь этот объем данных хранить внутри программы, применяют массивы – простейшую разновидность структурированных типов данных.
Массив – именованная последовательность областей памяти, хранящих однотипные элементы (рис. 10.1). Каждая такая область памяти называется элементом массива. Массивы обладают размерностью (большей или равной единице), которой задается число элементов, содержащихся в них, а также измерением, что предполагает возможность описания в программе одно- и многомерных массивов. Количество элементов в массиве называется его размером.
Рис. 10.1. Схематическое представление массивов
Простейшим аналогом двумерного массива может быть таблица, а трехмерного – несколько таблиц одинакового размера. Математические объекты типа вектор и матрица – примеры аналогов (соответственно одно- и двумерных) массивов.
Тип элемента массива может быть одним из базовых (скалярных), типом другого массива, типом указателя, типом структуры или объединения.
Элементы массива в С++ нумеруется, начиная с нуля. У одномерных массивов после его имени указывается один индекс (порядковый номер), заключенный в прямоугольные скобки [ ], а у многомерных – несколько, каждый из которых заключается в [ ]. Последнее означает, что многомерный массив создается путем определения массива из элементов типа массив.
Все элементы массива имеют одно имя – имя массива и отличаются индексами – порядковыми номерами в массиве. В определении массива можно задать его размерность по каждому измерению. Допустимо явное задание массива либо с помощью указателя (объекта, хранящего адрес начала области набора значений). Резервирование памяти для массива выполняется на этапе компиляции программы.
При объявлении массива компилятор выделяет для него последовательность ячеек памяти, для обращения к которым в программе применяется одно и то же имя. В то же время массив позволяет получить прямой доступ к своим отдельным элементам.
Объявление одномерных массивов
Синтаксис определения массива без дополнительных спецификаторов и модификаторов имеет два формата:
Тип ИмяМассива[ВыражениеТипаКонстанты];
или
Тип ИмяМассива[];
ИмяМассива – идентификатор массива.
Тип – тип элементов объявляемого массива. Элементами массива не могут быть функции, файлы и элементы типа void.
ВыражениеТипаКонстанты – задает количество элементов (размерность) массива. Выражение константного типа вычисляется на этапе компиляции. Данное константное выражение может быть опущено в случаях если:
при объявлении массив инициализируется;
массив объявлен как формальный параметр функции;
массив объявлен как ссылка на массив, явно определенный в другом файле.
Например:
1. int a[100]; //массив из 100 элементов целого типа
2. double d[14]; // массив из 14 элементов типа double
3. char s[]="Программирование"; //символьный массив
4. int t=5, k=8;
5. float wer[2*t+k];
6. //массив из 2*t+k элементов вещественного типа
7. int sample[853];
8. /*массив из элементов sample[0], sample[1],
9. sample[2],...,sample[852] типа int*/
равносильно объявлению
const int N_max=853;
int sample[N_max];
равносильно объявлению
#define N_max 853
...
int sample[N_max];
В языке С++ не производится проверки границ массивов: таким образом, исполнение кода не остановится при выходе за границы массива. Если переполнение массива происходит во время выполнения оператора присваивания, то лишние значения могут присвоиться другим переменным или включиться в текст программы. С другой стороны, можно объявить массив размером N и указать индекс элемента, выходящий за пределы N, что не приведет к появлению сообщений об ошибке, как на шаге компиляции, так и на шаге выполнения, даже если это послужит причиной аварийного завершения программы.
Инициализация одномерных массивов
Термином "инициализация" обозначают возможность задать начальные значения элементов массива без программирования соответствующих действий. Например, не прибегая к программным средствам типа присваивания значений в цикле или считывания данных из внешнего источника (файл, клавиатура, блок данных).
В С++ одновременно с объявлением массива можно задать начальные значения всех элементов массива или только нескольких первых его компонент.
Например:
float t[5]={1.0, 4.3, 8.1, 3.0, 6.74};
char b[7]={'П','р','и','в','е','т'};
/*в данных примерах длину массива компилятор вычисляет по
количеству начальных значений, перечисленных в фигурных
скобках*/
int d[10]={1, 2, 3};
char a[10]="Привет";
/*в данных примерах определяется значение только заданных
переменных d[0],d[1],d[2] и a[0],a[1],...,d[9], остальные
элементы не инициализируются*/
Если в определении массива явно указан его размер, то количество начальных значений не может быть больше количества элементов в массиве.
Пусть необходимо проинициализировать массивы для создания таблицы сообщений об ошибках:
char e1[12] = "read error\n";
char e2[13] = "write error\n";
char e3[18] = "cannot open file\n";
Компилятор С++ сам сформирует нужное значение по количеству инициализирующих данных. В нашем случае под массив e2 будет отведено 13 байтов, включая последний байт с нулевым кодом, завершающий каждую строку. Оператор
printf("%s имеет длину, равную %d\n",e2,sizeof (e2));
выведет на экран
write error
имеет длину, равную 13
Метод инициализации безразмерных массивов не только менее трудоемок, но и позволяет заменить любое сообщение, без перерасчета размера соответствующего массива.
Обращение к элементам одномерного массива
Адресация элементов массива осуществляется с помощью индексированного имени. Синтаксис обращения к элементу массива:
ИмяМассива[ВыражениеТипаКонстанты];
или
ИмяМассива[ЗначениеИндекса];
Обращаться к элементам массива можно также посредством механизма указателей.
Таким образом, чтобы обратиться к элементу массива, надо указать имя массива и номер элемента в массиве (индекс).
Например:
a[0] – индекс задается как константа,
d[55] – индекс задается как константа,
s[i] – индекс задается как переменная,
w[4*p] – индекс задается как выражение.
Следует помнить, что компилятор в процессе генерации кода задет начальный адрес массива, который в дальнейшем не может быть переопределен. Начальный адрес массива – это адрес первого элемента массива. Вообще в программе начальным адресом массива считается ИмяМассива либо &ИмяМассива[0]. Имя массива считается константой-указателем, ссылающимся на адрес начала массива.
Определение размера памяти для одномерных массивов
Массив занимает непрерывную область памяти. Для одномерного массива полный объем занимаемой памяти в байтах вычисляется по формуле:
Байты = sizeof (тип) * размер массива
Массив представляет собой набор однотипных данных, расположенных в памяти таким образом, чтобы по индексам элементов можно было легко вычислить адрес соответствующего значения. Например, пусть одномерный массив A состоит из элементов, расположенных в памяти подряд по возрастанию индексов, и каждый элемент занимает по k байт. Тогда адрес i -того элемента вычисляется по формуле:
адрес(A[i]) = адрес(A[0]) + i*k
Пример 1. Определение размера памяти одномерного массива.
#include "stdafx.h"
#include <iostream>
using namespace std;
#define v 4
#define p 3
int _tmain(int argc, _TCHAR* argv[]){
const int q=4, r=1;
int i_mas[10];
int k=sizeof(i_mas);
cout << "i_mas[10] занимает " << k << " байт\n";
float f_mas[7]={2.0,4.5,8.3,7.0,1.0};
int t=sizeof(f_mas);
cout << "f_mas[7]={2.0,4.5,8.3,7.0,1.0} занимает "<< t <<"байт\n";
double d_mas[2*q-r];
int w=sizeof(d_mas);
cout << "d_mas[2*q-r] занимает " << w << " байт\n";
double d1_mas[2*v/p];
int w1=sizeof(d1_mas);
cout << "d1_mas[2*v/p] занимает " << w1 << " байт\n";
char c_mas[]="Программирование";
int s=sizeof(c_mas);
cout << "c_mas[]=\"Программирование\"занимает"<< s <<"байт\n";
system("pause");
return 0;
}
Результат выполнения программы:
i_mas[10] занимает 40 байт – 4 байта (тип int ) * 10 (количество элементов массива)
f_mas[7] = {2.0,4.5,8.3,7.0,1.0} занимает 28 байт – 4 байта (тип float ) * 7 (объявленное количество элементов массива)
d_mas[2*q-r] занимает 56 байт – 8 байт (тип double ) * 7 (вычисленное через формулу количество элементов массива)
d1_mas[2*v/p] занимает 16 байт – 8 байт (тип double ) * 2 (вычисленное через формулу количество элементов массива)
c_mas[]="Программирование" занимает 17 байт – 1 байт (тип char ) * 17 (16 знаков + нулевой байт '\0' )
Указатели и одномерные массивы
В языке С++ между указателями и массивами существует тесная связь. Например, когда объявлен массив int array[25], этим определяет не только выделение памяти для двадцати пяти элементов массива, но и для указателя с именем array. В языке С++ имя массива без индексов трактуется как адрес начального элемента. То есть имя массива является указателем на массив. Таким образом, доступ к элементам массива осуществляется через указатель с именем array.
Поскольку имя массива является указателем, допустимо, например, такое присваивание:
int arrаy[25];
int *ptr;
ptr=array;
Здесь указатель ptr устанавливается на адрес первого элемента массива, причем присваивание ptr = arrаy можно записать в эквивалентной форме ptr=&arrаy[0].
Адрес каждого элемента массива можно получить, используя одно из трех выражений:
Адрес в памяти
...
Индекс
...
Значения
...
Адрес i - го элемента
array
&array[0]
ptr
array +1
&array[1]
ptr + 1
array +2
&array[2]
ptr + 2
array +3
&array[3]
ptr + 3
array +4
&array[4]
ptr + 4
...
array +24
&array[24]
ptr + 24
А обращение к пятому элементу массива можно записать как:
array[4], *( array + 4), *(рtr + 4).
Эти операторы вернут пятый элемент массива.
Таким образом, С++ дает два способа обращения к элементу массива:
с помощью индексированного имени;
посредством арифметики с указателями.
Версия с индексированным именем выполняется медленнее, так как в языке С++ на индексирование массива уходит больше времени, чем на выполнение оператора *. Поэтому использование указателей для доступа к элементам массива в языке С++ применяется довольно часто.
Пример 2.
#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[]){
int array[10];
int *p;
p=&array[0];
/*эквивалентные операции присваивания*/
*array=2; printf("%d\n", array[0]);
array[0]=2; printf("%d\n", array[0]);
*(array+0)=2; printf("%d\n", array[0]);
*p=2; printf("%d\n", array[0]);
p[0]=2; printf("%d\n", array[0]);
*(p+0)=2; printf("%d\n", array[0]);
system("pause");
return 0;
}
В результате выполнения любой из эквивалентных операций присваивания в данном примере начальному элементу массива присваивается значение 2, но быстрее всего компьютер выполнит операции *array=2 и *p=2, так как в них не требуется выполнять операции сложения.
Рис. 10.1. Схематическое представление массивов
Простейшим аналогом двумерного массива может быть таблица, а трехмерного – несколько таблиц одинакового размера. Математические объекты типа вектор и матрица – примеры аналогов (соответственно одно- и двумерных) массивов.
Тип элемента массива может быть одним из базовых (скалярных), типом другого массива, типом указателя, типом структуры или объединения.
Элементы массива в С++ нумеруется, начиная с нуля. У одномерных массивов после его имени указывается один индекс (порядковый номер), заключенный в прямоугольные скобки [ ], а у многомерных – несколько, каждый из которых заключается в [ ]. Последнее означает, что многомерный массив создается путем определения массива из элементов типа массив.
Все элементы массива имеют одно имя – имя массива и отличаются индексами – порядковыми номерами в массиве. В определении массива можно задать его размерность по каждому измерению. Допустимо явное задание массива либо с помощью указателя (объекта, хранящего адрес начала области набора значений). Резервирование памяти для массива выполняется на этапе компиляции программы.
При объявлении массива компилятор выделяет для него последовательность ячеек памяти, для обращения к которым в программе применяется одно и то же имя. В то же время массив позволяет получить прямой доступ к своим отдельным элементам.
Объявление одномерных массивов
Синтаксис определения массива без дополнительных спецификаторов и модификаторов имеет два формата:
Тип ИмяМассива[ВыражениеТипаКонстанты];
или
Тип ИмяМассива[];
ИмяМассива – идентификатор массива.
Тип – тип элементов объявляемого массива. Элементами массива не могут быть функции, файлы и элементы типа void.
ВыражениеТипаКонстанты – задает количество элементов (размерность) массива. Выражение константного типа вычисляется на этапе компиляции. Данное константное выражение может быть опущено в случаях если: