Вторая функция – это strcmp(s,t), которая сравнивает символы строк s и t, возвращая отрицательное, нулевое или положительное значение в соответствии с тем, меньше, равно или больше лексикографически s, чем t.
Пример 6-10. Возвращаемое значение получается в результате вычитания символов из первой позиции, в которой s и t не совпадают.
// Получить return < 0, если s<t,
// return = 0, если s == t,
// return > 0, если s > t
strcmp(char s[], char t[]){
int i;
i = 0;
while (s[i] == t[i])
if (s[i++] == '\0')
return(0);
return(s[i]-t[i]);
}
Пример 6-11. А вот версия strcmp с указателями:
// Получить return < 0, если s<t,
// return = 0, если s == t,
// return > 0, если s > t
strcmp(char *s, char *t)
{
for ( ; *s == *t; s++, t++)
if (*s == '\0')
return(0);
return(*s-*t);
}
Так как ++ и -- могут быть как постфиксными, так и префиксными операциями, то встречаются и другие комбинации * и ++ и --, хотя менее часто. Например *++p увеличивает p до извлечения символа, на который указывает p, а *--p сначала уменьшает p.
Упражнение 6-2. Напишите вариант с указателями функции strcat из главы 3: strcat(s,t) копирует строку t в конец s.
Упражнение 6-3. Напишите макрос для strcpy.
Упражнение 6-4. Перепишите подходящие программы из предыдущих глав и упражнений, используя указатели вместо индексации массивов. Хорошие возможности для этого предоставляют функции getline (главы 2 и 6), atoi, itoa и их варианты (главы 3, 4 и 5), reverse (глава 4), index и getop (глава 5).
Вы, возможно, обратили внимание в предыдущих «С»-программах на довольно непринужденное отношение к копированию указателей. В общем это верно, что на большинстве машин указатель можно присвоить целому и передать его обратно, не изменив его; при этом не происходит никакого масштабирования или преобразования и ни один бит не теряется. К сожалению, это ведет к вольному обращению с функциями, возвращающими указатели, которые затем просто передаются другим функциям, – необходимые описания указателей часто опускаются.
Пример 6-12. Рассмотрим функцию strsave(s), которая копирует строку s в некоторое место для хранения, выделяемое посредством обращения к функции alloc, и возвращает указатель на это место. Правильно она должна быть записана так:
char *strsave(char *s) /* save string s somewhere */
{
char *p, *alloc();
if ((p = alloc(strlen(s)+1)) != null)
strcpy(p, s);
return(p);
}
На практике существует сильное стремление опускать описания:
*strsave(s) /* save string s somewhere */
{
char *p;
if ((p = alloc(strlen(s)+1)) != null)
strcpy(p, s);
return(p);
}
Эта программа будет правильно работать на многих машинах, потому что по умолчанию функции и аргументы имеют тип int, а указатель и целое обычно можно безопасно пересылать туда и обратно. Однако такой стиль программирования в своем существе является рискованным, поскольку зависит от деталей реализации и архитектуры машины и может привести к неправильным результатам на конкретном используемом вами компиляторе. Разумнее всюду использовать полные описания. Среда программирования Visual C++ или отладочная программа lint предупредят о таких конструкциях, если они по неосторожности все же появятся.
В языке «C» предусмотрены прямоугольные многомерные массивы, хотя на практике существует тенденция к их значительно более редкому использованию по сравнению с массивами указателей. В этом разделе мы рассмотрим некоторые их свойства.
Пример 6-13. Рассмотрим задачу преобразования дня месяца в день года и наоборот. Например, 1-ое марта является 60-м днем невисокосного года и 61-м днем високосного года. Давайте введем две функции для выполнения этих преобразований: day_of_year преобразует месяц и день в день года, а month_day преобразует день года в месяц и день. Так как эта последняя функция возвращает два значения, то аргументы месяца и дня должны быть указателями:
month_day(1977, 60, &m, &d)
Полагает m равным 3 и d равным 1 (1-ое марта).
Обе эти функции нуждаются в одной и той же информационной таблице, указывающей число дней в каждом месяце. Так как число дней в месяце в високосном и в невисокосном году отличается, то проще представить их в виде двух строк двумерного массива, чем пытаться прослеживать во время вычислений, что именно происходит в феврале. Вот этот массив и выполняющие эти преобразования функции:
static int day_tab[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 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 += day_tab[leap][i];
return(day);
}
// Опредлить месяц и день по дню года
month_day(int year, int yearday,
int *pmonth, int *pday)
{
leap= year%4 == 0 && year%100 != 0 || year%400 == 0;
for (i = 1; yearday > day_tab[leap][i]; i++)
yearday -= day_tab[leap][i];
*pmonth = i;
*pday = yearday;
}
Массив day_tab должен быть внешним как для day_of_year, так и для month_day, поскольку он используется обеими этими функциями.
Массив day_tab является первым двумерным массивом, с которым мы имеем дело. По определению в «C» двумерный массив по существу является одномерным массивом, каждый элемент которого является массивом. Поэтому индексы записываются следующим образом:
day_tab[i][j]
Нельзя писать так:
day_tab[i,j]
– как в большинстве языков. В остальном с двумерными массивами можно, в основном, обращаться таким же образом, как в других языках. Элементы хранятся по строкам, т.е. при обращении к элементам в порядке их размещения в памяти быстрее всего изменяется самый правый индекс.
Массив инициализируется с помощью списка начальных значений, заключенных в фигурные скобки; каждая строка двумерного массива инициализируется соответствующим подсписком. Мы поместили в начало массива day_tab столбец из нулей для того, чтобы номера месяцев изменялись естественным образом от 1 до 12, а не от 0 до 11. Так как за экономию памяти у нас пока не награждают, такой способ проще, чем подгонка индексов.
Если двумерный массив передается функции, то описание соответствующего аргумента функции должно содержать количество столбцов; количество строк несущественно, поскольку, как и прежде, фактически передается указатель. В нашем конкретном случае это указатель объектов, являющихся массивами из 13 чисел типа int. Таким образом, если бы требовалось передать массив day_tab функции f, то описание в f имело бы вид:
f(int day_tab[2][13])
{
...
}
Так как количество строк является несущественным, то описание аргумента в f могло бы быть и таким:
int day_tab[][13];
или таким
int (*day_tab)[13];
в которм говорится, что аргумент является указателем массива из 13 целых. Круглые скобки здесь необходимы, потому что квадратные скобки [ ] имеют более высокий уровень старшинства, чем *; как мы увидим в следующем разделе, без круглых скобок
int *day_tab[13];
является описанием массива из 13 указателей на целые.
6.8. Массивы указателей; указатели указателей
Так как указатели сами являются переменными, то вы вполне могли бы ожидать использования массива указателей. Это действительно так.
Пример 6-14. Мы проиллюстрируем это написанием программы сортировки в алфавитном порядке набора текстовых строк, предельно упрощенного варианта утилиты Sort операционной систем Unix (или соответствующей функции электронных таблиц 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 // Максимальная длина строки