значення елементів масиву | |||||
….. | індекси елементів масиву |
Щоб звернутися до елементу масиву, треба вказати ім'я масиву і номер елемента в масиві (індекс):
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. Сортування методом простого обміну
Порівнюються і міняються місцями пари елементів, починаючи з останнього. В результаті найменший елемент масиву виявляється самим лівим елементом масиву. Процес повторюється з рештою елементами масиву.
|
|
42 | |||||
for(int i=1;i<n;i++)
for(int j=n-1;j>=i;j--)
if(a[j]<a[j-1])
{
int r=a[j];
a[j]=a[j-1];
a[j-1]=r;}
}