Массивы указателей; указатели указателей
Так как указатели сами являются переменными, то вы вполне могли бы ожидать использования массива указателей. Это действительно так. Мы проиллюстрируем это написанием программы сортировки в алфавитном порядке набора текстовых строк, предельно упрощенного варианта утилиты sort операционной систем UNIX.
В лекции №3 мы привели функцию сортировки по Шеллу, которая упорядочивала массив целых. Этот же алгоритм будет работать и здесь, хотя теперь мы будем иметь дело со строчками текста различной длины, которые, в отличие от целых, нельзя сравнивать или перемещать с помощью одной операции. Мы нуждаемся в таком представлении данных, которое бы позволяло удобно и эффективно обрабатывать строки текста переменной длины.
Здесь и возникают массивы указателей. Если подлежащие сортировке сроки хранятся одна за другой в длинном символьном массиве (управляемом, например, функцией alloc ), то к каждой строке можно обратиться с помощью указателя на ее первый символ. Сами указатели можно хранить в массиве. Две строки можно сравнить, передав их указатели функции strcmp.
Если две расположенные в неправильном порядке строки должны быть переставлены, то фактически переставляются указатели в массиве указателей, а не сами тексты строк. Этим исключаются сразу две связанные проблемы: сложного управления памятью и больших дополнительных затрат на фактическую перестановку строк.
Процесс сортировки включает три шага:
- чтение всех строк ввода
- их сортировка
- вывод их в правильном порядке
Как обычно, лучше разделить программу на несколько функций в соответствии с естественным делением задачи и выделить ведущую функцию, управляющую работой всей программы. Давайте отложим на некоторое время рассмотрение шага сортировки и сосредоточимся на структуре данных и вводе-выводе. функция, осуществляющая ввод, должна извлечь символы каждой строки, запомнить их и построить массив указателей строк. Она должна также подсчитать число строк во вводе, так как эта информация необходима при сортировке и выводе. Так как функция ввода в состоянии справиться только с конечным числом вводимых строк, в случае слишком большого их числа она может возвращать некоторое число, отличное от возможного числа строк, например -1. функция осуществляющая вывод, должна печатать строки в том порядке, в каком они появляются в массиве указателей.
#define null 0 #define lines 100 /* max lines to be sorted */
main() /* sort input lines */ { char *lineptr[lines]; /*pointers to text lines */ int nlines; /* number of input lines read */
if ((nlines = readlines(lineptr, lines)) >= 0) { sort(lineptr, nlines); writelines(lineptr, nlines); } else printf("input too big to sort\n"); }
#define maxlen 1000
readlines(lineptr, maxlines) /* read input lines */ char *lineptr[]; /* for sorting */ int maxlines; { int len, nlines; char *p, *alloc(), line[maxlen];
nlines = 0; while ((len = getline(line, maxlen)) > 0) if (nlines >= maxlines) return(-1); else if ((p = alloc(len)) == null) return (-1); else { line[len-1] = '\0'; /* zap newline */ strcpy(p,line); lineptr[nlines++] = p; } return(nlines); }
Символ новой строки в конце каждой строки удаляется, так что он никак не будет влиять на порядок, в котором сортируются строки.
writelines(lineptr, nlines) /* write output lines */ char *lineptr[]; int nlines; { int i;
for (i = 0; i < nlines; i++) printf("%s\n", lineptr[i]); }
Существенно новым в этой программе является описание
char *lineptr[lines];
которое сообщает, что lineptr является массивом из lines элементов, каждый из которых - указатель на переменные типа char. Это означает, что lineptr[i] - указатель на символы, а *lineptr[i] извлекает символ.
Так как сам lineptr является массивом, который передается функции writelines, с ним можно обращаться как с указателем точно таким же образом, как в наших более ранних примерах. Тогда последнюю функцию можно переписать в виде:
writelines(lineptr, nlines) /* write output lines */ char *lineptr[]; int nlines; { int i;
while (--nlines >= 0) printf("%s\n", *lineptr++); }
здесь *lineptr сначала указывает на первую строку; каждое увеличение передвигает указатель на следующую строку, в то время как nlines убывает до нуля.
Справившись с вводом и выводом, мы можем перейти к сортировке. Программа сортировки по Шеллу из лекции №3 требует очень небольших изменений: должны быть модифицированы описания, а операция сравнения выделена в отдельную функцию. Основной алгоритм остается тем же самым, и это дает нам определенную уверенность, что он по-прежнему будет работать.
sort(v, n) /* sort strings v[0] ... v[n-1] */ char *v[]; /* into increasing order */ int n; { int gap, i, j; char *temp;
for (gap = n/2; gap > 0; gap /= 2) for (i = gap; i < n; i++) for (j = i - gap; j >= 0; j -= gap) { if (strcmp(v[j], v[j+gap]) <= 0) break; temp = v[j]; v[j] = v[j+gap]; v[j+gap] = temp; } }
Так как каждый отдельный элемент массива v (имя формального параметра, соответствующего lineptr) является указателем на символы, то и temp должен быть указателем на символы, чтобы их было можно копировать друг в друга.
Мы написали эту программу по возможности более просто с тем, чтобы побыстрее получить работающую программу. Она могла бы работать быстрее, если, например, вводить строки непосредственно в массив, управляемый функцией readlines, а не копировать их в line, а затем в скрытое место с помощью функции alloc. Но мы считаем, что будет разумнее первоначальный вариант сделать более простым для понимания, а об "эффективности" позаботиться позднее. Все же, по-видимому, способ, позволяющий добиться заметного ускорения работы программы состоит не в исключении лишнего копирования вводимых строк. Более вероятно, что существенной разницы можно достичь за счет замены сортировки по шеллу на нечто лучшее, например, на метод быстрой сортировки.
В лекции №1 мы отмечали, что поскольку в циклах while и for проверка осуществляется до того, как тело цикла выполнится хотя бы один раз, эти циклы оказываются удобными для обеспечения правильной работы программы при граничных значениях, в частности, когда ввода вообще нет. Очень полезно просмотреть все функции программы сортировки, разбираясь, что происходит, если вводимый текст отсутствует.
Упражнение 5-5
Перепишите функцию readlines таким образом, чтобы она помещала строки в массив, предоставляемый функцией main, а не в память, управляемую обращениями к функции alloc. Насколько быстрее стала программа?
