27.2. Функции для проверки символов и преобразования данных

Макроопределения, описанные в заголовочном файле <ctype.h>:

int isalnum(int ch)	истина, если ch буква или цифра
int isalpha(int ch)	истина, если ch буква
int isdigit(int ch)	истина, если ch цифра
int islower(int ch)	истина, если ch буква нижнего регистра
int isupper(int ch)	истина, если ch буква верхнего регистра
int ispunct(int ch)	истина, если ch знак пунктуации
int isspace(int ch)	истина, если ch пробел, знак табуляции, возврат каретки, символ перевода строки, вертикальной табуляции, перевода страницы
int isxdigit(int ch)	истина, если ch шестнадцатеричная цифра

Функции преобразования символов:

int tolower(int ch)	преобразует ch к нижнему регистру (работает только для букв латинского алфавита)
int toupper(int ch)	преобразует ch к верхнему регистру (работает только для букв латинского алфавита)

Функции преобразования данных:

int atoi(char *s)	преобразует строку s в десятичное целое
long atol(char *s)	преобразует строку s в длинное десятичное целое
double atof(char *s)	преобразует строку s в вещественное число
char *itoa(int v, char *s, int baz)	преобразует целое v в строку s для системы счисления baz
char *ltoa(long v, char *s, int baz)	преобразует длинное целое v в строку s для системы счисления baz
char *ultoa(unsigned long v, char *s, int baz)	преобразует длинное беззнаковое целое v в строку s для системы счисления baz

27.3. Функция быстрой сортировки – gsort()

Вы уже должны знать некоторые способы сортировки – и быстрые, и не очень. Если вам надо отсортировать большой массив данных, без метода быстрой сортировки не обойтись. Для быстрой сортировки есть функция в стандартной библиотеке языка С, причем она позволяет сортировать массивы данных произвольного типа (как базового так и пользовательского). Программисты часто изобретают собственные функции, потому что им лень разбираться с чужими. Но в результате затрачивается больше времени, а программа получается хуже. Стандартными функциями стоит еще заниматься потому, что они открывают много нового в самом языке С. Особенно это справедливо в отношении функции qsort(). Описание функции находится в файле <stdlib.h>.

Прототип функции быстрой сортировки:

void qsort(const void *base,

unsigned int n, unsigned int size,

int (*cmp)(const void *, const void *));

Описание параметров: base – указатель на начало сортируемого массива, n – число сортируемых элементов в массиве, size – размер в байтах одного элемента массива, int (*cmp)(const void*, const void*) – указатель на функцию сравнения, которая показывает, какой из двух сравниваемых элементов больше. Использование в качестве параметра указателя на функцию сравнения и позволяет сортировать нам массивы произвольного типа и так, как нам захочется – по возрастанию или убыванию, по одному или нескольким полям, строки по алфавиту и по длине и т.д.

Т.к. тип массива может быть произвольный, формальный параметр с адресом массива имеет тип void *base. В применении к указателям void * говорит об универсальности. Указатель на void – это обобщенный указатель, о котором нельзя сказать, на что он указывает, до тех пор, пока его не приведут к какому-то конкретному типу. Объявление первого параметра функции как указатель на void позволяет принять любой указатель. Если бы в списке параметров стояло int *base, функция qsort() могла бы обрабатывать только целочисленные данные.

Функция, на которую указывает cmp, сравнивает два сортируемых элемента. Ее нужно писать самостоятельно, потому что, сравнивать можно по-разному. Функция qsort() вызывает, когда это нужно, функцию cmp, передавая ей указатели на сравниваемые элементы. Функцию qsort() не интересуют внутренности функции сравнения cmp. Нужно только, чтобы cmp возвращала положительное значение, если первый аргумент больше второго, ноль – если они равны и отрицательное значение, если первый аргумент меньше второго. Указатели на void сообщают нам, что функция cmp может сравнивать элементы любого размера, а слово const говорит о том, что с помощью передаваемого указателя нельзя изменить сам элемент. И это разумно, потому что функция cmp не должна менять передаваемые ей элементы массива. Она должна только решать, какой из них больше.

Функция сравнения сравнивает между собой два адресуемых элемента массива и возвращает в зависимости от результата сравнения целое число:

если элементы: возвращает:

*elem1 < *elem2 целое число < 0

*elem1 == *elem2 0

*elem1 > *elem2 целое число > 0

При сравнении «меньше, чем» означает, что левый элемент в конце сортировки должен оказаться перед правым аргументом. Аналогично, «больше, чем» означает, что в конце сортировки левый элемент должен оказаться после правого.

Задача. Примеры применения функции qsort() для сортировки массива целых чисел по возрастанию и убыванию абсолютных величин, и массива строк по убыванию длины, причем строки одной длины сортируются по алфавиту.

#include <stdio.h>

#include <stdlib.h> // для функции qsort()

#include <string.h>

#include <conio.h>

int cmpInt(const void *,const void *);

int cmpAbs(const void *,const void *);

int cmpString(const void *, const void *);

int cmpPointer(const void *, const void *);

void main(){

int i;

int x[10] = {-5, 3, 2, -4, 6, 7, 11, -17, 0, 13};

char w[10][20] = {"b", "bbb", "ab", "a", "aa",

"c", "dddd", "aaa", "ccc", "ba"};

char *p[10] = {"b", "bbb", "ab", "a", "aa",

"c", "dddd", "aaa", "ccc", "ba"};

puts("===========================");

qsort(x, 10, sizeof(int), cmpInt);

for(i=0; i<10; i++)

printf("%d ", x[i]);

printf("\n===========================\n");

getch();

qsort(x, 10, sizeof(x[0]), cmpAbs);

for(i=0; i<10; i++)

printf("%d ", x[i]);

printf("\n===========================\n");

getch();

qsort(w, 10, sizeof(w[0]), cmpString);

for(i=0; i<10; i++)

puts(w[i]);

puts("===========================");

getch();

qsort(p, 10, sizeof(char *), cmpPointer);

for(i=0; i<10; i++)

puts(p[i]);

puts("===========================");

getch();

}

// для сортировки целых цисел по возрастанию

int cmpInt(const void *a, const void *b){

int n1, n2;

n1 = *(int *)a;

n2 = *(int *)b;

return n1-n2;

}

// для сортировки целых цисел по убыванию абсолютных величин

int cmpAbs(const void *a, const void *b){

int n1, n2;

n1 = abs(*(int *)a);

n2 = abs(*(int *)b);

if(n1 > n2) return -1;

else if(n1 == n2) return 0;

else return 1;

// можно и так: return n2–n1;

}

// для сортировки строк по убыванию длины,

// строки равной длины сортируются по алфавиту

int cmpString(const void *a, const void *b){

char *s1, *s2;

int n1, n2;

s1 = (char *)a;

s2 = (char *)b;

n1 = strlen(s1);

n2 = strlen(s2);

if(n1 > n2) return -1;

else if(n1 == n2) return strcmp(s1,s2);

else return 1;

}

// для сортировки строк как массива указателей по алфавиту

int cmpPointer(const void *a, const void *b){

char *s1,*s2;

int n1, n2;

s1=*(char **)a;

s2=*(char **)b;

return strcmp(s1,s2);

}

Задача. Пример частичной сортировки массива целых чисел.

#include <stdio.h>

#include <stdlib.h> // для функции qsort()

#include <conio.h>

// для сортировки целых цисел по возрастанию

int cmpInt(const void *a, const void *b){

return *(int *)a - *(int *)b;

}

void main(){

int i;

int x[10] = {-5, 3, 2, -4, 6, 7, 11, -17, 0, 13};

qsort(x+2, 6, sizeof(int), cmpInt);

for(i=0; i<10; i++)

printf("%d ", x[i]);

// увидим массив с отсортированными средними шестью элементами:

// -5 3 -17 -4 2 6 7 11 0 13

printf("\n");

getch();

}