Язык программирования Си. Издание 3-е, исправленное

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

Как обычно, выделим функции, соответствующие естественному делению задачи, и напишем главную программу 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 *lineptr[], 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.

Упражнение 5.7. Напишите новую версию readlines, которая запоминала бы строки в массиве, определенном в main, а не запрашивала память посредством программы alloc. Насколько быстрее эта программа?

5.7 Многомерные массивы

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