Б. Керриган, Д. Ритчи Язык программирования C. Б. Керниган, Д. зык программирования и . Издание 3е, исправленное Перевод с английского под редакцией Вс. С. Штаркмана СанктПетербург 2003
 Скачать 31.48 Mb.
|
|
Глава 5. Указатели и массивы а[0] а[9] Запись а[ i ] отсылает нас к i-му элементу массива. Если ра есть указатель на т. е. объявлен как int *pa; то результате присваивания ра = ра будет указывать на нулевой элемент а, иначе говоря, ра будет содер- жать адрес элемента ра: а[0] Теперь присваивание х = *ра; будет копировать содержимое а[0] в х. Если ра указывает на некоторый элемент массива, то по опреде- лению указывает на следующий элемент, pa+i - на i-й элемент после ра, a - на i-й элемент перед ра. Таким образом, если ра указывает на то есть содержимое а+i a[i], а а[0] 5.3. Указатели и массивы Сделанные замечания верны безотносительно к типу и размеру эле- ментов массива а. Смысл слов "добавить 1 к указателю", как и смысл лю- бой арифметики с указателями, состоит в том, чтобы указывал на следующий объект, а - на после ра. Между индексированием и арифметикой с указателями существует очень тесная связь. По определению значение переменной или выражения типа массив есть адрес нулевого элемента массива. После присваивания ра = ра и а имеют одно и то же значение. Поскольку имя массива является си- нонимом расположения его начального элемента, присваивание можно также записать в следующем виде: Еще более удивительно (по крайней мере на первый взгляд) что ] можно записать как * Вычисляя а [ i Си сразу преобразует его в указанные две формы записи эквивалентны. Из этого следует, что полученные в результате применения оператора & записи и a+i также будут эквивалентными, т. е. и в том и в другом случае это адрес элемента после а. С другой стороны, если ра - указатель, то его можно использовать с индексом, т. е. запись i ] эквивалентна записи * Короче говоря, элемент массива можно изображать как в виде указателя со смещением, так и в виде имени массива с индексом. Между именем массива и указателем, выступающим в роли имени мас- сива, существует одно различие. Указатель - это переменная, поэтому можно написать ра=а или ра++. Но имя массива не является переменной, и записи вроде а=ра или а++ не допускаются. Если имя массива передается функции, то последняя получает в каче- стве аргумента адрес его начального элемента. Внутри вызываемой функ- ции этот аргумент является локальной переменной, содержащей адрес. Мы можем воспользоваться отмеченным фактом и написать еще одну версию функции st вычисляющей длину строки. /* возвращает длину строки */ strlen(char *s) { int n; for (n = 0; != ; return n; Глава 5. Указатели и массивы Так как переменная s - указатель, к ней применима операция ++; s++ не оказывает никакого влияния на строку символов функции, которая об- ратилась к st Просто увеличивается на 1 некоторая копия указателя, находящаяся в личном пользовании функции Это значит, что все вызовы, такие как: /* строковая константа */ strlen(array); /* char */ strlen(ptr); /* char *ptr; */ правомерны. Формальные параметры char и char *s; в определении функции эквивалентны. Мы отдаем предпочтение послед- нему варианту, поскольку он более явно сообщает, что s есть указатель. Если функции в качестве аргумента передается имя массива, то она мо- жет рассматривать его так, как ей удобно - как имя массива, либо как указатель, и поступать с ним соответственно. Она может даже исполь- зовать оба вида записи, если это покажется уместным и понятным. Функции можно передать часть массива, для этого аргумент должен указывать на начало подмассива. Например, если а - массив, то в записях или f(a+2) функции f передается адрес подмассива, начинающегося с элемента а[2]. Внутри функции f описание параметров может выглядеть как f(int { . . . } • или f(int { ... } Следовательно, для f тот факт, что параметр указывает на часть массива, а не на весь массив, не имеет значения. Если есть уверенность, что элементы массива существуют, то возмож- но индексирование и в "обратную" сторону по отношению к нулевому элементу; выражения р[-1 ], т. д. не противоречат синтаксису язы- ка и обращаются к элементам, стоящим непосредственно перед р[0]. Ра- зумеется, нельзя "выходить" за границы массива и тем самым обращаться к несуществующим объектам. 5.4. Адресная арифметика 5.4. Адресная арифметика Если р есть указатель на некоторый элемент массива, то р++ увели- чивает р так, чтобы он указывал на следующий элемент, а р += i увели- чивает его, чтобы он указывал на i-й после того, на который ранее. Эти и подобные конструкции - самые простые приме- ры арифметики над указателями, называемой также адресной арифме- тикой. Си последователен и единообразен в своем подходе к адресной ариф- метике. Это соединение в одном языке указателей, массивов и адресной арифметики - одна из сильных его сторон. Проиллюстрируем сказанное построением простого распределителя памяти, состоящего из двух про- грамм. Первая, alloc(n), возвращает указатель р на последовательно расположенных ячеек типа программой, обращающейся к ос, эти ячейки могут быть использованы для запоминания символов. Вторая, af освобождает память для, возможно, повторной ее утилизации. Простота алгоритма обусловлена предположением, что обращения к af гее делаются в обратном порядке по отношению к соответствующим обра- щениям к Таким образом, память, с которой работают и af гее, является стеком (списком, в основе которого лежит принцип "последним вошел, первым ушел"). В стандартной библиотеке имеются функции malloc и которые делают то же самое, только без упомянутых огра- ничений; в параграфе 8.7 мы покажем, как они выглядят. Функцию alloc легче всего реализовать, если условиться, что она бу- дет выдавать куски некоторого большого массива типа г, который мы назовем Этот массив отдадим в личное пользование функциям alloc и af гее. Так как они имеют дело с указателями, а не с индексами массива, то другим программам знать его имя не нужно. Кроме того, этот массив можно определить в том же исходном файле, что и alloc и af объявив его static, благодаря он станет невидимым вне этого фай- ла. На практике такой массив может и вовсе не иметь имени, поскольку его можно запросить с помощью у операционной системы и полу- чить указатель на некоторый безымянный блок памяти. Естественно, нам нужно знать, сколько элементов массива allocbuf уже занято. Мы введем указатель allocp, который будет указывать первый свободный элемент. Если запрашивается память для п символов, то alloc возвращает текущее значение allocp (т. е. адрес начала свободного бло- ка) и затем увеличивает его на п, чтобы указатель allocp указывал на сле- дующую свободную область. Если же пространства нет, то alloc выдает нуль. Функция af гее[р] просто устанавливает allocp в значение р, если оно не выходит за пределы массива Глава 5. Указатели и массивы Перед вызовом allocp: 1 занято свободно После вызова alloc: занято ttdefine ALLOCSIZE 10000 /* размер доступного пространства */ static char static *allocp = allocbuf; /* память для alloc */ /* указатель на своб. место */ char n) /* возвращает указатель на п символов */ { if (allocbuf + ALLOCSIZE - allocp >= n) { allocp += n; /* пространство есть */ return allocp - n; /* старое р */ } else /* пространства нет */ return 0; } void *p) /* освобождает память, на которую указывает р */ { if (р >= allocbuf && р < allocbuf + ALLOCSIZE) allocp = р; В общем случае как и любую другую переменную, можно инициализировать, но только такими осмысленными для него значения- ми, как нуль или выражение, приводящее к адресу ранее определенных данных соответствующего типа. Объявление static char *allocp = allocbuf; определяет allocp как указатель на char и инициализирует его адресом массива a l l o c b u f , поскольку перед началом работы программы массив 5.4. Адресная арифметика _ пуст. Указанное объявление могло бы иметь и такой вид: static char *allocp = поскольку имя массива и есть адрес его нулевого элемента. Проверка if (allocbuf + ALLOCSIZE - allocp >= n) { /* годится */ контролирует, достаточно ли чтобы удовлетворить запрос на n символов. Если памяти достаточно, то новое значение для allocp долж- но указывать не далее чем на следующую позицию за последним элемен- том allocbuf. При выполнении этого требования выдает указатель на начало выделенного блока символов (обратите внимание на объявле- ние типа самой функции). Если требование не выполняется, функция должна выдать какой-то сигнал о том, что памяти не хватает. Си гаранти- рует, что нуль никогда не будет правильным адресом для данных, поэто- му мы будем использовать его в качестве признака аварийного события, в нашем случае нехватки памяти. Указатели и целые не являются взаимозаменяемыми объектами. Кон- станта нуль - единственное исключение из этого правила: ее можно при- своить указателю, и указатель можно сравнить с нулевой константой. Чтобы показать, что нуль - это специальное значение для указателя, вместо цифры нуль, как правило, записывают NULL - константу, опреде- ленную в файле С этого момента и мы будем ею пользоваться. Проверки if (allocbuf + ALLOCSIZE - allocp >= n) { /* годится */ и if (p >= allocbuf && p < allocbuf + ALLOCSIZE) демонстрируют несколько важных свойств арифметики с указателями. Во-первых, при соблюдении некоторых правил указатели можно сравни- вать. Если р и q указывают на элементы одного массива, то к ним можно при- менять операторы отношения =, <, >= и т. д. Например, отношение вида истинно, если р указывает на более ранний элемент массива, чем q. Лю- бой указатель всегда можно сравнить на равенство и неравенство с ну- лем. А вот для указателей, не указывающих на элементы одного масси- ва, результат арифметических операций или сравнений не определен. (Существует одно исключение: в арифметике с указателями можно ис- пользовать адрес несуществующего "следующего за массивом" элемента, 136 _ Глава 5. Указатели и массивы т. е. адрес того "элемента", который станет последним, если в массив до- бавить еще один элемент.) Во-вторых, как вы уже, наверное, заметили, указатели и целые можно складывать и вычитать. Конструкция р + п означает адрес объекта, занимающего л-е место после объекта, на кото- рый указывает р. Это справедливо безотносительно к типу объекта, на ко- торый указывает р; п автоматически домножается на коэффициент, со- ответствующий размеру объекта. Информация о размере неявно при- сутствует в объявлении р. Если, к примеру, int занимает четыре байта, то коэффициент умножения будет равен четырем. Допускается также вычитание указателей. Например, если р и q указы- вают на элементы одного массива и p int strlen(char *s) char while (*p p++; return p - s; } В своем объявлении р инициализируется значением s, т. е. вначале р указывает на первый символ строки. На каждом шаге цикла while прове- ряется очередной символ; цикл продолжается до тех пор, пока не встре- тится ' Каждое продвижение указателя р на следующий символ вы- полняется инструкцией р++, и разность p-s дает число пройденных сим- волов, т. е. длину строки. (Число символов в строке может быть слишком большим, чтобы хранить его в переменной типа int. Тип pt rdif f доста- точный для хранения разности (со знаком) двух указателей, определен в заголовочном файле . Однако, если быть очень осторожны- ми, нам следовало бы для возвращаемого результата использовать тип в этом случае наша программа соответствовала бы стандартной библиотечной версии. Тип есть тип беззнакового целого, возвраща- емого оператором Арифметика с указателями учитывает тип: если она имеет дело со зна- чениями занимающими больше памяти, чем и р - указатель на то р++ продвинет р на следующее значение Это значит, что 5.5. Символьные указатели функции другую версию которая имеет дело с элементами типа а не char, можно получить простой заменой в alloc и af гее всех char на Все операции с указателями будут автоматически откорректированы в со- ответствии с размером объектов, на которые указывают указатели. Можно производить следующие операции с указателями: присваива- ние значения указателя другому указателю того же типа, сложение и вы- читание указателя и целого, вычитание и сравнение двух указателей, ука- зывающих на элементы одного и того же массива, а также присваивание указателю нуля и сравнение указателя с нулем. Других операций с указа- телями производить не допускается. Нельзя складывать два указателя, пе- ремножать их, делить, сдвигать, выделять разряды; указатель нельзя скла- дывать со значением типа или double; указателю одного типа нельзя даже присвоить указатель другого типа, не выполнив предварительно опе- рации приведения (исключение составляют лишь указатели типа void 5.5. Символьные указатели функции Строковая константа, написанная в виде "Я строка" есть массив символов. Во внутреннем представлении этот массив закан- чивается нулевым символом ' по которому программа может найти конец строки. Число занятых ячеек памяти на одну больше, чем количе- ство символов, помещенных между двойными кавычками. Чаще всего строковые константы используются в качестве аргументов функций, как, например, в Когда такая символьная строка появляется в программе, доступ к ней осуществляется через символьный указатель; получает указатель на начало массива символов. Точнее, доступ к строковой константе осу- ществляется через указатель на ее первый элемент. Строковые константы нужны не только в качестве аргументов функ- ций. Если, например, переменную pmessage объявить как char то присваивание pmessage = "now is the time"; поместит в нее указатель на символьный массив, при этом сама строка не копируется, копируется лишь указатель на нее. Операции для рабо- ты со строкой как с единым целым в Си не предусмотрены. Глава 5. Указатели и массивы Существует важное различие между следующими определениями: char = "now is the /* массив */ char = "now is the time"; /* указатель */ - это имеющий такой объем, что в нем раз помещает- ся указанная последовательность символов и ' Отдельные символы внутри массива могут изменяться, но amessage всегда указывает на одно и то же место памяти. В противоположность ему есть указатель, инициализированный так, чтобы указывать на строковую константу. А значение указателя можно изменить, и тогда последний будет указы- вать на что-либо другое. Кроме того, результат будет неопределен, если вы попытаетесь изменить содержимое константы. now is the is the Дополнительные моменты, связанные с указателями и массивами, про- иллюстрируем на несколько видоизмененных вариантах двух полезных программ, взятых нами из стандартной библиотеки. Первая из них, функ- ция st копирует строку t в строку s. Хотелось бы написать пря- мо s=t, но оператор копирует указатель, а не символы. Чтобы ко- пировать символы, нам нужно организовать цикл. Первый вариант st гсру, с использованием массива, имеет следующий вид: /* копирует t в s; вариант с индексируемым void char *t) { int i = 0; while = != ) Для сравнения приведем версию st гсру с указателями: /* strcpy: копирует t в s: версия 1 (с указателями) */ void strcpy(char *s, char *t) 5.5. Символьные указатели функции _ { while = != ) { Поскольку передаются лишь копии значений аргументов, мо- жет свободно пользоваться параметрами s и t как своими локальными переменными. Они должным образом инициализированы указателя- ми, которые продвигаются каждый раз на следующий символ в каждом из массивов до тех пор, пока в копируемой строке t не встретится ' На практике так не пишут. Опытный программист предпочтет более короткую запись: /* strcpy: копирует t в s; версия 2 (с указателями) */ void strcpy(char *s, { while = *t++) Приращение s и t здесь осуществляется в управляющей части цикла. Значением является символ, на который указывает переменная t перед тем, как ее будет увеличено; постфиксный оператор не изменяет указатель пока не будет взят на который он указы- вает. То же в отношении s: сначала символ запомнится в позиции, на ко- торую указывает старое значение s, и лишь после этого значение пере- менной s увеличится. Пересылаемый символ является одновременно и значением, которое сравнивается с ' В итоге копируются все симво- лы, включая и заключительный символ ' Заметив, что сравнение с ' здесь лишнее (поскольку в Си ненулевое значение выражения в условии трактуется и как его истинность), мы мо- жем сделать еще одно и последнее сокращение текста программы: /* strcpy: копирует t в s; версия 3 (с указателями) */• void strcpy(char *s, char *t) { while = Хотя на первый взгляд то, что мы получили, выглядит загадочно, все же такая запись значительно удобнее, и следует освоить ее, поскольку в Си-программах будете с ней часто встречаться. _ _ Глава 5. Указатели и массивы Что касается функции strcpy из стандартной библиотеки h>, то она возвращает в качестве своего результата еще и указатель на новую копию строки. Вторая программа, которую мы здесь рассмотрим, это st Она сравнивает символы строк s и t и возвращает отрицательное, нулевое или положительное если строка s соответственно лексикографиче- ски меньше, равна или больше, чем строка t. Результат получается вычи- танием первых несовпадающих символов из s и t. /* выдает < 0 при s < t, 0 при s == t, > 0 при s > t */ int *s, char *t) { int i; for (i = 0; s[i] == i++) if (s[i] == return 0; return s[i] - Та же программа с использованием указателей выглядит так: /* выдает < 0 при s < t, 0 при s == t, > 0 при s > t */ int *s, char { for ( ; *s == *t; s++, t++) if == return 0; return *s - *t; Поскольку операторы ++ и — могут быть или префиксными, или пост- фиксными, встречаются (хотя и не так часто) другие их сочетания с опе- ратором *. Например: уменьшит р прежде, чем по этому указателю будет получен символ. На- пример, следующие два выражения: *р++ = /* поместить в стек */ = /* взять из стека значение и поместить в val »/ являются стандартными для посылки в стек и взятия из стека (см. пара- граф 5.6. Массивы указателей, указатели на Объявления функций, упомянутых в этом параграфе, а также ряда дру- гих стандартных функций, работающих со строками, содержатся в заго- ловочном h>. Упражнение 5.3. Используя указатели, напишите функцию которую мы рассматривали в главе 2 (функция st копирует стро- ку t в конец строки s). Упражнение 5.4. Напишите функцию которая выдает если строка t расположена в конце строки s, и нуль в противном случае. Упражнение 5.5. Напишите варианты библиотечных функций и которые оперируют с первыми символами своих аргументов, число которых не п. Например, копирует не более n символов t в s. Полные описания этих функций содержатся в приложении В. Упражнение 5.6. Отберите подходящие программы из предыдущих глав и упражнений и перепишите используя вместо индексирования указатели. Подойдут, в частности, программы getline (главы 1 4), atoi, itoa и их варианты (главы 2, 3 и 4), reverse (глава 3), и getop (глава 4). 5.6. Массивы указателей, указатели на указатели Как и любые другие переменные, указатели можно группировать в мас- сивы. Для иллюстрации этого напишем сортирующую в ал- фавитном порядке текстовые строки; это будет упрощенный вариант про- граммы rt системы UNIX. В главе 3 мы привели функцию сортировки по Шеллу, которая упо- рядочивает массив целых, а в главе 4 улучшили ее, повысив быстро- действие. Те же алгоритмы используются и здесь, однако теперь они бу- дут обрабатывать текстовые строки, которые могут иметь разную длину и сравнение или перемещение которых невозможно выполнить за одну операцию. Нам необходимо выбрать некоторое представление данных, которое бы позволило удобно и эффективно работать с текстовыми стро- ками произвольной длины. Для этого воспользуемся массивом указателей на начала строк. По- скольку строки в памяти расположены вплотную друг к другу, к каждой отдельной строке доступ просто осуществлять через указатель на ее пер- вый символ. Сами указатели можно организовать в виде массива. Одна |