Елементи масиву завжди нумеруються з 0

					значення елементів масиву
			…..		індекси елементів масиву

Щоб звернутися до елементу масиву, треба вказати ім'я масиву і номер елемента в масиві (індекс):

a [0] - індекс задається як константа,

a [55] - індекс задається як константа,

a [i] - індекс задається як змінна,

a [2 * i] - індекс задається як вираз.

Елементи масиву можна задавати при його визначенні:

int a [10] = {1,2,3,4,5,6,7,8,9,10};

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

2.2. поняття покажчика

Покажчики є спеціальними об'єктами в програмах на C / C + +. Покажчики призначені для зберігання адрес пам'яті.

Коли компілятор обробляє оператор визначення змінної, наприклад, int i = 10;, то в пам'яті виділяється ділянка пам'яті у відповідності з типом змінної (для int розмір ділянки пам'яті складе 4 байти) і записує в цю ділянку вказане значення. Усі звернення до цієї змінної компілятор замінить адресою області пам'яті, в якій зберігається ця змінна.

Рисунок 13 – Значення змінної та її адресу

Програміст може визначити власні змінні для збереження адрес областей пам'яті. Такі змінні називаються вказівниками. Покажчик не є самостійним типом, він завжди пов'язаний з якимось іншим типом.

У простому випадку оголошення покажчика має вигляд:

тип * ім'я;

Знак *, позначає покажчик і відноситься до типу змінної, тому його рекомендується ставити поряд з типом, а від імені змінної відокремлювати пробілом, за винятком тих випадків, коли описуються кілька покажчиків. При описі кількох покажчиків знак * ставиться перед ім'ям змінної-покажчика, тому що інакше буде не зрозуміло, що ця змінна також є покажчиком.

int * i;

double * f, * ff;/ / два покажчика

char * c;

Розмір покажчика залежить від моделі пам'яті. Можна визначити покажчик на покажчик: int ** a;

Покажчик може бути константою або змінною, а також вказувати на константу або змінну.

int i; / / ціла змінна

const int ci = 1; / / ціла константа

int * pi; / / покажчик на цілу змінну

const int * pci; / / покажчик на цілу константу

Покажчик можна відразу проинициализировать:

/ / Покажчик на цілу змінну

int * pi = &i;

З покажчиками можна виконувати наступні операції:

• разименованія (*);

• присвоювання;

• арифметичні операції (додавання з константою, віднімання,

інкремент + +, декремент -);

• порівняння;

• приведення типів.

Операція разименованія призначена для отримання значення змінної або константи, адреса якої зберігається в покажчику. Якщо покажчик вказує на змінну, то це значення можна змінювати, також використовуючи операцію разименованія.

int a; / / змінна типу int

int * pa = new int; / / покажчик і виділення пам'яті під / / динамічну змінну

* Pa = 10;/ / привласнили значення динамічної

/ / Змінної, на яку вказує покажчик

a = * pa;/ / привласнили значення змінної а

Арифметичні операції застосовні тільки до покажчиків одного типу.

• Інкремент збільшує значення покажчика на величину sizeof (тип).

char * pc;

int * pi;

double * pd;

.....

pc + +; / / значення збільшиться на 1

pi + +; / / значення збільшиться на 4 (добре)

pd + +; / / значення збільшиться на 8

• Декремент зменшує значення покажчика на величину sizeof (тип).

• Різниця двох вказівників - це різниця їх значень, поділена на розмір типу в байтах.

Підсумовування двох покажчиків не допускається.

• Можна підсумувати покажчик і константу:

2.3. Одновимірні масиви і покажчики

При визначенні масиву йому виділяється пам'ять. Після цього ім'я масиву сприймається як константний покажчик того типу, до якого відносяться елементи масиву. Винятком є використання операції sizeof (імя_массіва) і операції & імя_массіва.

int a [100];

/ * Визначення кількості займаної масивом пам'яті, в нашому випадку це 4 * 100 = 400 байт * /

int k = sizeof (a);

/ * Обчислення кількості елементів масиву * /

int n = sizeof (a) / sizeof (a [0]);

Результатом операції & є адреса нульового елемента масиву:

імя_массіва == & імя_массіва = & імя_массіва [0]

Ім'я масиву є вказівником-константою, значенням якої служить адреса першого елемента масиву, отже, до нього застосовні всі правила адресної арифметики, пов'язаної з покажчиками. Запис імя_массіва [індекс] цей вираз із двома операндами: ім'я масиву та індекс. Імя_массіва - це покажчик-константа, а індекс визначає зсув від початку масиву. Використовуючи вказівники, звернення за індексом можна записати наступним чином: * (імя_массіва + індекс).

for (int i = 0; i <n; i + +) / / друк масиву

cout << * (a + i) << "";

/ * До імені (адресою) масиву додається константа i і отримане значення разименовивается * /

Так як ім'я масиву є константним вказівником, то його неможливо змінити, отже, запис * (а + +) буде помилковою, а * (а +1) - немає.

Покажчики можна використовувати і при визначенні масивів:

int a [100] = {1,2,3,4,5,6,7,8,9,10};

/ / Поставили покажчик на вже певний масив

int * na = a;

/ * Виділили в динамічній пам'яті місце під масив з 100 елементів * /

int b = new int [100];

2.4. Перебір елементів масиву

1) Елементи масиву можна обробляти по одному елементу, рухаючись від початку масиву до його кінця (або в зворотному напрямку):

for (int i = 0; i <n; i + +) <обробка a [i]>

2) Елементи масиву можна обробляти по два елементи, рухаючись з обох сторін масиву до його середини:

int i = 0, j = n-1;

while (j <j) {

<Обробка a [I] і a [j]>;

i + +; j + +;}

Елементи масиву можна обробляти по два елементи, рухаючись від початку до кінця з кроком 1 (тобто обробляються пари елементів a [0] і a [1], a [1] і a [2] і т. д.)

for (i = 0; i <n-1; i + +)

<Обробка a [i] і a [i +1]>

Елементи масиву можна обробляти по два елементи, рухаючись від початку до кінця з кроком 2 (тобто обробляються пари елементів a [0] і a [1], a [2] і a [3] і т. д.)

i = 1;

while (i <n) {

<Обробка a [i] і a [i +1]>

i: = i +2;}

2.5. Класи задач по обробці масивів

1) До завдань 1 класу відносяться задачі, в яких виконується однотипна обробка всіх або зазначених елементів масиву. Вирішення таких завдань зводиться до встановлення того, як обробляється кожен елемент масиву або зазначені елементи, потім підбирається підходяща схема перебору, в яку вставляються оператори обробки елементів масиву. Прикладом такої задачі є знаходження середнього арифметичного елементів масиву.

2) До завдань 2 класу відносяться задачі, в яких змінюється порядок проходження елементів масиву. Обмін елементів всередині масиву виконується з використанням допоміжної змінної:

R = a [I]; a [I] = a [J]; a [J] = R;/ / обмін a [I] і a [J] елементів масиву.

3) До завдань 3 класу відносяться задачі, в яких виконується обробка декількох масивів або подмассіва одного масиву. Масиви можуть оброблятися за однією схемою - синхронна обробка або за різними схемами - асинхронна обробка масивів.

4) До завдань 4 класу відносяться задачі, в яких потрібно відшукати перший елемент масиву, що співпадає із заданим значенням - пошукові завдання в масиві.

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

Сортування - це процес перегрупування заданої множини об'єктів в деякому встановленому порядку.

2.4.1. Сортування за допомогою включення

Елементи масиву діляться на вже готову послідовність і вихідну. При кожному кроці, починаючи з I = 2, з вихідної послідовності витягується i-ий елемент і вставляється на потрібне місце готової послідовності, потім i збільшується на 1 і т. д.


готова	вихідна

У процесі пошуку потрібного місця здійснюються пересилання елементів більше вибраного на одну позицію вправо, тобто вибраний елемент порівнюють з черговим елементом відсортованої частини, починаючи з j: = i-1. Якщо вибраний елемент більше a [i], то його включають в відсортовану частину, в іншому випадку a [j] зрушують на одну позицію, а вибраний елемент порівнюють з наступним елементом відсортованої послідовності. Процес пошуку відповідного місця закінчується при двох різних умовах:

- Якщо знайдений елемент a [j]> a [i];

- Досягнутий лівий кінець готової послідовності.

int i, j, x;

for (i = 1; i <n; i + +)

{

x = a [i];/ / запам'ятали елемент, який будемо вставляти

j = i-1;

while (x <a[j]&&j> = 0) / / пошук підходящого місця

{

a [j +1] = a [j];/ / зсув вправо

j -;

}

a [j +1] = x;/ / вставка елемента

}

2.4.2. Сортування методом простого вибору

Вибирається мінімальний елемент масиву і міняється місцями з першим елементом масиву. Потім процес повторюється з рештою елементами і т. д.


		мин

int i,min,n_min,j;

for(i=0;i<n-1;i++)

{

min=a[i];n_min=i;//поиск минимального

for(j=i+1;j<n;j++)

if(a[j]<min)

{

min=a[j];

n_min=j;

}

a[n_min]=a[i];//обмен

a[i]=min;

}

2.4.3. Сортування методом простого обміну

Порівнюються і міняються місцями пари елементів, починаючи з останнього. В результаті найменший елемент масиву виявляється самим лівим елементом масиву. Процес повторюється з рештою елементами масиву.