5.6. Массивы указателей и указатели на указатели

Как и любые другие переменные, указатели можно группировать в массивы. Для иллюстрации этого напишем программу, сортирующую в алфавитном порядке текстовые строки; это будет упрощенный вариант программы sort системы UNIX.

В главе 3 мы привели функцию сортировки по Шеллу, которая упорядочивает массив целых чисел, а в главе 4 улучшили ее, повысив быстродействие. Те же алгоритмы используются и здесь, однако теперь они будут обрабатывать текстовые строки, которые могут иметь разную длину и сравнение или перемещение которых невозможно выполнить за одну операцию. Нам необходимо выбрать некоторое представление данных, которое бы позволило удобно и эффективно работать с текстовыми строками произвольной длины.

Для этого воспользуемся массивом указателей на начала строк. Поскольку строки в памяти расположены вплотную друг к другу, к каждой отдельной строке доступ просто осуществлять через указатель на ее первый символ. Сами указатели можно организовать в виде массива. Одна из возможностей сравнить две строки — передать указатели на них функции strcmp. Чтобы поменять местами строки, достаточно будет поменять местами в массиве их указатели (а не сами строки).

Здесь снимаются сразу две проблемы: одна — связанная со сложностью управления памятью, а вторая — с большими накладными расходами при перестановках самих строк.

Процесс сортировки распадается на три этапа:

    чтение всех строк из ввода
    сортировка введенных строк
    печать их по порядку

Как обычно, выделим функции, соответствующие естественному делению задачи, и напишем главную программу main, управляющую этими функциями. Отложим на время реализацию этапа сортировки и сосредоточимся на структуре данных и вводе-выводе.

Программа ввода должна прочитать и запомнить символы всех строк, а также построить массив указателей на строки. Кроме того, она должна подсчитать число введенных строк — эта информация понадобится для сортировки и печати. Так как функция ввода может работать только с конечным числом строк, то, если их введено слишком много, она будет выдавать некоторое значение, которое никогда не совпадет с количеством строк, например –1.

Программа вывода занимается только тем, что печатает строки, причем в том порядке, в котором в массиве расположены указатели на них .

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

  #define MAXLINES 5000 /*максимальное число строк */

  char *lineptr[MAXLINES];  /* указатели на строки */

  int readlines(char *lineptr[], int nlines);
  void writelines(char *lineptr[], int nlines);
  void qsort(char *lineptr[], int left, int right);

  /* Сортировка строк */
  main()
  {
      int nlines;  /* количество прочитанных строк */

      if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
          qsort(lineptr, 0, nlines - 1);
          writelines(lineptr, nlines);
          return 0;
      }
      else {
          printf("Ошибка: слишком много строк.\n");
          return 1;
      }
  }

  #define MAXLEN 1000 /* максимальная длина строки */
  int getline(char *, int);
  char *alloc(int);

  /* readlines: чтение строк */
  int readlines(char *lineptr[], int maxlines)
  {
      int len, nlines;
      char *p, line[MAXLEN];

      nlines = 0;
      while (( len = getline(line, MAXLEN)) > 0)
          if (nlines >= MAXLINES || (p = alloc(len)) == NULL)
              return -1;
          else {
              line[len-1] = '\0'; /* убираем символ \n */
              strcpy(p, line);
              lineptr[nlines++] = p;
          }
      return nlines;
  }

  /* writelines: печать строк */
  void writelines(char *lineptr[], int nlines)
  {
      int i;

      for (i = 0; i < nlines; i++)
          printf("%s\n", lineptr[i]);
    }

Функция getline взята из параграфа 1.9.

Основное новшество здесь — объявление lineptr:

  char *lineptr[MAXLINES];

в котором сообщается, что lineptr есть массив из MAXLINES элементов, каждый из которых представляет собой указатель на char. Иначе говоря, lineptr[i] — указатель на символ, а *lineptr[i] — символ, на который он указывает (первый символ i-й строки текста).

Так как lineptr — имя массива, его можно трактовать как указатель, т.е. так же, как мы это делали в предыдущих примерах, и переписать writelines следующим образом:

    /* writelines: печать строк */
    void writelines(char *lineprt[], int nlines)
    {
        while (nlines-- > 0)
            printf("%s\n", *lineptr++);
    }

Вначале *lineptr указывает на первую строку; каждое приращение указателя приводит к тому, что *lineptr указывает на следующую строку, и делается это до тех пор, пока nlines не станет равно нулю.

Теперь, когда мы разобрались с вводом и выводом, можно приступить к сортировке. Быструю сортировку, описанную в главе 4, надо несколько модифицировать: нужно изменить объявления, а операцию сравнения заменить обращением к strcmp. Алгоритм остался тем же, и это дает нам определенную уверенность в его правильности.

  /* qsort: сортирует v[left]...v[right] по возрастанию */
  void qsort(char *v[], int left, int right)
  {
      int i, last;
      void swap(char *v[], int i, int j);

      if (left >= right)  /* ничего не делается, если в массиве */
          return;         /* меньше двух элементов */
      swap(v, left, (left+right)/2);
      last = left;
      for (i = left+1; i <= right; i++)
          if (strcmp(v[i], v[left]) < 0)
              swap(v, ++last, i);
      swap(v, left, last);
      qsort(v, left, last-1);
      qsort(v, last+1, right);
  }

Небольшие поправки требуются и в программе перестановки.

  /* swap: поменять местами v[i] и v[j] */
  void swap(char *v[], int i, int j)
  {
      char *temp;

      temp = v[i];
      v[i] = v[j];
      v[j] = temp;
  }

Так как каждый элемент массива v (т.е. lineptr) является указателем на символ, temp должен иметь тот же тип, что и v — тогда можно будет осуществлять пересылки между temp и элементами массива v.