Сортування масивів

Константи у мові С

Робота з генератором випадкових чисел

Заповнення елементів масиву іноді зручно виконувати за допомогою генератора випадкових чисел. Функції для генерації випадкових чисел знаходяться у бібліотеці stdlib, яку треба підключати в тексті програми: #include <stdlib.h>.

void srand(int seed) – ініциалізує генератор випадкових чисел. seed – будь яке ціле число.

int rand(void) – не потребує параметрів. Повертає випадкове число

Приклад 4. Записати у цілу змінну випадкове число.

#include <stdlib.h>

int main()

{

int a;

srand(100);

a = rand();

return 0;

}

Для роботи зі змінними, що не змінюють свої значення, у мові С використовуються константи. Константи можна об’являти двома способами.

1. З використанням ключового слова const при об’яві змінної. При цьому змінну необхідно ініциіалізувати, нариклад:

const int a = 5;

2. З використанням директиви #define. Директива повинна розміщуватися поза межами функцій. Приклад:

#define N 10     int a[N]; double b[N];

Під час компіляції програми усі входження символу N будуть замінені на значення 10. Таким чином, у коді програми будуть виконані таки заміни: int a[10] та double b[10]

Самостійно: розробити алгоритм та програму для знаходження:

— кількості чисел, менших ніж 10 у масиві;

— кількості парних чисел у масиві;

— середнього значення елементів масиву.

Числа вводить користувач. Довжина масиву – 10 елементів.

Упорядкування елементів масиву за зростанням або убуванням виконується за допомогою сортування.

Бульбашковий алгоритм сортування (БАС) є найпростішим, але найменш ефективним. Ефективність алгоритму оцінюється за кількістю операцій та затратами часу на його виконання. При упорядкуванні елементів за зростанням, БАС виконує попарні порівняння елементів масиву, починаючи з його кінця, та виконує обмін елементів, якщо ніжній елемент є меншім ніж верхній. Після першого проходження по масиву, найменший елемент «випливає» вверх. Для виконання сортування масиву необхідно виконати n-1 проходжень по масиву, де n – кількість елементів масиву.

Якщо виконується упорядкування елементів масиву за убуванням, обмін сусідніх елементів виконується, якщо нижній елемент більший за верхнього.

Приклад роботи БАС. Заданий масив: 2, 4, 3, 1. Упорядкувати масив за зростанням його елементів.

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

Код програми:

void main()

{

int a[] = {2, 3, 4, 1};

int tmp, i, c = 0;

int count = 4; /* кількість елементів */

do {

for (i = count - 1; i > 0; i--) {

if (a[i] < a[i-1]) { /* порівняння */

tmp = a[i]; /* та обмін */

a[i] = a[i-1];

a[i-1] = tmp;

}

} /* end for */

c++;

} while (c < count -1);

for (i = 0; i < count; i++) { /* виведення */

printf("%d\n", a[i]); /* результату */

}

}

Більш ефективним алгоритмом сортування є алгоритм вставки мінімуму (максимуму). При упорядкуванні елементів за зростанням, виконується пошук мінімального елементу та його вставка на першу позицію. Елемент з першої позиції переміщується на місце мінімального елементу. Ця процедура виконується n-1 разів, де n – кількість елементів масиву.

Приклад роботи алгоритму сортування. Заданий масив:
2, 4, 3, 1. Упорядкувати масив за зростанням.

Мінімальний елемент встановлено на першу позицію     Третій елемент вже на вірному місці

Код програми:

void main()

{

int a[] = {2, 4, 3, 1};

int tmp, i, start = 0, count = 4;

int min; /* мінімум */

int mpos; /* позиція мінімального елементу */

do {

min = a[start]; /* встановлення мінімуму */

mpos = start;

for (i = start; i < count; i++) {

if (a[i] < min) { /* пошук мінімуму */

min = a[i]; /* мінімум */

mpos = i; /* його позиція */

}

}

if (mpos!= start) { /* обмін елементів */

tmp = a[start];

a[start] = min;

a[mpos] = tmp;

}

start++;

} while (start < count - 1);

for (i = 0; i < count; i++) { /* виведення результату */

printf("%d\n", a[i]);

}

}

Для сортування за убуванням, необхідно виконувати пошук максимуму та його вставку на першу позицію.

Лекція 6. Рядки.

Рядки. Представлення рядків. Об’ява рядків. Робота з рядками. Типові операції. Стандартні функції обробки рядків.

У мові С нема окремого типу для представлення рядків. Рядки представляються масивом символів: char string[]. Елементи масиву, в тому числі, й символьні, розташовуються у пам’яті послідовно. Ознакою завершення рядку у мові С є спеціальний символ: ‘\0’, що міститься у кінці рядка. Він є необхідним для коректної обробки рядків.

Приклади об’явлення рядків:

Об’ява у програмі char str1[6]; char str2[] = “Hello”; char *str3; char *str4 = “Bye”;

Комірки пам’яті

max=5 символів, останній ‘\0’ ‘\0’ доданий автоматично може вказувати на рядок ‘\0’ доданий автоматично

Важливо: 1. Для змінних str1, str2 та str4 пам’ять для розміщення відповідної кількості символів виділяється, для змінної str3 – не виділяється, це вказівник на рядок.

2. Рядки записуються у двійних лапках.

Введення та виведення рядків виконується за допомогою функцій scanf(), printf(), gets(), puts().

Для позначення рядку у функціях scanf() та printf() використовується символ %s. Наприклад, printf(“%s”, str).

Функція scanf() записує у рядок символи до першого пробілу. Так, якщо вводиться рядок “Hello, World!”, у змінної буде збережено тільки фрагмент “Hello,”. Також, при введенні рядку, у scanf() ім’я змінної вказується без символу &. Признак завершення рядку додається автоматично.

Функція gets(str) записує символи, що вводяться з клавіатури, у змінну str. Введення завершується після натискання клавіші Enter, признак завершення рядку додається у str автоматично.

Для виведення рядку str можна використовувати функцію puts(str).

Приклад 1.

char str[200];

gets(str);

puts(str);

Дата добавления: 2014-01-04