Меню

Въведение в структурите на данни в C ++

introduction data structures c

Уводен урок за структурите на данни в C ++.

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

Знаем, че в света на програмирането данните са центърът и всичко се върти около данните. Трябва да извършим всички операции с данни, включително съхраняване, търсене, сортиране, организиране и достъп до данни, и само тогава нашата програма може да успее.

как да настроите eclipse за c ++

=> Вижте тук, за да разгледате пълния списък с уроци за C ++.

Въведение в структурите на данни в C ++ (1)

Какво ще научите:

Общ преглед

Трябва да намерим най-ефективния начин за съхраняване на данни, който може да ни помогне да изградим динамични решения. Структурата на данните ни помага при изграждането на такива решения.

Докато организираме или подреждаме данни в структури, трябва да гарантираме, че подредбата представлява почти обект от реалния свят. На второ място, тази подредба трябва да бъде достатъчно проста, така че всеки да има лесен достъп до нея и да я обработва, когато е необходимо.

В тази поредица ще научим подробно за основните, както и за усъвършенстваната структура на данните. Също така ще научим подробно за различни техники за търсене и сортиране, които могат да бъдат изпълнени върху структури от данни.

След като научи тази поредица от уроци, читателят трябва да се запознае добре с всяка структура от данни и нейното програмиране.

Нека разгледаме някои от термините, които използваме, докато се занимаваме със структури от данни:

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

Пример - Структура на данните

  • Данни: Това е елементарната стойност. На горната фигура номер на студентски списък може да бъде данни.
  • Групова позиция: Това е елементът от данни, който има повече от един под-елемент. На горната фигура Student_name има собствено и фамилно име.
  • Запис: Това е колекция от елементи от данни. В горния пример елементите от данни като номер на студентски списък, име, клас, възраст, клас и т.н. образуват запис заедно.
  • Обект: Това е клас записи. В горната диаграма ученикът е субект.
  • Атрибут или поле: Свойствата на обект се наричат ​​атрибути и всяко поле представлява атрибут.
  • Файл: Файлът е колекция от записи. В горния пример студент може да има хиляди записи. По този начин файлът ще съдържа всички тези записи.

Читателят трябва да е наясно с всички тези термини, тъй като ги използваме от време на време, когато използваме различни структури от данни.

Структурите на данните са основният градивен елемент на програмата и като програмисти трябва да внимаваме коя структура от данни да използваме. Точната структура на данните, която трябва да се използва, е най-трудното решение за вземане по отношение на програмирането.

Нека обсъдим необходимостта от структура на данните в програмирането.

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

Тъй като количеството данни продължава да расте, приложенията стават все по-сложни, поради което за програмиста става трудно да управлява тези данни, както и софтуера.

Обикновено по всяко време приложението може да се изправи пред следните препятствия:

# 1) Търсене на големи количества данни: С голямо количество данни, които се обработват и съхраняват, по всяко време може да се наложи нашата програма да търси определени данни. Ако данните са твърде големи и не са организирани правилно, ще отнеме много време, за да получите необходимите данни.

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

# 2) Скорост на обработка: Неорганизираните данни могат да доведат до бавна скорост на обработка, тъй като много време ще бъде загубено за извличане и достъп до данни.

Ако организираме данните правилно в структура от данни, докато съхраняваме, тогава няма да губим време в дейности като извличане, като ги организираме всеки път. Вместо това можем да се концентрираме върху обработката на данни, за да произведем желания резултат.

# 3) Множество едновременни заявки: Много приложения в наши дни трябва да направят едновременна заявка за данни. Тези заявки трябва да бъдат обработвани ефективно, за да могат приложенията да работят безпроблемно.

Ако данните ни се съхраняват само на случаен принцип, тогава няма да можем да обработим всички едновременни заявки едновременно. Така че е разумно решение да подредите данните в правилна структура от данни, така че да сведете до минимум времето за изпълнение на едновременните заявки.

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

Структурите на данни, използвани в C ++, могат да бъдат класифицирани, както следва.

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

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

Видяхме всички типове данни, поддържани в C ++. Тъй като това е и начин за организиране на данни, ние казваме, че това е стандартна структура на данните.

Останалите структури от данни са непримитивни и потребителят трябва да ги дефинира, преди да ги използва в програма. Тези дефинирани от потребителя структури от данни са допълнително класифицирани в линейни и нелинейни структури от данни.

Линейна структура на данните

Линейните структури от данни имат всички свои елементи подредени по линеен или последователен начин. Всеки елемент в линейна структура от данни има предшественик (предходен елемент) и наследник (следващ елемент)

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

Най-популярният пример за линейна статична структура на данните е масив.

Масив

Масивът е последователна колекция от елементи от същия тип. Всеки елемент от масива може да бъде достъпен, като се използва неговата позиция в масива, наречена индекс или индекс на масива. Името на масива сочи към първия елемент в масива.

масив

Показаното по-горе е масив „а“ от n елемента. Елементите са номерирани от 0 до n-1. Размерът на масива (в случая n) се нарича още измерението на масива. Както е показано на горната фигура, името на масива сочи към първия елемент на масива.

Масивът е най-простата структура от данни и е ефективен, тъй като елементите могат да бъдат достъпни директно чрез индекси. Ако искаме да получим достъп до третия елемент в масива, просто трябва да кажем a [2].

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

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

Свързан списък

Свързаният списък е колекция от възли. Всеки възел съдържа елемента от данни и указател към следващия възел. Възлите могат да се добавят и изтриват динамично. Свързаният списък може да бъде единично свързан списък, в който всеки възел има указател само към следващия елемент. За последния елемент следващият указател е зададен като нула.

В двойно свързания списък всеки възел има два указателя един към предишния възел и втория към следващия възел. За първия възел предишният указател е нула, а за последния възел следващият указател е нула.

Свързан списък

Както е показано на фигурата по-горе, началото на списъка се нарича глава, докато краят на свързания списък се нарича опашка. Както е показано по-горе, всеки възел има указател към следващия елемент. Можем лесно да добавяме или изтриваме елементи, като променяме указателя към следващия възел.

Стек

Стекът е линейна структура от данни, при която елементите могат да се добавят или премахват само от единия край, известен като „Върха“ на стека. По този начин стекът показва тип достъп до паметта LIFO (Last In, First Out).

Стек

Както е показано по-горе, елементите в стека винаги се добавят в единия край и също се премахват от същия край. Това се нарича „Горната част“ на стека. Когато се добави елемент, той се избутва надолу по стека и горната част на стека се увеличава с една позиция.

По същия начин, когато елемент се премахне, горната част на стека се намалява. Когато стекът е празен, горната част на стека е зададена на -1. Има две основни операции „Push“ и „Pop“, които се извършват на стека.

Опашка

Опашката е още една линейна структура от данни, при която елементите се добавят в единия край, наречен „заден“ и се изтриват от друг край, наречен „преден“. Опашката демонстрира FIFO (First In, First Out) вида на методологията за достъп до паметта.

Опашка

Горната диаграма показва опашка със задни и предни краища. Когато опашката е празна, задните и предните указатели съвпадат помежду си.

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

В нелинейните структури от данни данните не са подредени последователно, а са подредени по нелинеен начин. Елементите са свързани помежду си в нелинейна подредба.

Нелинейните структури от данни са дървета и графики.

Дървета

Дърветата са нелинейни многостепенни структури от данни, имащи йерархична връзка между елементите. Елементите на дървото се наричат ​​Nodes.

Възелът в горната част се нарича корен на дървото. Коренът може да има един или повече дъщерни възли. Следващите възли също могат да имат един или повече дъщерни възли. Възлите, които нямат дъщерни възли, се наричат ​​листни възли.

Дървета

В горната диаграма сме показали дърво с 6 възла. От тези три възела са листните възли, един най-горният възел е коренът, а другите са дъщерни възли. В зависимост от броя на възлите, дъщерните възли и т.н. или връзката между възлите имаме различни видове дървета.

Графики

Графиката е набор от възли, наречени върхове свързани помежду си посредством извиканите връзки Ръбове . Графиките могат да имат цикъл вътре в себе си, т.е. същият връх може да бъде начална точка, както и крайна точка на определен път. Дърветата никога не могат да имат цикъл.

Графики

Горната диаграма е ненасочена графика. Можем също да имаме насочени графики, където представяме ръбовете с помощта на насочени стрелки.

Операции върху структурата на данните

Всички структури от данни изпълняват различни операции върху неговите елементи.

Те са общи за всички структури от данни и са изброени, както следва:

  • Търсене: Тази операция се извършва за търсене на определен елемент или ключ. Най-често срещаните алгоритми за търсене са последователно / линейно търсене и двоично търсене.
  • Сортиране: Операцията за сортиране включва подреждане на елементите в структурата на данни в определен ред или възходящ, или низходящ. Има различни алгоритми за сортиране, които са на разположение за структури от данни. Най-популярни сред тях са Quicksort, Selection sort, Merge sort и др.
  • Вмъкване: Операцията за вмъкване се занимава с добавяне на елемент към структурата на данните. Това е най-важната операция и в резултат на добавянето на елемент, подредбата се променя и трябва да се погрижим структурата на данните да остане непокътната.
  • Изтриване: Операцията за изтриване премахва елемент от структурата на данните. Същите условия, които трябва да се имат предвид при вмъкване, трябва да бъдат изпълнени и в случай на операция по изтриване.
  • Преминаване: Казваме, че обхождаме структура от данни, когато посещаваме всеки елемент в структурата. Преминаването е необходимо за извършване на определени специфични операции върху структурата на данните.

В следващите ни теми първо ще научим различните техники за търсене и сортиране, които трябва да бъдат извършени върху структури от данни.

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

  • Абстракция: Структурите на данни често се прилагат като абстрактни типове данни. Потребителите имат достъп само до външния му интерфейс, без да се притесняват за основната реализация. По този начин структурата на данните осигурява слой на абстракция.
  • Ефективност: Правилната организация на данните води до ефективен достъп до данни, като по този начин прави програмите по-ефективни. На второ място, можем да изберем правилната структура на данните в зависимост от нашите изисквания.
  • Многократна употреба: Можем да използваме повторно структурите от данни, които сме проектирали. Те могат да бъдат компилирани в библиотека, както и разпределени на клиента.

Заключение

С това завършваме този урок за въвеждане в структурите на данни. Представихме всяка от структурите на данни накратко в този урок.

В следващите ни уроци ще разгледаме повече за структурите на данни заедно с различните техники за търсене и сортиране.

=> Щракнете тук за абсолютната серия за обучение на C ++.

Препоръчително четене

^