Структури даних 101: Масиви - наочне введення для початківців

Познайомтеся зі структурами даних, якими ви користуєтеся щодня.

👋 Ласкаво просимо! Почнемо з життєво важливого контексту. Дозвольте запитати вас про це:

✅ Ви слухаєте музику на своєму смартфоні?

You Чи зберігаєте ви на телефоні список контактів?

Чи бачили ви коли-небудь таблицю лідерів під час змагань?

Якщо ваша відповідь "так" на будь-яке з цих питань, то майже напевно, що ви використовували масиви і навіть не знали цього! 😃 Масиви - це дуже потужні структури даних, які зберігають списки елементів. Вони мають нескінченні додатки. Вони дуже важливі у світі інформатики.

У цій статті ви дізнаєтесь плюси і мінуси масивів, їх структуру, операції та варіанти використання.

Давайте почнемо! 👍

Глибоке занурення в основну структуру масивів

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

Масиви використовують цю структуру "сітки" для зберігання списків відповідної інформації у сусідніх місцях пам'яті, щоб гарантувати надзвичайну ефективність пошуку цих значень. 🔳🔳🔳🔳

Ви можете думати про масиви так:

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

Чудово, правда? Давайте дізнаємось, як це працює за лаштунками! 😃

📚 Класифікація

Масиви класифікуються як однорідні структури даних, оскільки вонизберігати елементи одного типу .

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

Читання цінностей - магія починається!

Дивовижна потужність масивів походить від їхньої ефективності доступу до значень . Це досягається завдяки його сітчастій структурі. Давайте розглянемо це детальніше.🔍

Створюючи масив, ви:

- Призначити його змінної. 👈

- Визначте тип елементів, які він буде зберігати. 🎈

- Визначте його розмір (максимальна кількість елементів). 📚

Примітка: Ім’я, яке ви присвоїли цій змінній, є дуже важливим, оскільки ви будете використовувати його пізніше у своєму коді для доступу до значень та модифікації масиву.

Але як ви можете сказати комп’ютеру, до якого саме значення ви хочете отримати доступ? Тут індекси відіграють життєво важливу роль!

1️⃣ Індекси

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

Як ви можете бачити на діаграмі нижче, до першого елементу масиву посилається за допомогою індексу 0. По мірі просування вправо індекс збільшується на одиницю для кожного місця в пам'яті.

💡 Примітка: Я знаю, що спочатку здається дивним починати рахувати від 0 замість 1, але це називається нульовою нумерацією. Це дуже часто в інформатиці.

Загальний синтаксис доступу до елемента:[]

Наприклад:

Якщо ваш масив зберігається у змінній, myArrayі ви хочете отримати доступ до першого елемента (з індексом 0), ви б використалиmyArray[0]

2️⃣ Пам’ять

Тепер, коли ви знаєте, як отримати доступ до значень, давайте подивимося, як масиви зберігаються в пам’яті вашого комп’ютера. Коли ви визначаєте розмір масиву, весь цей простір у пам'яті з цього моменту "зарезервовано" для майбутніх значень, які ви можете вставити.

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

Наприклад:

Скажімо, ви визначаєте масив розміром 5, але вставляєте лише одне значення. Весь залишковий простір буде порожнім і "зарезервованим" в пам'яті, чекаючи майбутніх завдань.

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

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

🔧 Операції - за лаштунками!

Тепер, коли ви знаєте, що таке масиви, коли вони використовуються, і як вони зберігають елементи, ми заглибимося в їхні операції, такі як вставка та видалення.

1️⃣ Вставка - Ласкаво просимо!

Скажімо, у нас є масив розміром 6 і все ще є порожній простір. Ми хочемо вставити елемент “e” на початку масиву (індекс 0), але це місце вже зайняв елемент “a”. Що нам робити?

Щоб вставити в масиви , ми переміщуємо всі елементи, розташовані праворуч від місця вставки, на один індекс праворуч. Елемент "а" тепер буде мати індекс 1, елемент "b" - індекс 2 тощо.

💡 Примітка: Вам потрібно буде створити змінну для відстеження останнього індексуякий містить елементи. На діаграмі вище масив заповнюється до індексу 4 перед вставкою. Таким чином, ви можете визначити, заповнений масив, і який індекс слід використовувати, щоб вставити елемент в кінці.

Після цього наш елемент успішно вставлено. 👏

⚠️ Хвилинку! Що станеться, якщо масив заповнений?

Як ви думаєте, що станеться, якщо масив заповнений, і ви спробуєте вставити елемент? 😱

У цьому випадку вам потрібно створити новий, більший масив і вручну скопіювати всі елементи в цей новий масив. Ця операція дуже дорога, з часом. Уявіть, що сталося б, якби у вас був масив з мільйонами елементів! Це може зайняти дуже багато часу. ⏳

💡 Примітка . Єдиним винятком із цього правила, коли вставка відбувається дуже швидко, є вставка елемента в кінець масиву (в індексі, розташованому праворуч від останнього елемента), і ще є вільний простір. Це робиться за постійний час O (1).

2️⃣ Видалення - до побачення, до побачення!

Тепер припустимо, що ви хочете видалити елемент із масиву.

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

Ви повинні перемістити елементи, що йдуть після елемента, який ви хочете видалити на один індекс, ліворуч.

І нарешті, ви отримали цей масив resulting. Як бачите, “b” успішно видалено.

💡 Примітка: Видалення є дуже ефективним, коли ви видаляєте останній елемент. Оскільки вам потрібно створити змінну для відстеження останнього індексу, що містить елементи (на діаграмі вище, індекс 3), ви можете безпосередньо видалити цей елемент, використовуючи індекс.

3️⃣ Пошук елемента

У вас є три варіанти пошуку елемента в масиві:

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

👋 Коротко ...

  • Масиви - це надзвичайно потужні структури даних, які зберігають елементи одного типу. Тип елементів та розмір масиву фіксуються та визначаються під час його створення.
  • Пам'ять виділяється відразу після створення масиву, і вона порожня, поки ви не призначите значення.
  • Їх елементи розташовані в сусідніх місцях пам'яті , тому до них можна отримати дуже ефективний доступ (довільний доступ, O (1) = постійний час) за допомогою індексів .
  • Індекси починаються з 0 , а не з 1, як ми звикли.
  • Вставка елементів на початку або в середину масиву передбачає переміщення елементів праворуч. Якщо масив заповнений, створюється новий, більший масив (що не дуже ефективно). Вставка в кінець масиву є дуже ефективною, постійний час O (1).
  • Видалення елементів з початку або з середини масиву передбачає переміщення всіх елементів ліворуч, щоб уникнути залишення порожнього місця в пам'яті. Це гарантує, що елементи зберігаються в суміжних просторах в пам'яті. Видалення в кінці масиву дуже ефективно, оскільки ви видаляєте лише останній елемент.
  • Щоб знайти елемент , потрібно перевірити весь масив, поки не знайдете його. Якщо дані сортуються, ви можете використовувати алгоритми, такі як двійковий пошук, щоб оптимізувати процес.
"Навчайся з вчорашнього дня Живи сьогоднішнім днем ​​сподівайся на завтра. Головне - не припиняти допити ».

- Альберт Ейнштейн

👋 Дякую!

Я дуже сподіваюся, що вам сподобалась моя стаття. ❤️

Слідуйте за мною у Twitter, щоб знайти більше статей, подібних до цієї. 😃