6 Указатели и массивы
6.1 Указатели
Указатель – это целая беззнаковая переменная, содержащая адрес памяти какого-либо объекта программы. Указатель может содержать адрес переменной, массива, структуры, другого указателя, функции. Синтаксис определения (создания) указателя следующий:
тип *имя_указателя;
где тип – это тип переменной, адрес которой может содержать указатель.
int *ptri; // указательна переменную типа int
float *ptrf; // указатель на переменную типа float
Каждое из этих определений выделяет в памяти ячейки для переменной типа указатель. Размер памяти, занимаемый указателем, можно определить: sizeof(имя_указателя). Например,
int sz1=sizeof(ptri); int sz2=sizeof(ptrf);
В общем случае под указатель выделяется 4 байта для модели памяти large (2 байта – сегмент и 2 байта – смещение в сегменте).
Для использования указателей в программе им необходимо присвоить конкретные значения с помощью операции присвоения, либо путем инициализации.
Указатель может принимать следующие значения:
· адрес переменной, который можно получить с помощью операции &;
· указатель, уже имеющий значение;
· явно заданный адрес памяти.
Указатели можно инициализировать:
тип *имя_указателя=инициализирующее_выражение;
Пример.
int a=11;
int *ptra;
ptra=&a;// присвоили адрес переменной a
int *ptrb=ptra; // проинициализировали зн-ем указателя ptra
int*vb=(int*)0xB8000000; // явныйначальный адрес видеопамяти
printf("a=%d &a=%p ptra=%p &ptra=%p\n",a,&a,ptra,&ptra);
printf("ptrb=%p &ptrb=%p ptrc=%p &ptrc=%p\n",ptrb,&ptrb);
printf("vb=%p &vb=%p",vb,&vb);
В результате работы этого фрагмента получим:
a=11 &a=8ADAFFFC ptra=8ADAFFFC &ptra=8ADAFFF8
ptrb=8ADAFFFC &ptrb=8ADAFFF4
vb=B8000000 &vb=8ABFFFF0
т.е. адрес переменной a и значения указателей ptra, ptrb равны, и указатели, как любые другие переменные, имеют собственные адреса.
Для обращения (доступа) к объекту, адрес которого содержит указатель, используется операция разыменования *.
Пример.
float f=1.3,*pf=&f;
int a=5,*pa=&a;
cout<<"pf="<<pf; // pf=0xF9B00FFC
cout<<" *pf="<<*pf; // *pf=1.3
*pf=2.7; // изменили содержимое по адресу &f
cout<<" f="<<f; // f=2.7
printf("pa=%p *pa=%d",pa,*pa);// pa=F9B0:0FFA *pa=5
*pa=7; // изменили содержимое по адресу &a
printf("a=%d\n",a);// a=7
Операция разыменования показывает содержимое той ячейки памяти, адрес которой находится в указателе. Содержимое этой ячейки может быть любого типа. Для того чтобы операции с содержимым были возможны, необходимо знать тип этого содержимого, т.е. тип указателя.
Значение указателя увеличивается (при прибавлении целого числа N) или уменьшается (при вычитании целого числа N) на соответствующее количество переменных того типа, адрес которых содержит указатель. Значение указателя всегда изменяется на число байтов, равное N*sizeof(*имя_указателя) или N*sizeof(тип_указателя).
Указатели одного типа можно вычитать друг из друга. Разность указателей показывает, сколько переменных соответствующего типа может разместиться между этими указателями.
Складывать два указателя в языке С (С++) запрещено.
Над указателями можно выполнять следующие операции:
· взятие адреса & &ptra;
· разыменование * *ptra;
· определение размера указателя sizeof(ptra);
· преобразование типов (char*)ptra;
· присваивание ptra=&a;
· сложение и вычитание целых чисел ptra+=3; ptra–=2;
· инкремент, декремент ptra++; ptra–-;
· вычитание указателей int n=ptra-ptrb;
· операции отношения ==!= > >= < <= ptra>ptrb;.
Рассмотрим некоторые операции над указателями.
int a=5,b=7,c=10;
int *pa=&a, *pb=&b, *pc=&c;
printf("pa=%p pb=%p pc=%p\n",pa,pb,pc);
printf("pa-pb=%d ",pa-pb);
printf("pa-pc=%d ",pa-pc);
printf("*(pa-2)=%d *pa+1=%d \n",*(pa-2),*pa+1);
Результат:
pa=8B04FFFC pb=8B04FFF8 pc=8B04FFF4
pa-pb=1 pa-pc=2 *(pa-2)=10 *pa+1=6
6.2 Указатели и константы
При определении сам указатель и значение переменной, адрес которой хранится в указателе, могут быть определены как константы. Для этого используется модификатор const.
Указатель-константа – указатель, значение которого (находящийся адрес) нельзя изменить. Но значение переменной, адрес которой содержит этот указатель, можно просмотреть и изменять. Синтаксис следующий:
тип *const имя_указателя=инициализатор;
int a=5;
int *const Сptr=&a; // неизменяемый указатель
int а1=*Сptr; // обращение по указателю, допустимо, а1=5
*Сptr=10;// изменение содержимого по адресу в указателе, допустимо, а=10
Сptr=&a1;// изменение адреса, хранящегося в указателе-константе, ошибка
Указатель на константу – это такой указатель, при разыменовании которого значение переменной, адрес которой содержится в указателе, нельзя изменить. Но содержимое указателя (находящийся адрес) изменить можно, но при этом нельзя будет изменить значение новой переменной. Синтаксис:
тип const *имя_указателя=инициализатор;
const int b=2;
int const *ptrС=&b; // указатель на неизменяемое число (константу)
int b1=*ptrС; // обращение по указателю, допустимо, b1=2
*ptrС=5; // изменение содержимого по адресу в указателе, ошибка
ptrС=&b1; // изменение адреса, хранящегося в указателе, допустимо
Указатель-константа на константу – это указатель, в котором находящийся адрес и значение переменной по этому адресу изменить нельзя. В этом случае можно только посмотреть значение переменной, используя разыменование указателя. Синтаксис следующий:
тип const*const имя_указателя=инициализатор;
const int с=20;
int const*const СptrС=&с; // указатель-константа на константу
int с1=*СptrС; // обращение по указателю, допустимо, с1=20
*СptrС=5; // изменение содержимого по адресу в указателе,, ошибка
СptrС=&c1; // изменение адреса, хранящегося в указателе, ошибка
6.3 Связь указателей с массивами
Существует связь между массивами и указателями. При определении массива ему выделяется память для всех элементов массива. Но имя массива воспринимается как константный указатель того типа, к которому отнесены элементы массива.
Имя массива – это указатель-константа, значением которого служит адрес нулевого элемента массива.
Пример.
int m[]={1,2,3,4};
printf("*m=%d *(m+1)=%d\n",*m,*(m+1));// 1 2
char str[]="BORLAND C++";
for(int i=8;i<11;i++)
printf("%c",*(str+i));// C++
i=0;
while(*(str+i)!=’\0’)
printf("%c",*(str+i++));//BORLAND C++
Имя массива ‑ это указатель, но поведение его особенное. Если применить операцию sizeof(имя_массива), то результатом будет объем памяти в байтах, выделенный под весь массив. Если применить операцию взять адрес (&имя_массива), то получим адрес начального элемента массива. Имя массива ‑ это весь массив, а также адрес нулевого элемента.
Доступ к элементам массива осуществляется с использованием индекса, который является смещением от начала массива, а также путем разыменования указателя. При обработке массива для компилятора без разницы, как записано обращение к элементам массива. Например:
int mas[4]={9,8,7,6};
int *pmas=mas;
Так к последнему элементу массива mas можно обратиться следующими способами: mas[3], *(mas+3), *(3+mas), 3[mas]. Можно также использовать указатель pmas: pmas[3], *(pmas+3), *(3+pmas), 3[pmas].
6.4 Многомерные массивы
Многомерный массив – это массив массивов,т.е. массив, элементами которого служат массивы.
В общем случае определение многомерного массива выглядит так:
тип имя_массива[n1][n2]…[nk]
где k – размерность массива, n1 – количество в массиве массивов размерности k-1, n2 – количество в массиве массивов размерности k-2 и т.д.
Общее количество элементов в массиве равно произведению количества элементов в каждом массиве, т.е. n1·n2·n2·…·nk.
Любые двумерные массивы интерпретируются компилятором по следующей схеме. Пусть определен массив int a[2][3], тогда компилятор обрабатывает этот массив как указатель с именем a на массив указателей a[0], a[1], которые, в свою очередь указывают на массивы, начинающиеся с a[0][0], a[1][0]. Это удобно представить в виде схемы:
| Имя массива (указатель) | Массив указателей | Массивы элементов | |||||||
| a à | a[0] à | a[0][0] a[0][1] a[0][2] | |||||||
| a[1] à | a[1][0] a[1][1] a[1][2] | ||||||||
Операция sizeof(а) показывает, какое количество памяти в байтах занимают все элементы массива, а операция sizeof(а[0]) показывает, какое количество памяти в байтах занимают элементы массива в массиве а[0]. Причем, в этом случае a=&a, а[0]=&а[0].
Многомерные массивы, как и одномерные, бывают разного класса памяти: внешние (глобальные) (определены вне функций), статические (определены со словом static) и автоматические (определены внутри функций).
Элементы многомерных массивов инициализируются неявно и явно. Неявно (по умолчанию) внешние и статические массивы инициализируются нулями, а массивы с автоматическим классом памяти случайными, произвольными значениями. При определении многомерные массивы, как и одномерные, можно инициализировать явно. Явная инициализация может быть полной и неполной.
int b[2][2][3]={0,1,2,3,4,5,6,7,8,9,10,11,12};
// явная полная инициализация
При инициализации многомерных массивов можно вводить дополнительные фигурные скобки. При этом можно какие-то элементы не инициализировать, или наоборот, инициализировать только определенные элементы. Например, полная инициализация:
int a[2][3]={{1,2,5},{4,7,9}};
int b[3][2]={{2,5},{6,1},{3,4}};
и неполная инициализация:
int c[2][4]={{1,2},{5}}; //c [0][0] =1, c [0][1] =2, c [1][0] =5
Если при определении многомерный массив инициализируется с дополнительными скобками, то самая левая его размерность может не указываться:
int b[][3]={{1,2,3},{4,5,6}};
В этом случае компилятор создаст массив b[2][3].
При неполной инициализации с дополнительными скобками компилятор также определит размеры массива:
int a[][2]={{1,2},{3},{4}};
//a[0][0]=1, a[0][1]=2, a[1][0]=3, a[2][0]=4
Доступ к элементам многомерного массива возможен с помощью индексов и с помощью разыменования имени-указателя. Возможно объединение этих способов:
Рассмотрим доступ к элементам двумерного массива int b[4][3]:
b[i][j]=10; // доступ через два индекса (i=0,1,2,3, j=0,1,2)
*(b[i]+j)=10; // доступ через индекс и разыменование
*(*(b+i)+j)=10; // доступ через двойное разыменование
(*(b+i))[j]=10;. // доступ через разыменование и индекс
Рассмотрим доступ к элементам трехмерного массива int с[2][3][4]:
с[i][j][k]=20; // доступ через три индекса (i=0,1 j=0,1,2 k=0,1,2,3)
*(*(c[i]+j)+k)=20; // доступ через индекс и двойное разыменование
*(c[i][j]+k)=20; // доступ через два индекса и разыменование
*(*(*(c+i)+j)+k)=20; // доступ через тройное разыменование
Далее приведем некоторые примеры обращения к элементам массива:
int a[2][3]={{1,2,3},{4,5,6}};
printf("%d", a[1][1]); //5
printf("%d",*(a[0]+1); //2
printf("%d",*(*(a+1)+2); //6
Теперь рассмотрим пример работы с двумерным массивом.
Пример. Двумерный массив целых чисел заполним случайными значениями и найдем максимальный элемент в массиве и сумму всех элементов массива.
#include<stdio.h>
#include<stdlib.h>
Void main()
{int mas[4][3],i,j,sum=0,max;
for(i=0;i<4;i++)
for(j=0;j<3;j++)
mas[i][j]=rand()%201-50;
// случайные числа от-50 до +150, доступ через индексы
puts(“Массив mass”);
for(i=0;i<4;i++)
{for(j=0;j<3;j++)
printf("%4d",*(*(mas+i)+j));// доступ через разыменование
printf(“\n”); }
max=**mas; // доступ через разыменование
for(i=0;i<4;i++)
for(j=0;j<3;j++)
if(*(mas[i]+j)>max) // доступ через индекс и через разыменование
max=(*(mas+i))[j];// доступ через разыменование и через индекс
for(i=0;i<4*3;i++)
sum+=*(mas[0]+i); // доступ через индекс и через разыменование
printf("max=%4d sum=%4d\n", max, sum);}
6.5 Массивы указателей
Массив указателей – это массив, элементами которого являются указатели. Такой массив определяется следующим образом:
тип *имя_массива[размер];
Примеры определения массивов указателей:
int a1=12, mass[]={1,2,3,4}, arr[2][3]={{9,8,7},{6,5,4}};
int *ptr[]={&mass[0],&mass[3],&a1};
// массив из 3-х указателей
printf("%d %d %d\n",*ptr[0],*ptr[1],*ptr[2]);//1 4 12
int *parr[2]={arr[0],arr[1]);// массив из 2-х указателей.
printf("%d %d\n",*parr[0],*parr[1]);//9 6
Различают массив указателей и указатель на массив из заданного числа элементов.
int (*ppa)[3]=а;// указатель на массив из 3-х элементов.
printf("%d %d\n",*ppa[0],*(*(ppa+1)+1));//6 5
Наиболее часто массивы указателей используются при работе со строками.
Определим двумерный массив такого вида:
char fi[2][20]={"Петров","Иван"};
Создался массив из двух элементов по 20 символов. При таком определении массива строк память используется нерационально. Можно определить массив указателей, и каждый из указателей инициализировать строковой константой:
char *pf[]={"Петров","Иван"};
При этом память распределится более рационально. В памяти компилятор в этом случае выделит место длиной 6+1 и 4+1 байт под строковые константы и место для двух указателей.
Доступ к элементам возможен с помощью такого кода:
cout<<pf; //0x8ab80fd8
cout<<pf[0]; //Петров
Динамические массивы
7.1 Одномерные динамические массивы
Объем памяти, выделяемый для обычного массива, определяется на этапе компиляции в соответствии с обязательным указанием размера массива.
Массивы переменной длины создаются в динамической памяти ("куче") и их часто называют динамическими массивами. Куча – это свободная память, место расположения которой зависит от операционной системы, компилятора, модели памяти, для которой создана программа.
Для формирования массивов динамической памяти используются указатели и специальные функции и операторы. В языке Си в заголовочных файлах <stdlib.h> и <alloc.h> описаны функции malloc(), free(), которые предназначены для выделения, изменения и освобождения участков динамической памяти. Они сообщают (возвращают) в программу адрес начала свободного участка памяти (при его наличии) достаточного размера, т.е. они возвращают указатель. Этот указатель обычно (в зависимости от компилятора) имеет тип void*, который нужно преобразовать к типу данных создаваемого массива. После использования память освобождается.
Синтаксис следующий:
int n; scanf("%d",&n); // число элементов в массиве
тип *имя;
имя=(тип*)malloc(n*sizeof(тип));
if(имя==NULL){puts("Ошибка выделения памяти!");return-1;}
// программа
free(имя);
Пример. Создать динамический массив для чисел типа int, размер задать с клавиатуры.
#include <stdio.h>
#include <alloc.h>
Int main()
{int n, *ptr;
puts("Введите размер массива");
scanf("%d",&n);
ptr=(int*)malloc(n*sizeof(int));
if(ptr==NULL){puts("Ошибка выделения памяти!");
return -1;}
puts("Введите элементы массива");
for(int i=0;i<n;i++)
scanf("%d",&ptr[i]);
for(i=0;i<n;i++)
printf("%d\n",*(ptr+i));
free(ptr); return 0;}
В этом примере функция malloc() осуществляет запрос у операционной системы n*sizeof(int) байт свободной памяти для размещения массива чисел типа int. При наличии свободной памяти возвращается указатель типа void* на начало выделенного блока памяти, иначе ‑ NULL. Дальше выполняется преобразование типа void* в тип int*. Далее в выделенную память помещаются значения элементов массива, причем, доступ к элементам массива можно осуществлять как с помощью индексов, так и методом разыменования указателей на элементы. В конце выполняется вызов функции free(), которая освобождает выделенную ранее память.
В языке С++ введены специальные операции new, delete и delete[]. Операцию delete[] следует применять, если память выделена под массив, а операцию delete для освобождения памяти, предоставленной для простых переменных.
Синтаксис для одномерного массива такой
int n; scanf("%d",&n); // число элементов в массиве
тип *имя;
имя=new тип[n];// запрос памяти под элементы массива
if(имя==NULL){puts("Ошибка выделения памяти!");return -1;}
// программа
delete[]имя; // освобождение памяти
Пример. Создается динамический массив для чисел типа long, в который записываются случайные числа от 1 до 100, и находится произведение всех чисел. В конце программы память освобождается.
#include <stdio.h>
#include <stdlib.h>
Int main()
{int n,i,j;
long *arr,mul=1L;
puts("Введите размер массива");
scanf("%d",&n);
arr=new long[n];// запрос памяти под элементы массива
if(arr==NULL) {puts("Ошибка выделения памяти!");
return -1;}
randomize(); // запуск генератора случайных чисел
for(i=0;i<n;i++) {*(arr+i)=random(100)+1;
mul*=arr[i];}
for(i=0;i<n;i++)
printf("arr[%d]=%ld\n",i,arr[i]);
printf("mul=%ld\n”, mul);
delete [] arr; // освобождение памяти
return 0;
}
7.2 Двумерные динамические массивы
Для создания двумерного динамического массива используется указатель на массив указателей.
Синтаксис для создания двумерного массива динамической памяти с помощью функций malloc следующий:
// ввод количества элементов строк n и элементов в строке m
int n,m; scanf("%d%d",&n,&m);
тип **имя; // определение указателя на массив указателей
// запрос памяти для n указателей на строки
имя=(тип**)malloc(n*sizeof(тип*));
if(имя==NULL){puts("Ошибка выделения памяти!");return -1;}
// запрос памяти для m элементов в n строках
for(int i=0;i<n;i++)
{имя[i]=(тип*)malloc(m*sizeof(тип));
if(имя[i]==NULL){puts("Ошибка выделения памяти!");
free(имя); return -1;}
}
// программа
for(i=0;i<m;i++) free(имя[i]);
free(имя);
Синтаксис для двумерного массива с использованием операции new и delete такой:
// ввод количества элементов строк n и элементов в строке m
int n, m; scanf("%d%d",&n,&m);
тип **имя; // определение указателя на массив указателей
имя=new тип*[n];// запрос памяти для указателей на строки
if(имя==NULL){puts("Ошибка выделения памяти!");return -1;}
// запрос памяти для элементов в строках
for(int i=0;i<m;i++)
{имя[i]=new тип[n];
if(имя[i]==NULL){puts("Ошибка выделения памяти!");
delete[]имя; return -1;}
}
// программа
for(i=0;i<m;i++) delete имя[i];
delete[]имя; // освобождение памяти
Пример. Создать двумерную матрицу, ввести с клавиатуры количество строк и столбцов, а также ввести с клавиатуры значения элементов и заменить отрицательные элементы нулями.
#include <stdio.h>
Void main()
{int N, M, i, j;
int **ma; // указатель на массив указателей на строки
puts("Введите число строк и столбцов матрицы");
scanf("%d%d",&N,&M);
ma=(int**)malloc(N*sizeof(int*));
// запрос памяти под указатели на строки
//ma=new int*[N}; // для операции new – delete
if(ma==NULL){printf("Ошибка выделения памяти!\n");return-1;}
for(i=0;i<N;i++)
{ma[i]=(int*)malloc(M*sizeof(int));));
// запрос памяти под элементы в строке
// ma[i]=new int[M]; // для операции new – delete
if(ma[i]==NULL)
{printf("Ошибка выделения памяти!\n");