logo

Вступ до структур даних

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

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

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

Вступ до структур даних

Фігура 1: Представлення елементів даних

У наведеному вище прикладі такі елементи, як ідентифікатор, вік, стать, ім’я, середина, прізвище, вулиця, місцевість тощо, є елементами елементарних даних. Навпаки, ім’я та адреса є елементами даних групи.

Що таке структура даних?

Структура даних є галуззю інформатики. Вивчення структури даних дозволяє нам зрозуміти організацію даних і управління потоком даних, щоб підвищити ефективність будь-якого процесу або програми. Структура даних — це особливий спосіб зберігання та організації даних у пам’яті комп’ютера, щоб ці дані можна було легко отримати та ефективно використовувати в майбутньому, коли це буде потрібно. Даними можна керувати різними способами, наприклад, логічною або математичною моделлю для певної організації даних, відомою як структура даних.

Обсяг конкретної моделі даних залежить від двох факторів:

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

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

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

список створення java

Основні термінології, пов’язані зі структурами даних

Структури даних є будівельними блоками будь-якого програмного забезпечення чи програми. Вибір відповідної структури даних для програми є надзвичайно складним завданням для програміста.

Нижче наведено деякі фундаментальні термінології, які використовуються, коли йдеться про структури даних:

    дані:Ми можемо визначити дані як елементарне значення або набір значень. Наприклад, ім’я та ідентифікатор працівника є даними, пов’язаними з працівником.Елементи даних:Одиниця вартості відома як елемент даних.Згрупувати елементи:Елементи даних, які мають підпорядковані елементи даних, відомі як групові елементи. Наприклад, ім’я працівника може мати ім’я, по батькові та прізвище.Елементарні елементи:Елементи даних, які не можна розділити на піделементи, відомі як елементарні елементи. Наприклад, ID працівника.Сутність і атрибут:Клас певних об'єктів представлений Entity. Він складається з різних атрибутів. Кожен атрибут символізує конкретну властивість цієї сутності. Наприклад,
Атрибути ID Ім'я Стать Назва посади
Цінності 1234 Стейсі М. Хілл Жінка Розробник програмного забезпечення

Сутності зі схожими атрибутами утворюють an Набір сутностей . Кожен атрибут набору сутностей має діапазон значень, набір усіх можливих значень, які можна призначити певному атрибуту.

Термін «інформація» іноді використовується для даних із заданими атрибутами значущих або оброблених даних.

    Поле:Одна елементарна одиниця інформації, що символізує Атрибут Сутності, відома як Поле.запис:Набір різних елементів даних називається записом. Наприклад, якщо ми говоримо про сутність працівника, то його ім’я, ідентифікатор, адресу та посаду можна згрупувати, щоб сформувати запис для працівника.Файл:Набір різних записів одного типу сутності називається файлом. Наприклад, якщо є 100 співробітників, у пов’язаному файлі буде 25 записів, які містять дані про кожного працівника.

Розуміння потреби в структурах даних

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

Чому ми повинні вивчати структури даних?

  1. Структури даних і алгоритми є двома ключовими аспектами інформатики.
  2. Структури даних дозволяють нам упорядковувати та зберігати дані, тоді як алгоритми дозволяють обробляти ці дані змістовно.
  3. Вивчення структур даних і алгоритмів допоможе нам стати кращими програмістами.
  4. Ми зможемо написати більш ефективний і надійний код.
  5. Ми також зможемо вирішувати проблеми швидше та ефективніше.

Розуміння цілей структур даних

Структури даних задовольняють дві взаємодоповнюючі цілі:

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

Розуміння деяких ключових особливостей структур даних

Деякі з важливих особливостей структур даних:

    Міцність:Як правило, усі комп’ютерні програмісти прагнуть створювати програмне забезпечення, яке дає правильний вихід для кожного можливого введення разом із ефективним виконанням на всіх апаратних платформах. Цей тип надійного програмного забезпечення має керувати як дійсними, так і недійсними введеннями.Адаптивність:Створення програмних додатків, таких як веб-браузери, текстові процесори та пошукова система Інтернету, включає величезні програмні системи, які потребують правильної та ефективної роботи або виконання протягом багатьох років. Крім того, програмне забезпечення розвивається завдяки появі технологій або ринковим умовам, що постійно змінюються.Повторне використання:Такі функції, як багаторазове використання та адаптивність, йдуть рука об руку. Відомо, що програміст потребує багато ресурсів для створення будь-якого програмного забезпечення, що робить його дорогим підприємством. Однак, якщо програмне забезпечення розроблено таким чином, що його можна багаторазово використовувати та адаптувати, його можна застосовувати в більшості майбутніх програм. Таким чином, виконуючи якісні структури даних, можна створювати багаторазове програмне забезпечення, яке виглядає економічно ефективним і економить час.

Класифікація структур даних

Структура даних надає структурований набір змінних, пов’язаних одна з одною різними способами. Він є основою інструменту програмування, який вказує на зв’язок між елементами даних і дозволяє програмістам ефективно обробляти дані.

контроль збереженої програми

Ми можемо класифікувати структури даних на дві категорії:

  1. Примітивна структура даних
  2. Непримітивна структура даних

На наступному малюнку показано різні класифікації структур даних.

Вступ до структур даних

малюнок 2: Класифікації структур даних

Примітивні структури даних

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

Непримітивні структури даних

    Непримітивні структури данихце ті структури даних, які походять від примітивних структур даних.
  1. Цими структурами даних не можна маніпулювати або працювати безпосередньо за допомогою інструкцій на рівні машини.
  2. Ці структури даних зосереджені на формуванні набору елементів даних, який є будь-яким однорідний (однаковий тип даних) або неоднорідний (різні типи даних).
  3. Виходячи зі структури та розташування даних, ми можемо розділити ці структури даних на дві підкатегорії -
    1. Лінійні структури даних
    2. Нелінійні структури даних

Лінійні структури даних

Структура даних, яка зберігає лінійний зв’язок між своїми елементами даних, відома як лінійна структура даних. Розташування даних виконується лінійно, де кожен елемент складається з наступників і попередників, за винятком першого та останнього елементів даних. Однак це не обов’язково вірно у випадку пам’яті, оскільки розташування може не бути послідовним.

На основі розподілу пам’яті лінійні структури даних далі класифікуються на два типи:

    Статичні структури даних:Структури даних, що мають фіксований розмір, відомі як статичні структури даних. Пам'ять для цих структур даних виділяється під час компіляції, і їх розмір не може бути змінений користувачем після компіляції; однак дані, що зберігаються в них, можна змінити.
    The Масив є найкращим прикладом статичної структури даних, оскільки вони мають фіксований розмір, і його дані можуть бути змінені пізніше.Динамічні структури даних:Структури даних, що мають динамічний розмір, відомі як динамічні структури даних. Пам'ять для цих структур даних виділяється під час виконання, і їх розмір змінюється протягом часу виконання коду. Крім того, користувач може змінювати розмір, а також елементи даних, що зберігаються в цих структурах даних під час виконання коду.
    Зв’язані списки, стеки , і Хвости є типовими прикладами динамічних структур даних

Типи лінійних структур даних

Нижче наведено список лінійних структур даних, які ми зазвичай використовуємо:

1. Масиви

Ан Масив це структура даних, яка використовується для збору кількох елементів даних одного типу в одну змінну. Замість того, щоб зберігати кілька значень однакових типів даних в окремих іменах змінних, ми могли б зберігати їх усі разом в одній змінній. Це твердження не означає, що нам доведеться об’єднати всі значення одного типу даних у будь-якій програмі в один масив цього типу даних. Але часто бувають випадки, коли деякі конкретні змінні одного типу даних пов’язані одна з одною у спосіб, який підходить для масиву.

Масив — це список елементів, у якому кожен елемент має унікальне місце в списку. Елементи даних масиву мають однакове ім’я змінної; однак кожен має інший номер індексу, який називається нижнім індексом. Ми можемо отримати доступ до будь-якого елемента даних зі списку за допомогою його розташування в списку. Таким чином, ключовою особливістю масивів, яку слід зрозуміти, є те, що дані зберігаються в безперервних місцях пам’яті, що дає змогу користувачам переходити між елементами даних масиву, використовуючи їхні відповідні індекси.

Вступ до структур даних

малюнок 3. Масив

Масиви можна розділити на різні типи:

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

Деякі застосування масиву:

  1. Ми можемо зберігати список елементів даних, що належать до одного типу даних.
  2. Масив діє як допоміжне сховище для інших структур даних.
  3. Масив також допомагає зберігати елементи даних бінарного дерева фіксованої кількості.
  4. Масив також діє як сховище матриць.

2. Зв'язані списки

java string concat

А Зв'язаний список є ще одним прикладом лінійної структури даних, яка використовується для динамічного зберігання набору елементів даних. Елементи даних у цій структурі даних представлені вузлами, з’єднаними за допомогою посилань або покажчиків. Кожен вузол містить два поля, інформаційне поле складається з фактичних даних, а поле вказівника складається з адреси наступних вузлів у списку. Покажчик останнього вузла зв'язаного списку складається з нульового вказівника, оскільки він ні на що не вказує. На відміну від масивів, користувач може динамічно регулювати розмір пов’язаного списку відповідно до вимог.

Вступ до структур даних

малюнок 4. Зв'язаний список

Зв’язані списки можна класифікувати за різними типами:

    Однозв'язаний список:Однозв’язаний список є найпоширенішим типом зв’язаного списку. Кожен вузол має дані та поле покажчика, що містить адресу наступного вузла.Двозв'язаний список:Двозв’язаний список складається з інформаційного поля та двох полів покажчиків. Інформаційне поле містить дані. Перше поле вказівника містить адресу попереднього вузла, тоді як інше поле вказівника містить посилання на наступний вузол. Таким чином, ми можемо рухатися в обох напрямках (назад і вперед).Круговий зв'язаний список:Циркулярний пов’язаний список подібний до однозв’язаного списку. Єдина ключова відмінність полягає в тому, що останній вузол містить адресу першого вузла, утворюючи циклічний цикл у циклічному пов’язаному списку.

Деякі застосування пов’язаних списків:

  1. Зв’язані списки допомагають нам реалізувати стеки, черги, бінарні дерева та графи попередньо визначеного розміру.
  2. Ми також можемо реалізувати функцію операційної системи для динамічного керування пам'яттю.
  3. Зв’язані списки також дозволяють поліноміальну реалізацію для математичних операцій.
  4. Ми можемо використовувати Circular Linked List для реалізації операційних систем або функцій додатків, які виконують завдання Round Robin.
  5. Циркулярний пов’язаний список також корисний у слайд-шоу, коли користувачеві потрібно повернутися до першого слайда після показу останнього слайда.
  6. Подвійний зв’язаний список використовується для реалізації кнопок вперед і назад у браузері для переміщення вперед і назад на відкритих сторінках веб-сайту.

3. Стеки

А Стек це лінійна структура даних, яка слідує за ЛІФО Принцип (останній увійшов, перший вийшов), який дозволяє виконувати такі операції, як вставка та видалення з одного кінця стека, тобто зверху. Стеки можуть бути реалізовані за допомогою безперервної пам'яті, масиву, і несуміжної пам'яті, зв'язаного списку. Приклади Стосів із реального життя – це купи книг, колода карт, купи грошей та багато іншого.

Вступ до структур даних

малюнок 5. Реальний приклад стека

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

Основні операції в стеку такі:

    Push:Операція вставлення нового елемента в стек називається операцією надсилання.Поп:Операція видалення або видалення елементів зі стеку називається операцією Pop.
Вступ до структур даних

Малюнок 6. Стек

Деякі застосування стеків:

  1. Стек використовується як тимчасова структура зберігання для рекурсивних операцій.
  2. Стек також використовується як допоміжна структура зберігання для викликів функцій, вкладених операцій і відкладених/відкладених функцій.
  3. Ми можемо керувати викликами функцій за допомогою стеків.
  4. Стеки також використовуються для оцінки арифметичних виразів у різних мовах програмування.
  5. Стеки також корисні для перетворення інфіксних виразів у постфіксні вирази.
  6. Стеки дозволяють перевірити синтаксис виразу в середовищі програмування.
  7. Ми можемо порівняти дужки за допомогою стеків.
  8. Стеки можна використовувати для перевертання рядка.
  9. Стеки корисні у вирішенні проблем, заснованих на ретрокурсі.
  10. Ми можемо використовувати стеки для пошуку в глибину в обході графів і дерев.
  11. Стеки також використовуються у функціях операційної системи.
  12. Стеки також використовуються у функціях UNDO і REDO під час редагування.

4. Хвости

А Черга це лінійна структура даних, подібна до стеку, з деякими обмеженнями щодо вставки та видалення елементів. Вставлення елемента в чергу виконується на одному кінці, а видалення — на іншому або протилежному кінці. Таким чином, ми можемо зробити висновок, що структура даних черги дотримується принципу FIFO (першим прийшов, першим вийшов) для маніпулювання елементами даних. Реалізацію черг можна виконати за допомогою масивів, пов’язаних списків або стеків. Деякі реальні приклади черг – це черга біля каси, ескалатор, автомийка та багато іншого.

Вступ до структур даних

Малюнок 7. Реальний приклад черги

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

Нижче наведено основні операції черги:

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

Малюнок 8. Черга

Деякі застосування черг:

  1. Черги зазвичай використовуються в операції пошуку в ширину в Graphs.
  2. Черги також використовуються в операціях планувальника завдань операційних систем, як-от буферна черга клавіатури для зберігання натиснутих користувачами клавіш і буферна черга друку для зберігання документів, надрукованих принтером.
  3. Черги відповідають за планування ЦП, планування завдань і планування дисків.
  4. Пріоритетні черги використовуються в операціях завантаження файлів у браузері.
  5. Черги також використовуються для передачі даних між периферійними пристроями та ЦП.
  6. Черги також відповідають за обробку переривань, створених програмами користувача для ЦП.

Нелінійні структури даних

Нелінійні структури даних — це структури даних, у яких елементи даних розташовані не в послідовному порядку. Тут вставка та видалення даних неможливі лінійним способом. Між окремими елементами даних існує ієрархічний зв’язок.

Типи нелінійних структур даних

Нижче наведено список нелінійних структур даних, які ми зазвичай використовуємо:

1. Дерева

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

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

Вступ до структур даних

Малюнок 9. Дерево

перетворення рядка на дату

Дерева можна розділити на кілька видів:

    Бінарне дерево:Структура даних дерева, де кожен батьківський вузол може мати не більше двох дочірніх вузлів, називається бінарним деревом.Двійкове дерево пошуку:Двійкове дерево пошуку — це структура даних дерева, де ми можемо легко підтримувати відсортований список чисел.Дерево AVL:Дерево AVL — це самобалансуюче бінарне дерево пошуку, у якому кожен вузол зберігає додаткову інформацію, відому як коефіцієнт балансу, значення якого дорівнює -1, 0 або +1.B-Tree:B-дерево — це особливий тип самобалансового бінарного дерева пошуку, де кожен вузол складається з кількох ключів і може мати більше двох дочірніх елементів.

Деякі застосування дерев:

  1. Дерева реалізують ієрархічні структури в комп’ютерних системах, таких як каталоги та файлові системи.
  2. Дерева також використовуються для реалізації структури навігації веб-сайту.
  3. Ми можемо створити код, подібний до коду Хаффмана, використовуючи Дерева.
  4. Дерева також допомагають приймати рішення в ігрових програмах.
  5. Дерева відповідають за реалізацію пріоритетних черг для функцій планування ОС на основі пріоритетів.
  6. Дерева також відповідають за розбір виразів і операторів у компіляторах різних мов програмування.
  7. Ми можемо використовувати Дерева для зберігання ключів даних для індексування системи керування базами даних (СУБД).
  8. Spanning Trees дозволяє нам маршрутизувати рішення в комп’ютерних і комунікаційних мережах.
  9. Дерева також використовуються в алгоритмі пошуку шляху, реалізованому в додатках штучного інтелекту (AI), робототехніки та відеоігор.

2. Графіки

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

Структура даних графа G вважається математичною структурою, що складається з набору вершин V і набору ребер E, як показано нижче:

G = (V,E)

Вступ до структур даних

Малюнок 10. Графік

Наведений вище малюнок представляє граф, що має сім вершин A, B, C, D, E, F, G і десять ребер [A, B], [A, C], [B, C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F] і [E, G].

Залежно від положення вершин і ребер, графи можна класифікувати на різні типи:

    Нульовий графік:Граф із порожнім набором ребер називається нульовим графом.Тривіальний графік:Граф, що має лише одну вершину, називається тривіальним графом.Простий графік:Граф, у якому немає ані петель, ані множинних ребер, називається простим графом.Мультиграф:Граф називається Мульти, якщо він складається з кількох ребер, але не містить самоциклів.Псевдограф:Граф із самоциклами та кількома ребрами називається псевдографом.Неорієнтований граф:Граф, що складається з неорієнтованих ребер, відомий як неорієнтований граф.Спрямований графік:Граф, що складається з орієнтованих ребер між вершинами, називається орієнтованим графом.Підключений графік:Граф із принаймні одним шляхом між кожною парою вершин називається зв’язаним графом.Відключений графік:Граф, у якому не існує жодного шляху між принаймні однією парою вершин, називається роз’єднаним графом.Регулярний графік:Граф, у якому всі вершини мають однаковий ступінь, називається регулярним графом.Повний графік:Граф, у якому всі вершини мають ребро між кожною парою вершин, називається повним графом.Графік циклу:Граф називається циклом, якщо він має принаймні три вершини та ребра, які утворюють цикл.Циклічний графік:Граф називається циклічним тоді і тільки тоді, коли існує хоча б один цикл.Ациклічний графік:Граф, що має нульові цикли, називається ациклічним графом.Кінцевий граф:Граф зі скінченною кількістю вершин і ребер відомий як скінченний граф.Нескінченний графік:Граф із нескінченною кількістю вершин і ребер відомий як нескінченний граф.Дводольний граф:Граф, у якому вершини можна розділити на незалежні множини A і B, а всі вершини множини A повинні бути з’єднані лише з вершинами множини B за допомогою деяких ребер, називається дводольним графом.Планарний графік:Граф називається планарним, якщо ми можемо намалювати його в одній площині з двома ребрами, що перетинаються одне з одним.Графік Ейлера:Граф називається Ейлеровим тоді і тільки тоді, коли всі його вершини мають парні ступені.Гамільтонів графік:Зв’язаний граф, що складається з гамільтонового контуру, відомий як гамільтонів граф.

Деякі застосування графіків:

  1. Графіки допомагають нам представляти маршрути та мережі в програмах транспорту, подорожей і зв’язку.
  2. Графіки використовуються для відображення маршрутів у GPS.
  3. Графіки також допомагають нам представити взаємозв’язки в соціальних мережах та інших мережевих програмах.
  4. Графіки використовуються в картографічних програмах.
  5. Графіки відповідають за представлення переваг користувача в програмах електронної комерції.
  6. Графіки також використовуються в комунальних мережах для виявлення проблем, які постають перед місцевими або муніципальними корпораціями.
  7. Графіки також допомагають керувати використанням і доступністю ресурсів в організації.
  8. Графіки також використовуються для створення карт посилань на документи веб-сайтів, щоб відобразити зв’язок між сторінками за допомогою гіперпосилань.
  9. Графіки також використовуються в роботах і нейронних мережах.

Основні операції зі структурами даних

У наступному розділі ми обговоримо різні типи операцій, які ми можемо виконувати для маніпулювання даними в кожній структурі даних:

    Обхід:Обхід структури даних означає доступ до кожного елемента даних точно один раз, щоб ним можна було керувати. Наприклад, обхід необхідний під час друку імен усіх співробітників у відділі.пошук:Пошук — це ще одна операція зі структурою даних, яка означає пошук розташування одного або кількох елементів даних, які відповідають певним обмеженням. Такий елемент даних може або не бути присутнім у заданому наборі елементів даних. Наприклад, за допомогою пошукової операції ми можемо знайти імена всіх співробітників, які мають досвід роботи більше 5 років.Вставка:Вставка означає вставлення або додавання нових елементів даних до колекції. Наприклад, ми можемо використовувати операцію вставки, щоб додати відомості про нового співробітника, якого компанія нещодавно найняла.Видалення:Видалення означає видалення або видалення певного елемента даних із заданого списку елементів даних. Наприклад, ми можемо використати операцію видалення, щоб видалити ім’я працівника, який залишив роботу.Сортування:Сортування означає впорядкування елементів даних у порядку зростання або спадання залежно від типу програми. Наприклад, ми можемо використати операцію сортування, щоб упорядкувати імена співробітників у відділі в алфавітному порядку або оцінити трійку найкращих виконавців місяця, упорядкувавши продуктивність співробітників у порядку спадання та витягнувши деталі трьох найкращих.Об'єднати:Злиття означає поєднання елементів даних двох відсортованих списків, щоб сформувати єдиний список відсортованих елементів даних.створити:Create — це операція, яка використовується для резервування пам’яті для елементів даних програми. Ми можемо виконати цю операцію за допомогою оператора оголошення. Створення структури даних може відбуватися під час наступного:
    1. Час компіляції
    2. Час виконання
      Наприклад, malloc() функція використовується в мові C для створення структури даних.
    Вибір:Вибір означає вибір певних даних із доступних даних. Ми можемо вибрати будь-які дані, вказавши умови всередині циклу.Оновлення:Операція Оновлення дозволяє нам оновлювати або змінювати дані в структурі даних. Ми також можемо оновити будь-які конкретні дані, вказавши деякі умови всередині циклу, наприклад операцію Selection.Розщеплення:Операція розділення дозволяє нам розділити дані на різні підчастини, зменшуючи загальний час завершення процесу.

Розуміння абстрактного типу даних

Відповідно до Національний інститут стандартів і технологій (NIST) , структура даних — це розташування інформації, як правило, у пам’яті, для підвищення ефективності алгоритму. Структури даних включають пов’язані списки, стеки, черги, дерева та словники. Вони також можуть бути теоретичною сутністю, як ім’я та адреса особи.

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

  1. Високий рівень абстракцій, наприклад додавання або видалення елемента зі списку.
  2. Пошук і сортування елемента в списку.
  3. Доступ до елемента з найвищим пріоритетом у списку.

Кожного разу, коли структура даних виконує такі операції, вона називається an Абстрактний тип даних (ADT) .

додати до масиву в java

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

Реалізація ADI містить структуру зберігання для зберігання елементів даних і алгоритмів для основних операцій. Усі структури даних, такі як масив, пов’язаний список, черга, стек тощо, є прикладами ADT.

Розуміння переваг використання ADT

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

Деякі застосування структур даних

Нижче наведено деякі застосування структур даних:

  1. Структури даних допомагають в організації даних у пам’яті комп’ютера.
  2. Структури даних також допомагають у представленні інформації в базах даних.
  3. Структури даних дозволяють реалізувати алгоритми пошуку в даних (наприклад, пошукова система).
  4. Ми можемо використовувати структури даних для реалізації алгоритмів для маніпулювання даними (наприклад, текстові процесори).
  5. Ми також можемо реалізувати алгоритми для аналізу даних за допомогою структур даних (наприклад, майнери даних).
  6. Структури даних підтримують алгоритми для створення даних (наприклад, генератор випадкових чисел).
  7. Структури даних також підтримують алгоритми для стиснення та розпакування даних (наприклад, утиліта zip).
  8. Ми також можемо використовувати структури даних для реалізації алгоритмів шифрування та дешифрування даних (наприклад, системи безпеки).
  9. За допомогою структур даних ми можемо створити програмне забезпечення, яке може керувати файлами та каталогами (наприклад, файловий менеджер).
  10. Ми також можемо розробити програмне забезпечення, яке може відтворювати графіку за допомогою структур даних. (Наприклад, веб-браузер або програмне забезпечення для 3D-візуалізації).

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