Мени

Увод у структуре података на језику Ц ++

introduction data structures c

Испробајте Наш Инструмент За Елиминисање Проблема

Уводни водич о структурама података на језику Ц ++.

„Структура података може се дефинисати као организовано прикупљање података које помажу програму да ефикасно и брзо приступи подацима, тако да цео програм може ефикасно да функционише. „

Знамо да су у свету програмирања подаци центар и све се врти око података. Морамо све радње података, укључујући складиштење, претраживање, сортирање, организовање и приступ подацима, обавити ефикасно и тек тада наш програм може успети.

=> Погледајте овде како бисте истражили целу листу водича за Ц ++.

Увод у структуре података на Ц ++ (1)

Шта ћете научити:

Преглед

Морамо пронаћи најефикаснији начин чувања података који нам може помоћи у изградњи динамичких решења. Структура података нам помаже у изградњи таквих решења.

Док организујемо или уређујемо податке у структуре, морамо да осигурамо да аранжман представља готово стварни објекат. Друго, овај аранжман треба да буде довољно једноставан да му свако може лако приступити и обрадити га кад год је то потребно.

У овој серији ћемо детаљно научити како о основној тако и о напредној структури података. Такође ћемо детаљно научити о разним техникама претраживања и сортирања које се могу изводити на структурама података.

Након што је научио ову серију туторијала, читалац би требало да се добро упозна са сваком структуром података и њеним програмирањем.

Прођимо кроз неке термине које користимо док се бавимо структурама података:

На пример,узми одређеног ученика. Ученик може имати следеће детаље представљене сликовито.

Пример - структура података

  • Подаци: То је елементарна вредност. На горњој слици, подаци о броју ученика могу бити подаци.
  • Ставка групе: Ово је ставка података која има више подтачака. На горњој слици, Студент_наме има Име и Презиме.
  • Запис: То је збирка података. У горњем примеру, ставке података попут броја ученика, имена, класе, старости, оцене итд. Заједно чине запис.
  • Ентитет: То је класа записа. На горњем дијаграму ученик је ентитет.
  • Атрибут или поље: Својства ентитета називају се атрибутима и свако поље представља атрибут.
  • Датотека: Датотека је збирка записа. У горњем примеру, студентски ентитет може имати хиљаде записа. Тако ће датотека садржати све ове записе.

Читалац треба да буде свестан свих ових израза јер их свако мало користимо када користимо различите структуре података.

Структуре података су главни блок програма и као програмери, требали бисмо бити опрезни коју структуру података користити. Тачна структура података која ће се користити је најтежа одлука што се тиче програмирања.

Размотримо потребу за структуром података у Програмирању.

Потреба за структуром података у програмирању

Како количина података наставља да расте, апликације постају све сложеније, тако да програмеру постаје тешко да управља тим подацима као и софтвером.

Типично, у било ком тренутку апликација се може суочити са следећим препрекама:

# 1) Претраживање велике количине података: С великом количином података која се обрађује и чува, у било ком тренутку од нашег програма ће се можда захтевати да претражује одређене податке. Ако су подаци превелики и нису правилно организовани, требаће вам пуно времена да бисте добили потребне податке.

Када за складиштење и организовање података користимо структуре података, њихово преузимање постаје брже и лакше.

# 2) Брзина обраде: Неорганизовани подаци могу резултирати спором брзином обраде, јер ће се много времена губити на преузимање и приступ подацима.

Ако податке правилно организујемо у структури података током складиштења, нећемо губити време на активности попут преузимања, сваки пут их организујући. Уместо тога, можемо се концентрисати на обраду података како бисмо произвели жељени резултат.

# 3) Више истовремених захтева: Многе апликације данас морају истовремено да захтевају податке. Ови захтеви би требали бити ефикасно обрађени како би се апликације могле несметано покретати.

Ако су наши подаци похрањени само насумично, тада нећемо моћи истовремено да обрадимо све истовремене захтеве. Стога је мудра одлука да се подаци поређају у одговарајућој структури података тако да се минимализује време извршавања истовремених захтева.

Класификација структуре података

Структуре података коришћене у језику Ц ++ могу се класификовати на следећи начин.

Класификација структура података

Структура података је начин организације података. Дакле, можемо класификовати структуре података како су приказане у примитивне или стандардне структуре података и непримитивне или кориснички дефинисане структуре података.

Видели смо све типове података подржане у Ц ++. Како је ово такође начин организације података, кажемо да је то стандардна структура података.

Остале структуре података нису примитивне и корисник их мора дефинисати пре него што их користи у програму. Ове кориснички дефинисане структуре података даље се класификују у линеарне и нелинеарне структуре података.

Линеарна структура података

Линеарне структуре података имају све елементе поредане линеарно или секвенцијално. Сваки елемент у линеарној структури података има претходника (претходни елемент) и наследника (следећи елемент)

Линеарне структуре података се даље деле на статичке и динамичке структуре података. Статичке структуре података обично имају фиксну величину и када се њихова величина декларише у време компајлирања, не може се променити. Динамичке структуре података могу динамички променити своју величину и прилагодити се себи.

Најпопуларнији пример линеарне статичке структуре података је низ.

Арраи

Низ је секвенцијална колекција елемената истог типа. Сваком елементу низа може се приступити користећи његов положај у низу који се назива индекс или индекс низа. Име низа показује на први елемент у низу.

низ

Горе приказано је низ „а“ од н елемената. Елементи су нумерисани од 0 до н-1. Величина низа (у овом случају н) назива се и димензија низа. Као што је приказано на горњој слици, име низа показује на први елемент низа.

Низ је најједноставнија структура података и ефикасан је јер се елементима може директно приступити помоћу претплата. Ако желимо да приступимо трећем елементу низа, онда морамо само да кажемо (2).

Али додавање или брисање елемената низа је тешко. Отуда користимо низове само у једноставним апликацијама или у апликацијама где додавање / брисање елемената није потребно.

Популарне линеарне динамичке структуре података су повезана листа, стек и ред.

Повезана листа

Повезана листа је колекција чворова. Сваки чвор садржи елемент података и показивач на следећи чвор. Чворови се могу динамички додавати и брисати. Повезана листа може бити појединачно повезана листа у којој сваки чвор има показивач само на следећи елемент. За последњи елемент, следећи показивач је постављен на нулу.

На двоструко повезаној листи, сваки чвор има два показивача, један на претходни, а други на следећи чвор. За први чвор, претходни показивач је нула, а за последњи чвор је следећи.

Повезана листа

Као што је приказано на горњој слици, почетак листе назива се глава, док се крај повезане листе назива реп. Као што је горе приказано, сваки чвор има показивач на следећи елемент. Лако можемо додавати или брисати елементе променом показивача на следећи чвор.

Гомила

Стек је линеарна структура података у којој се елементи могу додавати или уклањати само с једног краја познатог као „Врх“ стека. На овај начин, стек показује ЛИФО (Ласт Ин, Фирст Оут) тип приступа меморији.

Гомила

Као што је горе приказано, елементи у стеку се увек додају на један крај и такође уклањају са истог краја. Ово се назива „Врх“ стека. Када се дода елемент, он се гура низ стек, а врх стека се увећава за један положај.

Слично томе, када се елемент уклони, врх стека се смањује. Када је стек празан, врх стека је постављен на -1. Постоје две главне операције „Пусх“ и „Поп“ које се изводе на стеку.

Ред чекања

Ред је још једна линеарна структура података у којој се елементи додају на једном крају који се назива „задњи“ и бришу са другог краја који се назива „предњи“. Ред чекања приказује ФИФО (Фирст Ин, Фирст Оут) тип методологије приступа меморији.

Ред чекања

Горњи дијаграм приказује ред са задњим и предњим крајевима. Када је ред празан, задњи и предњи показивачи се међусобно подударају.

Нелинеарна структура података

У нелинеарним структурама података подаци нису поређани секвенцијално, већ су распоређени на нелинеаран начин. Елементи су међусобно повезани у нелинеарном распореду.

Нелинеарне структуре података су Дрвеће и Графови.

модел водопада животног циклуса развоја софтвера

Дрвеће

Стабла су нелинеарне вишеразинске структуре података које имају хијерархијски однос између елемената. Елементи стабла називају се Чворови.

Чвор на врху назива се корен стабла. Корен може имати један или више подређених чворова. Наредни чворови такође могу имати један или више подређених чворова. Чворови који немају подређене чворове називају се чворови листова.

Дрвеће

На горњем дијаграму приказали смо стабло са 6 чворова. Од ова три чвора су чворови листа, један највиши чвор је корен, а остали су подређени чворови. У зависности од броја чворова, подређених чворова итд. Или односа између чворова, имамо различите врсте стабала.

Графикони

Графикон је скуп чворова који се називају темена међусобно повезани помоћу тзв Ивице . Графови могу имати циклус унутар себе, тј. Исти врх може бити почетна тачка као и крајња тачка одређене путање. Дрвеће никада не може имати циклус.

Графикони

Горњи дијаграм је неусмерени графикон. Такође можемо имати усмерене графиконе где ивице представљамо помоћу усмерених стрелица.

Операције на структури података

Све структуре података изводе разне операције над његовим елементима.

Они су заједнички за све структуре података и наведени су на следећи начин:

  • У потрази: Ова операција се изводи за тражење одређеног елемента или кључа. Најчешћи алгоритми претраживања су секвенцијално / линеарно и бинарно претраживање.
  • Сортирање: Операција сортирања укључује распоређивање елемената у структури података у одређеном редоследу или узлазно или силазно. Постоје различити алгоритми за сортирање који су доступни за структуре података. Најпопуларнији међу њима су Куицксорт, Селецтион сорт, Мерге сорт итд.
  • Уметање: Операција уметања бави се додавањем елемента у структуру података. Ово је најважнија операција и као резултат додавања елемента, распоред се мења и морамо водити рачуна да структура података остане нетакнута.
  • Брисање: Операција брисања уклања елемент из структуре података. Исти услови које треба узети у обзир за уметање морају бити испуњени и у случају операције брисања.
  • Прелазак: Кажемо да прелазимо структуру података када посетимо сваки елемент у структури. Прелазак је потребан за обављање одређених специфичних операција на структури података.

У следећим темама прво ћемо научити разне технике претраживања и сортирања које ће се изводити на структурама података.

Предности структуре података

  • Одвајање: Структуре података се често примењују као апстрактни типови података. Корисници приступају само спољном интерфејсу без бриге о основној имплементацији. Тако структура података пружа слој апстракције.
  • Ефикасност: Правилна организација података резултира ефикасним приступом подацима, чиме програми постају ефикаснији. Друго, можемо одабрати одговарајућу структуру података у зависности од наших захтева.
  • Могућност поновне употребе: Можемо поново користити структуре података које смо дизајнирали. Они се такође могу компајлирати у библиотеку и дистрибуирати клијенту.

Закључак

Овим завршавамо овај водич о уводу у структуре података. Укратко смо представили сваку од структура података у овом упутству.

У нашим следећим водичима истражићемо више о структурама података заједно са разним техникама претраживања и сортирања.

=> Кликните овде за апсолутну Ц ++ серију тренинга.

Препоручено читање

^