Керниган и Ритчи - Язык программирования Си (793773), страница 28
Текст из файла (страница 28)
Например, следующие два выражения:*р++ = val; /* поместить val в стек */val = *--р; /* взять из стека значение и поместить в val */являются стандартными для посылки в стек и взятия из стека (см. параграф 4.3.).Объявления функций, упомянутых в этом параграфе, а также ряда других стандартных функций, работающихсо строками, содержатся в заголовочном файле <string.h>.Упражнение 5.3. Используя указатели, напишите функцию strcat, которую мы рассматривали в главе 2(функция strcat(s, t) копирует строку t в конец строки s).Упражнение 5.4. Напишите функцию strend(s, t), которая выдает 1, если строка t расположена в концестроки s, и нуль в противном случае.Упражнение 5.5.
Напишите варианты библиотечных функций strncpy, strncat и strncmp, которыеоперируют с первыми символами своих аргументов, число которых не превышает n. Например, strncpy(t, s, n) копирует не более n символов t в s. Полные описания этих функций содержатся в приложенииВ.Упражнение 5.6. Отберите подходящие программы из предыдущих глав и упражнений и перепишите их,используя вместо индексирования указатели. Подойдут, в частности, программы getline (главы 1 и 4),atoi, itoa и их варианты (главы 2, 3 и 4), reverse (глава 3), а также strindex и getop (глава 4).5.6.
Массивы указателей, указатели на указателиКак и любые другие переменные, указатели можно группировать в массивы. Для иллюстрации этого напишемпрограмму, сортирующую в алфавитном порядке текстовые строки; это будет упрощенный вариантпрограммы 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 wntelines(char *lineptr[], int nlines);void qsort(char *lineptr[], int left, int right);/* сортировка строк */main(){int nlines; /* количество прочитанных строк */if ((nlines = readlinesdineptr, MAXLINES)) >= 0) {qsort(lineptr, 0, nlines-1);writelines(lineptr, nlines);return 0;} else {printf("ошибка: слишком много строк\п");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 I ! (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] — указатель на символ, a *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, a 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 i I 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, таккак он нужен и той и другой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
