Методические указания к выполнению контрольных работ по дисциплине "Основы программирования" (стр. 33 из 40)
low = mid + 1;
else
return (mid);
}
return(-1);
}
Мы вскоре приведем функцию getword; пока достаточно сказать, что она возвращает letter каждый раз, как она находит слово, и копирует это слово в свой первый аргумент.
Величина nkeys – это количество ключевых слов в массиве keytab. Хотя мы можем сосчитать это число вручную, гораздо легче и надежнее поручить это машине, особенно в том случае, если список ключевых слов подвержен изменениям. Одной из возможностей было бы закончить список инициализаторов указанием на нуль и затем пройти в цикле сквозь массив keytab, пока не найдется конец.
Но, поскольку размер этого массива полностью определен к моменту компиляции, здесь имеется более простая возможность. Число элементов просто есть:
sizeof keytab / sizeof struct key
Дело в том, что в языке «C» предусмотрена унарная операция sizeof, выполняемая во время компиляции, которая позволяет вычислить размер любого объекта. Выражение sizeof(object) выдает целое, равное размеру указанного объекта. (Размер определяется в неспецифицированных единицах, называемых «байтами», которые имеют тот же размер, что и переменные типа char).
Объект может быть фактической переменной, массивом и структурой, или именем основного типа, как int или double, или именем производного типа, как структура. В нашем случае число ключевых слов равно размеру массива, деленному на размер одного элемента массива. Это вычисление используется в утверждении #define для установления значения nkeys:
#define nkeys (sizeof(keytab) / sizeof(struct key))
Теперь перейдем к функции getword. Мы фактически написали более общий вариант функции getword, чем необходимо для этой программы, но он не на много более сложен. Функция getword возвращает следующее «слово» из ввода, где словом считается либо строка букв и цифр, начинающихся с буквы, либо отдельный символ. Тип объекта возвращается в качестве значения функции. Это может быть:
· letter, если найдено слово;
· eof для конца файла;
· сам символ, если он не буквенный.
// Получить следующее слово из потока символов ввода
getword(char *w, int lim)
{
int c, t;
if (type(c=*w++=getch()) != letter)
{
*w='\0';
return(c);
}
while (--lim > 0)
{
t = type(c = *w++ = getch());
if (t != letter && t != digit)
{
ungetch(c);
break;
}
}
*(w-1) - '\0';
return(letter);
}
Функция getword использует функции getch и ungetch, которые мы написали в главе 5: когда набор алфавитных символов прерывается, функция getword получает один лишний символ. В результате вызова ungetch этот символ помещается назад во ввод для следующего обращения. Функция getword обращается к функции type для определения типа каждого отдельного символа из файла ввода. Вот вариант, справедливый только для алфавита ASCII.
// Получить тип символа ASCII
int type(int c)
{
if (c>= 'a' && c<= 'z' || c>= 'a' && c<= 'z')
return(letter);
else if (c>= '0' && c<= '9')
return(digit);
else
return(c);
}
Символические константы letter и digit могут иметь любые значения, лишь бы они не вступали в конфликт с символами, отличными от буквенно-цифровых, и с eof; очевидно возможен следующий выбор:
#define letter 'a'
#define digit '0'
Функция getword могла бы работать быстрее, если бы обращения к функции type были заменены обращениями к соответствующему массиву type[]. В стандартном заголовочном h-файле <ctype.h> языка «C» предусмотрены макросы isalpha и isdalnum, действующие необходимым образом.
Упражнение 7-1. Сделайте такую модификацию функции getword и оцените, как изменится скорость работы программы.
Упражнение 7-2. Напишите вариант функции type, не зависящий от конкретного набора символов.
Упражнение 7-3. Напишите вариант программы подсчета ключевых слов, который бы не учитывал появления этих слов в заключенных в кавычки строках.
Пример 7-3. Чтобы проиллюстрировать некоторые соображения, связанные с использованием указателей и массивов структур, давайте снова составим программу подсчета ключевых строк, используя на этот раз указатели, а не индексы массивов.
Внешнее описание массива keytab не нужно изменять, но функции main и binary требуют модификации.
// Подсчет ключевых слов «С»; версия с указателями
main()
{
int t;
char word[maxword];
struct key *binary(), *p;
while ((t = getword(word, maxword;) != eof)
if (t==letter)
if ((p=binary(word,keytab,nkeys)) != null)
p->keycount++;
for (p=keytab; p>keytab + nkeys; p++)
if (p->keycount > 0)
printf("%4d %s/n", p->keycount, p->keyword);
}
// Функция binary: найти слова в tab[0]...tab[n-1]
struct key *binary(char *word, struct key tab[],int n)
{
int cond;
struct key *low = &tab[0];
struct key *high = &tab[n-1];
struct key *mid;
while (low <= high)
{
mid = low + (high-low) / 2;
if ((cond = strcmp(word, mid->keyword)) < 0)
high = mid - 1;
else if (cond > 0)
low = mid + 1;
else
return(mid);
}
return(null);
}
Здесь имеется несколько моментов, которые стоит отметить.
Во-первых, описание функции binary должно указывать, что она возвращает указатель на структуру типа key, а не на целое; это объявляется как в функции main, так и в binary. Если функция binary находит слово, то она возвращает указатель на него; если же нет, она возвращает null.
Во-вторых, все обращения к элементам массива keytab осуществляются через указатели. Это влечет за собой одно существенное изменение в функции binary: средний элемент больше нельзя вычислять просто по формуле:
mid = (low + high) / 2 ,
потому что сложение двух указателей не дает какого-нибудь полезного результата (даже после деления на 2) и в действительности является незаконным. Эту формулу надо заменить на:
mid = low + (high-low) / 2 ,
в результате которой mid становится указателем на элемент, расположенный посередине между low и high.
Вам также следует разобраться в инициализации low и high. Указатель можно инициализировать адресом ранее определенного объекта; именно как мы здесь и поступили.
В функции main мы написали:
for (p=keytab; p < keytab+nkeys; p++) .
Если p является указателем структуры, то любая арифметика с p учитывает фактический размер данной структуры, так что p++ увеличивает p на нужную величину, в результате чего p указывает на следующий элемент массива структур. Но не считайте, что размер структуры равен сумме размеров ее элементов, – из-за требований выравнивания для различных объектов в структуре могут возникать «дыры».
И, наконец, несколько второстепенный вопрос о форме записи программы. Если возвращаемая функцией величина имеет тип, как, например, в:
struct key *binary(...) ,
то может оказаться, что имя функции трудно выделить среди текста. В связи с этим иногда используется другой стиль записи:
struct key *
binary(...) .
Это, главным образом, дело вкуса; выберите ту форму, которая вам нравится, и придерживайтесь ее.
7.5. Структуры, ссылающиеся на себя; двоичные деревья
Пример 7-4. Предположим, что нам надо справиться с более общей задачей, состоящей в подсчете числа появлений всех слов в некотором файле ввода. Так как список слов заранее не известен, мы не можем их упорядочить удобным образом и использовать бинарный поиск. Мы даже не можем осуществлять последовательный просмотр при поступлении каждого слова, с тем, чтобы установить, не встречалось ли оно ранее; такая программа будет работать «вечно». (Более точно, ожидаемое время работы растет как квадрат числа вводимых слов). Как же нам организовать программу, чтобы справиться со списком произвольных слов?
Одно из решений состоит в том, чтобы все время хранить массив поступающих до сих пор слов в упорядоченном виде, помещая каждое слово в нужное место по мере их поступления. Однако это не следует делать, перемещая слова в линейном массиве, – это также потребует слишком много времени. Вместо этого мы используем структуру данных, называемую двоичным деревом.
Каждому новому слову соответствует один «узел» дерева; каждый узел содержит:
· указатель текста слова;
· счетчик числа появлений;
· указатель узла левого потомка;
· указатель узла правого потомка.
Никакой узел не может иметь более двух «детей» (отсюда название «двоичного» дерева); возможно отсутствие детей или наличие только одного потомка.
Узлы создаются таким образом, что левое поддерево каждого узла содержит только те слова, которые лексикографически меньше слова в этом узле, а правое поддерево только те слова, которые больше. Чтобы определить, находится ли новое слово уже в дереве, начинают с корня и сравнивают новое слово со словом, хранящимся в этом узле. Если слова совпадают, то вопрос решается утвердительно. Если новое слово меньше слова в дереве, то переходят к рассмотрению левого потомка; в противном случае исследуется правый потомок. Если в нужном направлении потомок отсутствует, то значит новое слово не находится в дереве и место этого недостающего потомка как раз и является местом, куда следует поместить новое слово. Поскольку поиск из любого узла приводит к поиску одного из его потомков, то сам процесс поиска по существу является рекурсивным. В соответствии с этим наиболее естественно использовать рекурсивные процедуры ввода и вывода.
 |
Вот как выглядит дерево, построенное для фразы: «now is the time for all good men to come to the aid of their party» (пер. с англ.: «настало время всем добрым людям помочь своей партии»), – по завершении процесса, в котором для каждого нового слова в него добавляется новый узел (рис. 7.1):
Возвращаясь назад к описанию узла, становится ясно, что это будет структура с четырьмя компонентами:
struct tnode
{ // struct: Узел дерева
char *word; // Указатель на текст
int count; // Число вхождений (появлений)
struct tnode *left; // Левый «сын»
struct tnode *right; // Правый «сын»
};
Это «рекурсивное» описание узла может показаться рискованным, но на самом деле оно вполне корректно. Структура не имеет права содержать саму себя, но:
struct tnode *left;
описывает left как указатель на узел, а не как сам узел.
Текст самой программы оказывается удивительно маленьким, если, конечно, иметь в распоряжении набор написанных нами ранее процедур, обеспечивающих нужные действия. Мы имеем в виду функцию getword для извлечения каждого слова из файла ввода и функцию alloc для выделения места для хранения слов.