Б. Керриган, Д. Ритчи Язык программирования C. Б. Керниган, Д. зык программирования и . Издание 3е, исправленное Перевод с английского под редакцией Вс. С. Штаркмана СанктПетербург 2003
 Скачать 31.48 Mb.
|
|
Глава 6. Структуры for ( ; > 0; w++) if = { break; } = ; return > Функция getword обращается к и которые мы написали в главе 4. По завершении набора букв-цифр оказывается, что rd взя- ла лишний символ. Обращение к u n g e t c h позволяет вернуть его назад во входной поток. В используются также isspace - для пропуска символов-разделителей, isalpha - для идентификации букв и - для распознавания букв-цифр. они описаны в стандартном заголовоч- ном файле h">. Упражнение Наша версия getwo rd не обрабатывает должным образом знак подчеркивания, строковые константы, комментарии и управляющие строки препроцессора. Напишите более совершенный вариант программы. 6.4. Указатели на структуры Для иллюстрации некоторых моментов, касающихся указателей на структуры и массивов структур, перепишем программу ключе- вых слов, пользуясь для получения элементов массива вместо индексов указателями. Внешнее объявление массива keytab остается без a main и нужно модифицировать. 100 int getword(char *, int); struct key *binsearch(char *, struct key *, int); /* подсчет ключевых слов версия с указателями */ { char struct key *p; 6.4. Указатели на структуры _ _ 177 while != EOF) if if ((p keytab, NKEYS)) != NULL) p->count++; for (p = keytab; p < keytab + NKEYS; p++) if (p->count > 0) p->count, p->word); return 0; /* binsearch: найти слово word в */ struct key *word, struct key *tab, int n) { int cond; struct key *low = struct key *high = struct key while (low < high) { mid = low + (high - low) / 2; if = < 0) high = mid; else if (cond > 0) , low = mid + else return mid; > return NULL; } Некоторые детали этой программы требуют пояснений. Во-первых, описание функции binsearch должно отражать тот факт, что она возвра- щает указатель на st key, а не целое; это объявлено как в прототипе функции, так и в функции binsearch. Если binsearch находит слово, то она выдает указатель на него, в противном случае она возвращает NULL. Во-вторых, к элементам доступ в нашей программе осуществляет- ся через указатели. Это потребовало значительных изменений в binsea rch. Инициализаторами для low и h i g h теперь служат указатели на начало и на место сразу после конца массива. Вычисление положения среднего элемента с помощью формулы mid = (low + high) /* НЕВЕРНО не годится, поскольку указатели нельзя складывать. Однако к ним можно Глава 6. Структуры применить операцию вычитания, и так как high-low есть число элемен- тов, присваивание mid = low + (high-low) / 2 превратит mid в указатель на элемент, лежащий посередине между low и high. Самое важное при переходе на новый вариант программы - сделать так, чтобы не генерировались неправильные указатели и не было попыток обратиться за пределы массива. Проблема в том, что и и находятся вне границ массива. Первый адрес определенно неверен, нельзя также осуществить доступ и по второму адресу. По правилам языка, од- нако, гарантируется, что адрес ячейки следующей сразу за кон- цом массива (т. е. в арифметике с указателями воспринимается правильно. В главной программе мы написали for (р - keytab; р < keytab + NKEYS; Если р - это указатель на структуру, то при выполнении операций с р учитывается размер структуры. Поэтому р++ увеличит р на такую вели- чину, чтобы выйти на следующий структурный элемент массива, а про- верка условия вовремя остановит цикл. Не следует, однако, полагать, что размер структуры равен сумме разме- ров ее элементов. Вследствие выравнивания объектов разной длины в струк- туре могут появляться безымянные "дыры". если переменная типа занимает один байт, a int - четыре байта, то для структуры struct { char с; int i; }; может потребоваться восемь байтов, а не пять. Оператор sizeof возвра- щает правильное значение. Наконец, несколько слов относительно формата программы. Если функ- ция возвращает значение сложного типа, как, например, в нашем случае она возвращает указатель на структуру: struct key *word, struct key то "высмотреть" имя функции оказывается совсем не просто. В подобных случаях иногда пишут так: struct key * struct key int n) Какой форме отдать предпочтение - дело вкуса. Выберите ту, которая больше всего вам нравится, и придерживайтесь ее. 6.5. Структуры со ссылками на себя 6.5. Структуры со ссылками на себя , • у Предположим, мы хотим решить более общую задачу - написать про- грамму, подсчитывающую частоту встречаемости для любых слов входного потока. как список слов заранее не известен, мы не можем предваритель- но упорядочить и применить бинарный поиск. бы неразумно пользо- ваться и линейным поиском каждого полученного слова, чтобы встречалось оно ранее нет - этом случае программа работала бы слиш- ком медленно. (Более точная оценка: время такой программы про- порционально квадрату количества слов.) Как можно организовать данные, чтобы эффективно справиться со списком произвольных слов? Один из способов - постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не на- рушалась имеющаяся упорядоченность. Делать это передвижкой слов в ли- нейном массиве не следует, - хотя бы потому, что процедура тоже слишком долгая. Вместо этого мы воспользуемся структурой дан- ных, называемой бинарным деревом. В дереве на каждое отдельное слово предусмотрен "узел", который со- держит: - указатель на текст слова; — счетчик числа встречаемости; - указатель на левый сыновний узел; - указатель на правый сыновний узел. У каждого узла может быть один или два сына, или узел вообще может не иметь сыновей. в дереве располагаются так, что по отношению к любому узлу левое поддерево содержит только те слова, которые лексикографически меньше, чем слово данного узла, а правое - слова, которые больше него. Вот как выглядит дерево, построенное для фразы "now is the time f o r all good men to come to the aid of their время всем добрым людям помочь своей партии"), по завершении процесса, в кото- ром для каждого нового слова в него добавлялся новый узел: now all good party their to aid come Глава 6. Структуры Чтобы определить, помещено ли уже в дерево вновь поступившее слово, начинают с корня, сравнивая это слово со словом из корневого узла. Если они совпали, то ответ на вопрос — положительный. Если новое слово мень- ше слова из дерева, то поиск продолжается в левом поддереве, если боль- ше, то — в Если же в выбранном направлении поддерева не оказа- лось, то этого слова в дереве нет, а пустующая позиция, говорящая об от- сутствии поддерева, как раз и есть то место, куда нужно "подвесить" узел с новым словом. Описанный процесс по сути рекурсивен, так как поиск в любом узле использует результат поиска в одном из своих сыновних узлов. В соответствии с этим для добавления узла и печати дерева здесь наиболее естественно применить рекурсивные функции. Вернемся к описанию узла, которое удобно представить в виде струк- туры с четырьмя компонентами: struct tnode { /* узел дерева */ . char /* указатель на текст */ int count; /* число вхождений */ struct tnode *left; /* левый сын */ struct tnode /* правый сын */ } ; Приведенное рекурсивное определение узла может показаться рискован- ным, но оно правильное. Структура не может включать саму себя, но ведь struct tnode объявляет как указатель на tnode, а не сам tnode. Иногда возникает потребность во взаимоссылающихся структурах: двух структурах, ссылающихся друг на друга. Прием, позволяющий спра- виться с этой задачей, демонстрируется следующим фрагментом: struct t { struct s *p; /* p указывает на s */ }; struct s { I struct t *q; /* q указывает на t */ } ; Вся программа удивительно мала - правда, она использует вспомога- тельные программы вроде уже написанные нами. Главная про- грамма читает слова с помощью и вставляет их в дерево посред- 6.5. Структуры со ссылками на себя 181 tfinclude struct tnode tnode *, char • void treeprint(struct tnode *); int *, int); /* подсчет частоты встречаемости */ { struct tnode char root = NULL; while (getword (word, MAXWORD) != EOF) if root = return 0; } Функция рекурсивна. Первое слово функция main помещает на верхний уровень дерева (корень дерева). Каждое вновь поступив- шее слово сравнивается со словом узла и "погружается" или в левое, или в правое поддерево с помощью рекурсивного обращения к addt Через некоторое время это слово обязательно либо совпадет с каким-нибудь из имеющихся в дереве слов (в этом случае к счетчику будет добавлена либо программа встретит пустую позицию, что послужит сигналом для создания нового узла и добавления к дереву. Создание нового узла сопровождается тем, что возвращает на него указатель, который вставляется в узел родителя. struct tnode *talloc(void); char *); /* addtree: добавляет узел со словом в р или ниже него */ struct tnode tnode *p, char *w) { int cond; if (p == NULL) { /* слово встречается впервые */ _ Глава Структуры р = /* создается новый узел */ p->word = p->count = 1; p->left = p->right = NULL; } else if ((cond = == 0) p->count++; /* это слово уже встречалось */ else if (cond < 0) /* меньше корня левого поддерева */ p->left = else /* больше корня правого поддерева */ p->right = addtree(p->right, w); return p; } Память для нового узла запрашивается с помощью программы talloc, которая возвращает указатель на свободное пространство, достаточное для хранения одного узла дерева, а копирование нового слова в отдель- ное место памяти осуществляется с помощью st (Мы рассмотрим эти программы чуть позже.) В тот (и только в тот) момент, когда к дереву подвешивается новый узел, происходит инициализация счетчика и обну- ление указателей на сыновей. Мы опустили (что неразумно) контроль ошибок, который должен выполняться при получении значений от st rdup и talloc. Функция treeprint печатает дерево в порядке; для каждого узла она печатает его левое поддерево (все слова, которые меньше слова данного узла), затем само слово и, правое подде- рево (слова, которые больше слова данного узла). /* упорядоченная печать дерева р */ void tnode *p) { if (р != NULL) { treeprint(p->left); p->count, p->word); Если вы не уверены, что досконально разобрались в том, как рекурсия, "проиграйте" действия t reeprint на дереве, приведенном выше. Практическое замечание: если дерево "несбалансировано" (что быва- ет, когда слова поступают не в случайном порядке), то время работы про- граммы может сильно возрасти. Худший вариант, когда слова уже упоря- дочены; в этом случае затраты на вычисления будут такими же, как при 6.5. Структуры со ссылками на себя линейном поиске. Существуют обобщения бинарного дерева, которые не страдают этим недостатком, но здесь мы их не описываем. Прежде чем завершить обсуждение этого примера, сделаем краткое от- ступление от темы и поговорим о механизме запроса памяти. Очевидно, хотелось бы иметь всего лишь одну функцию, выделяющую память, даже если эта память предназначается для разного рода объектов. Но если одна и та же функция обеспечивает память, скажем, и для указателей и для указателей на st то возникают два вопроса. Первый: как справиться с требованием большинства машин, в которых объекты опре- деленного типа должны быть выровнены (например, int часто должны размещаться, начиная с четных адресов)? И второе: как объявить функ- цию-распределитель памяти, которая вынуждена в качестве результата возвращать указатели разных типов? Вообще говоря, требования, касающиеся выравнивания, можно легко выполнить счет некоторого перерасхода памяти. Однако для этого воз- вращаемый указатель должен быть таким, чтобы удовлетворялись любые ограничения, связанные с выравниванием. Функция описанная в главе 5, не гарантирует нам любое конкретное выравнивание, поэтому мы будем пользоваться стандартной библиотечной функцией ко- торая это делает. В главе 8 мы покажем один из способов ее реализации. Вопрос об объявлении типа таких функций, как malloc, является кам- нем преткновения в любом языке с жесткой проверкой типов. В Си во- прос естественным образом: malloc объявляется как функция, которая возвращает указатель на Полученный указатель затем явно приводится к желаемому Описания malloc и связанных с ней функ- ций находятся в стандартном заголовочном файле Таким об- разом, функцию talloc можно записать так: «include /* talloc: создает tnode */ struct tnode { return (struct tnode *) о приведении типа величины, возвращаемой функцией пере- писать. Пример и работает, но совет является спорным в ANSI/ISO 1988-1989 На самом деле это не обязательно условии что к автоматически) и возможно если malloc или ее заместитель не может быть как функций, возвращающая Явное может скрыть случайную ошибку. В другие времена (до появления стан- дарта ANSI) приведение считалось обязательным, что также и для C++. — Примеч. авт. Глава 6. Структуры Функция st просто копирует строку, указанную в аргументе, в ме- сто, полученное с помощью char *strdup(char *s) /* делает дубликат s */ { char *p; p = (char *) /* +1 для */ if (p != NULL) strcpy(p, s); return p; } Функция malloc возвращает NULL, если свободного пространства нет; st возвращает это же значение, оставляя заботу о выходе из ошибочной си- туации вызывающей программе. Память, полученную с помощью можно освободить для повтор- ного использования, обратившись к функции f (см. главы 7 и 8). Упражнение 6.2. Напишите программу, которая читает текст Си-про- граммы и печатает в алфавитном порядке все группы имен переменных, в которых совпадают первые 6 символов, но последующие в чем-то различаются. Не обрабатывайте внутренности закавыченных строк и комментариев. Число 6 сделайте параметром, задаваемым в командной строке. Упражнение 6.3. Напишите программу печати таблицы "перекрестных ссылок", которая будет печатать все слова документа и указывать для каждого из них номера строк, где оно встретилось. Программа должна игнорировать "шумовые" слова, такие как "и", "или" и пр. Упражнение 6.4. Напишите программу, которая печатает весь набор различных слов, образующих входной поток, в порядке возрастания частоты их встречаемости. Перед каждым словом должно быть указано число вхождений. 6.6. Просмотр таблиц В этом параграфе, чтобы проиллюстрировать новые аспекты примене- ния структур, мы напишем ядро пакета программ, осуществляющих встав- ку элементов в таблицы и их поиск внутри таблиц. Этот пакет - типич- ный набор программ, с помощью которых работают с таблицами 6.6. Просмотр таблиц 185 в любом макропроцессоре или компиляторе. Рассмотрим, ин- струкцию Когда встречается строка вида IN 1 имя IN и замещающий его текст 1 должны запоминаться в таблице. Если затем имя IN встретится в инструкции, например в state = IN; оно должно быть заменено на Существуют две манипулирующие с именами и замеща- ющими их текстами. Это t), которая записывает имя s и заме- щающий его текст t в таблицу, где s и t - строки, и lookup( осуществля- ющая поиск s в таблице и возвращающая указатель на место, где имя s было найдено, или NULL, если s в таблице не оказалось. Алгоритм основан на хэш-поиске: поступающее имя в неотрицательное число (хэш-код), которое затем используется в качестве индекса в массиве указателей. Каждый элемент этого массива является указателем на начало связанного списка описывающих имена с данным хэш-кодом. Если элемент массива равен NULL, это значит, что имен с соответствующим хэш-кодом нет. 0 0 0 0 0 • V 7 0 имя текст мя Блок в списке - это структура, содержащая указатели на имя, на заме- щающий текст и на следующий блок в списке; значение NULL в указателе на следующий блок означает конец списка. struct { struct nlist *next; char char *defn; /* элемент таблицы */ /* указатель на следующий элемент */ /* определенное имя */ /* замещающий текст */ А вот как записывается определение «define HASHSIZE 101 static struct nlist /* таблица указателей */ _ Глава 6. Структуры Функция хэширования, используемая в lookup и install, суммирует коды символов в строке и в качестве результата выдает остаток от деле- ния полученной суммы на размер массива указателей. Это не самая луч- шая функция хэширования, но достаточно лаконичная и эффективная. /* hash: получает для строки s */ unsigned hash(char *s) { unsigned for (hashval != hashval = *s + 31 * hashval; return hashval % HASHSIZE; } Беззнаковая арифметика гарантирует, что хэш-код будет неотрицательным. Хэширование порождает стартовый индекс для массива hashtab; если соответствующая строка в таблице есть, она может быть обнаружена толь- ко в списке блоков, на начало которого указывает элемент массива hashtab с этим индексом. Поиск осуществляется с помощью lookup. Если lookup находит элемент с заданной строкой, то возвращает указатель на нее, если не находит, то возвращает NULL. /* lookup: ищет s */ ' struct *lookup(char { struct nlist *np; for (np = np != NULL; np = np->next) if (strcmp(s, == 0) return np; /* нашли */ return NULL; /* не нашли */ В f функции lookup для просмотра списка используется стандарт- ная конструкция for (ptr = head; ptr != NULL; ptr = ptr->next) Функция install обращается к lookup, чтобы определить, имеется ли уже вставляемое Если это так, то старое определение будет новым. В противном случае будет образован новый элемент. Если запрос памяти для нового элемента не может быть удовлетворен, функция install выдает NULL. 6.7. Средство typedef __ struct *lookup(char *); char *strdup(char *); / /* install: заносит имя и текст (name, defn) в таблицу */ struct nlist *install(char char { struct nlist *np; unsigned hashval; if ((np = == NULL) { /* не найден */ np = (struct nlist *) if (np == NULL = == NULL) return NULL; hashval = np->next = = np; } else /* уже имеется */ *) np->defn); /* освобождаем прежний defn */ if = == NULL) return NULL; return np; |