Учебное введение
Оператор FOR
Копирование файла
Подсчет строк
Массивы
Аргументы - вызов по значению
Область действия: внешние переменные
Резюме
Константы
Арифметические операции
Затем, если один из операндов имеет тип DOUBLE, то другой преобразуется в DOUBLE, и результат имеет тип DOUBLE
Побитовые логические операции
Условные выражения
Поток управления
Переключатель
Цикл DO - WHILE
Оператор GOTO и метки
Функции, возвращающие нецелые значения
Внешние переменные
Правила, определяющие область действия
Статические переменные
Инициализация
Препроцессор языка “C”
Указатели и адреса
Адресная арифметика
Указатели символов и функции
Многомерные массивы
Инициализация массивов указателей
Структуры
Массивы сруктур
Указатели на структуры
Поиск в таблице
Объединения
Ввод и вывод Средства ввода/вывода не являются составной частью языка “с”, так что мы не выделяли их в нашем предыдущем изложении
Форматный вывод - функция PRINTF
Обычные символы (не %), которые предполагаются совпадающими со следующими отличными от символов пустых промежутков символами входного потока
Форматное преобразование в памяти
Низкоуровневый ввод/вывод - операторы READ и WRITE
Произвольный доступ - SEEK и LSEEK
Пример - распределитель памяти
Лексические соглашения Имеется шесть классов лексем: идентификаторы, ключевые слова, константы, строки, операции и другие разделители
Характеристики аппаратных средств Следующая ниже таблица суммирует некоторые свойства аппаратного оборудования, которые меняются от машины к машине
Первичные выражения Первичные выражения, включающие ., ->, индексацию и обращения к функциям, группируются слева направо
Унарные операции Выражение с унарными операциями группируется справо налево
Операции равенства Выражение-равенства: выражение == выражение выражение != выражение
Операция запятая Выражение-с-запятой: выражение , выражение
Внешние определения данных
Снова о типах В этом разделе обобщаются сведения об операциях, которые можно применять только к объектам определенных типов
Анахронизмы Так как язык “C” является развивающимся языком, в старых программах можно встретить некоторые устаревшие конструкции
Навигация
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 != ''; ) 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);
)
145
Функция 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 01
#DEFINE EXTERNAL 02
#DEFINE STATIC 04
(числа должны быть степенями двойки). Тогда обработка битов сведется к “жонглированию битами” с помощью операций сдвига, маскирования и дополнения, описанных нами в главе 2.
Некоторые часто встречающиеся идиомы: FLAGS != EXTERNAL ! STATIC;
включает биты EXTERNAL и STATIC в FLAGS, в то время как FLAGS &= ^(еXTERNAL ! STATIC);
146
их выключает, а 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); они не являются массивами; они не имеют адресов, так что к ним не применима операция &.
Похожие работы
... основаниям. При этом философская абстракция языка оказывается неразрывно связана с основными темами и движениями философии в целом. Более конкретно, на ранние стадии традиционно рассматриваемого в рамках АФ анализа обыденного языка глубокое влияние оказала философия Дж. Э. Мура, особенно его учение о здравом смысле, согласно которому такие понятия, как «человек», «мир», «я», «внешний мир», « ...
... и других странах СНГ, а также облегчение доступа к русской и мировой культуре и науке. Таким образом, судя по данным наших исследований, востребованность русского языка осталась в республике достаточно высокой. Многие представители современной молдавской молодежи продолжают, как их отцы и деды, тянуться к русской культуре, научным и техническим достижениям России. Русский язык остается языком ...
... рисуночное словесно-слоговое письмо). Памятники среднеэламского периода (14—12 вв. до н.э.) выполнены аккадской клинописью. Памятники новоэламского периода относятся к 8—6 вв. до н.э. Был официальным языком в персидском государстве Ахеменидов в 6—4 вв. предполагается, что он, подвергшись влиянию древнеперсидского, сохранился до раннего средневековья. 7. Бурушаски язык Язык бурушаски ( ...
... /диалект), скифский, согдийский, среднеперсидский, таджикский, таджриши (язык/диалект), талышский, татский, хорезмийский, хотаносакский, шугнано-рушанская группа языков, ягнобский, язгулямский и др. Они относятся к индоиранской ветви индоевропейских языков. Области распространения: Иран, Афганистан, Таджикистан, некоторые районы Ирака, Турции, Пакистана, Индии, Грузии, Российской Федерации. Общее ...
0 комментариев