Язык программирования Си Брайан Керниган, Деннис Ритчи 3е издание Версия 1 Table of Contents
 Скачать 2.33 Mb.
|
|
5.4. Адресная арифметика Если р есть указатель на некоторый элемент массива, то р++ увеличивает р так, чтобы он указывал на следующий элемент, а р += i увеличивает его, чтобы он указывал на i -й элемент после того, на который указывал ранее. Эти и подобные конструкции — самые простые примеры арифметики над указателями, называемой также адресной арифметикой. Си последователен и единообразен в своем подходе к адресной арифметике. Это соединение в одном языке указателей, массивов и адресной арифметики — одна из сильных его сторон. Проиллюстрируем сказанное построением простого распределителя памяти, состоящего из двух программ. Первая, alloc(n) , возвращает указатель р на n последовательно расположенных ячеек типа char ; программой, обращающейся к alloc , эти ячейки могут быть использованы для запоминания символов. Вторая, afree(р) , освобождает память для, возможно, повторной ее утилизации. Простота алгоритма обусловлена предположением, что обращения к afree делаются в обратном порядке по отношению к соответствующим обращениям к alloc Таким образом, память, с которой работают alloc и afree , является стеком (списком, в основе которого лежит принцип "последним вошел, первым ушел"). В стандартной библиотеке имеются функции malloc и free , которые делают то же самое, только без упомянутых ограничений; в параграфе 8.7 мы покажем, как они выглядят. Функцию alloc легче всего реализовать, если условиться, что она будет выдавать куски некоторого большого массива типа char , который мы назовем allocbuf . Этот массив отдадим в личное пользование функциям alloc и afree . Так как они имеют дело с указателями, а не с индексами массива, то другим программам знать его имя не нужно. Кроме того, этот массив можно определить в том же исходном файле, что и alloc и afree , объявив его static , благодаря чему он станет невидимым вне этого файла. На практике такой массив может и вовсе не иметь имени, поскольку его можно запросить с помощью malloc у операционной системы и получить указатель на некоторый безымянный блок памяти. Естественно, нам нужно знать, сколько элементов массива allocbuf уже занято. Мы введем указатель allocp , который будет указывать на первый свободный элемент. Если запрашивается память для n символов, то alloc возвращает текущее значение allocp (т. е. адрес начала свободного блока) и затем увеличивает его на n , чтобы указатель allocp указывал на следующую свободную область. Если же пространства нет, то alloc выдает нуль. Функция afree[р] просто устанавливает allocp в значение р , если оно не выходит за пределы массива allocbuf Перед вызовом alloc : После вызова alloc : #define ALLOCSIZE 10000 /* размер доступного пространства */ static char allocbuf[ALLOCSIZE]; /* память для alloc */ static char *allocp = allocbuf; /* указатель на своб. место */ char *alloc(int n) /* возвращает указатель на п символов */ { if (allocbuf + ALLOCSIZE - allocp >= n) { allocp += n; /* пространство есть */ return allocp - n; /* старое р */ } else /* пространства нет */ return 0; } void afree(char *p) /* освобождает память, на которую указывает р */ { if (р >= allocbuf && р < allocbuf + ALLOCSIZE) allocp = р; } В общем случае указатель, как и любую другую переменную, можно инициализировать, но только такими осмысленными для него значениями, как нуль или выражение, приводящее к адресу ранее определенных данных соответствующего типа. Объявление static char *allocp = allocbuf; определяет allocp как указатель на char и инициализирует его адресом массива allocbuf , поскольку перед началом работы программы массив allocbuf пуст. Указанное объявление могло бы иметь и такой вид: static char *allocp = &allocbuf[0]; поскольку имя массива и есть адрес его нулевого элемента. Проверка if (allocbuf + ALLOCSIZE - allocp >= n) { /* годится */ контролирует, достаточно ли пространства, чтобы удовлетворить запрос на n символов. Если памяти достаточно, то новое значение для allocp должно указывать не далее чем на следующую позицию за последним элементом allocbuf . При выполнении этого требования alloc выдает указатель на начало выделенного блока символов (обратите внимание на объявление типа самой функции). Если требование не выполняется, функция alloc должна выдать какой-то сигнал о том, что памяти не хватает. Си гарантирует, что нуль никогда не будет правильным адресом для данных, поэтому мы будем использовать его в качестве признака аварийного события, в нашем случае нехватки памяти. Указатели и целые не являются взаимозаменяемыми объектами. Константа нуль — единственное исключение из этого правила: ее можно присвоить указателю, и указатель можно сравнить с нулевой константой. Чтобы показать, что нуль — это специальное значение для указателя, вместо цифры нуль, как правило, записывают NULL — константу, определенную в файле . С этого момента и мы будем ею пользоваться. Проверки if (allocbuf + ALLOCSIZE - allocp >= n) { /* годится */ и if (p >= allocbuf && p < allocbuf + ALLOCSIZE) демонстрируют несколько важных свойств арифметики с указателями. Во-первых, при соблюдении некоторых правил указатели можно сравнивать. Если р и q указывают на элементы одного массива, то к ним можно применять операторы отношения == , != , < , >= и т. д. Например, отношение вида p < q истинно, если р указывает на более ранний элемент массива, чем q . Любой указатель всегда можно сравнить на равенство и неравенство с нулем. А вот для указателей, не указывающих на элементы одного массива, результат арифметических операций или сравнений не определен. (Существует одно исключение: в арифметике с указателями можно использовать адрес несуществующего "следующего за массивом" элемента, т. е. адрес того "элемента", который станет последним, если в массив добавить еще один элемент.) Во-вторых, как вы уже, наверное, заметили, указатели и целые можно складывать и вычитать. Конструкция р + n означает адрес объекта, занимающего n -е место после объекта, на который указывает р . Это справедливо безотносительно к типу объекта, на который указывает р ; n автоматически домножается на коэффициент, соответствующий размеру объекта. Информация о размере неявно присутствует в объявлении р . Если, к примеру, int занимает четыре байта, то коэффициент умножения будет равен четырем. Допускается также вычитание указателей. Например, если р и q указывают на элементы одного массива и p есть число элементов от р до q включительно. Этим фактом можно воспользоваться при написании еще одной версии strlen : /* strlen: возвращает длину строки s */ int strlen(char *s) { char *p = s; while (*p != '\0' ) p++; return p - s; } В своем объявлении р инициализируется значением s , т. е. вначале р указывает на первый символ строки. На каждом шаге цикла while проверяется очередной символ; цикл продолжается до тех пор, пока не встретится '\0' . Каждое продвижение указателя р на следующий символ выполняется инструкцией р++ , и разность p- s дает число пройденных символов, т. е. длину строки. (Число символов в строке может быть слишком большим, чтобы хранить его в переменной типа int . Тип ptrdiff_t , достаточный для хранения разности (со знаком) двух указателей, определен в заголовочном файле . Однако, если быть очень осторожными, нам следовало бы для возвращаемого результата использовать тип size_t , в этом случае наша программа соответствовала бы стандартной библиотечной версии. Тип size_t есть тип беззнакового целого, возвращаемого оператором sizeof .) Арифметика с указателями учитывает тип: если она имеет дело со значениями float , занимающими больше памяти, чем char , и р — указатель на float , то р++ продвинет р на следующее значение float . Это значит, что другую версию alloc , которая имеет дело с элементами типа float , а не char , можно получить простой заменой в alloc и afree всех char на float . Все операции с указателями будут автоматически откорректированы в соответствии с размером объектов, на которые указывают указатели. Можно производить следующие операции с указателями: присваивание значения указателя другому указателю того же типа, сложение и вычитание указателя и целого, вычитание и сравнение двух указателей, указывающих на элементы одного и того же массива, а также присваивание указателю нуля и сравнение указателя с нулем. Других операций с указателями производить не допускается. Нельзя складывать два указателя, перемножать их, делить, сдвигать, выделять разряды; указатель нельзя складывать со значением типа float или double ; указателю одного типа нельзя даже присвоить указатель другого типа, не выполнив предварительно операции приведения (исключение составляют лишь указатели типа void* ). 5.5. Символьные указатели функции Строковая константа, написанная в виде "Я строка" есть массив символов. Во внутреннем представлении этот массив заканчивается нулевым символом '\0' , по которому программа может найти конец строки. Число занятых ячеек памяти на одну больше, чем количество символов, помещенных между двойными кавычками. Чаще всего строковые константы используются в качестве аргументов функций, как, например, в printf("здравствуй, мир\п"); Когда такая символьная строка появляется в программе, доступ к ней осуществляется через символьный указатель; printf получает указатель на начало массива символов. Точнее, доступ к строковой константе осуществляется через указатель на ее первый элемент. Строковые константы нужны не только в качестве аргументов функций. Если, например, переменную pmessage объявить как char *pmessage то присваивание pmessage = "now is the time"; поместит в нее указатель на символьный массив, при этом сама строка не копируется, копируется лишь указатель на нее. Операции для работы со строкой как с единым целым в Си не предусмотрены. Существует важное различие между следующими определениями: char amessage[] = "now is the time"; /* массив */ char *pmessage = "now is the time"; /* указатель */ amessage — это массив, имеющий такой объем, что в нем как раз помещается указанная последовательность символов и '\0' . Отдельные символы внутри массива могут изменяться, но amessage всегда указывает на одно и то же место памяти. В противоположность ему pmessage есть указатель, инициализированный так, чтобы указывать на строковую константу. А значение указателя можно изменить, и тогда последний будет указывать на что-либо другое. Кроме того, результат будет неопределен, если вы попытаетесь изменить содержимое константы. Дополнительные моменты, связанные с указателями и массивами, проиллюстрируем на несколько видоизмененных вариантах двух полезных программ, взятых нами из стандартной библиотеки. Первая из них, функция strcpy(s, t) , копирует строку t в строку s . Хотелось бы написать прямо s=t , но такой оператор копирует указатель, а не символы. Чтобы копировать символы, нам нужно организовать цикл. Первый вариант strcpy , с использованием массива, имеет следующий вид: /* strcpy: копирует t в s; вариант с индексируемым массивом*/ void strcpy(char *s, char *t) { int i; i = 0; while ((s[i] = t[i]) != '\0' ) i++; } Для сравнения приведем версию strcpy с указателями: /* strcpy: копирует t в s: версия 1 (с указателями) */ void strcpy(char *s, char *t) { while ((*s = *t) != '\0' ) { s++; t++; } } Поскольку передаются лишь копии значений аргументов, strcpy может свободно пользоваться параметрами s и t как своими локальными переменными. Они должным образом инициализированы указателями, которые продвигаются каждый раз на следующий символ в каждом из массивов до тех пор, пока в копируемой строке t не встретится '\0' На практике strcpy так не пишут. Опытный программист предпочтет более короткую запись: /* strcpy: копирует t в s; версия 2 (с указателями) */ void strcpy(char *s, char *t) { while ((*s++ = *t++) != '\0') ; } Приращение s и t здесь осуществляется в управляющей части цикла. Значением *t++ является символ, на который указывает переменная t перед тем, как ее значение будет увеличено; постфиксный оператор ++ не изменяет указатель t , пока не будет взят символ, на который он указывает. То же в отношении s : сначала символ запомнится в позиции, на которую указывает старое значение s , и лишь после этого значение переменной s увеличится. Пересылаемый символ является одновременно и значением, которое сравнивается с '\0' . В итоге копируются все символы, включая и заключительный символ '\0' Заметив, что сравнение с '\0' здесь лишнее (поскольку в Си ненулевое значение выражения в условии трактуется и как его истинность), мы можем сделать еще одно и последнее сокращение текста программы: /* strcpy: копирует t в s; версия 3 (с указателями) */ void strcpy(char *s, char *t) { while (*s++ = *t++) ; } Хотя на первый взгляд то, что мы получили, выглядит загадочно, все же такая запись значительно удобнее, и следует освоить ее, поскольку в Си-программах вы будете с ней часто встречаться. Что касается функции strcpy из стандартной библиотеки , то она возвращает в качестве своего результата еще и указатель на новую копию строки. Вторая программа, которую мы здесь рассмотрим, это strcmp(s, t) . Она сравнивает символы строк s и t и возвращает отрицательное, нулевое или положительное значение, если строка s соответственно лексикографически меньше, равна или больше, чем строка t . Результат получается вычитанием первых несовпадающих символов из s и t /* strcmp: выдает < 0 при s < t, 0 при s == t, > 0 при s > t */ int strcmp(char *s, char *t) { int i; for (i = 0; s[i] == t[i]; i++) if (s[i] == '\0') return 0; return s[i] - t[i]; } Та же программа с использованием указателей выглядит так: /* strcmp: выдает < 0 при s < t, 0 при s == t, > 0 при s > t */ int strcmp(char *s, char *t) { for ( ; *s == *t; s++, t++) if (*s == '\o') return 0; return *s - *t; } Поскольку операторы ++ и -- могут быть или префиксными, или постфиксными, встречаются (хотя и не так часто) другие их сочетания с оператором * . Например: *--р уменьшит р прежде, чем по этому указателю будет получен символ. Например, следующие два выражения: *р++ = val; /* поместить val в стек */ val = *--р; /* взять из стека значение и поместить в val */ являются стандартными для посылки в стек и взятия из стека (см. параграф 4.3.). Объявления функций, упомянутых в этом параграфе, а также ряда других стандартных функций, работающих со строками, содержатся в заголовочном файле Упражнение 5.3. Используя указатели, напишите функцию strcat , которую мы рассматривали в главе 2 (функция strcat(s, t) копирует строку t в конец строки s). Упражнение 5.4. Напишите функцию strend(s, t) , которая выдает 1, если строка t расположена в конце строки s , и нуль в противном случае. Упражнение 5.5. Напишите варианты библиотечных функций strncpy , strncat и strncmp , которые оперируют с первыми символами своих аргументов, число которых не превышает n . Например, strncpy (t, s, n) копирует не более n символов t в s . Полные описания этих функций содержатся в приложении В. Упражнение 5.6. Отберите подходящие программы из предыдущих глав и упражнений и перепишите их, используя вместо индексирования указатели. Подойдут, в частности, программы getline (главы 1 и 4), atoi , itoa и их варианты (главы 2, 3 и 4), reverse (глава 3), а также strindex и getop (глава 4). 5.6. Массивы указателей, указатели на указатели Как и любые другие переменные, указатели можно группировать в массивы. Для иллюстрации этого напишем программу, сортирующую в алфавитном порядке текстовые строки; это будет упрощенный вариант программы sort системы UNIX. В главе 3 мы привели функцию сортировки по Шеллу, которая упорядочивает массив целых, а в главе 4 улучшили ее, повысив быстродействие. Те же алгоритмы используются и здесь, однако теперь они будут обрабатывать текстовые строки, которые могут иметь разную длину и сравнение или перемещение которых невозможно выполнить за одну операцию. Нам необходимо выбрать некоторое представление данных, которое бы позволило удобно и эффективно работать с текстовыми строками произвольной длины. Для этого воспользуемся массивом указателей на начала строк. Поскольку строки в памяти расположены вплотную друг к другу, к каждой отдельной строке доступ просто осуществлять через указатель на ее первый символ. Сами указатели можно организовать в виде массива. Одна из возможностей сравнить две строки — передать указатели на них функции strcmp . Чтобы поменять местами строки, достаточно будет поменять местами в массиве их указатели (а не сами строки). Здесь снимаются сразу две проблемы: одна — связанная со сложностью управления памятью, а вторая - с большими накладными расходами при перестановках самих строк. Процесс сортировки распадается на три этапа: чтение всех строк из ввода сортировка введенных строк печать их по порядку Как обычно, выделим функции, соответствующие естественному делению задачи, и напишем главную программу main , управляющую этими функциями. Отложим на время реализацию этапа сортировки и сосредоточимся на структуре данных и вводе-выводе. Программа ввода должна прочитать и запомнить символы всех строк, а также построить массив указателей на строки. Она, кроме того, должна подсчитать число введенных строк — эта информация понадобится для сортировки и печати. Так как функция ввода может, работать только с конечным числом строк, то, если их введено слишком много, она будет выдавать некоторое значение, которое никогда не совпадет с количеством строк, например -1. Программа вывода занимается только тем, что печатает строки, причем в том порядке, в котором расположены указатели на них в массиве. #include #include #define MAXLINES 5000 /* максимальное число строк */ char *lineptr[MAXLINES]; /* указатели на строки */ int readlines(char *lineptr[], int nlines); void wntelines(char *lineptr[], int nlines); void qsort(char *lineptr[], int left, int right); /* сортировка строк */ main() { int nlines; /* количество прочитанных строк */ if ((nlines = readlinesdineptr, MAXLINES)) >= 0) { qsort(lineptr, 0, nlines-1); writelines(lineptr, nlines); return 0; } else { printf("ошибка: слишком много строк\п"); return 1; } } #define MAXLEN 1000 /* максимальная длина строки */ int getline(char *, int); char *alloc(int); /* readlines: чтение строк */ int readlines(char *lineptr[], int maxlines) { int len, nlines; char *p, line[MAXLEN]; nlines = 0; while ((len = getline(line, MAXLEN)) > 0) if (nlines >= maxlines I ! (p = alloc(len)) == NULL) return -1; else { line[len-1] = '\0'; /* убираем символ \n */ strcpy(p, line); lineptr[nlines++] = p; } return nlines; /* writelines: печать строк */ void writelines(char *lineptr[], int nlines) { int i; for (i = 0; i < nlines; i++) printf("%s\n", lineptr[i]); } Функция getline взята из параграфа 1.9. Основное новшество здесь — объявление lineptr : char *lineptr[MAXLINES] в котором сообщается, что lineptr есть массив из MAXLINES элементов, каждый из которых представляет собой указатель на char . Иначе говоря, lineptr[i] — указатель на символ, a *lineptr[i] — символ, на который он указывает (первый символ i -й строки текста). Так как lineptr — имя массива, его можно трактовать как указатель, т. е. так же, как мы это делали в предыдущих примерах, и writelines переписать следующим образом: /* writelines: печать строк */ void writelines(char *lineptr[], int nlines) { while (nlines-- > 0) printf( "%s\n", *lineptr++); } Вначале *lineptr указывает на первую строку; каждое приращение указателя приводит к тому, что *lineptr указывает на следующую строку, и делается это до тех пор, пока nlines не станет нулем. Теперь, когда мы разобрались с вводом и выводом, можно приступить к сортировке. Быструю сортировку, описанную в главе 4, надо несколько модифицировать: нужно изменить объявления, а операцию сравнения заменить обращением к strcmp . Алгоритм остался тем же, и это дает нам определенную уверенность в его правильности. /* qsort: сортирует v[left]...v[right] по возрастанию */ void qsort(char *v[], int left, int right) { int i, last; void swap(char *v[], int i, int j); if (left >= right) /* ничего не делается, если в массиве */ return; /* менее двух элементов */ swap(v, left, (left+ right)/2); last = left; for (i = left+1; i <= right; i++) if (strcmp(v[i], v[left]) < 0) swap(v, ++last, i); swap(v, left, last); qsort(v, left, last-1); qsort(v, last+1, right); } Небольшие поправки требуются и в программе перестановки. /* swap: поменять местами v[i] и v[j] */ void swap(char *v[], int i, int j) { char *temp; temp = v[i]; v[i] = v[j]; v[j] = temp; } Так как каждый элемент массива v (т. е. lineptr ) является указателем на символ, temp должен иметь тот же тип, что и v — тогда можно будет осуществлять пересылки между temp и элементами v |