Массивы указателей; указатели указателей

 

Так как указатели сами являются переменными, то вы вполне могли бы ожидать использования массива указателей. Это действительно так.

Пример 6-14. Мы проиллюстрируем это написанием программы сортировки в алфавитном порядке набора текстовых строк, предельно упрощенного варианта утилиты S ort операционной систем U nix (или соответствующей функции электронных таблиц Exel в операционной системе Windows).

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

Здесь и возникают массивы указателей. Если подлежащие сортировке сроки хранятся одна за другой в длинном символьном массиве (управляемом, например, функцией alloc), то к каждой строке можно обратиться с помощью указателя на ее первый символ. Сами указатели можно хранить в массиве. Две строки можно сравнить, передав их указатели функции strcmp.

Если две расположенные в неправильном порядке строки должны быть переставлены, то фактически переставляются указатели в массиве указателей, а не сами тексты строк. Этим исключаются сразу две связанные проблемы: сложного управления памятью и больших дополнительных затрат на фактическую перестановку строк.

Процесс сортировки включает три шага:

1) чтение всех строк ввода;

2) их сортировка;

3) вывод их в правильном порядке.

 

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

Давайте отложим на некоторое время рассмотрение шага сортировки и сосредоточимся на структуре данных и вводе-выводе. Функция, осуществляющая ввод, должна извлечь символы каждой строки, запомнить их и построить массив указателей строк. Она должна также подсчитать число строк во вводе, так как эта информация необходима при сортировке и выводе. Так как функция ввода в состоянии справиться только с конечным чис лом вводимых строк, в случае слишком большого их числа она может возвращать некоторое число, отличное от возможного числа строк, например –1. Функция осуществляющая вывод, должна печатать строки в том порядке, в каком они появляются в массиве указателей.

#define null 0

#define lines 100 // Максимальное число строк

main()       // Сортировка вводимых строк

{

char *lineptr[lines]; // Указатели на след. строки

int nlines; // Количество введенных линий

if ((nlines = readlines(lineptr, lines)) >= 0)

{

sort(lineptr, nlines);

writelines(lineptr, nlines);

}

else

printf("Input too big to sort\n");

}

 

// Ввод строк для сортировки

#define maxlen 1000 // Максимальная длина строки

readlines(char *lineptr[],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(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(char *lineptr[],int nlines)

{

int i;

while (--nlines >= 0)

   printf("%s\n", *lineptr++);

}

 

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

Справившись с вводом и выводом, мы можем перейти к сортировке. Программа сортировки по Шеллу из главы 4 требует очень небольших изменений: должны быть модифицированы описания, а операция сравнения выделена в отдельную функцию. Основной алгоритм остается тем же самым, и это дает нам определенную уверенность, что он по-прежнему будет работать.

 

// Отсортировать строки v[0] ... v[n-1]

// в возрастающем порядке

sort(char *v[],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. Но мы считаем, что будет разумнее первоначальный вариант сделать более простым для понимания, а об «эффективности» позаботиться позднее.

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

В главе 2 мы отмечали, что поскольку в циклах while и for проверка осуществляется до того, как тело цикла выполнится хотя бы один раз, эти циклы оказываются удобными для обеспечения правильной работы программы при граничных значениях, в частности, когда ввода вообще нет. Очень полезно просмотреть все функции программы сортировки, разбираясь, что происходит, если вводимый текст отсутствует.

Упражнение 6-5. Перепишите функцию readlines таким образом, чтобы она помещала строки в массив, предоставляемый функцией main, а не в память, управляемую обращениями к функции alloc. Насколько быстрее стала программа?