Оскільки покажчики — це також змінні, їх можна зберегти в масивах, так само як і інші змінні. Дозвольте нам проілюструвати це шляхом написання програми, що сортує в алфавітному порядку набір рядків тексту. Це спрощена версія UNIX програми sort.
У Розділі 3, ми представили функцію сортування Шелла, яка сортує масив цілих чисел, і вРозділі 4, ми вдосконалили її за допомогою quicksort. Той самий алгоритм підійде і цього разу за виключенням того, що тепер нам доведеться мати справу з рядками тексту, які будуть різної довжини і які, напротивагу цілим числам, неможливо порівняти або перемістити тільки однією операцією. Нам знадобиться таке представлення даних, що успішно і легко справлятиметься з рядками тексту змінної довжини.
Саме тут вступають в гру масиви покажчиків. Якщо рядки, які треба посортувати, зберігати від початку до кінця в довгих символьних масивах, тоді до кожного рядка можна мати доступ через покажчик на його перший символ. Самі покажчики також можна зберегти в масиві. Два рядка можна порівняти, передаючи їх покажчики strcmp. Якщо ці два невпорядкованих рядки потрібно поміняти місцями, міняються місцями покажчики з масиву покажчиків, а не самі рядки тексту.
+---+ +--------+ +---+ +--------+
| *-|---->| defghi | | *-|-. .->| defghi |
| | +--------+ | | \ / +--------+
| | +-------------+ | | \ / +-------------+
| *-|---->| jklmnopqrst | | *-|----X---->| jklmnopqrst |
| | +-------------+ | | / \ +-------------+
| | +-----+ | | / \ +-----+
| *-|---->| abc | | *-|-' `->| abc |
+---+ +-----+ +---+ +-----+
В такий спосіб ми можемо уникнути складної проблеми керування збереженням даних і значної ресурсоємкості переміщення самих рядків.
Процес сортування складається з трьох етапів:
читання всіх рядків вводу
їхнє сортування
вивід впорядкованих рядків
Як звичайно, найкращим вирішенням буде поділити програму на функції, що збігаються з цим логічним поділом, функція 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("error: input too big to sort\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'; /* вилучає символ нового рядка */
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] — це покажчик на символ, а *lineptr[i]— це самий символ, на який він вказує, перший символ i-ного збереженого текстового рядка.
Так як lineptr, самий по собі, це назва масиву, його можна трактувати як покажчик, так само як і в попередніх прикладах, а writelines написати натомість як
/* writelines: виводить рядки */
void writelines(char *lineptr[], int nlines)
{
while (nlines-- > 0)
printf("%s\n", *lineptr++);
}
Початково, *lineptr вказує на перший рядок; кожний елемент просуває його до натупного покажчика на рядок, у той час як nlines відраховує по спадаючій.
Маючи ввід і вивід під контролем, ми можемо перейти до сортування. Функція quicksort зРозділу 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 вимагає тільки незначних змін:
/* 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повинна бути такою самою, тож їх можна копіювати одне до одного.
Вправа 5-7. Перепишіть наново readlines, щоб вона зберігала рядки в масиві, наданому функцією main, замість виклику alloc для підтримки місця для зберігання. Наскільки швидшою буде програма?
