«Не в сукупності шукай єдності, але в однаковості поділу».
Козьма Прутков.
Масив покажчиків як тип даних і як структура даних
Масив покажчиків (МУ) - найпростіша структура даних, в якій проявляється відмінність між фізичним і логічним порядком проходження елементів. Спосіб організації даних ясний вже з самого визначення: це масив, кожен елемент якого містить покажчик на змінну (об'єкт).
Мал. 62.1. Різниця між масивом покажчиків - типом і структурою даних
Якщо це записати в термінах контекстного визначення змінних, то отримаємо, наприклад
Змінну p слід розуміти як масив (операція []), кожним елементом якого є покажчик на змінну типу double (операція *). Мінлива p є масивом покажчиків як тип даних, але не є такою як структура даних. Щоб перетворитися в структуру даних, вона бути доповнена указуемимі змінними і покажчиками (зв'язками).
Різноманіття варіантів реалізації масивів покажчиків виникає з кількох причин:
· C ам масив покажчиків, указуемие змінні і посилання (покажчики) можуть бути задані статично (в тексті програми), або динамічно створені під час її виконання;
· Двояка інтерпретація покажчика як покажчика на окрему змінну і на масив змінних (рядок), дозволяє створювати одномірні СД - масиви покажчиків на змінні і двовимірні - масиви покажчиків на масиви (рядки) таких змінних;
· Указуемие змінні можуть бути «власністю» структури даних, проте масив покажчиків може посилатися і на змінні (об'єкти), які є складовими частинами інших структур даних.
Основна складність полягає в тому, що у всіх випадках використовуються одні й ті ж типи даних, а конкретний вид структури даних визначається контекстом їх використання в тексті програми.
Типи даних, які використовуються при роботі з масивами вказівників
Один тип даних вже був нами згаданий - це масив покажчиків, змінна виду int * p []. Крім неї використовується ще одні тип виду int ** pp. який можна визначити в загальному вигляді як покажчик на покажчик.
Мал. 6 2 .2. Різноманіття інтерпретацій типу даних int ** pp
Нагадаємо, що в Сі мають місце дві інтерпретації покажчика, розрізнити які в тексті програми можна тільки по виду застосовуваних до покажчика операцій (тобто тільки в контексті його використання):
· Традиційної інтерпретації покажчика як посилання на окрему змінну відповідає операція непрямого звернення за вказівником * pp;
Покажчик на покажчик таким чином допускає цілих чотири інтерпретації. При цьому для кожної з них повинна бути створена (инициализирована) своя структура даних. Становище ускладнюється ще й тим, що за відповідністю структури даних і операціями над нею повинен стежити програміст (компілятор цього не робить).
int a = 5, b = 10; int * p = a; int ** pp = p;
int a [10] = 5, b [10] = 10; int * p = a; int ** pp = p;
for (int i = 0; i<10;i++) (*pp)[i]=0;
Другий варіант також досить екзотичний - покажчик на покажчик на лінійний масив змінних. У виразах, які використовуються в такій структурі даних присутні пріоритетні дужки, оскільки операція непрямого звернення на першому рівні передує операції індексації на другому.
В інших випадках тип даних int ** застосовується для роботи з масивами вказівників. Класична інтерпретація - покажчик на масив покажчиків на окремі об'єкти використовує природний порядок операцій * p [i] для доступу до указуемим об'єктів.
for (int s = 0, i = 0; i<10;i++) s=s+*pp[i];
Масив покажчиків на лінійні масиви змінних є двовимірною структурою даних і використовує подвійну індексацію. Функціонально вона є еквівалентом двовимірного масиву.
for (int s = 0, i = 0; i<3;i++)
for (int j = 0; j<4;j++) s=s+pp[i][j];
Статичні і динамічні масиви покажчиків
Інше джерело різноманітності - спосіб формування перерахованих структур даних. Статичний масив покажчиків формується при трансляції: змінні (сам масив покажчиків і указуемие змінні) визначаються статично, як звичайні іменовані змінні, а покажчики инициализируются. Структура даних включена безпосередньо в програмний код і «готова до роботи».
for (i = 0; i<19; i++) pd[i] = &d[i];
Нарешті, якщо масив покажчиків формується як динамічна структура даних, то динамічний масив покажчиків створюється в процесі роботи програми. Операція new як результат повертає покажчик на область пам'яті, що містить покажчики, тобто тип int **. який запам'ятовується у змінній того ж типу.
pp = newint * [20]; // пам'ять під масив покажчиків
for (i = 0; i<19; i++)
pp [i] = p; // можна pp [i] = new int; * Pp [i] = i;
Масив покажчиків. Фізичний і логічний порядок
При роботі з масивом покажчиків використовуються два контексту:
- pp [i] -i-й покажчик в масиві;
- * Pp [i]-значення i -ої указуемой змінної.
Алгоритми роботи з масивом покажчиків і звичайним масивом зовні дуже схожі. Різниця ж полягає в тому, що розміщення даних в звичайному масиві відповідає їх фізичним порядком проходження в пам'яті, а масив покажчиків дозволяє сформувати логічний порядок проходження елементів відповідно до розміщення покажчиків на них. Тоді зміна порядку проходження (включення, виключення, впорядкування, перестановка), яке в звичайному масиві полягає в переміщенні самих елементів, в масиві покажчиків має супроводжуватися операціями над покажчиками на них. Очевидні переваги виникають, коли самі указуемие змінні є досить великими, або переміщення їх неможливо з яких-небудь причин (наприклад, на них посилаються інші частини програми). Для порівняння наведемо функції сортування масиву і масиву покажчиків.
// --- Сортування масиву і масиву покажчиків
void sort1 (double d [], int sz)
for (k = 0, i = 0; i void sort2 (double * pd [])
for (k = 0, i = 0; pd [i + 1]! = NULL; i ++) if (* pd [i]> * pd [i +1]) // Порівняння указуемих змінних c = pd [i]; pd [i] = pd [i + 1]; pd [i + 1] = c; k = 1;> Якщо динамічний масив покажчиків посилається на безліч «вже відомих», тобто не ним створених і не йому належать змінних (об'єктів), то його доречно розглядати як колекцію, що має власний логічний порядок. Як приклад розглянемо функцію, яка створює масив покажчиків на впорядковані по зростанню позитивні значення, взяті з масиву. Як і для будь-якого динамічного масиву, для масиву покажчиків справедливі всі висновки про його розмірності: в даному випадку вона може бути обчислена заздалегідь. Результат функції має тип double ** - покажчик на динамічний масив покажчиків, створений усередині функції. // -------- Динамічний масив покажчиків // на впорядковані позитивні елементи вихідного масиву double ** create (double in [], int n)
int i. j. m; // Обчислити розмірність for (i = 0, m = 0; i double ** pp = new double * [m + 1]; // Створити ДМУ for (i = 0, j = 0; i if (in [i]> 0) pp [j ++] = in [i]; // позитивний елемент // --- Матриця довільної розмірності - масив покажчиків на масиви double ** load (char nm [], int n. int m)
if (fd == NULL) return NULL; fscanf (fd, "..", n, m); // Читання размерностей double ** pp = new double * [n]; // Створення ДМУ по першій розмірності pp [i] = new double [m]; // Створення лінійних ДМ (рядків) for (int j = 0; jДинамічний масив покажчиків на змінні (об'єкти)
Динамічний масив покажчиків на масиви змінних
Мал. 6 2 .3. Подання матриці змінної розмірності у вигляді ДМУ на рядкиСхожі статті