Geum.ru

Адреса и указатели. Операции получения адреса и косвенной адреса­ции. Отождествление массивов и указателей. Адресная арифметика. Ука­затели на массивы

Вид материалаЛекция

Содержание


4. Динамическое выделение памяти под массивы
5. Инициализация указателей
Подобный материал:
ЛЕКЦИЯ 4

Адреса и указатели. Операции получения адреса и косвенной адреса­ции. Отождествление массивов и указателей. Адресная арифметика. Ука­затели на массивы. Массивы указателей и многомерные массивы. Динами­ческое выделение памяти под массивы. Инициализация указателей.

$ 1. АДРЕСА И УКАЗАТЕЛИ.

Во время выполнения всякой программы, используемые ею данные размещаются в оперативной памяти ЭВМ, причем каждому элементу данных ставится в соответствие его индивидуальный адрес. При реализации мно­гих алгоритмов и представлении сложных структур данных часто оказыва­ется полезной возможность непосредственной работы с адресами памяти. Подобная ситуация возникает, например, при обработке массивов пере­менных. Действительно, поскольку соседние элементы массива располага­ются в смежных ячейках памяти, то для перехода от одного его элемента к другому можно вместо изменения значения индексного выражения мани­пулировать адресами этих элементов. Предположим для определенности, что нулевой элемент целочисленного массива расположен в ячейке памяти с адресом (номером) Ао. Тогда, зная, что длина элемента данных типа int составляет два байта, нетрудно вычислить адрес (номер) ячейки, в которой будет находиться i-ый элемент этого массива:

Ai = Ao + 2*i

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

Объекты языка Си, значениями которых являются адреса оперативной памяти, получили название указателей. В общем случае указатели явля­ются переменными величинами и над ними можно выполнять определенный набор операций подобно тому, как мы оперировали числовыми переменны­ми. В языке Си всякий указатель имеет базовый тип, который совпадает с типом элемента данных, на который может ссылаться этот указатель. Такое соглашение, возможно несколько ограниченое, существенно упроща­ет и делает значительно более эффективной работу с указателями.

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

тип *идентификатор;

где символ (*) определяет саму переменную как указатель.

Примеры:

int *ptr;

long *sum;

float *rez, *val;

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

*sum = 0;

for(*ptr = 1; *ptr <= 100; (*ptr)++)

*sum = *sum + (*ptr) * (*ptr);

что соответствует фрагменту программы вычмсления суммы квадратов первых 100 натуральных чисел. Круглые скобки в корректирующем выраже­нии оператора цикла являются существенными.

Строго говоря, компилятор языка Си рассматривает комбинации вида

*идентификатор

в составе выражений как некоторую операцию над указателями. Эта операция, символом которой как раз и является звездочка перед именем указателя, носит название косвенной адресации и служит для доступа к значению, расположенному по заданному указателем адресу.

Существует и другая операция, в определенном смысле противополож­ная операции косвенной адресации и именуемая операцией получения ад­реса. Она обозначается символом амперсанд ( & ) перед именем простой переменной или элемента массива:

&a &mas[4]

и сопоставляет своему аргументу адрес его размещения в памяти, т.е.указатель. Естественно, что этим аргументом может быть и указатель,поскольку указатели, как и другие переменные, хранятся в ячейках опе­ративной памяти.

Всевозможные выражения, построенные с использованием указателей или операторов * и &, принято называть адресными выражениями, а сами сами арифметические операции над указателями - адресной арифметикой. Одноместные операции * и & имеют такой же высокий приоритет, как и другие унарные операции, и в составе выражений обрабатываются справа налево. Именно поэтому в предыдущем примере небходимы скобки в выра­жении (*ptr)++ , ибо без них оператор ++ относился бы к указателю ptr, а не к значению, на которое ссылается этот указатель.

Замечание. Если, например, mas есть массив переменных, то выраже­ние &mas[0] равносильно простому употреблению имени массива без сле­дующего за ним индексного выражения, поскольку последнее отождествля­ется с адресом размещения в памяти первого элемента этого массива.

Примеры.

1. Аргументами функции scanf являются адреса переменных, которым должны быть присвоены прочитанные значения:

scanf("%d%d", &m,&n);

2. Следующая пара операторов

px = &x;

y = *px;

где переменная рх объявлена предварительно как указатель, равносильна

непосредственному присваиванию

y = x;

3. При выполнении следующего фрагмента программы сравнение в опе­раторе if всегда будет истинно, поскольку значение указателя numptr совпадает с адресом переменной number:

int number;

int *numptr = &number;

scanf("%d%d", &number, numptr);

if(number == *numptr)

printf("сравнение истинно");

else

printf("Сравнение ложно");

$ 2. ОТОЖДЕСТВЛЕНИЕ МАССИВОВ И УКАЗАТЕЛЕЙ. АДРЕСНАЯ АРИФМЕТИКА.

Как мы уже отмечали, при отсутствии индексного выражения имя мас­сива по существу есть указатель на его первый (нулевой) элемент. Поэ­тому доступ к i-ому элементу этого массива можно получить, увеличивая значение указателя на соответствующую величину.

Рассмотрим в качестве примера следующее описание int a[10];

определяющее массив из десяти элементов типа int. Поскольку a == &a[0], то адрес элемента a[i] равен

a + sizeof(int) * i

Хотя приведенная запись и отражает существо дела, тем не менее она является недостаточно удобной из-за своей громоздкости. Действитель­но, учитывая, что всякий элемент массива а имеет тип int и занимает sizeof(int) байт памяти, из адресного выражения можно было бы исклю­чить информацию о длине элемента массива. Для этого достаточно, нап­ример, принять соглашение о том, что выражение вида a = i как раз и определяет адрес i-ого элемента, т.е.

&a[i] == a+i

Тогда обозначение a[i] становится эквивалентным адресному выраже­нию *(a+i) в том смысле, что оба они определяют одно и то же числовое значение, а именно:

a[i] == *(a+i)

Пусть теперь имеется пара описаний

int a[10];

int *pa;

Выполняя операцию присваивания

pa = a или pa =&a[0]

мы устанавливаем указатель ра на нулевой элемент массива а и поэтому

справедливы равенства

&a[i] == pa+i и a[i] == *(a+i)

т.е. операцию pa=i, увеличивающую значение указателя, можно ин­терпретировать как смещение вправо на i элементов базового типа. Все это означает, что всякое обращение к i-ому элементу массива или его адресу допустимо представлять как в индексной форме, так и на языке указателей.

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

pa = pa+i или pa = a или pa++

Однако ввиду того, что имя массива есть константа, определяющая фиксированный адрес размещения этого массива в памяти ЭВМ, операции вида

a = pa a = a+i a++ pa = &a

следует считать лишенными какого-либо смысла.

Продрлжая далее анологию массивов и указателей, необходимо разре­шить индексирование указателей, полагая

pa[i] == *(pa+i) или &pa[i] == pa+i

что является совершенно естественным, если обозначение pa[i] понимать

как взятие значения по адресу pa+i. Индексируя элементы массива, мы

по сути дела находимся в рамках того же самого соглашения.

Заметим, что было бы грубой ошибкой считать, что описания int a[10];

int *pa;

полностью равносильны одно другому. Дело в том, что в первом случае

определен адрес начала массива и выделено место в памяти ЭВМ, доста­точное для хранения десяти его элементов. Во втором случае указатель имеет неопределенное (нулевое) значение и не ссылается ни на какую связную цепочку байт. Для того, чтобы указатель стал полностью экви­валентен массиву, необходимозаставить его ссылаться на область памяти соответствующей длины. Это можно сделать при помощи стандартных функ­ций malloc() и alloca(), захватывающих требуемое количество байт па­мяти и возвращающих адрес первого из них. Так, например, после выпол­нения оператора

pa = (int*)alloca(10*sizeof(int));

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

Указатели также можно использовать для представления и обработки символьных строк. Так, например, описание

char string[] = "Это строка символов";

определяет массив из 20 символов типа char, инициализируя их сим­волами строки. Обращение к какому-либо элементу этого массива обеспе­чивает доступ к отдельному символу, а адрес начала строки равен &string[0]. С другой стороны, ввиду того, что строковая константа в правой части нашего описания отождествляется компилятором с адресом первого символа, правомерной является запись следующего вида:

char *strptr = "Это строка символов";

инициализирующая указатель значением адреса строки-константы. Разли­чие двух приведенных описаний такое же, как и отмеченное выше разли­чие массивов и указателей. Так во втором случае мы могли бы написать

strptr = strptr + 4;

сместив тем самым указатель на начало второго слова строки. Более то­го, является допустимым присваивание

strptr = "Это другая строка символов";

изменяющее значение указателя (но не выполняющее копирования строки символов !). Подобная операция не имеет смысла для имени массива, ко­торое во внутреннем машинном представлении отождествляется с фиксиро­ванным адресом его нулевого элемента.

Кроме определенной выше операции увеличения указателя, можно также использовать операцию его уменьшения, что равносильно движению вдоль массива в направлении уменьшения значения индекса. Более того, мно­жество значений переменной-указателя является упорядоченным (т.к. упорядочены адреса оперативной памяти) и поэтому использование указа­телей в качестве операндов условных и логических выражений не проти­воречит семантическим правилам языка Си.

$ 3. УКАЗАТЕЛИ НА МАССИВЫ. МАССИВЫ УКАЗАТЕЛЕЙ И МНОГОМЕРНЫЕ МАССИВЫ

Введённое в предыдущем параграфе понятие указателя на простую переменную естественным образом распространяется на любые структурированные типы данных. В частности декларация

float ( *vektor) [15];

определяет имя vektor как указатель не массив из пятнадцати элементов типа float, причем круглые скобки в этой записи являются существенными. Обращение к i -ому элементу такого массива будет выглядеть следующим образом:

(*vektor)[ i ]

Определяя указатель на массив, мы сохраняем все преимущества работы с указателями и, кроме того, требуем от компилятьра выделить реальную память для размещения элементов этого массива.

Так как сами по себе указатели являются переменными, то нетрудно построить ограниченный вектор элементов-указателей на некоторый базовый тип данных. Такие структуры в языке С принято называть массивами указателей. Их описание строится на той же синтаксической основе, что и описание обычных массивов. Например, описание

char *text[100]

определяет массив из ста указателей на переменны (элементы данных) типа char/ Поскольку каждый отдельный элемент этого массива может хранить адрес некоторой строки символов, то весь массив будет задавать набор ста строк неопределённой, вообще говоря, длины. Элементы массива указателей могут быть инициализированы подобно тому, как инициализировались отдельные указатели и обычные массивы:

char *week[ ] = { «Понедельник»,

«Вторник»,

«Среда»,

«Четверг»,

«Пятница»,

«Суббота»,

«Воскресенье»

};

week[0] – адрес 0 строки («Понедельник»), week[ 1] [ 3 ] – буква р в слове Вторник. Аналогично week[3] – адрес 3 строки ( «Четверг»).

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

Тип имя [константное выр-е][ константное выр-е]

где все обозначения использованы в том же смысле, что и ранее. Так описание

char table [10][20];

определяет массив десяти массивов, каждый из которых содержит по двадцать элементов типа char Легко заметить, что это есть ни что иное, как синоним многомерного массива, причем первый индекс определяет номер строки, а второй - номер столбца. Очевидно, что желая сохранить тесную связь массивов и указателей, следует потребовать, чтобы многомерные массивы размещались в памяти ЭВМ по строкам, отождествив имя массива с адресной ссылкой table [0][0]. Обращение к индивидуальному элементу многомерного массива осуществляется , как и в случае одного измерения, посредством индексных выражений. Отличие массива указателей от массива массивов состоит главным образом в том, что в первом случае определяются лишь адреса строк двумерной таблицы, но реальная память для хранения элементов каждой строки не выделяется. Во втором же случае полностью определен объем памяти, занимаемой всей таблицей. Общая аналогия между двумя этими структурами данных позволяет работать с массивами указателей точно так же, как и с многомерными массивами, используя, например, двойную индексацию:

week[2][3]

для выделения четвертого по счету символа в третьей строке, и наоборот, рассматривая ссылку вида

table [i]

как адрес нулевого элемента i-той строки таблицы table .

Нетрудно заметить, что несмотря на общность свойств, массивы указателей обеспечивают возможность более гибкого манипулирования данными, нежели многомерные массивы. Дальнейшее увеличение гибкости структур данных связано с понятием косвенного указателя или «указателя на указатель», который может быть определен следующим образом:

тип **имя;

Здесь вновь сохраняется аналогия с рассмотренными выше объектами, т.е. такое описание окажется полностью равносильным двумерному массиву после того, как будет выделена реальная память под хранение его строк и столбцов. Это можно сделать, используя, например, функции malloc() и calloc():


double **dataptr;

dataptr = (double**)malloc(m*sizeof(double*));

for (i = 0; i < m; i++)

dataptr[i] = (double*) malloc(n*sizeof(double));

В последнем примере осуществляется размещение в памяти ЭВМ двумерного массива размера m * n элементов типа double.


4. ДИНАМИЧЕСКОЕ ВЫДЕЛЕНИЕ ПАМЯТИ ПОД МАССИВЫ

В двух предыдущих параграфах при обсуждении вопроса об эквивалентности массивов и указателей мы воспользовались стандартными функциями %% и %% для динамического выделения памяти под хранение элементов массива. Здесь будут рассмотрены некоторые детали затронутой проблемы.

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

Пусть нам необходимо написать программу скалярного умножения векторов А и В, размерность которых заранее не известна. Для этого поступим следующим образом. Опишем в заголовке программы переменную %%, определяющую длину соответствующих массивов, и указатели %%%, которые будут определять размещение в памяти векторов-сомножителей и вектора-результата:

%%

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


%% /* Выделяет %%байт памяти из программного стека. Возвращает указатель типа %% на первый байт соответствующего пространства. Память освобождается после завершения работы текущей программной компоненты. */


%% /* Выделяет %% байт памяти из программного стека. Возвращает указатель типа %% на первый байт соответствующего пространства. Память освобождается после завершения работы программы или при помощи функции %%.*/


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

Выбрав, например, функцию %%, можно записать:

%%

%%

%%


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

%%

В случае двумерных массивов необходимо воспользоваться косвенным указателем

%%

и выделить память в два этапа:

%%

%%

После этого работа с %% может выполняться точно так же, как и с обычными двумерными массивами.


5. ИНИЦИАЛИЗАЦИЯ УКАЗАТЕЛЕЙ


В виду того, что с инициализацией указателей мы уже столкнулись при их обсуждении в предыдущих параграфах, здесь будет рассмотрен лишь один частный вопрос.

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

%%, рассмотрим способ обращения к ячейкам видеопамяти в алфавитно-цифровом режиме. Учитывая, что интересующая нас область памяти имеет сегментный адрес %% и каждой позиции экрана отвечают два байта этой памяти, достаточно определить массив элементов типа %%, расположив его по требуемому адресу. В том случае, когда видеосистема установлена в режим 25 строк по 80 символов, соответствующее описание должно иметь следующий вид:

%%

После этого занесению какой-либо информации во всякий элемент массива %% будет соответствовать определенный эффект на экране видеотерминала.


Пример 1.


(далее идут одни примеры!!!!)