Лекция 11-12

 

Массивы

 

Массив – это набор данных одного типа, собранных под одним именем.

Форма объявления массива:

класс_памяти тип список_массивов;

Поле класс_памяти определяет класс памяти массива и является необязательным. Поле тип является обязательным и определяет тип элементов массива. Все элементы массива должны быть одного типа. Элементами могут быть: переменные базового типа, константы перечислимого типа, структуры, объединения, указатели, массивы. Элементами массива не могут быть: переменные типа void, функции. Поле список_массивов является обязательным и содержит одно или несколько объявлений массивов, разделённых запятыми.

Форма объявления массива в поле список_массивов:

имя[размер1][размер2]…[размерN]={список_инициализаторов}

Поле имя является обязательным и содержит идентификатор массива. Далее может следовать любое количество пар квадратных скобок (но не менее одной пары), определяющих мерность (число координат) массива, внутри каждой пары скобок содержится целая константная величина, определяющая размер массива по данной координате. Следующий после этого знак равенства и поле список_инициализаторов являются необязательными и используются для инициализации массива.

Возможна ещё вторая форма объявления массива в поле список_массивов (на примере одномерного массива):

имя[]={список_инициализаторов}

Данная форма разрешается в объявлениях массива в качестве формального параметра функции или в объявлениях с явной инициализацией элементов массива.

Элементы массива имеют свои порядковые номера (индексы), определяющие их положение в массиве. Для обращении к элементу массива в программе используется операция «обращение к элементу массива». Форма записи:

операнд[операнд 1][операнд2]…[операндN]

Операнд – это идентификатор массива, операнд1-операндN – номера элемента массива по соответствующей координате (индексы). Если координат несколько, обращение производится по каждой координате. Под массив выделяется непрерывное место в оперативной памяти, элементы массива располагаются друг за другом в порядке возрастания индексов элементов. Объем памяти, занимаемой массивом, можно вычислить по следующей формуле:

количество_байт=размер_типа*количество_элементов

При обращении к элементам массива индексы массива изменяются от 0 до L-1, где L – размер массива по координате соответствующей мерности массива. Индекс элемента массива – это не его порядковый номер, а смещение относительно начала массива.

 

Пример 1

Расположение в памяти массива из 5 элементов a[5] с указанием их индексов, L=5.

a[0]

a[1]

a[2]

a[3]

a[4]

Первый элемент будет располагаться по индексу 0 (a[0]), соответствующему нулевому смещению от начала массива, второй элемент – по индексу 1 (a[1]), а последний, пятый – по индексу 4 (a[4]).

 

Пример 2

Логическое расположение в памяти элементов двумерного массива a[2][3], L1=2, L2=3.

a[0][0]	a[0][1]	a[0][2]
a[1][0]	a[1][1]	a[1][2]

Так как память ЭВМ имеет линейную структуру адресации, то в памяти элементы массива будут расположены последовательно в следующем порядке.

a[0][0]

a[0][1]

a[0][2]

a[1][0]

a[1][1]

a[1][2]

 

Общее правило расположения в памяти элементов N-мерного массива: сначала в памяти всегда будут расположены элементы с наименьшими значениями n-1 индекса в порядке возрастания значений n-го индекса от 0 до Ln-1, для всех индексов от 1 до N (не путать мерность массива с индексацией, N определяет число координат и всегда больше 0).

В языке C при обращении к элементам массива не проверяется выход индекса за пределы как соответствующей координаты, так и всего массива целиком. Например, к элементу a[1][1] из примера 2 можно обратиться следующим способом: a[0][4]. В данном случае выход второй координаты за установленные пределы компилятором не проверяется, и никаких предупреждений выдано не будет. Тем не менее, следует избегать подобных обращений как возможного источника ошибок, возникающих в процессе выполнения программы. Например, при обращении к элементу a[1][4] будет произведено обращение по адресу, расположенному за границами массива, и результат подобного обращения непредсказуем.

 

Пример 3

int a[2][2];

for(int i=0;i<2;i++)

for(int j=0;j<2;j++)

{

a[i][j]=i*2+j;

printf("%d ",a[i][j]);

}

На экране будет напечатано: 0 1 2 3

 

Массивы символов. Строки.

Массив символов – это массив, элементы которого являются символами. Строка – это одномерный массив символов, заканчивающийся нулевым байтом. Каждый бит нулевого байта равен нулю, для него определена символьная константа ‘’. Если строка содержит L символов, то длина массива должна быть не меньше, чем L+1.

 

Пример 4

char s[10]="Hello";

Содержимое массива s в памяти:

H

e

l

l

o

‘’

un

un

un

un

 

При инициализации массива символов строкой можно использовать вторую форму объявления массива.

 

Пример 5

char s[]="Hello";

В данном случае размер массива будет определяться компилятором автоматически и будет равен шести элементам массива. Содержимое массива s в памяти:

H

e

l

l

o

‘’

 

Для работы со строками в среде Borland C++ 3.1 имеется специальная библиотека функций, описанная в заголовочном файле string.h. Описание этих функций можно посмотреть во встроенной справочной системе.

 

Инициализация массивов.

Инициализация массива используется для присвоения элементам массива начальных значений при объявлении массива. При инициализации после указания размерностей массива ставится знак ‘=’ и указывается список инициализаторов. Список инициализаторов представляет собой последовательность константных выражений или других списков инициализаторов, разделённых запятыми. Список инициализаторов заключается в фигурные скобки. Вложенные списки инициализаторов используются для инициализации многомерных массивов. Список инициализаторов может содержать в себе меньшее число константных выражений, чем размерность массива, в это случае часть элементов массива остаётся неинициализированной. Если же выражений в списке инициализаторов больше, чем число элементов массива, компилятор выдаст сообщение об ошибке.

 

Пример 6

Инициализация одномерных массивов

int a[4]={1,2,3,4},b[4]={5,6};

расположение массива a[4] в памяти

расположение массива b[4] в памяти

un

un

 

Многомерные массивы можно инициализировать двумя путями: как одномерные массивы и как многомерные массивы. В первом случае список инициализаторов представляет собой последовательность константных выражений, значения которых по порядку присваиваются элементам массива в соответствии с расположением этих элементов в памяти. Во втором случае список инициализаторов является вложенным и содержит в себе другие списки инициализаторов для следующих координат массива. Порядок вложенности подобных списков зависит от мерности массива.

 

Пример 7

Инициализация двумерных массивов

int a[3][5]={1,2,3,4,5,6,7,8,9,10,11};

int b[3][5]={{1,2,3},{4,5,6,7,8},{9,10,11}};

расположение массива a[3][5] в памяти

	un	un	un	un

расположение массива b[3][5] в памяти

			un	un
			un	un

 

Символьный массив может быть инициализирован как обычный массив.

 

Пример 8

char s[6]={‘H’,’e’,’l’,’l’,’o’};

В данном случае нулевой байт добавлен не будет. Содержимое массива s в памяти:

H

e

l

l

o

un

 

Автоматически инициализируются только массивы, объявленные на внешнем уровне (вне функций) или на внутреннем с классом памяти static – их элементы зануляются, если не производится явная инициализация.

Явная инициализация недопустима для массивов внешнего уровня с классом памяти extern.

 

Указатели

 

Указатель – это ячейка памяти, предназначенная для хранения адреса объекта некоторого типа (указывающая на данный объект). Адрес объекта – это адрес в памяти компьютера. Форма объявления указателя:

модификатор тип список_указателей;

Поле модификатор определяет класс памяти или модель памяти указателя или особенности преобразования указателя компилятором и является необязательным. Поле тип является обязательным и определяет тип объекта, на который указывает указатель. Возможны следующие типы объектов: базовые (в том числе и void), перечислимые, структуры, объединения, другие указатели. Указатель может хранить и адрес входа в функцию, тогда это указатель на функцию. Указатель на тип void имеет особое значение и может указывать на объект любого типа. Но ни с самим указателем на тип void, ни с объектом, на который он указывает, нельзя выполнять никакие операции, кроме присвоения адресного значения, если тип указателя явно не преобразовать к типу объекта.

Поле список_указателей является обязательным и содержит один или несколько идентификаторов указателей, разделённых запятыми. При объявлении указателя компилятор выделяет место в памяти компьютера, необходимое для размещения адреса объекта данного типа (размер адреса не соответствует размеру объекта).

Форма объявления указателя в поле список_указателей:

*модификатор имя=инициализатор

Поле модификатор является необязательным и содержит модификатор, определяющий класс памяти или модель памяти объекта, на который указывает указатель. Для модели памяти модификатор может принимать значения near, far, huge. Эти ключевые слова используются только в среде программирования Borland C++ 3.1. Подробнее об этом – при рассмотрении моделей памяти и модификаторов языка C.

Символ ‘*’ – признак указателя. При объявлении нескольких указателей символ ‘*’ ставится перед каждым указателем.

Поле инициализатор является необязательным и содержит адрес, которым инициализируется указатель. Рекомендуется использовать в качестве инициализаторов адреса переменных, константы или инициализированные указатели.

 

Пример 9

int *p,a,*f;

В данном примере объявляются указатели p и f и переменная a.

 

С указателями связаны две специальные унарные операции: «взятие адреса» и «обращение по адресу». Форма записи операции «обращение по адресу»: *операнд. Операнд – указатель. Операция производит обращение к объекту, адрес которого хранится в указателе. Форма записи операции «взятие адреса»: &операнд. Операнд – объект. Операция возвращает адрес объекта. Знаки данных операций имеют свои аналоги среди знаков бинарных операций, и в контексте программы они различаются по количеству операндов, участвующих в операции.

 

Пример 10

short int i=10,j=3,k;

short int *p=&i,*s;

s=&j;

*p+=1;

k=i**p+*s;

printf("%d ",k);

s=&k;

*s+=10;

printf("%d ",k);

На экране будет напечатано: 124 134

 

Как и обычные переменные, указатели инициализируются нулевым значением (константа NULL определена в файле stdio.h) при компиляции, только если они объявлены на внешнем уровне или с классом памяти static. Для остальных указателей инициализация не проводится, они указывают на произвольную область памяти, поэтому, прежде, чем использовать указатель, его значение необходимо явно определить. Ни в коем случае нельзя присваивать значение указателю непосредственно.

 

Пример 11

int *p, *j;

p=(int*)0xDE35;

j=NULL;

 

Кроме того, инициализация объекта, на который указывает указатель, неявно не производится никогда, за исключением массивов, объявленных на внешнем уровне с классом памяти static. Значение объекта, на который указывает указатель, также необходимо определять до его использования.

 

Связь указателей и массивов.

В языке C имя массива – это адрес памяти, начиная с которого расположен массив, то есть адрес первого элемента массива со смещением 0.

 

Операции над указателями.

Над указателями можно производить арифметические операции сложения и вычитания указателей с целыми числами, присвоения и сравнения указателей, инкремента и декремента. Кроме того, возможна операция вычитания указателей одного типа. Складывать указатели нельзя.

Важное значение имеет тип указателя. Так как указатель указывает на объект какого-то типа, то и значения указателя могут изменяться исходя из значений размера объекта данного типа. При сложении и вычитании указателей с целым числом значение указателя изменяется на произведение складываемого числа и размера в байтах типа данных указателя.

 

Пример 12

short int m[4]={0,1,2,3};

short int *p=&m[0];

short int *s=&m[2];

printf("%p %p %d %d ",p,s,s-p,*(p+1));

p++;

printf("%p %d",p,*p);

if(p>s)

printf(" p>s");

else

printf(" p<=s");

На экране будет напечатано: FFEE FFF2 2 1 FFF0 1 p<=s

 

В примере 12 при увеличении указателя p на единицу значение указателя увеличивается на 2, так как это указатель типа short int, а данный тип имеет размер 2 байта. Если бы тип указателя был double, значение указателя изменилось бы на 8. При вычитании указателей одного типа результатом также является не сама численная разница значений указателей (адресов), а её отношение к размеру типа указателей в байтах. При выполнении сравнения указателей производится сравнение их численных значений (адресов).

 

Массивы указателей и указатель на указатель.

Указатели могут объединяться в массивы, каждый элемент которого является указателем. Каждому элементу такого массива можно присвоить адрес. Форма объявления:

класс_памяти тип *имя [размер1][размер2]…[размерN] ={список_инициализаторов};

Поля имеют тот же смысл, что и при объявлении массивов переменных.

 

Пример 13

short int i=1,j=2;

short int *m[2]={&i,&j};

printf("%d %d ",*m[0],*m[1]);

m[0]=m[1];

*m[1]+=2;

printf("%d %d ",*m[0],*m[1]);

char *s[]={"Hello, ","World!"};

printf("%s%s",s[0],s[1]);

На экране будет напечатано: 1 2 4 4 Hello, World!

 

Указатель на указатель – это указатель на объект, который в свою очередь также является указателем на объект. Форма объявления:

тип модификатор * модификатор * модификатор имя=инициализатор;

Поля имеют тот же смысл, что и при объявлении указателей.

 

Пример 14

short int i=1,*p=&i,**f=&p;

*p+=1;

**f+=2;

printf("%d %d %d",i,*p,**f);

На экране будет напечатано: 4 4 4

 

Приведенный индекс.

Приведённый индекс – это возможность адресоваться к элементам N-мерного массива с использованием N-P координат, P – произвольно, P<N.

При обращении к элементу массива a[индекс1][индекс2]…[индексN] компилятор вычисляет смещение этого элемента от начала массива по формуле:

cмещение=индекс1*размер2*…*размерN+индекс2*размер3*…размерN+…+индексN-1*размерN+индексN

Зная это, можно при адресации к элементам массива использовать меньшее число координат. Обычно приведённый индекс используется при адресации к элементам многомерного массива через одномерный массив с использованием указателей.

 

Пример 15

Для двумерного массива a[X][Y] к элементу a[i][j] можно адресоваться следующим образом через указатель *b: *(b+i*Y+j), 0<=i<=X-1, 0<=j<=Y-1, b=&a[0][0].

 

Пример 16

Для трёхмерного массива a[X][Y][Z] к элементу a[i][j][k] можно адресоваться следующим образом через указатель *b: *(b+i*Y*Z+j*Z+k), 0<=i<=X-1, 0<=j<=Y-1, 0<=k<=Z-1, b=&a[0][0][0].

 

В примерах 15 и 16 используется указатель b вместо a, так как при попытке обращения a[i*Y*Z+j*Z+k] компилятор выдаст ошибку. Многомерный массив мерности N является массивом массивов мерности N-1 (например, трехмерный массив – это массив двумерных массивов, каждый из которых является массивом одномерных массивов). При этом массив мерности N>1 представляется программой как массив указателей, под него также выделяется память. Поэтому если обратиться к N-мерному массиву, используя меньше, чем N, координат, компилятор выдаст ошибку. Для использования приведённого индекса необходимо использовать указатель b, тип которого совпадает с типом элементов массива.

 

Пример 17

Объявление массива m[2][3] приводит к появлению в памяти трёх объектов: указатель на указатель m, который указывает на безымянный массив указателей длиной в два элемента, и безымянный массив из 6 чисел. Каждый указатель безымянного массива указателей указывает на позицию, соответствующую началу второй координаты массива при изменении значения первой координаты.

m[2][3]

<noname>[0]		m[0][0]	m[0][1]	m[0][2]
<noname>[1]	m[1][0]	m[1][1]	m[1][2]

 

Пример 18

int m[2][1][3],*p=**m;

for(int i=0;i<2;i++)

for(int j=0;j<1;j++)

for(int k=0;k<3;k++)

{

m[i][j][k]=i*1*3+j*3+k;

printf("%d ",m[i][j][k]);

(*(p+i*1*3+j*3+k))++;

}

for(int t=0;t<6;t++)

printf("%d ",*(p+t));

На экране будет напечатано: 0 1 2 3 4 5 1 2 3 4 5 6