Программа вывода занимается только тем, что печатает строки, причем в том порядке, в котором расположены указатели на них в массиве.
#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 Многомерные массивы
В Си имеется возможность задавать прямоугольные многомерные массивы, правда, на практике по сравнению с массивами указателей они используются значительно реже. В этом параграфе мы продемонстрируем некоторые их свойства.
Рассмотрим задачу перевода даты "день-месяц" в "день года" и обратно. Например, 1 марта - это 60-й день невисокосного или 61-й день високосного года. Определим две функции для этих преобразований: функция day_of_year будет преобразовывать месяц и день в день года, a month_day - день года в месяц и день. Поскольку последняя функция вычисляет два значения, аргументы месяц и день будут указателями. Так вызов
month_day(1988, 60, &m, &d)
присваивает переменной m значение 2, а d - 29 (29 февраля).
Нашим функциям нужна одна и та же информация, а именно таблица, содержащая числа дней каждого месяца. Так как для високосного и невисокосного годов эти таблицы будут различаться, проще иметь две отдельные строки в двумерном массиве, чем во время вычислений отслеживать особый случай с февралем. Массив и функции, выполняющие преобразования, имеют следующий вид:
static char daytab[2][13] = {
{0, 31, 28, 31. 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
}
/* day_of_year: определяет день года по месяцу и дню */
int day_of_year(int year, int month, int day)
{
int i, leap;
leap = year % 4 == 0 && year % 100 !=0 || year % 400 == 0;
for (i = 1; i ‹ month; i++)
day += daytab[leap][i];
return day;
}
/* month_day: определяет месяц и день по дню года */
void month_day(int year, int yearday, int *pmonth, int *pday)
{
int i, leap;
leap = year % 4 == 0 && year % 100 != 0 || year % 400 == 0;
for (i = 1; yearday › daytab[leap][i]; i++)
yearday -= daytab[leap][i];
*pmonth = i;
*pday = yearday;
}
Напоминаем, что арифметическое значение логического выражения (например выражения, с помощью которого вычислялось leap) равно либо нулю (ложь), либо единице (истина), так что мы можем использовать его как индекс в массиве daytab.
Массив daytab должен быть внешним по отношению к обеим функциям day_of_year и month_day, так как он нужен и той и другой. Мы сделали его типа char, чтобы проиллюстрировать законность применения типа char для малых целых без знака.
Массив daytab - это первый массив из числа двумерных, с которыми мы еще не имели дела. Строго говоря, в Си двумерный массив рассматривается как одномерный массив, каждый элемент которого - также массив. Поэтому индексирование изображается так: