Мы продемонстрируем, как правильно выполнить эту задачу

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.

Напишите программу, которая печатает слова из своего

файла ввода, расположенные в порядке убывания частоты их по-

явления. Перед каждым словом напечатайте число его появле-

ний.

·     143 -

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 , получается просто как остаток от

деления суммы символьных значений строки на размер массива.

(Это не самый лучший возможный алгоритм, но его достоинство

состоит в исключительной простоте).

·     144 -

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);

\)

·     145 -

Функция STRSAVE просто копирует строку, указанную в ка-

честве аргумента, в место хранения, полученное в результате

обращения к функции ALLOC. Мы уже привели эту функцию в гла-

ве 5. Так как обращение к функции ALLOC и FREE могут проис-

ходить в любом порядке и в связи с проблемой выравнивания,

простой вариант функции ALLOC из главы 5 нам больше не под-

ходит; смотрите главы 7 и 8.

Упражнение 6-7.

Напишите процедуру, которая будет удалять имя и опреде-

ление из таблицы, управляемой функциями LOOKUP и INSTALL.

Упражнение 6-8.

Разработайте простую, основанную на функциях этого раз-

дела, версию процессора для обработки конструкций #DEFINE ,

пригодную для использования с “C”-программами. Вам могут

также оказаться полезными функции GETCHAR и UNGETCH.

Похожие работы

Анализ обыденного языка: общая характеристика направления

Скачать

48443

0

0

... основаниям. При этом философская абстракция языка оказывается неразрывно связана с основными темами и движениями философии в целом. Более конкретно, на ранние стадии традиционно рассматриваемого в рамках АФ анализа обыденного языка глубокое влияние оказала философия Дж. Э. Мура, особенно его учение о здравом смысле, согласно которому такие понятия, как «человек», «мир», «я», «внешний мир», « ...

Русский язык в современной Молдове

Скачать

43709

0

0

... и других странах СНГ, а также облегчение доступа к русской и мировой культуре и науке. Таким образом, судя по данным наших исследований, востребованность русского языка осталась в республике достаточно высокой. Многие представители современной молдавской молодежи продолжают, как их отцы и деды, тянуться к русской культуре, научным и техническим достижениям России. Русский язык остается языком ...

Неиндоевропейские языки

Скачать

39778

0

1

... рисуночное словесно-слоговое письмо). Памятники среднеэламского периода (14—12 вв. до н.э.) выполнены аккадской клинописью. Памятники новоэламского периода относятся к 8—6 вв. до н.э. Был официальным языком в персидском государстве Ахеменидов в 6—4 вв. предполагается, что он, подвергшись влиянию древнеперсидского, сохранился до раннего средневековья. 7. Бурушаски язык Язык бурушаски ( ...

Индоевропейские языки

Скачать

64931

0

0

... /диалект), скифский, согдийский, среднеперсидский, таджикский, таджриши (язык/диалект), талышский, татский, хорезмийский, хотаносакский, шугнано-рушанская группа языков, ягнобский, язгулямский и др. Они относятся к индоиранской ветви индоевропейских языков. Области распространения: Иран, Афганистан, Таджикистан, некоторые районы Ирака, Турции, Пакистана, Индии, Грузии, Российской Федерации. Общее ...