[ «ЯЗЫК С Аннотация Язык C(произносится си) — это универсальный язык программирования, для которого характерны экономичность выражения, современный поток управления и структуры данных, богатый набор операторов. Язык C не ...»
Б.В. Керниган,
Д.М. Ричи.
ЯЗЫК С
Аннотация
Язык "C"(произносится "си") — это универсальный язык программирования, для
которого характерны экономичность выражения, современный поток управления и
структуры данных, богатый набор операторов. Язык "C" не является ни языком "очень
высокого уровня", ни "большим" языком, и не предназначается для некоторой
специальной области применения. но отсутствие ограничений и общность языка
делают его более удобным и эффективным для многих задач, чем языки, предположительно более мощные.
Язык "C", первоначально предназначавшийся для написания операционной системы "UNIX" на ЭВМ DEC PDP-11, был разработан и реализован на этой системе Деннисом Ричи. Операционная система, компилятор с языка "C" и по существу все прикладные программы системы "UNIX" (включая все программное обеспечение, использованное при подготовке этой книги) написаны на "C". Коммерческие компиляторы с языка "C" существуют также на некоторых других ЭВМ, включая IBM SYSTEM/370, HONEYWELL 6000, INTERDATA 8/32. Язык "C", однако, не связан с какими-либо определенными аппаратными средствами или системами, и на нем легко писать программы, которые можно пропускать без изменений на любой ЭВМ, имеющей "C"-компилятор.
Эта книга предназначена для того, чтобы помочь читателю научиться программировать на языке "C". Она содержит учебное введение, цель которого — позволить новым пользователям начать программировать как можно быстрее, отдельные главы по всем основным особенностям языка и справочное руководство.
Обучение построено в основном на чтении, написании и разборе примеров, а не голой формулировке правил. Примеры, приводимые в книге, по большей части являются законченными реальными программами, а не отдельными фрагментами. Все примеры были проверены непосредственно с текста книги, где они напечатаны в виде, пригодном для ввода в машину. Кроме указаний о том, как сделать использование языка более эффективным, мы также пытались, где это возможно, проиллюстрировать полезные алгоритмы и принципы хорошего стиля и разумной разработки.
Настоящая книга не является вводным курсом в программирование; она предполагает определенное знакомство с основными понятиями программирования такими как переменные, операторы присваивания, циклы, функции. Тем не менее и новичок в программировании должен оказаться в состоянии читать подряд и освоиться с языком, хотя при этом была бы полезной помощь более опытного коллеги.
По нашему опыту, "C" показал себя приятным, выразительным и разносторонним языком на широком множестве разнообразных программ. Его легко выучить, и он не теряет своих качеств с ростом опыта программиста. Мы надеемся, что эта книга поможет вам хорошо его использовать.
Вдумчивая критика и предложения многих наших друзей и коллег очень много добавили как для самой книги, так и для нашего удовольствия при ее написании. В частности, Майк Биапси, Джим Блю, Стью Фельдман, Доуг Мак-Илрой, Билл Рум, Боб Розин и Ларри Рослер тщательно прочитали множество вариантов. Мы также обязаны Элю Ахо, Стиву Борну, Дэву Двораку, Чаку Хэлею, Дебби Хэлей, Мариону Харрису, Рику Холту, Стиву Джонсону, Джону Машею, Бобу Митцу, Ральфу Мьюа, Питеру Нельсону, Эллиоту Пинсону, Биллу Плагеру, Джерри Спиваку, Кену Томпсону и Питеру Вейнбергеру за полезные замечания на различных этапах и Майку Лоску и Джо Осанна за неоценимую помощь при печатании книги.
Брайен В. Керниган Деннис М. Ричи Содержание ВВЕДЕНИЕ 1. УЧЕБНОЕ ВВЕДЕНИЕ 1.1. HАЧИНАЕМ 1.2. ПЕРЕМЕННЫЕ И АРИФМЕТИКА 1.3. ОПЕРАТОР FOR 1.4. СИМВОЛИЧЕСКИЕ КОНСТАНТЫ 1.5. НАБОР ПОЛЕЗНЫХ ПРОГРАММ 1.5.1. ВВОД И ВЫВОД СИМВОЛОВ 1.5.2. КОПИРОВАНИЕ ФАЙЛА 1.5.3. ПОДСЧЕТ СИМВОЛОВ 1.5.4. ПОДСЧЕТ СТРОК 1.5.5. ПОДСЧЕТ СЛОВ 1.6. МАССИВЫ 1.7. ФУНКЦИИ 1.8. АРГУМЕНТЫ — ВЫЗОВ ПО ЗНАЧЕНИЮ 1.9. МАССИВЫ СИМВОЛОВ 1.10. ОБЛАСТЬ ДЕЙСТВИЯ: ВНЕШНИЕ ПЕРЕМЕННЫЕ 2. ТИПЫ, ОПЕРАЦИИ И ВЫРАЖЕНИЯ 2.1. ИМЕНА ПЕРЕМЕННЫХ 2.2. ТИПЫ И РАЗМЕРЫ ДАННЫХ 2.3. КОНСТАНТЫ 2.3.1. СИМВОЛЬНАЯ КОНСТАНТА 2.3.2. КОНСТАНТНОЕ ВЫРАЖЕНИЕ 2.3.3. СТРОЧНАЯ КОНСТАНТА 2.4. ОПИСАНИЯ 2.5. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ
2.6. ОПЕРАЦИИ ОТНОШЕНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ
2.7. ПРЕОБРАЗОВАНИЕ ТИПОВ 2.8. ОПЕРАЦИИ УВЕЛИЧЕНИЯ И УМЕНЬШЕНИЯ 2.9. ПОБИТОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ 2.10. ОПЕРАЦИИ И ВЫРАЖЕНИЯ ПРИСВАИВАНИЯ 2.11. УСЛОВНЫЕ ВЫРАЖЕНИЯ 2.12. СТАРШИНСТВО И ПОРЯДОК ВЫЧИСЛЕНИЯ 3. ПОТОК УПРАВЛЕНИЯ 3.1. ОПЕРАТОРЫ И БЛОКИ 5.8. МАССИВЫ УКАЗАТЕЛЕЙ; УКАЗАТЕЛИ УКАЗАТЕЛЕЙ 7.2. СТАНДАРТНЫЙ ВВОД И ВЫВОД — ФУНКЦИИ GETCHAR И PUTCHAR 7.9.1. ПРОВЕРКА ВИДА СИМВОЛОВ И ПРЕОБРАЗОВАНИЯДЕСКРИПТОРЫ ФАЙЛОВ
НИЗКОУРОВНЕВЫЙ ВВОД/ВЫВОД — ОПЕРАТОРЫ READ И WRITE
ОТКРЫТИЕ, СОЗДАНИЕ, ЗАКРЫТИЕ И РАСЦЕПЛЕНИЕ (UNLINK)
ПРОИЗВОЛЬНЫЙ ДОСТУП — SEEK И LSEEK
ПРИМЕР — РЕАЛИЗАЦИЯ ФУНКЦИЙ FOPEN И GETC
ПРИМЕР — РАСПЕЧАТКА СПРАВОЧНИКОВ
ПРИМЕР — РАСПРЕДЕЛИТЕЛЬ ПАМЯТИ
9. ПРИЛОЖЕНИЕ А: СПРАВОЧНОЕ РУКОВОДСТВО ПО ЯЗЫКУ 'C' 14.3. ПЛАВАЮЩИЕ И ЦЕЛОЧИСЛЕННЫЕ ВЕЛИЧИНЫ 14.6. АРИФМЕТИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ 15.3. МУЛЬТИПЛИКАТИВНЫЕ ОПЕРАЦИИ 15.9. ПОБИТОВАЯ ОПЕРАЦИЯ ИСКЛЮЧАЮЩЕГО 'ИЛИ' 15.10. ПОБИТОВАЯ ОПЕРАЦИЯ ВКЛЮЧАЮЩЕГО 'ИЛИ' 15.12. ОПЕРАЦИЯ ЛОГИЧЕСКОГО 'ИЛИ' 16.1. СПЕЦИФИКАТОРЫ КЛАССА ПАМЯТИ 16.5. ОПИСАНИЕ СТРУКТУР И ОБЪЕДИНЕНИЙ 17.2. СОСТАВНОЙ ОПЕРАТОР (ИЛИ БЛОК) 19. ПРАВИЛА, ОПРЕДЕЛЯЮЩИЕ ОБЛАСТЬ ДЕЙСТВИЯ 19.1. ЛЕКСИЧЕСКАЯ ОБЛАСТЬ ДЕЙСТВИЯ 19.2. ОБЛАСТЬ ДЕЙСТВИЯ ВНЕШНИХ ИДЕНТИФИКАТОРОВ 20. СТРОКИ УПРАВЛЕНИЯ КОМПИЛЯТОРОМ 22.3. МАССИВЫ, УКАЗАТЕЛИ И ИНДЕКСАЦИЯ 22.4. ЯВНЫЕ ПРЕОБРАЗОВАНИЯ УКАЗАТЕЛЕЙ 29. ТАБЛИЦА ИЗОБРАЖЕНИЙ НЕПЕЧАТНЫХ СИМВОЛОВ ЯЗЫКА "C". Введение Язык "C" является универсальным языком программирования. Он тесно связан с операционной системой "UNIX", так как был развит на этой системе и так как "UNIX" и ее программное обеспечение написано на "C". Сам язык, однако, не связан с какой-либо одной операционной системой или машиной; и хотя его называют языком системного программирования, так как он удобен для написания операционных систем, он с равным успехом использовался при написании больших вычислительных программ, программ для обработки текстов и баз данных.Язык "C" — это язык относительно "низкого уровня". В такой характеристике нет ничего оскорбительного; это просто означает, что "C" имеет дело с объектами того же вида, что и большинство ЭВМ, а именно, с символами, числами и адресами. Они могут объединяться и пересылаться посредством обычных арифметических и логических операций, осуществляемых реальными ЭВМ.
В языке "C" отсутствуют операции, имеющие дело непосредственно с составными объектами, такими как строки символов, множества, списки или с массивами, рассматриваемыми как целое. Здесь, например, нет никакого аналога операциям PL/1, оперирующим с целыми массивами и строками. Язык не предоставляет никаких других возможностей распределения памяти, кроме статического определения и механизма стеков, обеспечиваемого локальными переменных функций;
здесь нет ни "куч"(HEAP), ни "сборки мусора", как это предусматривается в АЛГОЛЕНаконец, сам по себе "C" не обеспечивает никаких возможностей ввода-вывода:
здесь нет операторов READ или WRITE и никаких встроенных методов доступа к файлам. Все эти механизмы высокого уровня должны обеспечиваться явно вызываемыми функциями.
Аналогично, язык "C" предлагает только простые, последовательные конструкции потоков управления: проверки, циклы, группирование и подпрограммы, но не мультипрограммирование, параллельные операции, синхронизацию или сопрограммы.
Хотя отсутствие некоторых из этих средств может выглядеть как удручающая неполноценность ("выходит, что я должен обращаться к функции, чтобы сравнить две строки символов?!"), но удержание языка в скромных размерах дает реальные преимущества. Так как "C" относительно мал, он не требует много места для своего описания и может быть быстро выучен. Компилятор с "C" может быть простым и компактным. Кроме того, компиляторы легко пишутся; при использовании современной технологии можно ожидать написания компилятора для новой ЭВМ за пару месяцев и при этом окажется, что 80 процентов программы нового компилятора будет общей с программой для уже существующих компиляторов. Это обеспечивает высокую степень мобильности языка. Поскольку типы данных и стуктуры управления, имеющиеся в "C", непосредственно поддерживаются большинством существующих ЭВМ, библиотека, необходимая во время прогона изолированных программ, оказывается очень маленькой. На PDP -11, например, она содержит только программы для 32-битового умножения и деления и для выполнения программ ввода и вывода последовательностей. Конечно, каждая реализация обеспечивает исчерпывающую, совместимую библиотеку функций для выполнения операций ввода-вывода, обработки строк и распределения памяти, но так как обращение к ним осуществляется только явно, можно, если необходимо, избежать их вызова; эти функции могут быть компактно написаны на самом "C".
Опять же из-за того, что язык "C" отражает возможности современных компьютеров, программы на "C" оказываются достаточно эффективными, так что не возникает побуждения писать вместо этого программы на языке ассемблера.
Наиболее убедительным примером этого является сама операционная система "UNIX", которая почти полностью написана на "C". Из 13000 строк программы системы только около 800 строк самого низкого уровня написаны на ассемблере. Кроме того, по существу все прикладное программное обеспечение системы "UNIX" написано на "C"; подавляющее большинство пользователей системы "UNIX"(включая одного из авторов этой книги) даже не знает языка ассемблера PDP-11.
Хотя "C" соответствует возможностям многих ЭВМ, он не зависит от какой-либо конкретной архитектуры машины и в силу этого без особых усилий позволяет писать "переносимые" программы, т.е. программы, которые можно пропускать без изменений на различных аппаратных средствах. В наших кругах стал уже традицией перенос программного обеспечения, разработанного на системе "UNIX", на системы ЭВМ: HONEYWELL, IBM и INTERDATA. Фактически компиляторы с "C" и программное обеспечение во время прогона программ на этих четырех системах, по-видимому, гораздо более совместимы, чем стандартные версии фортрана американского национального института стандартов (ANSI). Сама операционная система "UNIX" теперь работает как на PDP-11, так и на INTERDATA 8/32. За исключением программ, которые неизбежно оказываются в некоторой степени машинно-зависимыми, таких как компилятор, ассемблер и отладчик. Написанное на языке "C" программное обеспечение идентично на обеих машинах. Внутри самой операционной системы 7000 строк программы, исключая математическое обеспечение языка ассемблера ЭВМ и управления операциями ввода-вывода, совпадают на 95 процентов.
Программистам, знакомым с другими языками, для сравнения и противопоставления может оказаться полезным упоминание нескольких исторических, технических и философских аспектов "C".
Многие из наиболее важных идей "C" происходят от гораздо более старого, но все еще вполне жизненного языка BCPL, разработанного Мартином Ричардсом.
Косвенно язык BCPL оказал влияние на "C" через язык "B", написанный Кеном Томпсоном в 1970 году для первой операционной системы "UNIX" на ЭВМ PDP-7.
Хотя язык "C" имеет несколько общих с BCPL характерных особенностей, он никоим образом не является диалектом последнего. И BCPL и "B" — "безтипные" языки; единственным видом данных для них являются машинное слово, а доступ к другим объектам реализуется специальными операторами или обращением к функциям. В языке "C" объектами основных типов данных являются символы, целые числа нескольких размеров и числа с плавающей точкой. Кроме того, имеется иерархия производных типов данных, создаваемых указателями, массивами, структурами, объединениями и функциями.
Язык "C" включает основные конструкции потока управления, требуемые для хорошо структуированных программ: группирование операторов, принятие решений (IF), циклы с проверкой завершения в начале (WHILE, FOR) или в конце (DO) и выбор одного из множества возможных вариантов (SWITCH). (Все эти возможности обеспечивались и в BCPL, хотя и при несколько отличном синтаксисе; этот язык предчувствовал наступившую через несколько лет моду на структурное программирование).
В языке "C" имеются указатели и возможность адресной арифметики.
Аргументы передаются функциям посредством копирования значения аргумента, и вызванная функция не может изменить фактический аргумент в вызывающей программе. Если желательно добиться "вызова по ссылке", можно неявно передать указатель, и функция сможет изменить объект, на который этот указатель указывает.
Имена массивов передаются указанием начала массивов, так что аргументы типа массивов эффективно вызываются по ссылке.
К любой функции можно обращаться рекурсивно, и ее локальные переменные обычно "автоматические", т.е. Создаются заново при каждом обращении. Описание одной функции не может содержаться внутри другой, но переменные могут описываться в соответствии с обычной блочной структурой. Функции в "C" — программе могут транслироваться отдельно. переменные по отношению к функции могут быть внутренними, внешними, но известными только в пределах одного исходного файла, или полностью глобальными. Внутренние переменные могут быть автоматическими или статическими. Автоматические переменные для большей эффективности можно помещать в регистры, но объявление регистра является только указанием для компилятора и никак не связано с конкретными машинными регистрами.
Язык "C" не является языком со строгими типами в смысле паскаля или алгола 68. Он сравнительно снисходителен к преобразованию данных, хотя и не будет автоматически преобразовывать типы данных с буйной непринужденностью языка PL/1. Существующие компиляторы не предусматривают никакой проверки во время выполнения программы индексов массивов, типов аргументов и т.д.
В тех ситуациях, когда желательна строгая проверка типов, используется специальная версия компилятора. Эта программа называется LINT очевидно потому, она выбирает кусочки пуха из вашей программы. Программа LINT не генерирует машинного кода, а делает очень строгую проверку всех тех сторон программы, которые можно проконтролировать во время компиляции и загрузки. Она определяет несоответствие типов, несовместимость аргументов, неиспользованные или очевидным образом неинициализированные переменные, потенциальные трудности переносимости и т.д. Для программ,которые благополучно проходят через LINT, гарантируется отсутствие ошибок типа примерно с той же полнотой, как и для программ, написанных, например, на АЛГОЛЕ-68. Другие возможности программы LINT будут отмечены, когда представится соответствующий случай.
Наконец, язык "C", подобно любому другому языку, имеет свои недостатки.
Некоторые операции имеют неудачное старшинство; некоторые разделы синтаксиса могли бы быть лучше; сушествует несколько версий языка, отличающихся небольшими деталями. Тем не менее язык "C" зарекомендовал себя как исключительно эффективный и выразительный язык для широкого разнообразия применений программирования.
Содержание книги организовано следующим образом.
Глава 1 является учебным введением в центральную часть языка "C".
Цель — позволить читателю стартовать так быстро,как только возможно, так как мы твердо убеждены, что единственный способ изучить новый язык — писать на нем программы. При этом, однако, предполагается рабочее владение основными элементами программирования; здесь не объясняется, что такое ЭВМ или компилятор, не поясняется смысл выражений типа N=N+1. Хотя мы и пытались, где это возможно, продемонстрировать полезную технику программирования. Эта книга не предназначается быть справочным руководством по структурам данных и алгоритмам; там, где мы вынуждены были сделать выбор, мы концентрировались на языке.
В главах со 2-й по 6-ю различные аспекты "C" излагаются более детально и несколько более формально, чем в главе 1, хотя ударение по-прежнему делается на разборе примеров законченных, полезных программ, а не на отдельных фрагментах.
В главе 2 обсуждаются основные типы данных, операторы и выражения. В главе 3 рассматриваются управляющие операторы: IF-ELSE, WHILE, FOR и т.д. Глава 4 охватывает функции и структуру программы — внешние переменные, правила определенных областей действия описания и т.д. В главе 5 обсуждаются указатели и адресная арифметика. Глава 6 содержит подробное описание структур и объединений.
В главе 7 описывается стандартная библиотека ввода-вывода языка "C", которая обеспечивает стандартный интерфейс с операционной системой. Эта библиотека ввода-вывода поддерживается на всех машинах, на которых реализован "C", так что программы, использующие ее для ввода, вывода и других системных функций, могут переноситься с одной системы на другую по существу без изменений.
В главе 8 описывается интерфейс между "C" — программами и операционной системой "UNIX". Упор делается на ввод-вывод, систему файлов и переносимость.
Хотя некоторые части этой главы специфичны для операционной системы "UNIX", программисты, не использующие "UNIX", все же должны найти здесь полезный материал, в том числе некоторое представление о том, как реализована одна версия стандартной библиотеки и предложения для достижения переносимости программы.
Приложение A содержит справочное руководство по языку "C". Оно является "официальным" изложением синтаксиса и семантики "C" и (исключая чей-либо собственный компилятор) окончательным арбитром для всех двусмысленностей и упущений в предыдущих главах.
Так как "C" является развивающимся языком, реализованным на множестве систем, часть материла настоящей книги может не соответствовать текущему состоянию разработки на какой-то конкретной системе. Мы старались избегать таких проблем и предостерегать о возможных трудностях. В сомнительных случаях, однако, мы обычно предпочитали описывать ситуацию для системы "UNIX" PDP-11, так как она является средой для большинства программирующих на языке "C". В приложении а также описаны расхождения в реализациях языка "C" на основных системах.
1. Учебное введение Давайте начнем с быстрого введения в язык "C". Наша цель — продемонстрировать существенные элементы языка на реальных программах, не увязая при этом в деталях, формальных правилах и исключениях. В этой главе мы не пытаемся изложить язык полностью или хотя бы строго (разумеется, приводимые примеры будут корректными). Мы хотим как можно скорее довести вас до такого уровня, на котором вы были бы в состоянии писать полезные программы, и чтобы добиться этого, мы сосредотачиваемся на основном: переменных и константах, арифметике, операторах передачи управления, функциях и элементарных сведениях о вводе и выводе. Мы совершенно намеренно оставляем за пределами этой главы многие элементы языка "C", которые имеют первостепенное значение при написании больших программ, в том числе указатели, сртуктуры, большую часть из богатого набора операторов языка "C", несколько операторов передачи управления и несметное количество деталей.
Такой подход имеет, конечно, свои недостатки. Самым существенным является то, что полное описание любого конкретного элемента языка не излагается в одном месте, а пояснения, в силу краткости, могут привести к неправильному истолкованию. Кроме того, из-за невозможности использовать всю мощь языка, примеры оказываются не столь краткими и элегантными, как они могли бы быть. И хотя мы старались свести эти недостатки к минимуму, все же имейте их ввиду.
Другой недостаток состоит в том, что последующие главы будут неизбежно повторять некоторые части этой главы. Мы надеемся, что такое повторение будет скорее помогать, чем раздражать.
Во всяком случае, опытные программисты должны оказаться в состоянии проэкстраполировать материал данной главы на свои собственные программистские нужды. Начинающие же должны в дополнение писать аналогичные маленькие самостоятельные программы. И те, и другие могут использовать эту главу как каркас, на который будут навешиваться более подробные описания, начинающиеся с главы 2.
1.1. Hачинаем Единственный способ освоить новый язык программирования — писать на нем программы. Первая программа, которая должна быть написана, — одна для всех языков: напечатать слова : HELLO, WORLD.
Это — самый существенный барьер; чтобы преодолеть его, вы должны суметь завести где-то текст программы, успешно его скомпилировать, загрузить, прогнать и найти, где оказалась ваша выдача. Если вы научились справляться с этими техническими деталями, все остальное сравнительно просто.
Программа печати "HELLO, WORLD" на языке "C" имеет вид:
Как пропустить эту программу — зависит от используемой вами системы. В частности, на операционной системе "UNIX" вы должны завести исходную программу в файле, имя которого оканчивается на ".C", например, HELLO.C, и затем скомпилировать ее по команде Если вы не допустили какой-либо небрежности, такой как пропуск символа или неправильное написание, компиляция пройдет без сообщений и будет создан исполняемый файл с именем а.OUT. Прогон его по команде приведет к выводу На других системах эти правила будут иными; проконсультируйтесь с местным авторитетом.
Упражнение 1-1.
Пропустите эту программу на вашей системе. Попробуйте не включать различные части программы и посмотрите какие сообщения об ошибках вы при этом получите.
Теперь некоторые пояснения к самой программе. Любая "C"-программа, каков бы ни был ее размер, состоит из одной или более "функций", указывающих фактические операции компьютера, которые должны быть выполнены. Функции в языке "C" подобны функциям и подпрограммам фортрана и процедурам PL/1, паскаля и т.д. В нашем примере такой функцией является MAIN. Обычно вы можете давать функциям любые имена по вашему усмотрению, но MAIN — это особое имя;
выполнение вашей программы начинается сначала с функции MAIN. Это означает, что каждая программа должна в каком-то месте содержать функцию с именем MAIN. Для выполнения определенных действий функция MAIN обычно обращается к другим функциям, часть из которых находится в той же самой программе, а часть — в библиотеках, содержащих ранее написанные функции.
Одним способом обмена данными между функциями является передача посредством аргументов. Круглые скобки, следующие за именем функции, заключают в себе список аргументов; здесь маIN — функция без аргументов, что указывается как (). Операторы, составляющие функцию, заключаются в фигурные скобки и, которые аналогичны DO-END в PL/1 или BEGIN-END в алголе, паскале и т.д. Обращение к функции осуществляется указанием ее имени, за которым следует заключенный в круглые скобки список аргументов. здесь нет никаких операторов CALL, как в фортране или PL/1. Круглые скобки должны присутствовать и в том случае, когда функция не имеет аргументов. Строка PRINTF("HELLO, WORLD\N");
является обращением к функции, которое вызывает функцию с именем PRINTF и аргуметом "HELLO, WORLD\N". Функция PRINTF является библиотечной функцией, которая выдает выходные данные на терминал (если только не указано какое-то другое место назначения). В данном случае печатается строка символов, являющаяся аргументом функции.
Последовательность из любого количества символов, заключенных в удвоенные кавычки "...", называется 'символьной строкой' или 'строчной константой'. Пока мы будем использовать символьные строки только в качестве аргументов для PRINTF и других функций.
Последовательность \N в приведенной строке является обозначением на языке "C" для 'символа новой строки', который служит указанием для перехода на терминале к левому краю следующей строки. Если вы не включите \N (полезный эксперимент), то обнаружите, что ваша выдача не закончится переходом терминала на новую строку. Использование последовательности \N — единственный способ введения символа новой строки в аргумент функции PRINTF; если вы попробуете что-нибудь вроде то "C"-компилятор будет печатать злорадные диагностические сообщения о недостающих кавычках.
Функция PRINTF не обеспечивает автоматического перехода на новую строку, так что многократное обращение к ней можно использовать для поэтапной сборки выходной строки. Наша первая программа, печатающая идентичную выдачу, с точно таким же успехом могла бы быть написана в виде Подчеркнем, что \N представляет только один символ. Условные 'последовательности', подобные \N, дают общий и допускающий расширение механизм для представления трудных для печати или невидимых символов. Среди прочих символов в языке "C" предусмотрены следующие: \т — для табуляции, \B — для возврата на одну позицию, \" — для двойной кавычки и \\ для самой обратной косой черты.
Проведите эксперименты для того, чтобы узнать что произойдет, если в строке, являющейся аргументом функции PRINTF будет содержаться \X, где X — некоторый символ, не входящий в вышеприведенный список.
1.2. Переменные и арифметика Следующая программа печатает приведенную ниже таблицу температур по Фаренгейту и их эквивалентов по стоградусной шкале Цельсия, используя для перевода формулу
/* PRINT FAHRENHEIT-CELSIUS TABLE
INT LOWER, UPPER, STEP;
FLOAT FAHR, CELSIUS;
LOWER = 0; /* LOWER LIMIT OF TEMPERATURE UPPER =300; /* UPPER LIMIT */ FAHR = LOWER;WHILE (FAHR ".) Так как PD указывает на структуру, то к члену YEAR можно обратиться и следующим образом (*PD).YEAR но указатели структур используются настолько часто, что запись -> оказывается удобным сокращением. Круглые скобки в (*PD).YEAR необходимы, потому что операция указания члена стуктуры старше, чем *. Обе операции, "->" и ".", ассоциируются слева направо, так что конструкции слева и справа зквивалентны P->Q->MEMB (P->Q)->MEMB EMP.BIRTHDATE.MONTH (EMP.BIRTHDATE).MONTH Для полноты ниже приводится другая функция, MONTH_DAY, переписанная с использованием структур.
MONTH_DAY(PD) /* SET MONTH AND DAY FROM DAY OF YEAR */ STRUCT DATE
INT I, LEAP;LEAP = PD->YEAR % 4 == 0 && PD->YEAR % 100 != \!\! PD->YEAR % 400 == 0;
PD->DAY = PD->YEARDAY;
FOR (I = 1; PD->DAY > DAY_TAB[LEAP][I]; I++) PD->DAY -= DAY_TAB[LEAP][I];
PD->MONTH = I;
Операции работы со структурами "->" и "." наряду со () для списка аргументов и [] для индексов находятся на самом верху иерархии страшинства операций и, следовательно, связываются очень крепко. Если, например, имеется описание STRUCT \( \) *P;
то выражение ++P->X увеличивает х, а не р, так как оно эквивалентно выражению ++(P->х). Для изменения порядка выполнения операций можно использовать круглые скобки: (++P)->х увеличивает P до доступа к х, а (P++)->X увеличивает P после. (круглые скобки в последнем случае необязательны. Почему?) Совершенно аналогично *P->Y извлекает то, на что указывает Y; *P->Y++ увеличивает Y после обработки того, на что он указывает (точно так же, как и *S++);
(*P->Y)++ увеличивает то, на что указывает Y; *P++->Y увеличивает P после выборки того, на что указывает Y.
6.3. Массивы структур Структуры особенно подходят для управления массивами связанных переменных. Рассмотрим, например, программу подсчета числа вхождений каждого ключевого слова языка "C". Нам нужен массив символьных строк для хранения имен и массив целых для подсчета. одна из возможностей состоит в использовании двух параллельных массивов KEYWORD и KEYCOUNT:
CHAR *KEYWORD [NKEYS];
INT KEYCOUNT [NKEYS];
Но сам факт, что массивы параллельны, указывает на возможность другой организации. Каждое ключевое слово здесь по существу является парой:
CHAR *KEYWORD;
INT KEYCOUNT;
и, следовательно, имеется массив пар. Описание структуры STRUCT KEY \( CHAR *KEYWORD;INT KEYCOUNT; \) KEYTAB [NKEYS];
оперделяет массив KEYTAB структур такого типа и отводит для них память. Каждый элемент массива является структурой. Это можно было бы записать и так:
STRUCT KEY \( CHAR *KEYWORD;
INT KEYCOUNT; \);
STRUCT KEY KEYTAB [NKEYS];
Так как структура KEYTAB фактически содержит постоянный набор имен, то легче всего инициализировать ее один раз и для всех членов при определении.
Инициализация структур вполне аналогична предыдущим инициализациям — за определением следует заключенный в фигурные скобки список инициализаторов:
STRUCT KEY \( INT KEYCOUNT; \) KEYTAB[] =\( Инициализаторы перечисляются парами соответственно членам структуры. Было бы более точно заключать в фигурные скобки инициализаторы для каждой "строки" или структуры следующим образом:
\( "BREAK", 0 \), \( "CASE", 0 \), Но когда инициализаторы являются простыми переменными или символьными строками и все они присутствуют, то во внутренних фигурных скобках нет необходимости. Как обычно, компилятор сам вычислит число элементов массива KEYTAB, если инициализаторы присутствуют, а скобки [] оставлены пустыми.
Программа подсчета ключевых слов начинается с определения массива KEYTAB.
ведущая программа читает свой файл ввода, последовательно обращаясь к функции GETWORD, которая извлекает из ввода по одному слову за обращение. Каждое слово ищется в массиве KEYTAB с помощью варианта функции бинарного поиска, написанной нами в главе 3. (Конечно, чтобы эта функция работала, список ключевых слов должен быть расположен в порядке возрастания).
MAIN() /* COUNT "C" KEYWORDS */ INT N, T;
CHAR WORD[MAXWORD];
WHILE ((T = GETWORD(WORD,MAXWORD)) != EOF) IF((N = BINARY(WORD,KEYTAB,NKEYS)) >= 0) FOR (N =0; N < NKEYS; N++) IF (KEYTAB[N].KEYCOUNT > 0) KEYTAB[N].KEYCOUNT, KEYTAB[N].KEYWORD);
BINARY(WORD, TAB, N) /* FIND WORD IN TAB[0]...TAB[N-1] */ CHAR *WORD;
STRUCT KEY TAB[];
INT N;
INT LOW, HIGH, MID, COND;
WHILE (LOW 0) RETURN(-1);
Мы вскоре приведем функцию GETWORD; пока достаточно сказать, что она возвращает LETTER каждый раз, как она находит слово, и копирует это слово в свой первый аргумент.
Величина NKEYS — это количество ключевых слов в массиве KEYTAB. Хотя мы можем сосчитать это число вручную, гораздо легче и надежнее поручить это машине, особенно в том случае, если список ключевых слов подвержен изменениям. Одной из возможностей было бы закончить список инициализаторов указанием на нуль и затем пройти в цикле сквозь массив KEYTAB, пока не найдется конец.
Но, поскольку размер этого массива полностью определен к моменту компиляции, здесь имеется более простая возможность. Число элементов просто есть
SIZE OF KEYTAB / SIZE OF STRUCT KEY
дело в том, что в языке "C" предусмотрена унарная операция SIZEOF, выполняемая во время компиляции, которая позволяет вычислить размер любого объекта. Выражение SIZEOF(OBJECT) выдает целое, равное размеру указанного объекта. (Размер определяется в неспецифицированных единицах, называемых "байтами", которые имеют тот же размер, что и переменные типа CHAR). Объект может быть фактической переменной, массивом и структурой, или именем основного типа, как INT или DOUBLE, или именем производного типа, как структура. В нашем случае число ключевых слов равно размеру массива, деленному на размер одного элемента массива. Это вычисление используется в утверждении #DEFINE для установления значения NKEYS:#DEFINE NKEYS (SIZEOF(KEYTAB) / SIZEOF(STRUCT KEY)) Теперь перейдем к функции GETWORD. Мы фактически написали более общий вариант функции GETWORD, чем необходимо для этой программы, но он не на много более сложен. Функция GETWORD возвращает следующее "слово" из ввода, где словом считается либо строка букв и цифр, начинающихся с буквы, либо отдельный символ.
Тип объекта возвращается в качетве значения функции; это — LETTER, если найдено слово, EOF для конца файла и сам символ, если он не буквенный.
GETWORD(W, LIM) /* GET NEXT WORD FROM INPUT */ CHAR *W;
INT LIM;
IF (TYPE(C=*W++=GETCH()) !=LETTER) \( WHILE (--LIM > 0) \( T = TYPE(C = *W++ = GETCH());
IF (T ! = LETTER && T ! = DIGIT) \( *(W-1) — '\0';
RETURN(LETTER);
Функция GETWORD использует функции GETCH и UNGETCH, которые мы написали в главе 4: когда набор алфавитных символов прерывается, функция GETWORD получает один лишний символ. В результате вызова UNGETCH этот символ помещается назад во ввод для следующего обращения.
Функция GETWORD обращается к функции TYPE для определения типа каждого отдельного символа из файла ввода. Вот вариант, справедливый только для алфавита ASCII.
TYPE(C) /* RETURN TYPE OF ASCII CHARACTER */ IF (C>= 'A' && C= 'A' && C= '0' && CKEYCOUNT++;
FOR (P=KEYTAB; P>KEYTAB + NKEYS; P++) PRINTF("%4D % S/N", P->KEYCOUNT, P->KEYWORD);
STRUCT KEY *BINARY(WORD, TAB, N) /* FIND WORD */ CHAR *WORD /* IN TAB[0]...TAB[N-1] */ STRUCT KEY TAB [];
INT COND;
STRUCT KEY *LOW = &TAB[0];
STRUCT KEY *HIGH = &TAB[N-1];
STRUCT KEY *MID;
WHILE (LOW KEYWORD)) < 0) ELSE IF (COND > 0) RETURN(NULL);
Здесь имеется несколько моментов, которые стоит отметить. Во-первых, описание функции BINARI должно указывать, что она возвращает указатель на структуру типа KEY, а не на целое; это объявляется как в функции MAIN, так и в BINARY. Если функция BINARI находит слово, то она возвращает указатель на него;
если же нет, она возвращает NULL.
Во-вторых, все обращения к элементам массива KEYTAB осуществляются через указатели. Это влечет за собой одно существенное изменение в функции BINARY:
средний элемент больше нельзя вычислять просто по формуле MID = (LOW + HIGH) / потому что сложение двух указателей не дает какого-нибудь полезного результата (даже после деления на 2) и в действительности является незаконным. эту формулу надо заменить на MID = LOW + (HIGH-LOW) / в результате которой MID становится указателем на элемент, расположенный посередине между LOW и HIGH.
Вам также следует разобраться в инициализации LOW и HIGH. указатель можно инициализировать адресом ранее определенного объекта; именно как мы здесь и поступили.
В функции MAIN мы написали FOR (P=KEYTAB; P < KEYTAB + NKEYS; P++) Если P является указателем структуры, то любая арифметика с P учитывает фактический размер данной структуры, так что P++ увеличивает P на нужную величину, в результате чего P указывает на следующий элемент массива структур. Но не считайте, что размер структуры равен сумме размеров ее членов, — из-за требований выравнивания для различных объектов в структуре могут возникать "дыры".
И, наконец, несколько второстепенный вопрос о форме записи программы. Если возвращаемая функцией величина имеет тип, как, например, в STRUCT KEY *BINARY(WORD, TAB, N) Tо может оказаться, что имя функции трудно выделить среди текста. В связи с этим иногда используется другой стиль записи:
Это главным образом дело вкуса; выберите ту форму, которая вам нравится, и придерживайтесь ее.
6.5. Структуры, ссылающиеся на себя.
Предположим, что нам надо справиться с более общей задачей, состоящей в подсчете числа появлений всех слов в некотором файле ввода. Так как список слов заранее не известен, мы не можем их упорядочить удобным образом и использовать бинарный поиск. Мы даже не можем осуществлять последовательный просмотр при поступлении каждого слова, с тем чтобы установить, не встречалось ли оно ранее;
такая программа будет работать вечно. (Более точно, ожидаемое время работы растет как квадрат числа вводимых слов). Как же нам организовать программу, чтобы справиться со списком произвольных слов?
Одно из решений состоит в том, чтобы все время хранить массив поступающих до сих пор слов в упорядоченном виде, помещая каждое слово в нужное место по мере их поступления. OДнако это не следует делать, перемещая слова в линейном массиве, — это также потребует слишком много времени. Вместо этого мы используем структуру данных, называемую доичным деревом.
Каждому новому слову соответствует один "узел" дерева; каждый узел содержит:
указатель текста слова счетчик числа появлений указатель узла левого потомка указатель узла правого потомка Никакой узел не может иметь более двух детей; возможно отсутсвие детей или наличие только одного потомка.
Узлы создаются таким образом, что левое поддерево каждого узла содержит только те слова, которые меньше слова в этом узле, а правое поддерево только те слова, которые больше. Чтобы определить, находится ли новое слово уже в дереве, начинают с корня и сравнивают новое слово со словом, хранящимся в этом узле. Если слова совпадают, то вопрос решается утвердительно. Если новое слово меньше слова в дереве, то переходят к рассмотрению левого потомка; в противном случае исследуется правый потомок. Если в нужном направлении потомок отсутствует, то значит новое слово не находится в дереве и место этого недостающего потомка как раз и является местом, куда следует поместить новое слово. Поскольку поиск из любого узла приводит к поиску одного из его потомков, то сам процесс поиска по существу является рекурсивным. В соответствии с этим наиболее естественно использовать рекурсивные процедуры ввода и вывода.
Возвращаясь назад к описанию узла, ясно, что это будет структура с четырьмя компонентами:
STRUCT TNODE \( /* THE BASIC NODE */ CHAR *WORD; /* POINTS TO THE TEXT */ INT COUNT; /* NUMBER OF OCCURRENCES */ STRUCT TNODE *LEFT; /* LEFT CHILD */ STRUCT TNODE *RIGHT; /* RIGHT CHILD */ Это "рекурсивное" описание узла может показаться рискованным, но на самом деле оно вполне корректно. Структура не имеет права содержать ссылку на саму себя, но STRUCT TNODE *LEFT;
описывает LEFT как указатель на узел, а не как сам узел.
Текст самой программы оказывается удивительно маленьким, если, конечно, иметь в распоряжении набор написанных нами ранее процедур, обеспечивающих нужные действия. Мы имеем в виду функцию GETWORD для извлечения каждого слова из файла ввода и функцию ALLOC для выделения места для хранения слов.
Ведущая программа просто считывает слова с помощью функции GETWORD и помещает их в дерево, используя функцию TREE.
#DEFINE MAXWORD MAIN() /* WORD FREGUENCY COUNT */ STRUCT TNODE *ROOT, *TREE();
CHAR WORD[MAXWORD];
WHILE ((T = GETWORD(WORD, MAXWORD)) \! = EOF) TREEPRINT(ROOT);
Функция TREE сама по себе проста. Слово передается функцией MAIN к верхнему уровню (корню) дерева. На каждом этапе это слово сравнивается со словом, уже хранящимся в этом узле, и с помощью рекурсивного обращения к TREE просачивается вниз либо к левому, либо к правому поддереву. В конце концов это слово либо совпадает с каким-то словом, уже находящимся в дереве (в этом случае счетчик увеличивается на единицу), либо программа натолкнется на нулевой указатель, свидетельствующий о необходимости создания и добавления к дереву нового узла. В случае создания нового узла функция TREE возвращает указатель этого узла, который помещается в родительский узел.
STRUCT TNODE *TREE(P, W) STRUCT TNODE *P;
CHAR *W;
STRUCT TNODE *TALLOC();
CHAR *STRSAVE();
\) ELSE IF ((COND = STRCMP(W, P->WORD)) == 0) ELSE IF (COND < 0)/* LOWER GOES INTO LEFT SUBTREE */
ELSE /* GREATER INTO RIGHT SUBTREE */
RETURN(P);Память для нового узла выделяется функцией TALLOC, являющейся адаптацией для данного случая функции ALLOC, написанной нами ранее. Она возвращает указатель свободного пространства, пригодного для хранения нового узла дерева. (Мы вскоре обсудим это подробнее). Новое слово копируется функцией STRSAVE в скрытое место, счетчик инициализируется единицей, и указатели обоих потомков полагаются равными нулю. Эта часть программы выполняется только при добавлении нового узла к ребру дерева. Мы здесь опустили проверку на ошибки возвращаемых функций STRSAVE и TALLOC значений (что неразумно для практически работающей программы).
Функция TREEPRINT печатает дерево, начиная с левого поддерева; в каждом узле сначала печатается левое поддерево (все слова, которые младше этого слова), затем само слово, а затем правое поддерево (все слова, которые старше). Если вы неуверенно оперируете с рекурсией, нарисуйте дерево сами и напечатайте его с помощью функции TREEPRINT ; это одна из наиболее ясных рекурсивных процедур, которую можно найти.
TREEPRINT (P) /* PRINT TREE P RECURSIVELY */ STRUCT TNODE *P;
PRINTF("% 4D % S\N", P->COUNT, P->WORD);
Практическое замечание: если дерево становится "несбалансированным" из-за того, что слова поступают не в случайном порядке, то время работы программы может расти слишком быстро. В худшем случае, когда поступающие слова уже упорядочены, настоящая программа осуществляет дорогостоящую имитацию линейного поиска. Существуют различные обобщения двоичного дерева, особенно 2-3 деревья и AVL деревья, которые не ведут себя так "в худших случаях", но мы не будем здесь на них останавливаться.
Прежде чем расстаться с этим примером, уместно сделать небольшое отступление в связи с вопросом о распределении памяти. Ясно, что в программе желательно иметь только один распределитель памяти, даже если ему приходится размещать различные виды объектов. Но если мы хотим использовать один распределитель памяти для обработки запросов на выделение памяти для указателей на переменные типа CHAR и для указателей на STRUCT TNODE, то при этом возникают два вопроса. Первый: как выполнить то существующее на большинстве реальных машин ограничение, что объекты определенных типов должны удовлетворять требованиям выравнивания (например, часто целые должны размещаться в четных адресах)? Второй: как организовать описания, чтобы справиться с тем, что функция ALLOC должна возвращать различные виды указателей?
Вообще говоря, требования выравнивания легко выполнить за счет выделения некоторого лишнего пространства, просто обеспечив то, чтобы распределитель памяти всегда возвращал указатель, удовлетворяющий всем ограничениям выравнивания. Например, на PDP-11 достаточно, чтобы функция ALLOC всегда возвращала четный указатель, поскольку в четный адрес можно поместить любой тип объекта. единственный расход при этом — лишний символ при запросе на нечетную длину. Аналогичные действия предпринимаются на других машинах. Таким образом, реализация ALLOC может не оказаться переносимой, но ее использование будет переносимым. Функция ALLOC из главы 5 не предусматривает никакого определенного выравнивания; в главе 8 мы продемонстрируем, как правильно выполнить эту задачу.
Вопрос описания типа функции ALLOC является мучительным для любого языка, который серьезно относится к проверке типов. Лучший способ в языке "C" — объявить, что ALLOC возвращает указатель на переменную типа CHAR, а затем явно преобразовать этот указатель к желаемому типу с помощью операции перевода типов.
Таким образом, если описать P в виде преобразует его в выражениях в указатель на структуру типа TNODE. Следовательно, функцию TALLOC можно записать в виде:
STRUCT TNODE *TALLOC() CHAR *ALLOC();
RETURN ((STRUCT TNODE *) ALLOC(SIZEOF(STRUCT TNODE)));
это более чем достаточно для работающих в настоящее время компиляторов, но это и самый безопасный путь с учетом будующего.
Упражнение 6-4.
Напишите программу, которая читает "C"-программу и печатает в алфавитном порядке каждую группу имен переменных, которые совпадают в первых семи символах, но отличаются где-то дальше. (Сделайте так, чтобы 7 было параметром).
Упражнение 6-5.
Напишите программу выдачи перекрестных ссылок, т.е. Программу, которая печатает список всех слов документа и для каждого из этих слов печатает список номеров строк, в которые это слово входит.
Упражнение 6-6.
Напишите программу, которая печатает слова из своего файла ввода, расположенные в порядке убывания частоты их появления. Перед каждым словом напечатайте число его появлений.
6.6. Поиск в таблице Для иллюстрации дальнейших аспектов использования структур в этом разделе мы напишем программу, представляющую собой содержимое пакета поиска в таблице. Эта программа является типичным представителем подпрограмм управления символьными таблицами макропроцессора или компилятора. Рассмотрим, например, оператор #DEFINE языка "C". Когда встречается строка вида то имя YES и заменяющий текст 1 помещаются в таблицу. Позднее, когда имя YES появляется в операторе вида INWORD = YES;
Oно должно быть замещено на 1.
Имеются две основные процедуры, которые управляют именами и заменяющими их текстами. Функция INSTALL(S,T) записывает имя S и заменяющий текст T в таблицу; здесь S и T просто символьные строки. Функция LOOKUP(S) ищет имя S в таблице и возвращает либо указатель того места, где это имя найдено, либо NULL, если этого имени в таблице не оказалось.
При этом используется поиск по алгоритму хеширования — поступающее имя преобразуется в маленькое положительное число, которое затем используется для индексации массива указателей. Элемент массива указывает на начало цепочных блоков, описывающих имена, которые имеют это значение хеширования. Если никакие имена при хешировании не получают этого значения, то элементом массива будет NULL.
Блоком цепи является структура, содержащая указатели на соответствующее имя, на заменяющий текст и на следующий блок в цепи. Нулевой указатель следующего блока служит признаком конца данной цепи.
STRUCT NLIST \( /* BASIC TABLE ENTRY */ STRUCT NLIST *NEXT; /* NEXT ENTRY IN CHAIN */ Массив указателей это просто
TATIC STRUCT NLIST *HASHTAB[HASHSIZE] /* POINTER TABLE */
Значение функции хеширования, используемой обеими функциями LOOKUP и INSTALL, получается просто как остаток от деления суммы символьных значений строки на размер массива. (Это не самый лучший возможный алгоритм, но его достоинство состоит в исключительной простоте).HASH(S) /* FORM HASH VALUE FOR STRING */ CHAR *S;
RETURN(HASHVAL % HASHSIZE);
В результате процесса хеширования выдается начальный индекс в массиве HASHTAB ; если данная строка может быть где-то найдена, то именно в цепи блоков, начало которой указано там. Поиск осуществляется функцией LOOKUP. Если функция LOOKUP находит, что данный элемент уже присутствует, то она возвращает указатель на него; если нет, то она возвращает NULL.
STRUCT NLIST *LOOKUP(S) /* LOOK FOR S IN HASHTAB */ CHAR *S;
STRUCT NLIST *NP;
FOR (NP = HASHTAB[HASH(S)]; NP != NULL;NP=NP->NEXT) IF (STRCMP(S, NP->NAME) == 0) RETURN(NP); /* Функция INSTALL использует функцию LOOKUP для определения, не присутствует ли уже вводимое в данный момент имя; если это так, то новое определение должно вытеснить старое. В противном случае создается совершенно новый элемент. Если по какой-либо причине для нового элемента больше нет места, то функция INSTALL возвращает NULL.
STRUCT NLIST *INSTALL(NAME, DEF) /* PUT (NAME, DEF) */ CHAR *NAME, *DEF;
STRUCT NLIST *NP, *LOOKUP();
CHAR *STRSAVE(), *ALLOC();
INT HASHVAL;
IF((NP = LOOKUP(NAME)) == NULL) \( /* NOT FOUND */ NP = (STRUCT NLIST *) ALLOC(SIZEOF(*NP));
IF (NP == NULL) IF ((NP->NAME = STRSAVE(NAME)) == NULL) HASHVAL = HASH(NP->NAME);
NP->NEXT = HASHTAB[HASHVAL];
HASHTAB[HASHVAL] = NP;
FREE((NP->DEF);/* FREE PREVIOUS DEFINITION */ IF ((NP->DEF = STRSAVE(DEF)) == NULL) RETURN(NP);
Функция STRSAVE просто копирует строку, указанную в качестве аргумента, в место хранения, полученное в результате обращения к функции ALLOC. Мы уже привели эту функцию в главе 5. Так как обращение к функции ALLOC и FREE могут происходить в любом порядке и в связи с проблемой выравнивания, простой вариант функции ALLOC из главы 5 нам больше не подходит; смотрите главы 7 и 8.
Упражнение 6-7.
Напишите процедуру, которая будет удалять имя и определение из таблицы, управляемой функциями LOOKUP и INSTALL.
Упражнение 6-8.
Разработайте простую, основанную на функциях этого раздела, версию процессора для обработки конструкций #DEFINE, пригодную для использования с "C"программами. Вам могут также оказаться полезными функции GETCHAR и UNGETCH.
6.7. Поля Когда вопрос экономии памяти становится очень существенным, то может оказаться необходимым помещать в одно машинное слово несколько различных объектов; одно из особенно распросраненных употреблений — набор однобитовых признаков в применениях, подобных символьным таблицам компилятора. внешне обусловленные форматы данных, такие как интерфейсы аппаратных средств также зачастую предполагают возможность получения слова по частям.
Представьте себе фрагмент компилятора, который работает с символьной таблицей. С каждым идентификатором программы связана определенная информация, например, является он или нет ключевым словом, является ли он или нет внешним и/или статическим и т.д. Самый компактный способ закодировать такую информацию — поместить набор однобитовых признаков в отдельную переменную типа CHAR или INT.
Обычный способ, которым это делается, состоит в определении набора "масок", отвечающих соответствущим битовым позициям, как в #DEFINE KEYWORD #DEFINE EXTERNAL (числа должны быть степенями двойки). Тогда обработка битов сведется к "жонглированию битами" с помощью операций сдвига, маскирования и дополнения, описанных нами в главе 2.
Некоторые часто встречающиеся идиомы:
FLAGS \!= EXTERNAL \! STATIC;
включает биты EXTERNAL и STATIC в FLAGS, в то время как FLAGS &= \^(еXTERNAL \! STATIC);
их выключает, а IF ((FLAGS & (EXTERNAL \! STATIC)) == 0)...
истинно, если оба бита выключены.
Хотя этими идиомами легко овладеть, язык "C" в качестве альтернативы предлагает возможность определения и обработки полей внутри слова непосредственно, а не посредством побитовых логических операций. Поле — это набор смежных битов внутри одной переменной типа INT. Синтаксис определения и обработки полей основывается на структурах. Например, символьную таблицу конструкций #DEFINE, приведенную выше, можно бы было заменить определением трех полей:
UNSIGNED IS_KEYWORD : 1;
UNSIGNED IS_EXTERN : 1;
UNSIGNED IS_STATIC : 1;
Здесь определяется переменная с именем FLAGS, которая содержит три 1-битовых поля. Следующее за двоеточием число задает ширину поля в битах. Поля описаны как UNSIGNED, чтобы подчеркнуть, что они действительно будут величинами без знака.
На отдельные поля можно ссылаться, как FLAGS.IS_STATIE, FLAGS. IS_EXTERN, FLAGS.IS_KEYWORD И т.д., то есть точно так же, как на другие члены структуры.
Поля ведут себя подобно небольшим целым без знака и могут участвовать в арифметических выражениях точно так же, как и другие целые. Таким образом, предыдущие примеры более естественно переписать так:
FLAGS.IS_EXTERN = FLAGS.IS_STATIC = 1;
для включения битов;
FLAGS.IS_EXTERN = FLAGS.IS_STATIC = 0;
для выключения битов;
IF (FLAGS.IS_EXTERN == 0 &&FLAGS.IS_STATIC == 0)...
для их проверки.
Поле не может перекрывать границу INT; если указанная ширина такова, что это должно случиться, то поле выравнивается по границе следующего INT. Полям можно не присваивать имена; неименованные поля (только двоеточие и ширина) используются для заполнения свободного места. Чтобы вынудить выравнивание на границу следующего INT, можно использовать специальную ширину 0.
При работе с полями имеется ряд моментов, на которые следует обратить внимание. По-видимому наиболее существенным является то, что отражая природу различных аппаратных средств, распределение полей на некоторых машинах осуществляется слева направо, а на некоторых справа налево. Это означает, что хотя поля очень полезны для работы с внутренне определенными структурами данных, при разделении внешне определяемых данных следует тщательно рассматривать вопрос о том, какой конец поступает первым.
Другие ограничения, которые следует иметь в виду: поля не имеют знака; они могут храниться только в переменных типа INT (или, что эквивалентно, типа UNSIGNED); они не являются массивами; они не имеют адресов, так что к ним не применима операция &.
6.8. Объединения Oбъединения — это переменная, которая в различные моменты времени может содержать объекты разных типов и размеров, причем компилятор берет на себя отслеживание размера и требований выравнивания. Объединения представляют возможность работать с различными видами данных в одной области памяти, не вводя в программу никакой машинно-зависимой информации.
В качестве примера, снова из символьной таблицы компилятора, предположим, что константы могут быть типа INT, FLOAT или быть указателями на символы.
значение каждой конкретной константы должно храниться в переменной соотвествующего типа, но все же для управления таблицей самым удобным было бы, если это значение занимало бы один и тот же объем памяти и хранилось в том же самом месте независимо от его типа. это и является назначением объединения — выделить отдельную переменную, в которой можно законно хранить любую одну из переменных нескольких типов. Как и в случае полей, синтаксис основывается на структурах.
UNION U_TAG \( INT IVAL;
FLOAT FVAL;
CHAR *PVAL;
\) UVAL;
Переменная UVAL будет иметь достаточно большой размер,чтобы хранить наибольший из трех типов, независимо от машины, на которой осуществляется компиляция, — программа не будет зависить от характеристик аппаратных средств.
Любой из этих трех типов может быть присвоен UVAR и затем использован в выражениях, пока такое использование совместимо: извлекаемый тип должен совпадать с последним помещенным типом. Дело программиста — следить за тем, какой тип хранится в объединении в данный момент; если что-либо хранится как один тип, а извлекается как другой, то результаты будут зависеть от используемой машины.
Синтаксически доступ к членам объединения осуществляется следующим образом:
имя объединения.член указатель объединения ->член то есть точно так же, как и в случае структур. если для отслеживания типа, хранимого в данный момент в UVAL, используется переменная UTYPE, то можно встретить такой участок программы:
IF (UTYPE == INT) PRINTF("%D\N", UVAL.IVAL);
PRINTF("%F\N", UVAL.FVAL);
PRINTF("%S\N", UVAL.PVAL);
PRINTF("BAD TYPE % D IN UTYPE\N", UTYPE);
Объединения могут появляться внутри структур и массивов и наоборот. Запись для обращения к члену объединения в структуре (или наоборот) совершенно идентична той, которая используется во вложенных структурах. например, в массиве структур, определенным следующим образом STRUCT \( CHAR *NAME;
INT FLAGS;
INT UTYPE;
UNION \( INT IVAL;
FLOAT FVAL;
CHAR *PVAL;
\) UVAL;
\) SYMTAB[NSYM];
на переменную IVAL можно сослаться как SYMTAB[I].UVAL.IVAL а на первый символ строки PVAL как *SYMTAB[I].UVAL.PVAL В сущности объединение является структурой, в которой все члены имеют нулевое смещение. Сама структура достаточно велика, чтобы хранить "самый широкий" член, и выравнивание пригодно для всех типов, входящих в объединение. Как и в случае структур, единственными операциями, которые в настоящее время можно проводить с объединениями, являются доступ к члену и извлечение адреса; объединения не могут быть присвоены, переданы функциям или возвращены ими. указатели объединений можно использовать в точно такой же манере, как и указатели структур.
Программа распределения памяти, приводимая в главе 8, показывает, как можно использовать объединение, чтобы сделать некоторую переменную выровненной по определенному виду границы памяти.
6.9. Определение типа В языке "C" предусмотрена возможность, называемая TYPEDEF для введения новых имен для типов данных. Например, описание
TYPEDEF INT LENGTH;
делает имя LENGTH синонимом для INT. "Тип" LENGTH может быть использован в описаниях, переводов типов и т.д. Точно таким же образом, как и тип INT:LENGTH LEN, MAXLEN;
LENGTH *LENGTHS[];
Аналогично описанию
TYPEDEF CHAR *STRING;
делает STRING синонимом для CHAR*, то есть для указателя на символы, что затем можно использовать в описаниях вида STRING P, LINEPTR[LINES], ALLOC();Обратите внимание, что объявляемый в конструкции TYPEDEF тип появляется в позиции имени переменной, а не сразу за словом TYPEDEF. Синтаксически конструкция TYPEDEF подобна описаниям класса памяти EXTERN, STATIC и т. Д. мы также использовали прописные буквы, чтобы яснее выделить имена.
В качестве более сложного примера мы используем конструкцию TYPEDEF для описания узлов дерева, рассмотренных ранее в этой главе:
CHAR *WORD; /* POINTS TO THE TEXT */ INT COUNT; /* NUMBER OF OCCURRENCES */ \) TREENODE, *TREEPTR;
В результате получаем два новых ключевых слова: TREENODE (структура) и TREEPTR (указатель на структуру). Тогда функцию TALLOC можно записать в виде RETURN((TREEPTR) ALLOC(SIZEOF(TREENODE)));
Необходимо подчеркнуть, что описание TYPEDEF не приводит к созданию нового в каком-либо смысле типа; оно только добавляет новое имя для некоторого существующего типа. при этом не возникает и никакой новой семантики: описанные таким способом переменные обладают точно теми же свойствами, что и переменные, описанные явным образом. По существу конструкция TYPEDEF сходна с #DEFINE за исключением того, что она интерпретируется компилятором и потому может осуществлять подстановки текста, которые выходят за пределы возможностей макропроцессора языка "C". Например, TYPEDEF INT (*PFI) ();
создает тип PFI для "указателя функции, возвращающей значение типа INT", который затем можно было бы использовать в программе сортировки из главы 5 в контексте вида PFI STRCMP, NUMCMP, SWAP;
Имеются две основные причины применения описаний TYPEDEF. Первая причина связана с параметризацией программы, чтобы облегчить решение проблемы переносимости. Если для типов данных, которые могут быть машинно-зависимыми, использовать описание TYPEDEF, то при переносе программы на другую машину придется изменить только эти описания. Одна из типичных ситуаций состоит в использовании определяемых с помощью TYPEDEF имен для различных целых величин и в последующем подходящем выборе типов SHORT, INT и LONG для каждой имеющейся машины.
Второе назначение TYPEDEF состоит в обеспечении лучшей документации для программы — тип с именем TREEPTR может оказаться более удобным для восприятия, чем тип, который описан только как указатель сложной структуры.
И наконец, всегда существует вероятность, что в будущем компилятор или некоторая другая программа, такая как LINT, сможет использовать содержащуюся в описаниях TYPEDEF информацию для проведения некоторой дополнительной проверки программы.
7. Ввод и вывод Средства ввода/вывода не являются составной частью языка "с", так что мы не выделяли их в нашем предыдущем изложении. Однако реальные программы взаимодействуют со своей окружающей средой гораздо более сложным образом, чем мы видели до сих пор. В этой главе будет описана "стандартная библиотека ввода/вывода", то есть набор функций, разработанных для обеспечения стандартной системы ввода/вывода для "с"- программ. Эти функции предназначены для удобства программного интерфейса, и все же отражают только те операции, которые могут быть обеспечены на большинстве современных операционных систем. Процедуры достаточно эффективны для того, чтобы пользователи редко чувствовали необходимость обойти их "ради эффективности", как бы ни была важна конкретная задача. И, наконец, эти процедуры задуманы быть "переносимыми" в том смысле, что они должны существовать в совместимом виде на любой системе, где имеется язык "с", и что программы, которые ограничивают свои взаимодействия с системой возможностями, предоставляемыми стандартной библиотекой, можно будет переносить с одной системы на другую по существу без изменений.
Мы здесь не будем пытаться описать всю библиотеку ввода/вывода; мы более заинтересованы в том, чтобы продемонстрировать сущность написания "с"-программ, которые взаимодействуют со своей операционной средой.
7.1. Обращение к стандартной библиотеке Каждый исходный файл, который обращается к функции из стандартной библиотеки, должен вблизи начала содержать строку #INCLUDE в файле STDIO.H определяются некоторые макросы и переменные, используемые библиотекой ввода/вывода. Использование угловых скобок вместо обычных двойных кавычек — указание компилятору искать этот файл в справочнике, содержащем заголовки стандартной информации (на системе UNIX обычно LUSRLINELUDE).
Кроме того, при загрузке программы может оказаться необходимым указать библиотеку явно; на системе PDP-11 UNIX, например, команда компиляции программы имела бы вид:
CC исходные файлы и т.д. -LS где -LS указывает на загрузку из стандартной библиотеки.
7.2. Стандартный ввод и вывод — функции GETCHAR и PUTCHAR
PROG>OUTFILE
приведет к записи стандартного вывода в файл OUTFILE, а не на терминал. На системе UNIX можно также использовать поточный механизм.Строка PROG \! ANOTHERPROG помещает стандартный вывод PROG в стандартный ввод ANOTHERPROG. И опять PROG не будет осведомлена об изменении направления.
Вывод, осуществляемый функцией PRINTF, также поступает в стандартный вывод, и обращения к PUTCHAR и PRINTF могут перемежаться.
Поразительное количество программ читает только из одного входного потока и пишет только в один выходной поток; для таких программ ввод и вывод с помощью функций GETCHAR, PUTCHAR и PRINTF может оказаться вполне адекватным и для начала определенно достаточным. Это особенно справедливо тогда, когда имеется возможность указания файлов для ввода и вывода и поточный механизм для связи вывода одной программы с вводом другой. Рассмотрим, например, программу LOWER, которая преобразует прописные буквы из своего ввода в строчные:
#INCLUDE MAIN() /* CONVERT INPUT TO LOWER CASE */ INT C;
WHILE ((C = GETCHAR()) != EOF) PUTCHAR(ISUPPER(C)? TOLOWER(C) : C);
"Функции" ISUPPER и TOLOWER на самом деле являются макросами, определенными в STDIO.H. Макрос ISUPPER проверяет, является ли его аргумент буквой из верхнего регистра, и возвращает ненулевое значение, если это так, и нуль в противном случае.
Макрос TOLOWER преобразует букву из верхнего регистра в ту же букву нижнего регистра. Независимо от того, как эти функции реализованы на конкретной машине, их внешнее поведение совершенно одинаково, так что использующие их программы избавлены от знания символьного набора.
Если требуется преобразовать несколько файлов, то можно собрать эти файлы с помощью программы, подобной утилите CAT системы UNIX, CAT FILE1 FILE2... \! LOWER>OUTPUT и избежать тем самым вопроса о том, как обратиться к этим файлам из программы. (Программа CAT приводится позже в этой главе).
Кроме того отметим, что в стандартной библиотеке ввода/вывода "функции" GETCHAR и PUTCHAR на самом деле могут быть макросами. Это позволяет избежать накладных расходов на обращение к функции для обработки каждого символа. В главе 8 мы продемонстрируем, как это делается.
7.3. Форматный вывод — функция PRINTF Две функции: PRINTF для вывода и SCANF для ввода (следующий раздел) позволяют преобразовывать численные величины в символьное представлEние и обратно. Они также позволяют генерировать и интерпретировать форматные строки.
Мы уже всюду в предыдущих главах неформально использовали функцию PRINTF;
здесь приводится более полное и точное описание. Функция PRINTF(CONTROL, ARG1, ARG2,...) преобразует, определяет формат и печатает свои аргументы в стандартный вывод под управлением строки CONTROL. Управляющая строка содержит два типа объектов: обычные символы, которые просто копируются в выходной поток, и спецификации преобразований, каждая из которых вызывает преобразование и печать очередного аргумента PRINTF.
Каждая спецификация преобразования начинается с символа % и заканчивается символом преобразования. Между % и символом преобразования могут находиться:
- знак минус, который указывает о выравнивании преобразованного аргумента по левому краю его поля.
- Строка цифр, задающая минимальную ширину поля. Преобразованное число будет напечатано в поле по крайней мере этой ширины, а если необходимо, то и в более широком. Если преобразованный аргумент имеет меньше символов, чем указанная ширина поля, то он будет дополнен слева (или справа, если было указано выравнивание по левому краю)заполняющими символами до этой ширины.
Заполняющим символом обычно является пробел, а если ширина поля указывается с лидирующим нулем, то этим символом будет нуль (лидирующий нуль в данном случае не означает восьмеричной ширины поля).
- Точка, которая отделяет ширину поля от следующей строки цифр.
- Строка цифр (точность), которая указывает максимальное число символов строки, которые должны быть напечатаны, или число печатаемых справа от десятичной точки цифр для переменных типа FLOAT или DOUBLE.
- Модификатор длины L, который указывает, что соответствующий элемент данных имеет тип LONG, а не INT.
Ниже приводятся символы преобразования и их смысл:
D — аргумент преобразуется к десятичному виду.
O — Аргумент преобразуется в беззнаковую восьмеричную форму (без лидирующего нуля).
X — Аргумент преобразуется в беззнаковую шестнадцатеричную форму (без лидирующих 0X).
U — Аргумент преобразуется в беззнаковую десятичную форму.
C — Аргумент рассматривается как отдельный символ.
S — Аргумент является строкой: символы строки печатаются до тех пор, пока не будет достигнут нулевой символ или не будет напечатано количество символов, указанное в спецификации точности.
E — Аргумент, рассматриваемый как переменная типа FLOAT или DOUBLE, преобразуется в десятичную форму в виде [-]M.NNNNNNE[+-]XX, где длина строки из N определяется указанной точностью. Точность по умолчанию равна 6.
F — Аргумент, рассматриваемый как переменная типа FLOAT или DOUBLE, преобразуется в десятичную форму в виде [-]MMM.NNNNN, где длина строки из N определяется указанной точностью. Точность по умолчанию равна 6. отметим, что эта точность не определяет количество печатаемых в формате F значащих цифр.
G — Используется или формат % E или % F, какой короче; незначащие нули не печатаются.
Если идущий за % символ не является символом преобразования, то печатается сам этот символ; следовательно,символ % можно напечатать, указав %%.
проиллюстрировано в предыдущих главах. Единственным исключением является то, как точность взаимодействует со строками. Следующая таблица демонстрирует влияние задания различных спецификаций на печать "HELLO, WORLD" (12 символов).
Мы поместили двоеточия вокруг каждого поля для того, чтобы вы могли видеть его протяженность.
Предостережение: PRINTF использует свой первый аргумент для определения числа последующих аргументов и их типов. Если количество аргументов окажется недостаточным или они будут иметь несоответственные типы, то возникнет путаница и вы получите бессмысленные результаты.
Упражнение 7-1.
Напишите программу, которая будет печатать разумным образом произвольный ввод. Как минимум она должна печатать неграфические символы в восьмеричном или шестнадцатеричном виде (в соответствии с принятыми у вас обычаями) и складывать длинные строки.
7.4. Форматный ввод — функция SCANF Осуществляющая ввод функция SCANF является аналогом PRINTF и позволяет проводить в обратном направлении многие из тех же самых преобразований.
Функция SCANF(CONTROL, ARG1, ARG2,...) читает символы из стандартного ввода, интерпретирует их в соответствии с форматом, указанном в аргументе CONTROL, и помещает результаты в остальные аргументы. Управляющий аргумент описывается ниже; другие аргументы, каждый из которых должен быть указателем, определяют, куда следует поместить соответствующим образом преобразованный ввод.
Управляющая строка обычно содержит спецификации преобразования, которые используются для непосредственной интерпретации входных последовательностей.
Управляющая строка может содержать:
- пробелы, табуляции или символы новой строки ("символы пустых промежутков"), которые игнорируются.
- Обычные символы (не % ), которые предполагаются совпадающими со следующими отличными от символов пустых промежутков символами входного потока.
- Спецификации преобразования, состоящие из символа %, необязательного символа подавления присваивания *, необязательного числа, задающего максимальную ширину поля и символа преобразования.
Спецификация преобразования управляет преобразованием следующего поля ввода. нормально результат помещается в переменную, которая указывается соответствующим аргументом. Если, однако, с помощью символа * указано подавление присваивания, то это поле ввода просто пропускается и никакого присваивания не производится. Поле ввода определяется как строка символов, которые отличны от символов простых промежутков; оно продолжается либо до следующего символа пустого промежутка, либо пока не будет исчерпана ширина поля, если она указана. Отсюда следует, что при поиске нужного ей ввода, функция SCANF будет пересекать границы строк, поскольку символ новой строки входит в число пустых промежутков.
Символ преобразования определяет интерпретацию поля ввода; согласно требованиям основанной на вызове по значению семантики языка "с" соответствующий аргумент должен быть указателем. Допускаются следующие символы преобразования: D — на вводе ожидается десятичное целое;
соответствующий аргумент должен быть указателем на целое.
O — На вводе ожидается восьмеричное целое (с лидирующим нулем или без него);
соответствующий аргумент должен быть указателем на целое.
X — На вводе ожидается шестнадцатеричное целое (с лидирующими 0X или без них);
соответствующий аргумент должен быть указателем на целое.
H — На вводе ожидается целое типа SHORT; соответсвующий аргумент должен быть указателем на целое типа SHORT.
C — Ожидается отдельный символ; соответствующий аргумент должен быть указателем на символы; следующий вводимый символ помещается в указанное место. Обычный пропуск символов пустых промежутков в этом случае подавляется; для чтения следующего символа, который не является символом пустого промежутка, пользуйтесь спецификацией преобразования % 1S.
S — Ожидается символьная строка; соответствующий аргумент должен быть указателем символов, который указывает на массив символов, который достаточно велик для принятия строки и добавляемого в конце символа \0.
F — Ожидается число с плавающей точкой; соответствующий аргумент должен быть указателем на переменную типа FLOAT.
Е — символ преобразования E является синонимом для F. Формат ввода переменной типа FLOAT включает необязательный знак, строку цифр, возможно содержащую десятичную точку и необязательное поле экспоненты, состоящее из буквы E, за которой следует целое, возможно имеющее знак.
Перед символами преобразования D, O и X может стоять L, которая означает, что в списке аргументов должен находиться указатель на переменную типа LONG, а не типа INT. Аналогично, буква L может стоять перед символами преобразования E или F, говоря о том, что в списке аргументов должен находиться указатель на переменную типа DOUBLE, а не типа FLOAT.
Например, обращение INT I;
FLOAT X;
CHAR NAME[50];
SCANF("&D % F % S", &I, &X, NAME);
со строкой на вводе 25 54.32E-1 THOMPSON приводит к присваиванию I значения 25,X — значения 5.432 и NAME — строки "THOMPSON", надлежащим образом законченной символом \ 0. эти три поля ввода можно разделить столькими пробелами, табуляциями и символами новых строк, сколько вы пожелаете. Обращение INT I;
FLOAT X;
CHAR NAME[50];
SCANF("%2D % F % *D % 2S", &I, &X, NAME);
с вводом 56789 0123 45A присвоит I значение 56, X — 789.0, пропустит 0123 и поместит в NAME строку "45".
при следующем обращении к любой процедуре ввода рассмотрение начнется с буквы A. В этих двух примерах NAME является указателем и, следовательно, перед ним не нужно помещать знак &.
В качестве другого примера перепишем теперь элементарный калькулятор из главы 4, используя для преобразования ввода функцию SCANF:
#INCLUDE MAIN() /* RUDIMENTARY DESK CALCULATOR */ DOUBLE SUM, V;
WHILE (SCANF("% LF", &V) !=EOF) PRINTF("\T%.2F\N", SUM += V);
выполнение функции SCANF заканчивается либо тогда, когда она исчерпывает свою управляющую строку, либо когда некоторый элемент ввода не совпадает с управляющей спецификацией. В качестве своего значения она возвращает число правильно совпадающих и присвоенных элементов ввода. Это число может быть использовано для определения количества найденных элементов ввода. при выходе на конец файла возвращается EOF; подчеркнем, что это значение отлично от 0, что следующий вводимый символ не удовлетворяет первой спецификации в управляющей строке. При следующем обращении к SCANF поиск возобновляется непосредственно за последним введенным символом.
Заключительное предостережение: аргументы функции SCANF должны быть указателями. Несомненно наиболее распространенная ошибка состоит в написании SCANF("%D", N);
вместо SCANF("%D", &N);
7.5. Форматное преобразование в памяти От функции SCANF и PRINTF происходят функции SSCANF и SPRINTF, которые осуществляют аналогичные преобразования, но оперируют со строкой, а не с файлом.
Обращения к этим функциям имеют вид:
SPRINTF(STRING, CONTROL, ARG1, ARG2,...) SSCANF(STRING, CONTROL, ARG1, ARG2,...) Как и раньше, функция SPRINTF преобразует свои аргументы ARG1, ARG2 и т.д. В соответствии с форматом, указанным в CONTROL, но помещает результаты в STRING, а не в стандартный вывод. KОнечно, строка STRING должна быть достаточно велика, чтобы принять результат. Например, если NAME — это символьный массив, а N — целое, то SPRINTF(NAME, "TEMP% D", N);
создает в NAME строку вида TEMPNNN, где NNN — значение N. Функция SSCANF выполняет обратные преобразования — она просматривает строку STRING в соответствии с форматом в аргументе CONTROL и помещает результирующие значения в аргументы ARG1, ARG2 и т.д.эти аргументы должны быть указателями. В результате обращения SSCANF(NAME, "TEMP% D", &N);
переменная N получает значение строки цифр, следующих за TEMP в NAME.
Упражнение 7-2.
Перепишите настольный калькулятор из главы 4, используя для ввода и преобразования чисел SCANF и/или SSCANF.
7.6. Доступ к файлам Все до сих пор написанные программы читали из стандартного ввода и писали в стандартный вывод, относительно которых мы предполагали, что они магическим образом предоставлены программе местной операционной системой.
Следующим шагом в вопросе ввода-вывода является написание программы, работающей с файлом, который не связан заранее с программой. одной из программ, которая явно демонстрирует потребность в таких операциях, является CAT, которая объединяет набор из нескольких именованных файлов в стандартный вывод.
Программа CAT используется для вывода файлов на терминал и в качестве универсального сборщика ввода для программ, которые не имеют возможности обращаться к файлам по имени. Например, команда CAT X.C.Y.C печатает содержимое файлов X.C и Y.C в стандартный вывод.
Вопрос состоит в том, как организовать чтение из именованных файлов, т.е., как связать внешние имена, которыми мыслит пользователь, с фактически читающими данные операторами.
Эти правила просты. Прежде чем можно считывать из некоторого файла или записывать в него, этот файл должен быть открыт с помощью функции FOPEN из стандартной библиотеки. функция FOPEN берет внешнее имя (подобное X.C или Y.C), проводит некоторые обслуживающие действия и переговоры с операционной системой (детали которых не должны нас касаться) и возвращает внутреннее имя, которое должно использоваться при последующих чтениях из файла или записях в него.
Это внутреннее имя, называемое "указателем файла", фактически является указателем структуры, которая содержит информацию о файле, такую как место размещения буфера, текущая позиция символа в буфере, происходит ли чтение из файла или запись в него и тому подобное. Пользователи не обязаны знать эти детали, потому что среди определений для стандартного ввода-вывода, получаемых из файла STDIO.H, содержится определение структуры с именем FILE. Единственное необходимое для указателя файла описание демонстрируется примером:
Здесь говорится, что FP является указателем на FILE и FOPEN возвращает указатель на FILE. Oбратите внимание, что FILE является именем типа, подобным INT, а не ярлыку структуры; это реализовано как TYPEDEF. (Подробности того, как все это работает на системе UNIX, приведены в главе 8).
Фактическое обращение к функции FOPEN в программе имеет вид:
FP=FOPEN(NAME,MODE);
Первым аргументом функции FOPEN является "имя" файла, которое задается в виде символьной строки. Второй аргумент MODE ("режим") также является символьной строкой, которая указывает, как этот файл будет использоваться.
Допустимыми режимами являются: чтение ("R"), запись ("W") и добавление ("A").
Если вы откроете файл, который еще не сущетвует, для записи или добавления, то такой файл будет создан (если это возможно). Открытие существующего файла на запись приводит к отбрасыванию его старого содержимого. Попытка чтения несуществующего файла является ощибкой.
Ошибки могут быть обусловлены и другими причинами (например, попыткой чтения из файла, не имея на то разрешения). При наличии какой-либо ошибки функция возвращает нулевое значение указателя NULL (которое для удобства также определяется в файле STDIO.H).
Другой необходимой вещью является способ чтения или записи, если файл уже открыт. Здесь имеется несколько возможностей, из которых GETC и PUTC являются простейшими.функция GETC возвращает следующий символ из файла; ей необходим указатель файла, чтобы знать, из какого файла читать. Таким образом, помещает в "C" следующий символ из файла, указанного посредством FP, и EOF, если достигнут конец файла.
Функция PUTC, являющаяся обращением к функции GETC, помещает символ "C" в файл FP и возвращает "C". Подобно функциям GETCHAR и PUTCHAR, GETC и PUTC могут быть макросами, а не функциями.
При запуске программы автоматически открываются три файла, которые снабжены определенными указателями файлов. Этими файлами являются стандартный ввод, стандартный вывод и стандартный вывод ошибок;
соответствующие указатели файлов называются STDIN, STDOUT и STDERR. Обычно все эти указатели связаны с терминалом, но STDIN и STDOUT могут быть перенаправлены на файлы или в поток (PIPE), как описывалось в разделе 7.2.
Функции GETCHAR и PUTCHAR могут быть определены в терминалах GETC, PUTC, STDIN и STDOUT следующим образом: #DEFINE GETCHAR() GETC(STDIN) #DEFINE PUTCHAR(C) PUTC(C, STDOUT) При работе с файлами для форматного ввода и вывода можно использовать функции FSCANF и FPRINTF. Они идентичны функциям SCANF и PRINTF, за исключением того, что первым аргументом является указатель файла, определяющий тот файл, который будет читаться или куда будет вестись запись; управляющая строка будет вторым аргументом.
Покончив с предварительными замечаниями, мы теперь в состоянии написать программу CAT для конкатенации файлов. Используемая здесь основная схема оказывается удобной во многих программах: если имеются аргументы в командной строке, то они обрабатываются последовательно. Если такие аргументы отсутствуют, то обрабатывается стандартный ввод. Это позволяет использовать программу как самостоятельно, так и как часть большей задачи.
#INCLUDE MAIN(ARGC, ARGV) /*CAT: CONCATENATE FILES*/ INT ARGC;
CHAR *ARGV[];
FILE *FP, *FOPEN();
IF(ARGC==1) /*NO ARGS; COPY STANDARD INPUT*/ FILECOPY(STDIN);
ELSE WHILE (--ARGC > 0) IF ((FP=FOPEN(*++ARGV,"R"))==NULL) \( PRINTF("CAT:CAN'T OPEN %\N",*ARGV);
FILECOPY(FP) /*COPY FILE FP TO STANDARD OUTPUT*/
FILE *FP;WHILE ((C=GETC(FP)) !=EOF) PUTC(C, STDOUT);
Указатели файлов STDIN и STDOUT заранее определены в библиотеке ввода-вывода как стандартный ввод и стандартный вывод; они могут быть использованы в любом месте, где можно использовать объект типа FILE*.они однако являются константами, а не переменными, так что не пытайтесь им что-либо присваивать.
Функция FCLOSE является обратной по отношению к FOPEN; она разрывает связь между указателем файла и внешним именем, установленную функцией FOPEN, и высвобождает указатель файла для другого файла.большинство операционных систем имеют некоторые ограничения на число одновременно открытых файлов, которыми может распоряжаться программа. Поэтому, то как мы поступили в CAT, освободив не нужные нам более объекты, является хорошей идеей. Имеется и другая причина для применения функции FCLOSE к выходному файлу — она вызывает выдачу информации из буфера, в котором PUTC собирает вывод. (При нормальном завершении работы программы функция FCLOSE вызывается автоматически для каждого открытого файла).
7.7. Обработка ошибок — STDERR и EXIT Обработка ошибок в CAT неидеальна. Неудобство заключается в том, что если один из файлов по некоторой причине оказывается недоступным, диагностическое сообщение об этом печатается в конце объединенного вывода. Это приемлемо, если вывод поступает на терминал, но не годится, если вывод поступает в некоторый файл или через поточный (PIPELINE) механизм в другую программу.
Чтобы лучше обрабатывать такую ситуацию, к программе точно таким же образом, как STDIN и STDOUT, присоединяется второй выходной файл, называемый STDERR. Если это вообще возможно, вывод, записанный в файле STDERR, появляется на терминале пользователя, даже если стандартный вывод направляется в другое место.
Давайте переделаем программу CAT таким образом, чтобы сообщения об ошибках писались в стандартный файл ошибок.
"INCLUDE MAIN(ARGC,ARGV) /*CAT: CONCATENATE FILES*/ INT ARGC;
CHAR *ARGV[];
FILE *FP, *FOPEN();
FILECOPY(STDIN);
WHILE (--ARGC > 0) IF((FP=FOPEN(*++ARGV,"R#))==NULL) \( PRINTF(STDERR, \) ELSE \( EXIT(0);
Программа сообщает об ошибках двумя способами. Диагностическое сообщение, выдаваемое функцией FPRINTF, поступает в STDERR и, таким образом, оказывается на терминале пользователя, а не исчезает в потоке (PIPELINE) или в выходном файле.
Программа также использует функцию EXIT из стандартной библиотеки, обращение к которой вызывает завершение выполнения программы. Аргумент функции EXIT доступен любой программе, обращающейся к данной функции, так что успешное или неудачное завершение данной программы может быть проверено другой программой, использующей эту в качестве подзадачи. По соглашению величина в качетсве возвращаемого значения свидетельствует о том, что все в порядке, а различные ненулевые значения являются признаками нормальных ситуаций.
Функция EXIT вызывает функцию FCLOSE для каждого открытого выходного файла, с тем чтобы вывести всю помещенную в буферы выходную информацию, а затем вызывает функцию _EXIT. Функция _EXIT приводит к немедленному завершению без очистки каких-либо буферов; конечно, при желании к этой функции можно обратиться непосредственно.
7.8. Ввод и вывод строк Стандартная библиотека содержит функцию FGETS, совершенно аналогичную функции GETLINE, которую мы использовали на всем протяжении книги. В результате обращения FGETS(LINE, MAXLINE, FP) следующая строка ввода (включая символ новой строки) считывается из файла FP в символьный массив LINE; самое большое MAXLINE_1 символ будет прочитан.
Результирующая строка заканчивается символом \ 0. Нормально функция FGETS возвращает LINE; в конце файла она возвращает NULL. (Наша функция GETLINE возвращает длину строки, а при выходе на конец файла - нуль).
Предназначенная для вывода функция FPUTS записывает строку (которая не обязана содержать символ новой строки) в файл:
FPUTS(LINE, FP) Чтобы показать, что в функциях типа FGETS и FPUTS нет ничего таинственного, мы приводим их ниже, скопированными непосредственно из стандартной библиотеки ввода-вывода:
#INCLUDE CHAR *FGETS(S,N,IOP) /*GET AT MOST N CHARS FROM IOP*/ REGISTER FILE *IOP;
REGISTER INT C;
REGISTER CHAR *CS;WHILE(--N>0&&(C=GETC(IOP)) !=EOF) IF ((*CS++ = C)=='\N') *CS = '\0';
RETURN((C==EOF && CS==S) 7 NULL : S);
FPUTS(S,IOP) /*PUT STRING S ON FILS IOP*/ REGISTER CHAR *S;
REGISTER FILE *IOP;
REGISTER INT C;
WHILE (C = *S++) PUTC(C,IOP);Упражнение 7-3.
Напишите программу сравнения двух файлов, которая будет печатать первую строку и позицию символа, где они различаются.
Упражнение 7-4.
Переделайте программу поиска заданной комбинации символов из главы таким образом, чтобы в качестве ввода использовался набор именованных файлов или, если никакие файлы не указаны как аргументы, стандартный ввод. Следует ли печатать имя файла при нахождении подходящей строки?
Упражнение 7-5.
Напишите программу печати набора файлов, которая начинает каждый новый файл с новой страницы и печатает для каждого файла заголовок и счетчик текущих страниц.
7.9. Несколько разнообразных функций Стандартная библиотека предоставляет множество разнообразных функций, некоторые из которых оказываются особенно полезными. Мы уже упоминали функции для работы со строками: STRLEN, STRCPY, STRCAT и STRCMP. Вот некоторые другие.
7.9.1. Проверка вида символов и преобразования Некоторые макросы выполняют проверку символов и преобразования:
SALPHA(C) не 0, если "C" алфавитный символ, SUPPER(C) Не 0, если "C" буква верхнего регистра, SLOWER(C) Не 0, если "C" буква нижнего регистра, SDIGIT(C) Не 0, если "C" цифра, SSPACL(C) Не 0, если "C" пробел, табуляция или новая строка, 0 — OUPPER(C) Преобразует "C" в букву верхнего регистра.
OLOWER(C) Преобразует "C" в букву нижнего регистра.
7.9.2. Функция UNGETC Стандартная библиотека содержит довольно ограниченную версию функции UNGETCH, написанной нами в главе 4; она называется UNGETC. В результате обращения UNGETC(C,FP) символ "C" возвращается в файл FP. Позволяется возвращать в каждый файл только один символ. Функция UNGETC может быть использована в любой из функций ввода и с макросами типа SCANF, GETC или GETCHAR.
7.9.3. Обращение к системе Функция SYSTEM(S) выполняет команду, содержащуюся в символьной строке S, и затем возобновляет выполнение текущей программы. Содержимое S сильно зависит от используемой операционной системы. В качестве тривиального примера, укажем, что на системе UNIX строка SYSTEM("DATE");
приводит к выполнению программы DATE, которая печатает дату и время дня.
7.9.4. Управление памятью Функция CALLOC весьма сходна с функцией ALLOC, использованной нами в предыдущих главах. В результате обращения CALLOC(N, SIZEOF(OBJCCT)) возвращается либо указатель пространства, достаточного для размещения N объектов указанного размера, либо NULL, если запрос не может быть удволетворен. Отводимая память инициализируется нулевыми значениями.
Указатель обладает нужным для рассматриваемых объектов выравниванием, но ему следует приписывать соответствующий тип, как в CHAR *CALLOC();
INT *IP;
IP=(INT*) CALLOC(N,SIZEOF(INT));
Функция CFREE(P) освобождает пространство, на которое указывает "P", причем указатель "P" певоначально должен быть получен в результате обращения к CALLOC.
Здесь нет никаких ограничений на порядок освобождения пространства, но будет неприятнейшей ошибкой освободить что-нибудь, что не было получено обращением к CALLOC.
Реализация программы распределения памяти, подобной CALLOC, в которой размещенные блоки могут освобождаться в произвольном порядке, продемонстрирована в главе 8.
8. Интерфейс системы UNIX Материал этой главы относится к интерфейсу между с-программами и операционной системой UNIX. Так как большинство пользователей языка "C" работают на системе UNIX, эта глава окажется полезной для большинства читателей.
даже если вы используете с-компилятор на другой машине, изучение приводимых здесь примеров должно помочь вам глубже проникнуть в методы программирования на языке "C".
Эта глава делится на три основные части: ввод/вывод, система файлов и распределение памяти. Первые две части предполагают небольшое знакомство с внешними характеристиками системы UNIX.
В главе 7 мы имели дело с системным интерфейсом, который одинаков для всего многообразия операционных систем. На каждой конкретной системе функции стандартной библиотеки должны быть написаны в терминах ввода-вывода, доступных на данной машине. В следующих нескольких разделах мы опишем основную систему связанных с вводом и выводом точек входа операционной системы UNIX и проиллюстрируем, как с их помощью могут быть реализованы различные части стандартной библиотеки.
8.1. Дескрипторы файлов В операционной системе UNIX весь ввод и вывод осуществляется посредством чтения файлов или их записи, потому что все периферийные устройства, включая даже терминал пользователя, являются файлами определенной файловой системы.
Это означает, что один однородный интерфейс управляет всеми связями между программой и периферийными устройствами.
В наиболее общем случае перед чтением из файла или записью в файл необходимо сообщить системе о вашем намерении; этот процесс называется "открытием" файла. Система выясняет,имеете ли вы право поступать таким образом (существует ли этот файл? имеется ли у вас разрешение на обращение к нему?), и если все в порядке, возвращает в программу небольшое положительное целое число, называемое дескриптором файла. всякий раз, когда этот файл используется для ввода или вывода, для идентификации файла употребляется дескриптор файла, а не его имя. (Здесь существует примерная аналогия с использованием READ (5,...) и WRITE (6,...) в фортране). Вся информация об открытом файле содержится в системе;
программа пользователя обращается к файлу только через дескриптор файла.
Для удобства выполнения обычных операций ввода и вывода с помощью терминала пользователя существуют специальные соглашения. Когда интерпретатор команд ("SHELL") прогоняет программу, он открывает три файла, называемые стандартным вводом, стандартным выводом и стандартным выводом ошибок, которые имеют соответственно числа 0, 1 и 2 в качестве дескрипторов этих файлов. В нормальном состоянии все они связаны с терминалом, так что если программа читает с дескриптором файла 0 и пишет с дескрипторами файлов 1 и 2, то она может осуществлять ввод и вывод с помощью терминала, не заботясь об открытии соответствующих файлов.
Пользователь программы может перенаправлять ввод и вывод на файлы, используя операции командного интерпретатора SHELL "" :
PROG OUTFILE
В этом случае интерпретатор команд SHELL изменит присваивание по умолчанию дескрипторов файлов 0 и 1 с терминала на указанные файлы. Нормально дескриптор файла 2 остается связанным с терминалом, так что сообщения об ошибках могут поступать туда. Подобные замечания справедливы и тогда, когда ввод и вывод связан с каналом. Следует отметить, что во всех случаях прикрепления файлов изменяются интерпретатором SHELL, а не программой. Сама программа, пока она использует файл 0 для ввода и файлы 1 и 2 для вывода, не знает ни откуда приходит ее ввод, ни куда поступает ее выдача.8.2. Низкоуровневый ввод/вывод — операторы READ и WRITE Самый низкий уровень ввода/вывода в системе UNIX не предусматривает ни какойлибо буферизации, ни какого-либо другого сервиса; он по существу является непосредственным входом в операционную систему. Весь ввод и вывод осуществляется двумя функциями: READ и WRITE. Первым аргументом обеих функций является дескриптор файла. Вторым аргументом является буфер в вашей программе, откуда или куда должны поступать данные. Третий аргумент — это число подлежащих пересылке байтов. Обращения к этим функциям имеют вид:
N_READ=READ(FD,BUF,N);
N_WRITTEN=WRITE(FD,BUF,N);
При каждом обращении возвращается счетчик байтов, указывающий фактическое число переданных байтов. При чтении возвращенное число байтов может оказаться меньше, чем запрошенное число. Возвращенное нулевое число байтов означает конец файла, а "-1" указывает на наличие какой-либо ошибки. При записи возвращенное значение равно числу фактически записанных байтов; несовпадение этого числа с числом байтов, которое предполагалось записать, обычно свидетельствует об ошибке.
Количество байтов, подлежащих чтению или записи, может быть совершенно произвольным. Двумя самыми распространенными величинами являются "1", которая означает передачу одного символа за обращение (т.е. Без использования буфера), и "512", которая соответствует физическому размеру блока на многих периферийных устройствах. Этот последний размер будет наиболее эффективным, но даже ввод или вывод по одному символу за обращение не будет необыкновенно дорогим.
«