Page 42 - 6110

Лекція № 10

ЗБЕРЕЖЕННЯ І СОРТУВАННЯ МАСИВІВ ДАНИХ

Однією з переваг масивів є можливість компактного
збереження послідовності їх елементів в локальній області пам'яті
(що не завжди вдається, наприклад, для зв'язаних списків), що
дозволяє ефективно виконувати операції з послідовного обходу
елементів таких масивів.
Масиви є дуже економною щодо пам'яті структурою даних. Для
збереження 100 цілих чисел в масиві необхідно рівно в 100 разів
більше пам'яті, ніж для збереження одного числа (плюс, можливо,
ще декілька байтів). В той же час, усі структури даних, які
базуються на вказівниках, потребують додаткової пам'яті для
збереження самих вказівників разом з даними. Однак, операції з
фіксованими масивами ускладнюються тоді, коли виникає
необхідність додавання нових елементів у вже заповнений масив.
Тоді його необхідно розширювати, що не завжди можливо і для
таких задач слід використовувати зв'язані списки, або динамічні
масиви.
У випадках, коли розмір масиву є досить великий та
використання звичайного звертання за індексом стає
проблематичним, або великий відсоток його комірок не
використовується, слід звертатись до асоціативних масивів, де
проблема індексування великих об'ємів інформації вирішується
більш оптимально.
Оскільки масиви мають фіксовану довжину, слід дуже
обережно ставитись до процедури звертання до елементів за їхнім
індексом, тому що намагання звернутись до елементу, індекс якого
перевищує розмір такого масива (наприклад, до елементу з
індексом 6 в масиві з 5 елементів), може призвести до
непередбачуваних наслідків.
Слід також бути уважним щодо принципів нумерації елементів
масиву, яка в одних мовах програмування може починатись з 0, а в
інших – з 1.
Збереження одновимірного масиву в пам'яті є тривіальним,
тому що сама пам'ять комп'ютера є одновимірним масивом. Для
збереження багатовимірного масиву ситуація ускладнюється.
Найпоширеніші способи його організації в пам'яті такі:
- розташування “рядок за рядком”. Це найбільш уживаний на
сьогодні спосіб, який зустрічається у більшості мов
програмування (1 2 3 4 5 6 7 8 9);

41