Багатовимірні масиви в c

У першій статті були описані прийоми роботи з найпростішим видом масивів - одновимірним (лінійним) масивом. У цій, другій статті будуть розглянуті багатовимірні масиви. В основному, мова піде про двовимірних масивах. Але наведені приклади легко екстраполюються на масиви будь-якої розмірності. Також як і в першій статті, будуть розглядатися тільки масиви в стилі C / C ++, без використання можливостей STL.

Класика жанру

Якщо ми відкриємо класична праця «Мова програмування C» Брайана Керніган і Денніса Рітчі. то прочитаємо, що «В мові C є можливість працювати з багатовимірними прямокутними масивами, хоча на практиці вони використовуються набагато рідше, ніж масиви покажчиків». C ++ практично повністю успадкував роботу з багатовимірними масивами свого предтечі.

Визначення автоматичних багатовимірних масивів

У цьому розділі я буду іноді вживати термін «матриця» як синонім терміну «двовимірний масив». У C / C ++ прямокутний двовимірний масив чисел дійсно реалізує математичне поняття «матриця». Однак, в загальному випадку, двовимірний масив - поняття набагато ширше, ніж матриця, оскільки він може бути і не прямокутним, і не числовим.

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

У цьому прикладі визначається двовимірний масив з 3 рядків по 5 значень типу int в кожному рядку. Разом 15 значень типу int.

У другому прикладі визначається тривимірний масив, що містить 3 матриці, кожна з яких складається з 5 рядків по 2 значення типу int в кожному рядку.

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

При подальшому викладі для таких багатовимірних масивів буде вживатися термін «C-масив». що б відрізняти їх від масивів інших видів.

ініціалізація

При статичної (яка визначається на етапі компіляції) ініціалізації значення C-масиву перераховуються в порядку вказівки розмірів (індексів) у визначенні масиву. Кожен рівень (індекс), крім наймолодшого, багатовимірного масиву полягає в свою пару фігурних дужок. Значення наймолодшого індексу вказуються через кому:

У прикладі показана статична ініціалізація прямокутного масиву. Весь список ініціюючих значень укладений у фігурні дужки. Значення для кожної з 3 рядків укладені в свою пару з фігурних дужок, значення для кожного з 5 стовпців для кожного рядка перераховані через кому.

При наявності ініціалізатор, найлівіший розмір масиву може бути опущений. В цьому випадку компілятор сам визначить цей розмір, виходячи зі списку ініціалізації.

Заповнення масиву значеннями

Багатовимірний масив заповнюється значеннями за допомогою вкладених циклів. Причому, як правило, кількість циклів збігається з розмірністю масиву:

У цьому прикладі кожному елементу масиву присвоюється значення, перша цифра якого вказує номер рядка, а друга цифра - номер стовпця для цього значення (нумерація з 1).

Висновок значень масиву на консоль

В продовження попереднього прикладу можна написати:

В результаті отримаємо наступний висновок на консоль:

Для тривимірного масиву можна написати код, який використовує ті ж прийоми:

Тут присвоювання значення елементу масиву і висновок на консоль відбуваються в одній групі циклів.

Розташування в пам'яті

Для багатовимірного C-масиву виділяється єдиний блок пам'яті необхідного розміру: размер_массіва1 * размер_массіва2 *. * Размер_массіваN * sizeof (тіп_елемента_массіва).

Значення розташовуються послідовно. Самий лівий індекс змінюється найповільніше. Тобто для тривимірного масиву спочатку розташовуються значення для першої (індекс 0) матриці, потім для другої і т.д. Значення для матриць розташовуються через підрядник (пор. Зі статичної ініціалізацією масиву вище).

Ім'я (ідентифікатор) багатовимірного C-масиву є покажчиком на перший елемент масиву (так само як і для одновимірних масивів)

Якщо код з останнього прикладу трохи змінити:

поставити точку зупину на return і подивитися під отладчиком пам'ять, відведену під змінну ary. то буде видно, що значення, розташовані в пам'яті, послідовно зростають:

В останньому фрагменті здійснюється доступ до значень двовимірного масиву як до одновимірного масиву. Цивілізоване вирішення реалізується через union.

З двох прикладів, наведених вище, слід, що роботу з двовимірним або багатовимірним масивом (в розумінні на більш високому рівні абстракції) технічно можна організувати за допомогою одновимірного масиву відповідного розміру:

Цей прийом досить поширений. Його вигода в тому, що масив ary [DIM1 * DIM2] не обов'язково повинен бути виділений автоматично. Його можна виділяти і динамічно. Але при цьому логічно розглядати як C-масив.

нерідні близнюки

Тепер розглянемо роботу з «динамічними» багатовимірними масивами, тобто з масивами, пам'ять для яких виділяється динамічно.

Створення і знищення динамічних багатовимірних масивів

Як правило, робота з такими масивами здійснюється наступним чином:

(1) Для доступу до двовимірного масиву оголошується змінна ary типу покажчик на покажчик на тип (в даному випадку це покажчик на покажчик на int).

(2) Мінлива инициализируется оператором new. який виділяє пам'ять для масиву покажчиків на int.

(3) У циклі кожен елемент масиву покажчиків инициализируется оператором new. який виділяє пам'ять для масиву типу int.

Звільнення пам'яті відбувається строго в зворотному порядку: спочатку знищуються масиви значень типу int. а потім знищується масив покажчиків.

Робота з динамічним багатовимірним масивом синтаксично повністю збігається з роботою з багатовимірним C-масивом.

Приклад коду для тривимірного масиву:

Де собака порилася

Робота з динамічним багатовимірним масивом синтаксично повністю збігається з роботою з багатовимірним C-масивом. (Цитую попередній розділ.) Синтаксично - так, але між цими масивами є глибоке розходження, про який початківці програмісти часто забувають.

По-перше, для динамічного масиву виділяється інший обсяг пам'яті.

Якщо порахувати, скільки пам'яті буде виділятися для двовимірного масиву з прикладу вище, то вийде: перший оператор new виділив пам'ять для 3 покажчиків, другий оператор new в циклі тричі виділив пам'ять для 5 елементів типу int. Тобто вийшло, що виділили пам'яті для 15 значень типу int і для 3 значень типу покажчик на int. Для C-масиву компілятором була виділена пам'ять тільки для 15 значень типу int. (Усілякі вирівнювання та інші оптимізації не враховуємо!)

По-друге, пам'ять, виділена для динамічного масиву, що не неперервна. Отже, хак №1 (звернення з двовимірним масивом як з одновимірним) працювати не буде.

По-третє, передача багатовимірних масивів у функції і робота з ними буде відрізнятися для динамічних масивів і C-масивів.

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

Динамічний багатовимірний масив НЕ є C-масивом.

Парадоксально, але факт, що найбільш близьким родича для цих нерідних близнюків, є хак №2, який реалізує роботу з багатовимірним масивом за допомогою одновимірного масиву (див. Розділ Хакі). Всі три перерахованих вище відмінності для нього неактуальні.

Варто відзначити, що масив покажчиків на масиви - структура більш гнучка, ніж двовимірний C-масив. Наприклад, для масиву покажчиків на масиви розміри масивів можуть бути різними, або якийсь масив може взагалі бути відсутнім. Найбільш поширеним прикладом є «масив рядків», тобто масив покажчиків на масиви типу char (приклад - див. в наступному розділі).

Ще раз про заходи

З вищевикладеного випливає, що потрібно чітко відрізняти багатовимірні C-масиви виду

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

Іноді зовнішні відмінності досить незначні. Наприклад С-рядок - це одновимірний масив елементів типу char. закінчується нульовим байтом. Як реалізувати масив рядків?

Це - приклад визначення і ініціалізації двовимірного C-масиву

А тут визначено і инициализирован одновимірний (!) Масив покажчиків на масиви елементів типу char.

І, на закінчення, ще одне застереження.

Оскільки багатовимірні C-масиви, як правило, займають великий обсяг пам'яті, їх треба з особливою обережністю оголошувати всередині функцій, в тому числі в main (). І з обережністю в n-ного ступеня в рекурсивних функціях. Можна легко отримати переповнення стека і, як наслідок, аварійне завершення програми.

Багатовимірні масиви при роботі з функціями

Оскільки багатовимірні C-масиви і багатовимірні динамічні масиви - абсолютно різні типи даних, то і при роботі з функціями підходи будуть різні.

Передача в функцію багатовимірного C-масиву

Функція, яка отримує C-масив як параметр, може виглядати наступним чином:

Форма (1) - найбільш поширена.

Форма (2). При передачі багатовимірного C-масиву в функцію можна не вказувати довжину самого лівого вимірювання. Компілятору для розрахунку доступу до елементів масиву ця інформація не потрібна.

Повернути багатовимірний C-масив з функції в якості результату стандартними засобами неможливо.

Передача в функцію багатовимірного динамічного масиву

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

Для прикладу - повний код програми, яка демонструє роботу з двовимірним динамічним масивом з використанням функцій.

У першій статті я вже писав, що «Виділяти пам'ять в одній функції, а звільняти в інший - погана ідея, яка загрожує помилками». Тому розглядайте цей приклад тільки як демонстрацію роботи з функціями і масивами вказівників.

Хоча з іншого боку. З іншого боку, дуже схожий підхід повсюдно використовується в класах, коли якийсь ресурс (в даному випадку пам'ять) захоплюється в одній функції (конструкторі), а звільняється в інший (деструкції). Але в разі класів, безпека забезпечується инкапсуляцией критичних даних і підтримкою несуперечливого стану екземпляра класу методами класу.

Масив покажчиків використовується в кожній програмі, яка може отримувати вхідну інформацію з командного рядка (або при її виклику від операційної системи). Одна з класичних форм функції main () має вигляд:

Аргументами функції є кількість рядків argc (розмір масиву покажчиків) і масив покажчиків на рядки - argv. Тобто argv - це масив покажчиків на масиви значень типу char.

Мабуть це все, що я хотів розповісти в цій статті. Сподіваюся, що хтось вважатиме її корисною для себе.

Хай буде з вами святий Бьярн і апостоли його! ;-)