- Метод «бульбашки» [ правити ]
- Функція qsort з бібліотеки stdlib [ правити ]
- Динамічне виділення пам'яті [ правити ]
- Програма впорядкування рядків в алфавітному порядку [ правити ]
Завдання «сортування» (упорядкування) - одна з перших цікавих і складних задач теорії алгоритмів. Загальні принципи висвітлює стаття « алгоритми сортування », Тут же ми розглядаємо способи впорядкування за допомогою мови Сі.
Метод «бульбашки» [ правити ]
Один з найпростіших алгоритмів рішення - метод «бульбашки».
#include <stdio.h> #define N 1000 int main () {int n, i, j; scanf_s ( "% d", & n); int a [N]; // зчитуємо кількість чисел n // формуємо масив n чисел for (i = 0; i <n; i ++) {scanf_s ( "% d", & a [i]); } For (i = 0; i <n - 1; i ++) {// порівнюємо два сусідні елементи. for (j = 0; j <n - i - 1; j ++) {if (a [j]> a [j + 1]) {// якщо вони йдуть у неправильному порядку, то // міняємо їх місцями. int tmp = a [j]; a [j] = a [j + 1]; a [j + 1] = tmp; }}}}
Зрозуміло, що після першого «пробігу» найбільший елемент масиву виявиться на останньому місці. Після другого пробігу ми будемо впевнені, що другий за величиною елемент знаходиться на передостанньому місці.
Завдання: Доведіть, що досить n - 1 {\ displaystyle n-1} 
Вирішивши цю задачу, ви доведете, що метод «бульбашки» вирішує завдання сортування.
Функція qsort з бібліотеки stdlib [ правити ]
Два оператора for, в яких відбувається сортування, можна замінити на один рядок:
qsort (a, n, sizeof (int), cmp);
Це функція, описана в стандартній бібліотеці ANSI C і оголошена в заголовки stdlib.h.
Тому на початку програми потрібно додати
#include <stdlib.h>
Функцією qsort можна впорядковувати об'єкти будь-якої природи. По суті, вона призначена впорядковувати безлічі блоків байтів рівної довжини. Другий аргумент функції - це число таких блоків, третій аргумент - довжина кожного блоку. Перший аргумент - це адреса, де знаходиться початок першого блоку (передбачається, що блоки в пам'яті розташовані один за одним поспіль).
Четвертий аргумент функції qsort - це ім'я функції, яка вміє порівнювати два елементи масиву. У нашому випадку це
int cmp (const void * a, const void * b) {return * (int *) a - * (int *) b; }
З огляду на зазначеної універсальності функції сортування, функція порівняння отримує в якості аргументу адреси двох блоків, які потрібно порівняти і повертає 1, 0 або -1:
позитивне значення, якщо a> b 0, якщо a == b від'ємне значення, якщо a <b
Оскільки у нас блоки байт - це цілі числа (в 32-бітної архітектури це четирёхбайтовие блоки), то необхідно привести дані покажчики типу (const void *) до типу (int *) і здійснюється це за допомогою дописування перед покажчиком вираження «(const int *) ». Потім потрібно отримати значення змінної типу int, яка лежить за цією адресою. Це робиться за допомогою дописування спереду зірочки.
Таким чином, ми отримали наступну програму
#include <stdio.h> #include <stdlib.h> #define N 1000 int cmp (const void * a, const void * b) {return * (int *) a - * (int *) b; } Int main () {int n, i, j; int a [N]; scanf ( "% d", & n); for (i = 0; i <n; i ++) {// ЧИТАЕМ ВХІД scanf ( "% d", & a [i]); } Qsort (a, n, sizeof (int), cmp); // сортуємо for (i = 0; i <n; i ++) {// ВИВОДИМО РЕЗУЛЬТАТ printf ( "% d", a [i]); } Return 0; }
Динамічне виділення пам'яті [ правити ]
Нижче наведена програма, де пам'ять під масив виділяється динамічно:
#include <stdio.h> #include <stdlib.h> #include <malloc.h> int cmp (const void * a, const void * b) {return * (int *) a - * (int *) b; } Int main () {int n, i; int * a; scanf ( "% d", & n); a = (int *) malloc (sizeof (int) * n); for (i = 0; i <n; i ++) {scanf ( "% d", & a [i]); } Qsort (a, n, sizeof (int), cmp); for (i = 0; i <n; i ++) {printf ( "% d", a [i]); } Free (a); return 0; }
Функція malloc (від англ. Memory allocation --- виділення пам'яті) робить запит до ядра операційної системи по виділенню заданої кількості байт. Єдиний аргумент цієї функції - число байт, яке вам потрібно. Як результат функція повертає покажчик на початок виділеної пам'яті. Покажчик на початок виділеної пам'яті & mbsah - це адреса комірки пам'яті, починаючи з якого йдуть N байт, які ви можете використовувати під будь-які свої потреби. Всю пам'ять, яка була виділена з допомогою функції malloc, потрібно звільняти за допомогою функції free. Аргумент функції free - це покажчик на початок виділеної колись пам'яті.
Програма впорядкування рядків в алфавітному порядку [ правити ]
#include <stdlib.h> #include <string.h> #include <stdio.h> #define N 100 #define M 30 int main (int argc, char * argv []) {char a [N] [M] ; int n, i; scanf ( "% d", & n); for (i = 0; i <n; i ++) scanf ( "% s", & a [i]); qsort (a, n, sizeof (char [M]), (int (*) (const void *, const void *)) strcmp); for (i = 0; i <n; i ++) printf ( "% s \ n", a [i]); return 0; }
Зверніть увагу на складне приведення типів.
Функція strcmp, оголошена в файлі string.h має наступний прототип:
int strcmp (const char *, const char *);
Тобто функція отримує два аргументи - покажчики на шматочки пам'яті, де зберігаються елементи типу char, тобто два масиви символів, які не можуть бути змінені всередині функції strcmp (заборона на зміну задається за допомогою модифікатора const) [1] .
У той же час в якості четвертого елемента функція qsort хотіла б мати функцію типу
int cmp (const void *, const void *);
У мові Сі можна здійснювати приведення типів є типами функції. В даному прикладі тип
int (*) (const char *, const char *); // функція, яка отримує два елементи типу 'const char *' і повертає елемент типу 'int'
приводиться до типу
int (*) (const void *, const void *); // функція, яка отримує два елементи типу 'const void *' і повертає елемент типу 'int'
- ^ Функція strcmp відповідно до опису, що видаються командою man 3 strcmp, здійснює порівняння двох рядків і визначає, яка з двох рядків йде першою в алфавітному порядку (порівнює два рядки в лексикографічному порядку), а саме: вона повертає 1, якщо перший рядок "більше "другий (йде після другої в алфавітному порядку), 0 - якщо вони збігаються, і -1 - якщо перший рядок" менше "другий.