Меню

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

introduction data structures c

Спробуйте Наш Інструмент Для Усунення Проблем

Вступний посібник зі структур даних у C ++.

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

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

=> Дивіться тут, щоб ознайомитися з повним списком підручників з C ++.

Вступ до структур даних на C ++ (1)

Що ви дізнаєтесь:

Огляд

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

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

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

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

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

Наприклад,взяти конкретного студента. Студент може мати наступні деталі у вигляді зображеного.

Приклад - Структура даних

  • Дані: Це елементарне значення. На наведеному вище малюнку дані студентського списку можуть бути даними.
  • Елемент групи: Це елемент даних, який містить більше одного підпункту. На малюнку вище ім’я студента має ім’я та прізвище.
  • Запис: Це сукупність елементів даних. У наведеному вище прикладі елементи даних, такі як номер списку студентів, ім’я, клас, вік, клас тощо, разом утворюють запис.
  • Суб'єкт: Це клас записів. На наведеній вище схемі студент - це сутність.
  • Атрибут або поле: Властивості сутності називаються атрибутами, і кожне поле представляє атрибут.
  • Файл: Файл - це сукупність записів. У наведеному вище прикладі студент може мати тисячі записів. Таким чином, файл буде містити всі ці записи.

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

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

Давайте обговоримо необхідність структури даних у програмуванні.

Потреба в структурі даних при програмуванні

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

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

# 1) Пошук великих обсягів даних: Оскільки великий обсяг даних обробляється та зберігається, у будь-який момент наша програма може знадобитися для пошуку певних даних. Якщо дані занадто великі та неправильно організовані, отримання потрібних даних займе багато часу.

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

# 2) Швидкість обробки: Неорганізовані дані можуть призвести до повільної швидкості обробки, оскільки багато часу буде витрачено на отримання та доступ до даних.

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

# 3) Кілька одночасних запитів: Сьогодні багатьом додаткам потрібно одночасно подавати запит на дані. Ці запити слід ефективно обробляти, щоб програми працювали безперебійно.

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

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

Структури даних, що використовуються в C ++, можна класифікувати наступним чином.

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

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

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

Інші структури даних не примітивні, і користувач повинен їх визначити перед використанням у програмі. Ці визначені користувачем структури даних далі класифікуються на лінійні та нелінійні структури даних.

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

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

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

Найпопулярнішим прикладом лінійної статичної структури даних є масив.

Масив

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

масив

Наведене вище являє собою масив «а» з n елементів. Елементи нумеруються від 0 до n-1. Розмір масиву (в даному випадку n) також називається розмірністю масиву. Як показано на малюнку вище, ім'я масиву вказує на перший елемент масиву.

Масив є найпростішою структурою даних і є ефективним, оскільки елементи можуть отримати доступ безпосередньо за допомогою індексів. Якщо ми хочемо отримати доступ до третього елементу масиву, тоді нам просто потрібно сказати a (2).

Але додавати або видаляти елементи масиву складно. Отже, ми використовуємо масиви лише в простих додатках або в додатках, де додавання / видалення елементів не потрібно.

Популярні лінійні динамічні структури даних - це зв’язаний список, стек та черга.

Зв’язаний список

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

У подвійно зв’язаному списку кожен вузол має два покажчики - один на попередній вузол, а другий - на наступний вузол. Для першого вузла попередній вказівник є нульовим, а для останнього - наступним.

Зв’язаний список

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

Стек

Стек - це лінійна структура даних, в якій елементи можна додавати або видаляти лише з одного кінця, відомого як “Верх” стека. Таким чином, стек демонструє доступ до пам'яті типу LIFO (Last In, First Out).

Стек

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

Подібним чином, коли елемент видаляється, верх стека зменшується. Коли стек порожній, верхня частина стека встановлюється на -1. Існує дві основні операції 'Push' і 'Pop', які виконуються на стеку.

Черга

Черга - це ще одна лінійна структура даних, в якій елементи додаються з одного кінця, що називається 'тилом', і видаляються з іншого кінця, що називається 'спереду'. Черга демонструє тип методології доступу до пам'яті FIFO (First In, First Out).

Черга

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

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

У нелінійних структурах даних дані не розташовані послідовно, натомість вони розташовані нелінійно. Елементи з'єднані між собою в нелінійному розташуванні.

Нелінійні структури даних - це дерева та графіки.

які найкращі програми для віртуальної реальності

Дерева

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

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

Дерева

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

Графіки

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

Графіки

Наведена діаграма є ненаправленим графіком. Ми також можемо мати спрямовані графіки, де ми представляємо ребра, використовуючи спрямовані стрілки.

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

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

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

  • Пошук: Ця операція виконується для пошуку певного елемента або ключа. Найпоширенішими алгоритмами пошуку є послідовний / лінійний пошук та двійковий пошук.
  • Сортування: Операція сортування передбачає розташування елементів у структурі даних у певному порядку або за зростанням, або за спаданням. Існують різні алгоритми сортування, доступні для структур даних. Найпопулярнішими серед них є Quicksort, Selection sort, Merge sort тощо.
  • Вставка: Операція вставки має справу з додаванням елемента до структури даних. Це найважливіша операція, і в результаті додавання елемента компонування змінюється, і нам потрібно подбати про те, щоб структура даних залишалася недоторканою.
  • Видалення: Операція видалення вилучає елемент зі структури даних. Ті самі умови, які слід враховувати для вставки, також повинні виконуватися у випадку операції видалення.
  • Обхід: Ми говоримо, що обходимо структуру даних, коли відвідуємо кожен елемент у структурі. Обхід потрібен для здійснення певних конкретних операцій зі структурою даних.

У наступних темах ми спочатку вивчимо різні методи пошуку та сортування, які слід виконувати в структурах даних.

Переваги структури даних

  • Абстракція: Структури даних часто реалізуються як абстрактні типи даних. Користувачі отримують доступ лише до зовнішнього інтерфейсу, не турбуючись про основну реалізацію. Таким чином, структура даних забезпечує рівень абстракції.
  • Ефективність: Правильна організація даних призводить до ефективного доступу до даних, тим самим роблячи програми більш ефективними. По-друге, ми можемо вибрати правильну структуру даних залежно від наших вимог.
  • Багаторазове використання: Ми можемо повторно використовувати розроблені нами структури даних. Їх також можна скомпілювати у бібліотеку та розподілити клієнту.

Висновок

На цьому ми закінчуємо цей посібник із вступу до структур даних. Ми коротко представили кожну зі структур даних у цьому посібнику.

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

=> Клацніть тут, щоб переглянути абсолютну серію навчальних програм C ++.

Рекомендована література

^