Вступ до масивів у структурі даних
Масив - це тип структури даних, який використовується для зберігання однорідних даних у суміжних місцях пам'яті. Це реалізує ідею зберігати різні предмети, щоб їх можна було отримати або отримати доступ за один раз.
Тут індекс посилається на розташування елемента в масиві. Давайте уявимо, якщо P (L) - це ім'я масиву, де 'P' - ім'я змінної, а 'L' - довжина масиву, тобто кількість елементів, наявних у масиві. Тоді P (i) являє собою елемент у тому, що 'i + 1'є в масиві.
Наприклад:
P (6) = 72 означає елемент у 6 + 1-му місці масиву.
Необхідність масиву: це допомагає представити велику кількість елементів за допомогою однієї змінної. Це також робить доступ до елемента більш швидким для зберігання в пам'яті за допомогою індексу масиву, який представляє розташування елемента в масиві.
Як працюють масиви в структурі даних?
Масив зберігає змінні у суміжних місцях та дає їм певний індекс. Коли хтось хоче отримати дані, людина використовує цей індекс. У наведеному вище масиві "P" скажіть базову адресу для масиву = 100, тоді елементи зберігаються як нижче:
Пам'ять, виділена масиву, може бути обчислена як:
- Один розмірний масив: загальна пам'ять, що виділяється на масив = кількість елементів * розмір одного елемента. Наприклад: у наведеному вище випадку пам'ять = 7 * (розмір int)
- Порядок основного порядку: загальна пам'ять, виділена на 2D масив = Кількість елементів * розмір одного елемента
= Кількість рядків * Кількість стовпців * Розмір одного елемента - Основний порядок стовпців: Загальна пам'ять, виділена на 2D масив = Кількість елементів * розмір одного елемента
= Кількість рядків * Кількість стовпців * Розмір одного елемента
Як визначити масиви?
Таким чином, масив може бути визначений як похідна структура даних для зберігання однорідних даних примітивного типу даних у суміжних місцях пам'яті. Нижче наведені операції, які можна виконати на масивах:
1. Вставка: Це стосується вставки елемента в масив у певному індексі. Це можна виконати з O (n) складністю.
2. Видалення: Це стосується видалення елемента з певного індексу. Ця операція вимагає зміщення елементів після видалення, таким чином, приймає складність O (n).
3. Пошук: Це стосується доступу до елемента в певному індексі масиву.
4. Подорож: Це стосується друку всіх елементів масиву один за одним.
Властивості масивів у структурі даних
Нижче наведено властивості масивів у структурі даних:
- Це похідний тип даних, що складається з колекції різних примітивних типів даних, таких як int, char, float тощо.
- Елементи масиву зберігаються в суміжних блоках в основній пам'яті.
- Ім'я масиву зберігає базову адресу масиву. Він виконує функцію вказівника на блок пам'яті, де зберігався перший елемент.
- Індекси масиву починаються від 0 до N-1 у випадку масиву з одномірними розмірами, де n представляє кількість елементів масиву.
- Елементи масиву можуть складатися лише з констант і буквальних значень.
Як створити масиви?
Ми можемо створити масиви, використовуючи наведений нижче синтаксис:
1. Розмірний масив: var = (c1, c2, c3, …… .cn)
Тут var посилається на змінну для масиву, яка зберігає базове розташування масиву. І c1, c2… - це елементи масиву.
Приклад: int a = (4, 6, 7, 8, 9)
Довжина масиву = n
2. Багатовимірний масив: var = ((r 01, … r 0n ), (r 10, … ..r 1n )… .. (r m0 … .r mn ))
Тут var посилається на назву масиву m рядків і n стовпців.
Як отримати доступ до елемента масивів?
Індекси масиву починаються від 0 до -1, 0, що вказує на перший елемент масиву, а -1 вказує на останній елемент масиву. Так само -2 позначає останній, але один елемент масиву. Скажімо, є масив 'A', який містить 10 елементів. Потім тут змінна зберігає посилання на першу змінну масиву, і це називається "Base Address" масиву. Після цього, якщо хтось хоче отримати доступ до елемента масиву, то адреса цього елемента обчислюється за допомогою наведеної нижче формули.
Адреса i-го елемента = Базова адреса + розмір i * кожного елемента
Тут розмір кожного елемента відноситься до пам'яті, взятої різними примітивними типами даних, у яких є масив. Наприклад, int займає 2 байти простору, а float займає 4 байти простору в C.
Доступ до багатовимірного масиву
Скажімо, A (r l, …… .., r u ) (c u, ……, c l ) - багатовимірний масив і rl, r u, c u, c l - нижня та верхня межі рядків та стовпців. Чим число рядків у A скажіть NR = r u - r l +1, а кількість стовпців у A, скажімо NC = c l - c u +1.
Тепер для пошуку адреси елемента в масиві є 2 способи:
- Основний рядок: де ми переходимо рядок за рядком.
Адреса A (i) (j) = Базова адреса + ((i - r l ) * NC + (j- c l )) * розмір кожного елемента.
- Основний стовпчик: Де ми переходимо колонку за стовпцем.
Адреса A (i) (j) = Базова адреса + ((i - r l ) + (j- c l ) * NR) * розмір кожного елемента.
Складність: Доступ до будь-якого елемента в масиві набагато простіше і його можна зробити за складності O (1).
Висновок
Масиви - це дуже унікальний спосіб структурувати збережені дані таким чином, що до них можна легко отримати доступ та отримати запит на отримання значень під певне число, використовуючи значення індексу. Хоча вставлення елемента в масив займає багато часу, оскільки воно потребує повної перестановки та зміщення існуючих елементів масиву. Тим не менш, він використовується для реалізації різних інших складних структур даних, таких як дерево, черга або стек, а також використовується в різних алгоритмах.
Рекомендована стаття
Це посібник з масивів у структурі даних. Тут ми обговорюємо, як створити та отримати доступ до елементів масиву в структурі даних разом із властивостями. Ви також можете ознайомитись з іншими нашими пов’язаними статтями, щоб дізнатися більше -
- Як створити масиви в PHP?
- Масиви в програмуванні Java Переваги та недоліки
- Масиви в програмуванні на С (приклади)
- 10 питань щодо інтерв'ю щодо структури даних