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

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

2 Предположим для определенности, что нулевой элемент целочисленного массива расположен в ячейке памяти с номером A 0. Тогда, зная, что длина элемента данных типа int составляет четыре байта, нетрудно вычислить номер ячейки, в которой будет находиться i-ый элемент этого массива: A i = A o + 4*i Если массив двумерный int a[4][5]; то A[i][j] элемент имеет адрес A i = A o + 5*4*j + 4*i

3 На первый взгляд работа с адресами может показаться утомительной и бесполезной. На самом же деле она является даже более естественной, нежели работа с индексами, поскольку в процессе компиляции программы всякое индексное выражение трансформируется в операции над адресами. Это похоже на поиск комнаты 501 в общежитии. Если вы нашли комнату 500, вам не нужно возвращаться назад к 1 и считать снова. Достаточно добавить единицу к 500 Объекты языка Си, значениями которых являются адреса оперативной памяти, получили название указателей В общем случае указатели являются переменными величинами и над ними можно выполнять определенный набор операций подобно тому, как мы оперировали обычными числовыми переменными

4 В языке Си всякий указатель имеет базовый тип, который совпадает с типом элемента данных, на который может ссылаться этот указатель. Такое соглашение существенно упрощает и делает значительно более эффективной работу с указателями Переменные-указатели, как и переменные любых других типов, перед их использованием в программе должны быть предварительно объявлены в одной из инструкций описания данных. В случае указателей на простые переменные это делается следующим образом: type-specifier *identifier ; Здесь type-specifier задает тип переменной, на которую ссылается указатель с именем identifier, а символ звездочка (*) определяет саму переменную как указатель Приведем несколько примеров правильного описания указателей в программе: int *ptr; long *sum; float *result, *value;

5 Каждая из этих инструкций говорит о том, что соответствующая переменная есть указатель на элемент данных определенного типа, а комбинация, например, вида *ptr представляет собой величину типа int. По существу это означает, что подобные комбинации могут использоваться как операнды произвольных выражений В частности, сохраняя обозначения предыдущего примера, мы могли бы написать int *sum, *ptr; int x=0,i; sum = &x; ptr = &i; for (*ptr = 1; *ptr

6 Строго говоря, компилятор языка Си рассматривает комбинации вида *identifier в составе выражений как некоторую операцию над указателями. Эта операция, символом которой как раз и является звездочка перед именем указателя, носит название операции косвенной адресации и служит для доступа к значению, расположенному по заданному адресу Существует и другая операция, в определенном смысле противоположная операции косвенной адресации и именуемая операцией получения адреса. Она обозначается символом амперсанда (&) перед именем простой переменной или элемента массива: &identifier или &identifier[expression] и сопоставляет своему аргументу адрес его размещения в памяти, т.е. указатель. Естественно, что этим аргументом может быть и указатель, поскольку указатели, как и другие переменные, хранятся в ячейках оперативной памяти

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

8 Вот несколько примеров использования указателей и адресных выражений 1. Аргументами функции форматированного ввода scanf являются адреса переменных, которым должны быть присвоены прочитанные значения: scanf("%d",&n); 2. Следующая пара операторов px = &x; y = *px; где переменная px объявлена предварительно как указатель, равносильна непосредственному присваиванию y = x; 9 Отождествление массивов и указателей Адресная арифметика Нам предстоит разобраться в том, какой смысл следует вкладывать в арифметические операции над указателями и в каком отношении между собой находятся массивы и указатели Рассмотрим в качестве примера следующее описание int a[10]; определяющее массив из десяти элементов типа int. Поскольку a==&a[0], то адрес элемента a[i] равен a + sizeof(int)*i

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

11 Пусть теперь имеется пара описаний int a[10]; int *pa; Выполняя операцию присваивания pa = a или pa = &a[0] мы устанавливаем указатель pa на нулевой элемент массива a и поэтому справедливы равенства &a[i] == pa+i и a[i] == *(pa+i) т.е. операцию pa+i, увеличивающую значение указателя, можно интерпретировать как смещение вправо на i элементов базового типа. Все это означает, что всякое обращение к i-ому элементу массива или его адресу допустимо представлять как в индексной форме, так и на языке указателей

12 Обратим внимание на одно важное обстоятельство, отличающее массивы от указателей. Поскольку последние являются переменными величинами, то оказываются допустимыми следующие адресные выражении pa = pa+i или pa = a или pa++ Однако ввиду того, что имя массива есть константа, определяющая фиксированный адрес размещения этого массива в памяти компьютера, операции вида a = pa или a = a+i или a++ или pa = &a следует считать лишенными какого-либо смысла

13 Продолжая далее аналогию массивов и указателей, необходимо разрешить индексирование указателей, полагая pa[i] == *(pa+i) или &pa[i] == pa+i что является совершенно естественным, если обозначение pa[i] понимать как взятие значения по адресу pa+i. Индексируя элементы массива, мы по сути дела находимся в рамках того же самого соглашения Заметим, что было бы грубой ошибкой считать, что описания int a[10]; int *pa; полностью равносильны одно другому

14 int a[10]; int *pa; Дело в том, что в первом случае определен адрес начала массива и выделено место в памяти компьютера, достаточное для хранения десяти его элементов Во втором же случае указатель имеет неопределенное значение и не ссылается ни на какую связную цепочку байт. Для того, чтобы указатель стал полностью эквивалентен массиву, необходимо заставить его ссылаться на область памяти соответствующей длины. Это можно сделать при помощи стандартных функций malloc() и alloca(), захватывающих требуемое количество байт памяти и возвращающих адрес первого из них

15 Так, например, после выполнения оператора pa = (int*)malloc(10*sizeof(int)); определенные выше массив a и указатель pa становятся в полном смысле эквивалентными. Однако второе решение будет более гибким, ибо здесь затребованная память выделяется динамически в процессе выполнения программы и может быть при необходимости возвращена системе с помощью функции free(), чего нельзя сделать в случае массива

16 Остановимся особо на вопросе использования указателей для представления и обработки символьных строк. Поскольку в языке Си нет специального типа данных, который можно было бы использовать для описания символьных строк, последние хранятся в памяти компьютера в виде массивов символов Так, например, описание char string[] = "Это строка символов"; определяет массив двадцати элементов типа char, инициализируя их символами строки Обращение к какому-либо элементу этого массива обеспечивает доступ к отдельному символу, а адрес начала строки равен &string[0]

17 С другой стороны, ввиду того, что строковая константа в правой части нашего описания отождествляется компилятором с адресом ее первого символа, правомерной является запись следующего вида: char *strptr = "Это строка символов"; инициализирующая указатель значением адреса строки-константы. Различие двух приведенных описаний такое же, как и отмеченное выше различие массивов и указателей. Так, во втором случае мы могли бы написать strptr = strptr + 4; сместив тем самым указатель на начало второго слова строки

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

19 Указатели на массивы Массивы указателей и многомерные массивы Введенное в предыдущем параграфе понятие указателя на простую переменную естественным образом распространяется на любые структурированные типы данных. В частности, декларация float (*vector)[15]; определяет имя vector как указатель на массив пятнадцати элементов типа float, причем круглые скобки в этой записи являются существенными. Обращение к i-ому элементу такого массива будет выглядеть следующим образом: (*vector)[i]

20 Определяя указатель на массив, мы сохраняем все преимущества работы с указателями и, кроме того, требуем от компилятора выделить реальную память для размещения элементов этого массива Так как сами по себе указатели являются переменными, то нетрудно построить ограниченный вектор элементов-указателей на некоторый базовый тип данных. Такие структуры данных в языке Си принято называть массивами указателей. Их описание строится на той же синтаксической основе, что и описание обычных массивов Например, инструкция char *text[300]; определяет массив трехсот указателей на элементы данных типа char

21 Поскольку каждый отдельный элемент этого массива может хранить адрес начала некоторой цепочки символов, то после фактического выделения памяти под размещение трехсот таких цепочек и присвоения адреса каждой из них определенному элементу массива, весь массив указателей будет задавать набор соответствующего количества строк переменной Элементы массива указателей могут быть инициализированы подобно тому, как инициализировались отдельные указатели и обычные массивы: char *week[] = { "Понедельник", "Вторник", "Среда", "Четверг", "Пятница", "Суббота", "Воскресенье" };

22 Вспоминая проведенную аналогию между массивами и указателями, можно сказать, что массив указателей в определенном смысле эквивалентен "массиву массивов " char table[10][20]; определяет массив десяти массивов, каждый из которых содержит по двадцать элементов типа char Легко заметить, что это есть ни что иное, как синоним двумерного массива, причем первый индекс определяет номер строки, а второй - номер столбца

23 Очевидно, что желая сохранить тесную связь массивов и указателей, следует потребовать, чтобы двумерные массивы размещались в памяти компьютера по строкам, отождествив имя массива с адресной ссылкой &table[0][0] Обращение же к индивидуальным элементам двумерного массива осуществляется, как и в случае одного измерения, посредством индексных выражений Отличие массива указателей от массива массивов состоит, главным образом, в том, что в первом случае резервируются лишь ячейки памяти для хранения адресов строк двумерной таблицы, в то время как реальная память под размещение элементов каждой строки не выделяется. Во втором же случае полностью определен объем памяти, занимаемой всей таблицей С другой стороны, общее сходство между двумя этими структурами данных позволяет работать с массивами указателей точно так же, как и с двумерными массивами, используя, например, двойную индексацию week[2][3] для выделения четвертого по счету символа в третьей строке, и наоборот, рассматривая ссылку вида table[i] как адрес нулевого элемента i-ой строки таблицы table

24 Такое соглашение выглядит достаточно естественным, если вместо термина "многомерный массив" всюду использовать понятие "массив массивов« Проведенная аналогия между массивами указателей и массивами массивов дает возможность придать вполне конкретный смысл выражению вида table[i]+k, задающему адрес k-ого элемента i-ой строки массива table, который в терминах операции взятия адреса определяется как &table[i][k] Поэтому наряду с традиционной ссылкой table[i][k] на значение элемента (i, k) этого массива можно пользоваться эквивалентной ей ссылкой *(table[i] + k) на языке указателей Поскольку имя всякого массива при отсутствии индексных выражений отождествляется с адресом его самого первого элемента, видно, что выражение table+j является обычным адресным выражением, определяющим размещение в памяти нулевого элемента j-ой строки таблицы table

25 Массивы указателей обеспечивают возможность более гибкого манипулирования данными, нежели многомерные массивы. Дальнейшее увеличение гибкости структур данных связано с понятием косвенного указателя или " указателя на указатель", который может быть определен следующим образом: type-specifier **identifier ; Здесь вновь сохраняется аналогия с рассмотренными выше объектами, т.е. такое описание окажется полностью равносильным двумерному массиву после того, как будет выделена реальная память под хранение адресов его строк и размещение элементов каждой отдельной строки

26 Это можно сделать, используя, например, функцию malloc() или alloca() double **dataptr; dataptr = (double**)alloca(m*sizeof(double*)); for (i = 0; i < m; i++) dataptr[i] = (double*)alloca(n*sizeof(double)); В последнем примере осуществляется размещение в памятикомпьютера двумерного массива размера m*n элементов типа double Продолжая начатые построения, можно было бы по индукции ввести понятия массива произвольного числа измерений и указателя любого уровня косвенности, имея в виду установленную выше эквивалентность между этими объектами в одномерном и двумерном случаях. Однако, учитывая сравнительно редкое практическое использование таких структур данных и в то же время логическую простоту их построения, мы не будем особо останавливаться здесь на этом вопросе

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

28 Пусть нам необходимо написать программу скалярного умножения векторов A и B, размерность которых заранее не известна. Для этого поступим следующим образом. Опишем в заголовке программы переменную m, определяющую длину соответствующих массивов, и указатели a, b, c, которые будут определять размещение в памяти векторов-сомножителей и вектора-результата: int m; float *a, *b, *c; После того, как значение m будет определено (оно может быть, например, введено с клавиатуры терминала), необходимо выделить достаточный объем памяти для хранения всех трех векторов. Поскольку речь здесь идет о динамическом размещении массивов в процессе выполнения программы, мы должны воспользоваться одной из трех специальных функций, входящих в состав стандартной библиотеки и сведения о которых приведены ниже

29 Имя функции и назначение: alloca - резервирует size байт памяти из ресурса программного стека; выделенная память освобождается по завершении работы текущей программной компоненты. Формат и описание аргументов: void *alloca(size) int size; /* Требуемое количество байт памяти */ Возвращаемое значение является указателем типа char на первый байт зарезервированной области программного стека и равно NULL при отсутствии возможности выделить память требуемого размера. Для получения указателя на тип данных, отличный от char, необходимо применить к возвращаемому значению операцию явного преобразования типа

30 Имя функции и назначение: calloc - резервирует память для размещения n элементов массива, каждый из которых имеет длину size байт, инициализируя все элементы нулями; выделенная память освобождается по завершении работы программы или при помощи функции free() Формат и описание аргументов: void *calloc(n, size) int n; /* Общее количество элементов в массиве */ int size; /* Длина в байтах каждого элемента */ Возвращаемое значение является указателем неопределенного типа на первый байт зарезервированной области статической памяти и равно NULL при отсутствии возможности разместить требуемое количество элементов заданной длины. Для получения указателя на конкретный тип данных, необходимо применить к возвращаемому значению операцию явного преобразования типа

31 Имя функции и назначение: malloc - резервирует блок памяти размером size байт; затребованная память освобождается по завершении работы программы или при помощи функции free() Формат и описание аргументов: void *malloc(size) int size; /* Требуемое количество байт памяти */ Возвращаемое значение является указателем неопределенного типа на первый байт зарезервированной области статической памяти и равно NULL при отсутствии возможности выделить память требуемого размера.

32 Для получения указателя на конкретный тип данных, необходимо применить к возвращаемому значению операцию явного преобразования типа Предварительные описания всех этих функций помещены в файлы stdlib.h и malloc.h и при их использовании один из них должен быть включен в состав исходного текста программы при помощи директивы препроцессора #include Выбрав в нашей задаче для размещения массивов a, b и c какую- либо из этих функций, например calloc(), можно записать: a = (float*)calloc(m, sizeof(float)); b = (float*)calloc(m, sizeof(float)); c = (float*)calloc(m, sizeof(float)); где операция приведения (float*) преобразует указатель неопределенного типа в указатель типа float

33 Теперь, после предварительного ввода числовых значений элементов векторов, может быть выполнено их скалярное умножение: for (i = 0; i < m; i++) c[i] = a[i]*b[i]; Для динамического размещения двумерного массива необходимо воспользоваться косвенным указателем int m, n; float **matr; и выделять память в два этапа: matr = (float**)malloc(m*sizeof(float*)); for (i = 0; i < m; i++) matr[i] = (float*)calloc(n, sizeof(float));

34 После этого работа с matr может выполняться точно так же, как и с обычным двумерным массивом Память, затребованная у системы путем использования функций calloc() и malloc(), может быть возвращена назад до полного завершения работы программы при помощи функции free() Имя функции и назначение: free - освобождает блок памяти, предварительно зарезервированный одной из функций calloc(), malloc() или realloc() Формат и описание аргументов: void free(ptr) void *ptr; /* Указатель на освобождаемый блок */ Эта функция в результате своей работы не возвращает никакого значения. Кроме того, она игнорирует указатель ptr, если он равен NULL

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

36 Учитывая, что интересующая нас область памяти имеет сегментный адрес 0xB800 и каждой позиции экрана отвечают два байта этой памяти, достаточно определить массив элементов типа int, расположив его по требуемому адресу В том случае, когда видеосистема установлена в режим 25 строк по 80 символов, соответствующее описание должно иметь следующий вид: (*vmem_16)[25][80] = 0xB ; После этого занесению какой-либо информации во всякий элемент массива (*vmem_16) будет соответствовать определенный эффект на экране видеотерминала