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

Упражнение 5.4. Напишите функцию strend(s,t) , которая выдает 1, если строка t расположена в конце строки s , и нуль в противном случае.

Упражнение 5.5. Напишите варианты библиотечных функций strncpy , strncat и strncmp , которые оперируют с первыми символами своих аргументов, число которых не превышает n . Например, strncpy(t,s,n) копирует не более n символов t в s . Полные описания этих функций содержатся в приложении B.

Упражнение 5.6. Отберите подходящие программы из предыдущих глав и упражнений и перепишите их, используя вместо индексирования указатели. Подойдут, в частности, программы getline (главы 1 и 4), atoi , itoa и их варианты (главы 2, 3 и 4), reverse (глава 3), а также strindex и getop (глава 4).

Как и любые другие переменные, указатели можно группировать в массивы. Для иллюстрации этого напишем программу, сортирующую в алфавитном порядке текстовые строки; это будет упрощенный вариант программы sort системы UNIX.

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

Для этого воспользуемся массивом указателей на начала строк. Поскольку строки в памяти расположены вплотную друг к другу, к каждой отдельной строке доступ просто осуществлять через указатель на ее первый символ. Сами указатели можно организовать в виде массива. Одна из возможностей сравнить две строки - передать указатели на них функции strcmp . Чтобы поменять местами строки, достаточно будет поменять местами в массиве их указатели (а не сами строки).

Здесь снимаются сразу две проблемы: одна - связанная со сложностью управления памятью, а вторая - с большими накладными расходами при перестановках самих строк. Процесс сортировки распадается на три этапа:

чтение всех строк из ввода

сортировка введенных строк

печать их по порядку

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