Структуры, ссылающиеся на себя

Предположим, что нам надо справиться с более общей зада-чей, состоящей в подсчете числа появлений всех слов в неко-тором файле ввода. Так как список слов заранее не известен,мы не можем их упорядочить удобным образом и использоватьбинарный поиск. Мы даже не можем осуществлять последователь-ный просмотр при поступлении каждого слова, с тем чтобы ус-тановить, не встречалось ли оно ранее; такая программа будетработать вечно. (Более точно, ожидаемое время работы растеткак квадрат числа вводимых слов). Как же нам организоватьпрограмму, чтобы справиться со списком произвольных слов? Одно из решений состоит в том, чтобы все время хранитьмассив поступающих до сих пор слов в упорядоченном виде, по-мещая каждое слово в нужное место по мере их поступления.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 20MAIN() /* WORD FREGUENCY COUNT */\(STRUCT TNODE *ROOT, *TREE(); CHAR WORD[MAXWORD]; INT T; ROOT = NULL; WHILE ((T = GETWORD(WORD, MAXWORD)) \! = EOF) IF (T == LETTER) ROOT = TREE(ROOT, WORD); TREEPRINT(ROOT);\) Функция TREE сама по себе проста. Слово передается функ-цией MAIN к верхнему уровню (корню) дерева. На каждом этапеэто слово сравнивается со словом, уже хранящимся в этом уз-ле, и с помощью рекурсивного обращения к TREE просачиваетсявниз либо к левому, либо к правому поддереву. В конце концовэто слово либо совпадает с каким-то словом, уже находящимсяв дереве (в этом случае счетчик увеличивается на единицу),либо программа натолкнется на нулевой указатель, свидетель-ствующий о необходимости создания и добавления к дереву но-вого узла. В случае создания нового узла функция TREE возв-ращает указатель этого узла, который помещается в родитель-ский узел. STRUCT TNODE *TREE(P, W) /* INSTALL W AT OR BELOW P */ STRUCT TNODE *P; CHAR *W; \(STRUCT TNODE *TALLOC(); CHAR *STRSAVE(); INT COND; IF (P == NULL) \(/* A NEW WORD HAS ARRIVED */ P == TALLOC(); /* MAKE A NEW NODE */ P->WORD = STRSAVE(W); P->COUNT = 1; P->LEFT = P->RIGHT = NULL; \) ELSE IF ((COND = STRCMP(W, P->WORD)) == 0) P->COUNT++; /* REPEATED WORD */ ELSE IF (COND < 0)/* LOWER GOES INTO LEFT SUBTREE */ P->LEFT = TREE(P->LEFT, W); ELSE /* GREATER INTO RIGHT SUBTREE */ P->RIGHT = TREE(P->RIGHT, W); RETURN(P); \) Память для нового узла выделяется функцией TALLOC, явля-ющейся адаптацией для данного случая функции ALLOC, написан-ной нами ранее. Она возвращает указатель свободного прост-ранства, пригодного для хранения нового узла дерева. (Мывскоре обсудим это подробнее). Новое слово копируется функ-цией STRSAVE в скрытое место, счетчик инициализируется еди-ницей, и указатели обоих потомков полагаются равными нулю.Эта часть программы выполняется только при добавлении новогоузла к ребру дерева. Мы здесь опустили проверку на ошибкивозвращаемых функций STRSAVE и TALLOC значений (что неразум-но для практически работающей программы). Функция TREEPRINT печатает дерево, начиная с левого под-дерева; в каждом узле сначала печатается левое поддерево(все слова, которые младше этого слова), затем само слово, азатем правое поддерево (все слова, которые старше). Если вынеуверенно оперируете с рекурсией, нарисуйте дерево сами инапечатайте его с помощью функции TREEPRINT; это одна изнаиболее ясных рекурсивных процедур, которую можно найти. TREEPRINT (P) /* PRINT TREE P RECURSIVELY */ STRUCT TNODE *P; \(IF (P!= NULL) \(TREEPRINT (P->LEFT); PRINTF("%4D %S\N", P->COUNT, P->WORD); TREEPRINT (P->RIGHT); \)\) Практическое замечание: если дерево становится "несба-лансированным" из-за того, что слова поступают не в случай-ном порядке, то время работы программы может расти слишкомбыстро. В худшем случае, когда поступающие слова уже упоря-дочены, настоящая программа осуществляет дорогостоящую ими-тацию линейного поиска. Существуют различные обобщения дво-ичного дерева, особенно 2-3 деревья и AVL деревья, которыене ведут себя так "в худших случаях", но мы не будем здесьна них останавливаться. Прежде чем расстаться с этим примером, уместно сделатьнебольшое отступление в связи с вопросом о распределении па-мяти. Ясно, что в программе желательно иметь только одинраспределитель памяти, даже если ему приходится размещатьразличные виды объектов. Но если мы хотим использовать одинраспределитель памяти для обработки запросов на выделениепамяти для указателей на переменные типа CHAR и для указате-лей на STRUCT TNODE, то при этом возникают два вопроса. Пер-вый: как выполнить то существующее на большинстве реальныхмашин ограничение, что объекты определенных типов должныудовлетворять требованиям выравнивания (например, часто це-лые должны размещаться в четных адресах)? Второй: как орга-низовать описания, чтобы справиться с тем, что функция ALLOCдолжна возвращать различные виды указателей? Вообще говоря, требования выравнивания легко выполнитьза счет выделения некоторого лишнего пространства, простообеспечив то, чтобы распределитель памяти всегда возвращалуказатель, удовлетворяющий всем ограничениям выравнивания.Например, на PDP-11 достаточно, чтобы функция ALLOC всегдавозвращала четный указатель, поскольку в четный адрес можнопоместить любой тип объекта. единственный расход при этом -лишний символ при запросе на нечетную длину. Аналогичныедействия предпринимаются на других машинах. Таким образом,реализация ALLOC может не оказаться переносимой, но ее ис-пользование будет переносимым. Функция ALLOC из главы 5 непредусматривает никакого определенного выравнивания; в главе8 мы продемонстрируем, как правильно выполнить эту задачу. Вопрос описания типа функции ALLOC является мучительнымдля любого языка, который серьезно относится к проверке ти-пов. Лучший способ в языке "C" - объявить, что ALLOC возвра-щает указатель на переменную типа CHAR, а затем явно преоб-разовать этот указатель к желаемому типу с помощью операцииперевода типов. Таким образом, если описать P в виде CHAR *P;то (STRUCT TNODE *) P преобразует его в выражениях в указатель на структуру типаTNODE. Следовательно, функцию TALLOC можно записать в виде: STRUCT TNODE *TALLOC()\(CHAR *ALLOC(); RETURN ((STRUCT TNODE *) ALLOC(SIZEOF(STRUCT TNODE)));\) это более чем достаточно для работающих в настоящее времякомпиляторов, но это и самый безопасный путь с учетом будую-щего. Упражнение 6-4 ---------------- Напишите программу, которая читает "C"-программу и печа-тает в алфавитном порядке каждую группу имен переменных, ко-торые совпадают в первых семи символах, но отличаются где-тодальше. (Сделайте так, чтобы 7 было параметром). Упражнение 6-5 ---------------- Напишите программу выдачи перекрестных ссылок, т.е.Программу, которая печатает список всех слов документа и длякаждого из этих слов печатает список номеров строк, в кото-рые это слово входит. Упражнение 6-6 ---------------- Напишите программу, которая печатает слова из своегофайла ввода, расположенные в порядке убывания частоты их по-явления. Перед каждым словом напечатайте число его появле-ний.

Поиск в таблице

Для иллюстрации дальнейших аспектов использования струк-тур в этом разделе мы напишем программу, представляющую со-бой содержимое пакета поиска в таблице. Эта программа явля-ется типичным представителем подпрограмм управления символь-ными таблицами макропроцессора или компилятора. Рассмотрим,например, оператор #DEFINE языка "C". Когда встречаетсястрока вида #DEFINE YES 1 то имя YES и заменяющий текст 1 помещаются в таблицу. Позд-нее, когда имя YES появляется в операторе вида INWORD = YES; Oно должно быть замещено на 1. Имеются две основные процедуры, которые управляют имена-ми и заменяющими их текстами. Функция INSTALL(S,T) записыва-ет имя S и заменяющий текст T в таблицу; здесь S и T простосимвольные строки. Функция LOOKUP(S) ищет имя S в таблице ивозвращает либо указатель того места, где это имя найдено,либо NULL, если этого имени в таблице не оказалось. При этом используется поиск по алгоритму хеширования -поступающее имя преобразуется в маленькое положительное чис-ло, которое затем используется для индексации массива указа-телей. Элемент массива указывает на начало цепочных блоков,описывающих имена, которые имеют это значение хеширования.Если никакие имена при хешировании не получают этого значе-ния, то элементом массива будет NULL. Блоком цепи является структура, содержащая указатели насоответствующее имя, на заменяющий текст и на следующий блокв цепи. Нулевой указатель следующего блока служит признакомконца данной цепи. STRUCT NLIST \(/* BASIC TABLE ENTRY */ CHAR *NAME; CHAR *DEF; STRUCT NLIST *NEXT; /* NEXT ENTRY IN CHAIN */\); Массив указателей это просто DEFINE HASHSIZE 100 TATIC STRUCT NLIST *HASHTAB[HASHSIZE] /* POINTER TABLE */ Значение функции хеширования, используемой обеими функ-циями LOOKUP и INSTALL, получается просто как остаток отделения суммы символьных значений строки на размер массива.(Это не самый лучший возможный алгоритм, но его достоинствосостоит в исключительной простоте). HASH(S) /* FORM HASH VALUE FOR STRING */ CHAR *S; \(INT HASHVAL; FOR (HASHVAL = 0; *S!= '\0';) HASHVAL += *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); /* FOUND IT */RETURN(NULL); /* NOT FOUND */ Функция 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) RETURN(NULL); IF ((NP->NAME = STRSAVE(NAME)) == NULL) RETURN(NULL); HASHVAL = HASH(NP->NAME); NP->NEXT = HASHTAB[HASHVAL]; HASHTAB[HASHVAL] = NP; \) ELSE /* ALREADY THERE */ FREE((NP->DEF);/* FREE PREVIOUS DEFINITION */ IF ((NP->DEF = STRSAVE(DEF)) == NULL) RETURN (NULL); RETURN(NP); \) Функция STRSAVE просто копирует строку, указанную в ка-честве аргумента, в место хранения, полученное в результатеобращения к функции ALLOC. Мы уже привели эту функцию в гла-ве 5. Так как обращение к функции ALLOC и FREE могут проис-ходить в любом порядке и в связи с проблемой выравнивания,простой вариант функции ALLOC из главы 5 нам больше не под-ходит; смотрите главы 7 и 8. Упражнение 6-7 --------------- Напишите процедуру, которая будет удалять имя и опреде-ление из таблицы, управляемой функциями LOOKUP и INSTALL. Упражнение 6-8 --------------- Разработайте простую, основанную на функциях этого раз-дела, версию процессора для обработки конструкций #DEFINE,пригодную для использования с "C"-программами. Вам могуттакже оказаться полезными функции GETCHAR и UNGETCH.

Поля

Когда вопрос экономии памяти становится очень существен-ным, то может оказаться необходимым помещать в одно машинноеслово несколько различных объектов; одно из особенно расп-росраненных употреблений - набор однобитовых признаков вприменениях, подобных символьным таблицам компилятора. внеш-не обусловленные форматы данных, такие как интерфейсы аппа-ратных средств также зачастую предполагают возможность полу-чения слова по частям. Представьте себе фрагмент компилятора, который работаетс символьной таблицей. С каждым идентификатором программысвязана определенная информация, например, является он илинет ключевым словом, является ли он или нет внешним и/илистатическим и т.д. Самый компактный способ закодировать та-кую информацию - поместить набор однобитовых признаков в от-дельную переменную типа CHAR или INT. Обычный способ, которым это делается, состоит в опреде-лении набора "масок", отвечающих соответствущим битовым по-зициям, как в #DEFINE KEYWORD 01 #DEFINE EXTERNAL 02 #DEFINE STATIC 04 (числа должны быть степенями двойки). Тогда обработка битовсведется к "жонглированию битами" с помощью операций сдвига,маскирования и дополнения, описанных нами в главе 2. Некоторые часто встречающиеся идиомы: FLAGS \!= EXTERNAL \! STATIC; включает биты EXTERNAL и STATIC в FLAGS, в то время как FLAGS &= \^(еXTERNAL \! STATIC); их выключает, а IF ((FLAGS & (EXTERNAL \! STATIC)) == 0)... истинно, если оба бита выключены. Хотя этими идиомами легко овладеть, язык "C" в качествеальтернативы предлагает возможность определения и обработкиполей внутри слова непосредственно, а не посредством побито-вых логических операций. Поле - это набор смежных битоввнутри одной переменной типа INT. Синтаксис определения иобработки полей основывается на структурах. Например, сим-вольную таблицу конструкций #DEFINE, приведенную выше, можнобы было заменить определением трех полей: STRUCT \(UNSIGNED IS_KEYWORD: 1; UNSIGNED IS_EXTERN: 1; UNSIGNED IS_STATIC: 1; \) FLAGS; Здесь определяется переменная с именем 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); они не являютсямассивами; они не имеют адресов, так что к ним не применимаоперация &.

Объединения

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); ELSE IF (UTYPE == FLOAT) PRINTF("%F\N", UVAL.FVAL); ELSE IF (UTYPE == STRING) PRINTF("%S\N", UVAL.PVAL); ELSE 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,показывает, как можно использовать объединение, чтобы сде-лать некоторую переменную выровненной по определенному видуграницы памяти.

Определение типа

В языке "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 для описания узлов дерева, рассмотренных ра-нее в этой главе: TYPEDEF 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 */ \) TREENODE, *TREEPTR; В результате получаем два новых ключевых слова: TREENODE(структура) и TREEPTR (указатель на структуру). Тогда функ-цию TALLOC можно записать в виде TREEPTR TALLOC() \(CHAR *ALLOC(); 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. Ввод и вывод *

Средства ввода/вывода не являются составной частью языка"с", так что мы не выделяли их в нашем предыдущем изложении.Однако реальные программы взаимодействуют со своей окружаю-щей средой гораздо более сложным образом, чем мы видели досих пор. В этой главе будет описана "стандартная библиотекаввода/вывода", то есть набор функций, разработанных дляобеспечения стандартной системы ввода/вывода для "с"- прог-рамм. Эти функции предназначены для удобства программногоинтерфейса, и все же отражают только те операции, которыемогут быть обеспечены на большинстве современных операцион-ных систем. Процедуры достаточно эффективны для того, чтобыпользователи редко чувствовали необходимость обойти их "радиэффективности", как бы ни была важна конкретная задача. И,наконец, эти процедуры задуманы быть "переносимыми" в томсмысле, что они должны существовать в совместимом виде налюбой системе, где имеется язык "с", и что программы, кото-рые ограничивают свои взаимодействия с системой возможностя-ми, предоставляемыми стандартной библиотекой, можно будетпереносить с одной системы на другую по существу без измене-ний. Мы здесь не будем пытаться описать всю библиотеку вво-да/вывода; мы более заинтересованы в том, чтобы продемонст-рировать сущность написания "с"-программ, которые взаимодей-ствуют со своей операционной средой.