6.3. Массивы структур

Рассмотрим программу, определяющую число вхождений каждого ключевого слова в текст Си-программы. Нам нужно уметь хранить ключевые слова в виде массива строк и счетчики ключвых слов в виде массива целых чисел. Один из возможных вариантов — это иметь два параллельных массива:

  char *keyword[NKEYS];
  int  keycount[NKEYS];

Однако именно тот факт, что они параллельны, подсказывает нам другую организацию хранения — через массив структур. Каждое ключевое слово можно описать парой характеристик

  char *word;
  int  count;

Такие пары составляют массив. Объявление

  struct key {
      char *word;
      int  count;
  } keytab[NKEYS];

объявляет структуру типа key и определяет массив keytab, каждый элемент которого является структурой этого типа и для хранения которого где-то будет выделена память. Это же можно записать и по-другому:

  struct key {
      char *word;
      int  count;
  };
  struct key keytab[NKEYS];

Так как keytab содержит постоянный набор имен, его легче всего сделать внешним массивом и инициализировать один раз в момент определения. Инициализация структур аналогична ранее демонстрировавшимся инициализациям — за определением следует список инициализаторов, заключенный в фигурные скобки:

  struct key {
      char *word;
      int  count;
  } keytab[] = {
      "auto", 0,
      "break", 0,
      "case", 0,
      "char", 0,
      "const", 0,
      "continue", 0,
      "default", 0,
      /* . . . */
      "unsigned", 0,
      "void", 0,
      "volatile", 0,
      "while", 0
  };

Инициализаторы задаются парами, чтобы соответствовать конфигурации структуры. Строго говоря, пару инициализаторов для каждой отдельной структуры слдовало бы заключить в фигурные скобки, например, так

  {"auto", 0},
  {"break", 0},
  {"case", 0},
  ...

Однако когда инициализаторы — простые константы или строки символов и все они имеются в наличии, во внутренних скобках нет необходимости. Число элементов массива keytab будет вычислено по количеству инициализаторов, поскольку они представлены полностью, а внутри квадратных скобок [] ничего не задано.

Программа подсчета ключевых слов начинается с определения массива keytab. Функция main читает входные данные, многократно обращаясь к функции getword и получая при каждом ее вызове очередное слово. Каждое слово ищется в массиве keytab. Для этого используется функция бинарного поиска, которую мы написали в главе 3. Список ключевых слов должен быть упорядочен в алфавитном порядке.

  #include <stdio.h>
  #include <ctype.h>
  #include <string.h>

  #define MAXWORD 100

  int getword(char *, int);
  int binsearch(char *, struct key *, int);

  /* Подсчет ключевых слов Си */
  main()
  {
      int n;
      char word[MAXWORD];

      while (getword(word, MAXWORD) != EOF)
          if (isalpha(word[0]))
              if ((n = binsearch(word, keytab, NKEYS)) >= 0)
                  keytab[n].count++;
      for (n = 0; n < NKEYS; n++)
          if (keytab[n].count > 0)
              printf("%4d %s\n", keytab[n].count, keytab[n].word);
      return 0;
  }

  /* binsearch: поиск слова в массиве tab */
  int binsearch(char *word, struct key tab[], int n)
  {
      int cond;
      int low, high, mid;

      low = 0;
      high = n - 1;
      while (low <= high) {
          mid = (low + high) / 2;
          if ((cond = strcmp(word, tab[mid].word)) < 0)
              high = mid - 1;
          else if (cond > 0)
              low = mid + 1;
          else
              return mid;
      }
      return -1;
  }

Чуть позже мы рассмотрим функцию getword, а сейчас нам достаточно знать, что при каждом ее вызове получается очередное слово, которое запоминается в массиве, заданном первым аргументом.

Константа NKEYS — это количество ключевых слов в keytab. Хотя мы могли бы подсчитать число таких слов вручную, гораздо легче и безопасней сделать это с помощью машины, особенно если список ключевых слов может быть изменен. Одно из возможных решений — поместить в конец списка инициализаторов пустой указатель (NULL) и затем перебирать в цикле элементы keytab, пока не встретится концевой элемент.

Но возможно и более простое решение. Поскольку размер массива полностью определен во время компиляции и равен произведению количества элементов массива на размер его отдельного элемента, число элементов массива можно вычислить по формуле

  размер keytab / размер struct key

В Си имеется унарный оператор sizeof, который работает во время компиляции. Его можно применять для вычисления размера любого объекта. Выражения

  sizeof объект

и

  sizeof (имя типа)

выдают целые значения, равные размеру указанного значения или типа в байтах. (Строго говоря, sizeof выдает беззнаковое целое, тип которого size_t определен в заголовочном файле <stddef.h>.) Что касается объекта, то это может быть переменная, массив или структура. В качестве имени типа может выступать имя базового типа (int, double, ...) или имя производного типа, например структуры или указателя.

В нашем случае, чтобы вычислить количество ключевых слов, размер массива надо поделить на размер одного элемента. Указанное вычисление используется в инструкции #define для установки значения NKEYS:

  #define NKEYS (sizeof keytab / sizeof(struct key))

Этот же результат можно получить другим способом — поделить размер массива на размер какого-то его конкретного элемента:

  #define NKEYS (sizeof keytab / sizeof keytab[0])

Преимущество такого рода записей в том, что их не надо корректировать при изменении типа.

Поскольку препроцессор не обращает внимания на имена типов, оператор sizeof нельзя применять в #if. Но в #define выражение препроцессором не вычисляется, так что предложнная нами запись допустима.

Теперь поговорим о функции getword. Мы написали getword в несколько более общем виде, чем требуется для нашей программы, но она от этого не стала заметно сложнее. Функция getword берет из входного потока следующее «слово». Под словом понимается цепочка букв и цифр, начинающаяся с буквы, или отдельный символ, отличный от символа-разделителя. В случае конца файла функция возвращает EOF, в остальных случаях ее значением является код первого символа слова или сам символ, если это не буква.

  /* getword: принимает следующее слово или символ из ввода */
  int getword(char *word, int lim)
  {
      int c, getch(void);
      void ungetch(int);
      char *w = word;

      while (isspace(c = getch()))
          ;
      if (c != EOF)
          *w++ = c;
      if (!isalpha(c)) {
          *w = '\0';
          return c;
      }
      for (; --lim > 0; w++)
          if (!isalnum(*w = getch())) {
              ungetch(*w);
              break;
          }
      *w = '\0';
      return word[0];
  }

Функция getword обращается к getch и ungetch, которые мы написали в главе 4. По завершении набора букв и цифр оказывается, что getword взяла лишний символ. Обращение к ungetch позволяет вернуть его назад во входной поток. В getword используется также функции isspace (для пропуска символов-разделителей), isalpha (для идентификации букв) и isalnum (для распознавания букв и цифр). Все они описаны в стандартном заголовочнм файле <ctype.h>.