Масиви покажчиків

Масиви

1.9.1 Основні поняття
Між покажчиками і масивами існує тісний взаємозв'язок. Будь-яка дія над елементами масивів, що досягається індексуванням, може бути виконана за допомогою покажчиків (посилань) і операцій над ними. Варіант програми з покажчиками буде виконаний швидше, але для розуміння він складніший.
Як показує практика роботи на Сі, покажчики рідко використовуються зі скалярними змінними, а частіше - з масивами. Покажчики дають можливість застосовувати адреси приблизно так, як це робить ЕОМ на машинному рівні. Це дозволяє ефективно організувати роботу з масивами. Будь-яку серйозну програму, що використовує масиви, можна написати за допомогою покажчиків.
Для роботи з масивом необхідно:
1. визначити ім'я масиву, його розмірність (кількість вимірів) і розмір - кількість елементів масиву;
2. виділити ОП для його розміщення.
У мові Сі можна використовувати масиви даних будь-якого типу:
• статичні: з виділенням ОП до початку виконання функції; ОП виділяється в стеку або в ОП для статичних даних;
• динамічні: ОП виділяється з купи в процесі виконання програми, за допомогою функцій malloc() і calloc().
Динамічні змінні використовують, якщо розмір масиву невідомий до початку роботи програми і визначається в процесі її виконання, наприклад за допомогою обчислення або введення.
Розмір масиву визначається:
1. для статичних масивів при його оголошенні; ОП виділяється до початку виконання програми; ім'я масиву - покажчик-константа; кількість елементів масиву визначається:
a. явно; наприклад: int а[5];
b. неявно, при ініціалізації елементів масиву; наприклад:
int а[] = { 1, 2, 3 };
2. для динамічних масивів у процесі виконання програми; ОП для них запитується і виділяється динамічно, з купи; ім'я покажчика на масив - це змінна; масиви ці можуть бути:
a. одновимірні і багатовимірні; при цьому визначається кількість елементів усього масиву й ОП запитується для всього масиву;
b. вільні (спеціальні двовимірні); при цьому визначається кількість рядків і кількість елементів кожного рядка, і ОП запитується і виділяється для елементів кожного рядка масиву в процесі виконання програми; при використанні вільних масивів використовують масиви покажчиків;
Розмір масиву можна не вказувати. В цьому разі необхідно вказати порожні квадратні дужки:
1. якщо при оголошенні ініціалізується значення його елементів; наприклад:
static int а[] = {1, 2, 3};
char b[] = "Відповідь:";
2. для масивів - формальних параметрів функцій; наприклад:
int fun1(int a[], int n);
int fun2(int b[k][m][n]);
3. при посиланні на раніше оголошений зовнішній масив; наприклад:
int а[5]; /* оголошення зовнішнього масиву */
main ()
{
extern int а[]; /*посилання на зовнішній масив */
}
В усіх оголошеннях масиву ім'я масиву - це покажчик-константа! Для формування динамічного масиву може використовуватися тільки ім'я покажчика на масив - це покажчик-змінна. Наприклад:
int *m1 = (int *) malloc (100 * sizeof (int));
float *m2 = (float *) malloc (200 * sizeof (float));
де m1 - змінна-покажчик на масив 100 значень типу int;
m2 - змінна-покажчик на масив 200 значень типу float.
Звільнення виділеної ОП відбувається за допомогою функції:
free (покажчик-змінна);
Наприклад:
free(ml);
free(m2);
Звертання до елементів масивів m1 і m2 може виглядати так:
m1[i], m2[j].
Пересилання масивів у Сі немає. Але можна переслати масиви поелементно або сумістити масиви в ОП, давши їм практично те саме ім'я.
Наприклад:
int *m1 = (int *) malloc(100 * sizeof(int));
int *m2 = (int *) malloc(100 * sizeof(int));
Для пересилання елементів одного масиву в іншій можна використати оператор циклу:
for (i = 0; i < 100; i++) m2[i] = ml [i];
Замість m2[i] = m1 [i]; можна використовувати:
*m2++ = *ml++;
або: *(m2 + i) = *(ml + i);
За допомогою покажчиків можна сполучити обидва масиви й у такий спосіб:
free(m2);
m2 = ml;
Після цього обидва масиви займатимуть одну й ту саму область ОП, виділену для масиву m1. Однак це не завжди припустимо. Наприклад, коли масиви розташовані в різних типах ОП: один - у стеку, інший - у купі. Наприклад, у функції main () оголошені:
int *m1 = (int *) malloc(100* sizeof(int));
int m2[100];
У вищенаведеному прикладі m1 - пакажчик-змінна, і масив m1 розташований у купі, m2 - покажчик-константа, і масив m2 розташований у стеку. У цьому випадку помилковий оператор: m2 = m1; тому що m2 - це покажчик-константа. Але після free(m1) припустимим є оператор:
m1 = m2; /* оскільки m1 - покажчик-змінна */
Для доступу до частин масивів і до елементів масивів використовується індексування (індекс). Індекс - це вираз, що визначає адресу значення або групи значень масиву, наприклад адреса значень чергового рядка двовимірного масиву. Індексування можна застосовувати до покажчиків-змінних на одновимірний масив - так само, як і до покажчиків-констант.
Індексний вираз обчислюється шляхом додавання адреси початку масиву з цілим значенням для одержання адреси необхідного елемента або частини масиву. Для одержання значення за індексним виразом до результату - адреси елемента масиву застосовується операція непрямої адресації (*), тобто одержання значення за заданою адресою. Відповідно до правил обчислення адреси цілочисельний вираз, що додається до адреси початку масиву, збільшується на розмір кванта ОП типу, що адресується покажчиком.
Розглянемо способи оголошення і формування адрес частини масиву й елементів одновимірних і багатомірних масивів за допомогою покажчиків.

1.9.2 Оголошення та звертання в одновимірних масивах
Форма оголошення одновимірного масиву з явною вказівкою кількості елементів масиву:
тип ім'я_масива [кількість-елементів-масива];
Звертання до елементів одновимірного масиву в загальному випадку можна представити індексуванням, тобто у вигляді
ім'я-масива [вираз];
де ім'я-масиву - покажчик-константа;
вираз - індекс, число цілого типу; він визначає зсув - збільшення адреси заданого елемента масиву щодо адреси нульового елемента масиву.
Елементи одновимірного масиву розташовуються в ОП підряд: нульовий, перший і т д. Приклад оголошення масиву:
int а[10];
іnt *p = а; /* - р одержує значення а */
При цьому компілятор виділяє масив в стеку ОП розміром (sizeof(Type) * розмір-масиву) байтів.
У вищенаведеному прикладі це 2 * 10 = 20 байтів. Причому а - покажчик-константа, адреса початку масиву, тобто його нульового елемента, р - змінна; змінній р можна присвоїти значення одним із способів:
р = а;
р = &а[0];
р = &a[i];
де &а[i] == (а + i) - адреса і-елемента масиву.
Відповідно до правил перетворення типів значення адреси i-елемента масиву на машинному рівні формується таким чином:
&а[i]= а + i * sizeof(int);
Справедливі також наступні співвідношення:
&a == a+0 == &a[0] - адреса а[0] - нульового елемента масиву;
а+2 == &а[2] - адреса а[2] - другого елементи масиву;
а+i == &a[i] - адреса a[i] - i-гo елемента масиву;
*а==*(а+0)==*(&а[0])==a[0] - значення 0-ого елемента масиву;
*(а + 2) == а[2] - значення а[2] - другого елементи масиву;
*(а + i) == а[i] - значення a[i] - i-гo елемента масиву;
*а + 2 == а[0] + 2 - сума значень а[0] і 2.
Якщо р - покажчик на елементи такого ж типу, які і елементи масиву a та p=а, то а та р взаємозамінні; при цьому:
p == &a[0] == a + 0;
p+2 == &a[2] == a + 2;
*(p + 2) == (&a[2]) == a[2] == p[2];
*(p + i) == (&a[i]) == a[i] == p[i];
Для a та p еквівалентні всі звертання до елементів a у вигляді:
a[i], *(a+i), *(i+a), i[a], та
p[i], *(p+i), *(i+p), i[p]

1.9.3 Оголошення та звертання до багатовимірних масивів
У даному розділі розглянемо оголошення і зв'язок покажчиків і елементів багатомірних масивів - що мають 2 та більше вимірів.
Багатомірний масив у мові Сі розглядається як сукупність масивів меншої розмірності. Наприклад, двовимірний масив - це сукупність одновимірних масивів (його рядків), тривимірний масив - це сукупність матриць, матриці - сукупності рядків, а рядок - сукупність елементів одновимірного масиву.
Елементи масивів розташовуються в ОП таким чином, що швидше змінюються самі праві індекси, тобто елементи одновимірного масиву розташовуються підряд, двовимірного - по рядках, тривимірного - по матрицях, а матриці - по рядках.
Для звертання до елементів багатомірного масиву можна використовувати нуль і більш індексів (індексних виразів):
ім'я-масиву [вираз1][вираз2]...
Наприклад, для звертання:
• до одновимірного масиву можна використовувати одно-індексний вираз (індекс);
• до двовимірного - 1 або 2 індексний вираз;
• до тривимірного - 1, 2 або 3 індексний вираз і т.д.
При звертанні до багатомірних масивів одержання значення елемента масиву можливо тільки після визначення адреси елемента масиву, тобто при повній кількості індексів. При цьому обчислюються індексні вираз зліва на право, і доступу до значення виконується після обчислення останнього індексного виразу.
Приклад оголошення двовимірного масиву значень типу int:
int а[m][n];
Цей масив складається з m одновимірних масивів (рядків), у кожному з яких утримується n елементів (стовпців). При роботі з цим двовимірним масивом можна використовувати одно або 2 індексний вираз. Наприклад:
а[i][j]- містить 2 індекси; використовується для звертання до елемента i -рядка, j -стовпця масиву; обчислюються індексні вирази, визначається адреса елемента масиву і вилучається його значення;
a[i] - містить 1 індекс; визначає адресу одновимірного масиву: адреса початку i-рядка масиву;
а - не містить індексу і визначає адресу масиву, його нульового елемента.
Таким чином, звертання до двовимірних масивів за допомогою імені і тільки одного індексу визначає покажчик на початок відповідного рядка масиву (адреса його нульового елемента). Наприклад:
а[0] == &a[0][0] == a+0*n*sizeof(int);
а[1] == &а[1][0] == a+1*n*sizeof(int);
a[i] == &a[i][0] == a+i*n*sizeof(int);
Приклад оголошення тривимірного масиву:
int а[k][m][n];
де:
• k- кількість матриць з m рядками і n стовпцями;
• m - кількість рядків (одновимірних масивів) у матриці;
• n - кількість стовпців (елементів у рядку) матриці.
Цей масив складається з k матриць, кожна з яких складається з m одновимірних масивів (рядків) по n елементів (стовпців). При звертанні до цього масиву можна використовувати імена:
a[l][i][j] - містить 3 індекси; використовується для звертання до елемента l -матриці, i -рядка. j -стовпця масиву; обчислюються індексні вирази, визначається адреса елемента масиву і вилучається його значення;
a[k][i] - визначає одновимірний масив - адреса початку i -рядка; k - матриці;
a[k] - визначає двовимірний масив - адреса початку k - матриці, тобто нульового елемента його нульового рядка;
а - адреса початку масиву, нульового елемента нульового рядка нульової матриці.
Наприклад:
int b[3][4][5];
int i, *ip, *ipp;
i = b[0][0][1];
ip = b[2][0];
ipp = b[2];
де: ip, ipp - покажчики на значення типу int.
Після ip = b[2][0]; ip є покажчиком на елемент 0-рядка 0-го стовпця 2-й матриці масиву, тобто b[2][0][0].
Після ipp = b[2]; ipp адресує 0-й рядок 2-ї матриці масиву, тобто містить адреса b[2][0][0].
Звертання до елементів багатомірного масиву більш детально розглянемо на прикладі двовимірного масиву. Наприклад:
int а[3][4]; /* а - покажчик-константа */
int *р = а; /* р - покажчик-змінна */
Після цього покажчик р можна використовувати замість покажчика а для звертання до рядків або елементів масиву а у вигляді: ім'я покажчика і зсув елемента щодо адреси початку масиву а.
В ОП елементи масиву а розташовуються таким чином, що швидше всіх змінюється самий правий індекс, тобто в послідовності:
а[0][0] а[0][1] а[0][2] а[0][3] а[1][0]... а[2][2] а[2][3].
При цьому для звертання до масиву а можна використовувати імена:
&a == а == &а[0][0] == *а - адреса а[0][0] - елемента 0-ого рядка 0-ого стовпця масиву а;
**а == *(&а[0][0]) == а[0][0] - значення елемента нульового рядка нульового стовпця масиву а;
a[i] == (а + i) == *(а + i) == &а[i][0] - адреса елемента i -рядка 0-стовпця;
*a[i] == **(а + i) == *(&а[i]) == a[i][0] - значення 0-го елемента i -рядка;
a[i][j] == *(*(а + i) + j) == *(a[i] + j) == a[i][j] - значення елемента i -рядка j -стовпця масиву а;
де:
(а + i) == *(а + i) == a[i] - адреса 0-го елемента i -рядка == &a[i][0];
(*(а + i) + j)- адреса j -елемента i -рядка = &a[i][j];
*(*(а + i) + j)- значення j -елемента i-рядка = a[i][j].
Значення адреси початку i -рядка (адреси 0-елемента i -рядка) на машинному рівні формується у виді:
a[i] = а + i == (a+i*n*sizeof(int)), де n - кількість значень в одному рядку.
Таким чином, адреса (i+1)-рядка відстоїть від i -рядка на (n*sizeof(int)) байтів, тобто на відстань одного рядка масиву.
Вираз a[i][j] компілятор Сі переводить в еквівалентний вираз:
*(*а + i) + j). Зрозуміло, запис a[i][j] більш традиційний у математиці і більш наочний.
До елементів двовимірного масиву можна звернутися і за допомогою скалярного покажчика на масив. Наприклад, після оголошення:
int а[m][n], *р = а;
*(p+i*n+j) - значення j - елемента i-рядка;
де: n - кількість елементів у рядку;
i*n + j - змішання а[i][j]- елемента відносно початку масиву а.

За допомогою масивів покажчиків можна формувати великі масиви і вільні масиви - колекції масивів будь-яких типів.

1.10.1 Робота з великими масивами
Розмір одного масиву даних повинний бути не більше 64 Кб. Але в реальних задачах можуть використовуватися масиви, що вимагають ОП, більшої ніж 64 Кб. Наприклад, масив даних типу float з 300 рядків і 200 стовпців потребує для розміщення 300 * 200 * 4 = 240000 байтів.
Для вирішення поставленої задачі можна використовувати масив покажчиків і динамічне виділення ОП для кожного рядка матриці. Рядок матриці не повинен перевищувати 64 Кб. У вищенаведеному прикладі ОП для рядка складає всього 800 байтів. Для виділення ОП з купи кожен рядок повинний мати покажчик. Для всіх рядків масиву треба оголосити масив покажчиків, по одному для кожного рядка. Потім кожному рядку масиву виділити ОП, привласнивши кожному елементу масиву покажчиків адресу початку розміщення рядка в ОП, і заповнити цей масив.
У запропонованому лістингу представлена програма для роботи з великим масивом цілих значень: з 300 рядків і 200 стовпців. Для розміщення він вимагає: 200 * 300 * 2 = 120000 байтів. При формуванні великого масиву використовується р - статичний масив покажчиків
При виконанні програми перебираються i-номери рядків масиву. Для кожного рядка за допомогою функції malloc () виконується запит ОП з купи і формується p[i] - значення покажчика на дані i -рядки. Потім перебираються i -номери рядків від 1 до 200. Для кожного рядка перебираються j-номери стовпчиків від 1 до 300. Для кожного i та j за допомогою генератора випадкових чисел формуються і виводяться *(р[i] + j) - значення елементів масиву. Після обробки масиву за допомогою функції free (p[i]) звільняється ОП виділена i-рядку масиву.
У наведеній нижче програмі використовуються звертання до Ai,j - елементів масиву у вигляді: *(p[i]+j), де p[i] + j - адреса Ai,j-елемента масиву.
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
void main()
{
int *p[200], i, j;
clrscr();
randomize();
for (i=0;i<200;i++)
/* Запит ОП для рядків великого масиву: */
p[i] = (int*) malloc (300 * sizeof (int));
for (i = 0; i < 200; i++)
for (j = 0; j < 300; j++)
{
*(p[i] + j) = random(100);
printf("%3d", *(p[i] + j));
if ((j + 1) % 20 == 0)
printf ("\n");
}
/* Звільння ОП рядків великого масиву: */
for (i=0; i < 200; i++)
free(p[i]);
}
У програмі використовується р - масив покажчиків.

1.10.2 Вільні масиви та покажчики
Термін "вільний" масив відносять до двовимірних масивів. Вони можуть бути будь-якого типу, у тому числі int, float, char і типу структура. Вільний масив - це двовимірний масив, у якому довжини його рядків можуть бути різними. Для роботи з вільними масивами використовуються масиви покажчиків, що містять в собі кількість елементів, рівну кількості рядків вільного масиву. Кожен елемент масиву покажчиків містить адресу початку рядка значень вільного масиву. ОП виділяється для кожного рядка вільного масиву, наприклад за допомогою функції malloc (), і звільняється функцією free (). Для того щоб виконати функцію malloc (), треба визначити кількість елементів у рядку, наприклад із вводу користувача або яким-небудь іншим способом. У нульовому елементі кожного рядка вільного масиву зберігається число, рівне кількості елементів даного рядка Дані в кожен рядок можуть вводитися з файлу або з клавіатури в режимі діалогу. Приклад вільного масиву цілих чисел приведений на рис 1.12:

У масиві на рис. 1.12 три рядки; у нульовому стовпці кожного рядка стоїть кількість елементів даного рядка. Далі - значення елементів матриці.
Приклад оголошення вільного масиву цілих, тобто статичного масиву покажчиків на дані типу int:
int *а[100];
Для масиву а приділяється ОП для 100 покажчиків на значення цілого типу, по одному покажчику на кожний з 100 рядків вільного масиву. Після визначення кількості елементів рядка для значень рядка повинна бути виділена ОП і сформоване значення покажчика в змінній a[i]. Цей покажчик посилається на область ОП, виділену для значень і-рядка матриці. Тільки після цього можна заносити в цю ОП значення елементів вільного масиву.
Реально ОП - це лінійна послідовність перенумерованих байтів. Елементи рядків вільного масиву можуть бути розташовані підряд або несуміжними відрізками ОП, виділеними для рядків.

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