Б. Керриган, Д. Ритчи Язык программирования C. Б. Керниган, Д. зык программирования и . Издание 3е, исправленное Перевод с английского под редакцией Вс. С. Штаркмана СанктПетербург 2003
 Скачать 31.48 Mb.
|
|
Глава 5. Указатели и массивы strcat(out, token); strcat(out, Приведенные программы служат только иллюстративным целям и не вполне надежны. Что касается то ее возможности существенно огра- ничены. Она может работать только с простыми типами вроде char и int и не справляется с типами аргументов в функциях и с вроде const. Лишние пробелы для нее опасны. Она не предпринимает ни- каких мер по выходу из ошибочной ситуации, и поэтому неправильные описания также ей противопоказаны. Устранение этих недостатков мы оставляем для упражнений. Ниже приведены глобальные переменные и главная программа main. h> «include MAXTOKEN 100 PARENS, BRACKETS }; void dcl(void); void dirdcl(void); int int tokentype; char char char char /* тип последней лексемы */ /* текст последней лексемы */ /* имя /* тип = char, int и т.д. */ /* выдаваемый текст */ /* преобразование в словесное описание */ while (gettoken() EOF) { strcpy(datatype, token); out[0] = /* разбор остальной части строки %s name, out, datatype); /* 1-я лексема в строке */ /* это тип данных */ / return 0; Сложные объявления _ Функция gettoken пропускает пробелы и табуляции и затем получает следующую лексему из ввода; "лексема" (token) - это имя, или пара круг- лых скобок, или пара квадратных скобок (быть может, с помещенным в них числом), или любой другой единичный символ. int gettoken(void) /* возвращает следующую лексему */ { • void ungetch(int); char *p = token; while = ' ' с == if (c if = strcpy(token, return tokentype = PARENS; } else { return tokentype = } } else if (c for (*p++ c; (*p++ = ) = return tokentype = BRACKETS; } else if { (*p++ = c; = ) = c; = return tokentype = NAME; } else return tokentype = c; Функции getch и ungetch были рассмотрены в главе 4. Обратное преобразование реализуется легче, особенно если не прида- вать значения тому, что будут генерироваться лишние скобки. Программа превращает фразу вроде есть функция, возвращающая указатель на массив указателей на функции, возвращающие которую мы бу- дем представлять в виде х () * [] * () char _ Глава 5. Указатели и массивы в объявление char Такой сокращенный входной синтаксис позволяет повторно пользовать- ся функцией gettoken. Функция использует те же самые внешние переменные, что и /* преобразует словесное описание в объявление */ { int type; while (gettoken() != EOF) { while = != if (type PARENS type BRACKETS) strcat(qut, token); else if (type == { sprintf(temp, out); strcpy(out, temp); } else if (type == NAME) { token, out); strcpy(out, temp); } else printf( "неверный элемент %s в token); out); } return 0; Упражнение 5.18. Видоизмените таким образом, чтобы она обра- батывала ошибки во входной информации. Упражнение 5.19. Модифицируйте undcl так, чтобы она не генерировала лишних скобок. Упражнение 5.20. Расширьте возможности чтобы обрабатывала объявления с типами аргументов функции, вроде const и т. п. Глава 6 Структуры Структура - это одна или несколько переменных (возможно, различ- ных типов), которые для удобства работы с ними сгруппированы под од- ним именем. (В некоторых языках, в частности в Паскале, структуры на- зываются записями.) Структуры помогают в организации сложных дан- ных (особенно в больших программах), поскольку позволяют группу свя- занных между собой переменных трактовать не как множество отдель- ных элементов, а как единое целое. Традиционный пример структуры - строка платежной ведомости. Она содержит такие сведения о служащем, как его полное имя, адрес, номер карточки социального страхования, зарплата и т. д. Некоторые из этих характеристик сами могут быть структурами: полное имя со- стоит из нескольких компонент (фамилии, имени и отчества); аналогич- но адрес, и даже зарплата. Другой пример (более типичный для Си) - из области графики: точка есть пара координат, прямоугольник есть пара точек и т. д. Главные изменения, внесенные стандартом ANSI в отношении струк- тур, - это введение для них операции присваивания. Структуры могут копироваться, над ними могут выполняться операции присваивания, их можно передавать функциям в качестве аргументов, а функции могут возвращать их в качестве результатов. В большинстве компиляторов уже давно реализованы эти возможности, но теперь они точно оговорены стан- дартом. Для автоматических структур и массивов теперь также допуска- ется инициализация. Основные сведения о структурах Сконструируем несколько графических структур. В качестве основно- го объекта выступает точка с координатами х и у целого типа. Глава 6. Структуры (4,3) Указанные две компоненты можно поместить в структуру, объявленную, например, следующим struct point { x; int у; } ; Объявление структуры начинается с ключевого слова st ruct и содер- жит список объявлений, заключенный в фигурные скобки. За словом может следовать имя, называемое структуры, (point в на- шем случае). Тег дает название структуре данного вида и далее может служить кратким той части объявления, которая заключе- на в фигурные скобки. Перечисленные в структуре переменные называются элементами Имена элементов и тегов без каких-либо коллизий могут со- впадать с именами обычных переменных (т. е. не элементов), так как они всегда различимы по контексту. Более того, одни и те же имена элемен- тов могут встречаться в разных структурах, хотя, если следовать хороше- му стилю программирования, лучше одинаковые имена давать только близким по смыслу объектам. Объявление структуры определяет тип. За правой фигурной скобкой, закрывающей список элементов, могут следовать переменные точно так же, как они могут быть указаны после названия любого базового типа. Таким образом, выражение struct { } х, у, 2; с зрения синтаксиса аналогично выражению ' int x, у, z; в том смысле, что и то и другое объявляет х, у и z переменными указанно- го типа; и то и другое приведет к выделению памяти соответствующего • размера. ' От слова tag — ярлык, этикетка. - Примеч. пер. некоторых изданиях (в том числе во 2-м издании на русском языке этой книги) members как Примеч. ред. сведения о структурах Объявление структуры, не содержащей списка переменных, не ре- зервирует памяти; оно просто описывает шаблон, или образец структу- ры. Однако если структура имеет тег, то этим тегом далее можно пользо- ваться при определении структурных объектов. с помощью заданного описания структуры point строка struct point pt; определяет структурную переменную pt типа st point. Структурную переменную при ее определении можно формируя список инициализаторов ее элементов в виде константных выражений: struct point = { 320, 200 }; Инициализировать автоматические структуры можно также присваива- нием или к функции, возвращающей структуру соответству- ющего типа. Доступ к отдельному элементу структуры осуществляется посредством конструкции вида: элемент Оператор доступа к элементу структуры . соединяет имя структуры и имя элемента. Чтобы напечатать, например, координаты точки pt, годит- ся следующее обращение к pt.x, Другой пример: чтобы вычислить расстояние от начала координат (0,0) до pt, можно написать double dist, sqrt(double); dist = * pt.x + * pt.y); Структуры могут быть вложены друг в друга. Одно из возможных пред- ставлений прямоугольника - это пара точек на углах одной из его диаго- налей: У Pt1 struct rect { struct point pt1; struct point i; 168 6. Структуры Структура rect содержит две структуры point. Если мы объявим screen как struct rect screen; то обращается к координате х точки из 6.2. Структуры и функции Единственно возможные операции над структурами - это их копиро- вание, присваивание, взятие адреса с помощью & и осуществление доступа к ее элементам. Копирование и присваивание включают в себя пе- редачу функциям аргументов и возврат ими значениий. Структуры нельзя сравнивать. Инициализировать структуру можно константных значений ее элементов; автоматическую структуру также можно инициа- лизировать присваиванием. Чтобы лучше познакомиться со структурами, напишем несколько функ- ций, манипулирующих точками и прямоугольниками. Возникает вопрос: а как передавать функциям названные объекты? Существует по крайней три подхода: передавать компоненты по отдельности, передавать всю структуру целиком и передавать указатель на структуру. Каждый подход имеет свои плюсы и минусы. Первая функция, получает два целых значения и возвраща- ет структуру point. /* makepoint: формирует точку по х и у */ struct point x, int у) { struct point temp; = x; = у; return temp; } Заметим: никакого конфликта между именем аргумента и именем эле- мента структуры не возникает; более того, сходство подчеркивает род- ство обозначаемых им объектов. Теперь с помощью makepoint можно выполнять динамическую иници- ализацию любой структуры или формировать структурные аргументы для той или иной функции: 6.2. Структуры и функции _ struct rect screen; struct point middle; struct point int); = 0); = YMAX); middle = + + Следующий шаг состоит в определении ряда функций, реализующих различные операции над точками. В качестве примера рассмотрим следу- ющую функцию: /* addpoint: сложение двух точек */ struct point addpoint(struct point p1, struct point p2) { += += p2.y; return } Здесь оба аргумента и возвращаемое значение - структуры. Мы увеличи- ваем компоненты прямо в р1 и не используем для этого временной пере- чтобы подчеркнуть, что структурные параметры передаются по значению так же, как и любые другие. В качестве другого примера приведем функцию которая про- веряет: находится ли точка внутри прямоугольника, относительно кото- рого мы принимаем соглашение, что в него входят его левая и нижняя стороны, но не входят верхняя и правая. /* ptinrect: возвращает 1, если р в и 0 в противном случае */ int ptinrect(struct point p, struct rect r) return >= && < && >= && < Здесь предполагается, что прямоугольник представлен в стандартном виде, т. е. координаты точки pt1 меньше соответствующих координат точ- ки Следующая функция гарантирует получение прямоугольника в каноническом виде. b) < (D) ? (а) : (b)) «define b) (b) ? : Глава 6. Структуры /* канонизация координат */ struct rect rect r) { struct rect temp; = r.pt2.x); = r.pt2.y); = r.pt2.x); = return temp; > Если функции передается большая структура, то, чем копировать ее це- эффективнее передать указатель на нее. Указатели на структуры ничем не отличаются от указателей на обычные переменные. Объявление struct point *pp; сообщает, что рр - это указатель на структуру типа point. Если рр указывает на структуру point, то *рр - это сама структура, а х и у - ее элементы. Используя указатель рр, мы могли бы написать point origin, *pp; рр = &origin; (*pp).x, (*pp).y); Скобки в необходимы, поскольку приоритет оператора . выше, чем приоритет Выражение х будет проинтерпретировано как что неверно, поскольку х не является указателем. Указатели на структуры используются весьма часто, поэтому для до- ступа к ее элементам была придумана еще одна, более короткая форма записи. Если р — указатель на структуру, то р -> элемент-структуры есть ее отдельный элемент. (Оператор -> состоит из знака -, за которым сразу следует знак >.) Поэтому printf можно переписать в виде pp->x, pp->y); Операторы . и -> выполняются слева направо. Таким образом, при на- личии объявления \ struct rect r. *rp = & r ; следующие четыре выражения будут эквивалентны: 6.3. Массивы структур 171 pt1 (rp->pt1).x Операторы доступа к элементам структуры . и -> вместе с оператора- ми вызова функции и индексации массива [ ] занимают самое высокое положение в иерархии приоритетов и выполняются раньше любых дру- гих операторов. если задано объявление struct { int char > TO ++p->len увеличит на 1 значение элемента структуры len, а не указатель р, посколь- ку в этом выражении как бы неявно присутствуют скобки: Что- бы изменить порядок выполнения операций, нужны явные скобки. Так, в прежде чем взять значение программа прирастит указа- тель р. В указатель р увеличится после того, как будет взято значение len (в последнем случае скобки не обязательны). тем же правилам r обозначает содержимое объекта, на который указывает *p->str++ прирастит указатель после получения значе- ния объекта, на который он указывал (как и в выражении *s++); увеличит значение объекта, на который указывает st r; *p++->st r увеличит р после получения того, на что указывает st r. 6.3. Массивы структур Рассмотрим программу, определяющую число вхождений каждого клю- чевого слова в текст Си-программы. Нам нужно уметь хранить ключевые слова в виде массива строк и счетчики ключевых слов в виде массива целых. Один из возможных вариантов - это иметь два параллельных мас- сива: char int Однако именно тот что они параллельны, подсказывает нам дру- гую организацию хранения - через массив структур. Каждое ключевое Глава 6. Структуры слово можно описать парой характеристик char int count; Такие пары составляют массив. Объявление struct key { char int } объявляет структуру типа key и определяет массив keytab, каждый эле- мент которого является структурой этого типа и которому где-то будет выделена память. Это же можно записать и по-другому: struct key { char *word; int count; }; struct key Так как keytab содержит постоянный набор имен, его легче всего сде- лать внешним массивом и инициализировать один раз в момент опреде- ления. Инициализация структур аналогична ранее демонстрировавшим- ся инициализациям — за определением следует список инициализаторов, заключенный в фигурные скобки: struct key { char int count; } = { "auto", 0, "break", 0, "case", 0, "char", 0, "const", 0, 0, Л ... V "unsigned", 0, "void", 0, "volatile", 0, "while", 0 6.3. Массивы структур Инициализаторы задаются парами, чтобы соответствовать конфигурации структуры. Строго говоря, пару инициализаторов для каждой отдельной структуры следовало бы заключить в фигурные скобки, как, например, в { "auto", 0 }, { "break", 0 }, { "case", 0 }, Однако когда инициализаторы - простые константы или строки симво- лов и все они имеются в наличии, во внутренних скобках нет необходи- мости. Число элементов массива tab будет вычислено по количеству инициализаторов, поскольку они представлены полностью, а внутри квад- ратных ничего не задано. Программа подсчета ключевых слов начинается с определения keytab. Программа main читает ввод, многократно обращаясь к функции и получая на каждом ее вызове очередное слово. Каждое слово ищется в keytab. Для этого используется функция бинарного поиска, которую мы написали в главе 3. Список ключевых слов должен быть упорядочен в ал- фавитном порядке. MAXWORD 100 int *, int); int binsearch(char *, struct key *, int); /* подсчет ключевых слов Си */ { int n; char MAXWORD) EOF) if if = binsearch(word, keytab, NKEYS)) 0) for (n 0; n NKEYS; if > 0) return 0; _ Глава 6. Структуры binsearch: найти слово в - Т] */ int struct key int n) { int int high, mid; low = 0; high = n - while (low <= high) { mid = (low + high)/2; if = < 0) high = mid - 1; else if (cond > 0) low = mid + else return mid; > return Чуть позже мы рассмотрим функцию а сейчас нам достаточно знать, что при каждом ее вызове получается очередное слово, которое за- поминается в массиве, заданном первым аргументом. NKEYS - количество ключевых слов в keytab. Хотя мы могли бы подсчи- тать число таких слов вручную, гораздо легче и сделать это с помощью машины, особенно если список ключевых слов может быть изменен. Одно из возможных решений - поместить в конец списка ини- циализаторов пустой указатель (NULL) и затем перебирать в цикле эле- менты keytab, пока не встретится концевой элемент. Но возможно и более простое решение. Поскольку размер массива пол- ностью определен во время компиляции и равен произведению количе- ства элементов массива на размер его отдельного элемента, число элемен- тов массива можно вычислить по формуле размер keytab / размер struct key В Си имеется унарный оператор который работает во время ком- пиляции. Его можно применять для вычисления размера любого объек- та. Выражения sizeof объект и sizeof выдают целые значения, равные размеру указанного объекта или типа 6.3. Массивы структур в байтах. (Строго говоря, sizeof выдает беззнаковое целое, тип которого size_t определен в заголовочном файле h>.) Что объек- та, то это может быть переменная, массив или структура. В качестве име- ни типа может выступать имя базового типа (int, или имя про- изводного типа, например структуры или указателя. В нашем случае, чтобы вычислить количество ключевых слов, размер массива надо поделить на размер одного элемента. Указанное вычисле- ние используется в инструкции ine для установки значения NKEYS (sizeof keytab / Этот же результат можно получить другим способом - поделить размер массива на размер какого-то его конкретного элемента: NKEYS (sizeof keytab / sizeof Преимущество такого рода записей в том, что их не надо корректировать при изменении типа. Поскольку препроцессор не обращает внимания на имена типов, опе- ратор sizeof нельзя применять в Но в выражение препроцес- сором не вычисляется, так что предложенная нами запись допустима. Теперь поговорим о функции getword. Мы написали в несколь- ко более общем виде, чем требуется для нашей программы, но она от это- го не стала заметно сложнее. Функция берет из входного потока следующее "слово". Под словом понимается цепочка букв-цифр, начина- ющаяся с буквы, или отдельный символ, отличный от символа-раздели- теля. В случае конца файла функция возвращает EOF, в остальных случа- ях ее значением является код первого символа слова или сам символ, если это не буква. getword: принимает следующее слово или символ из ввода */ int getword (char *word, int { int c, getch(void); void ungetch(int); char *w = word; while (isspace(c = if (c != EOF) *w++ = if { *w = return |