От изобретяването на компютрите хората използват термина „ Данни ' за препратка към компютърна информация, предадена или съхранена. Има обаче данни, които съществуват и в типове поръчки. Данните могат да бъдат числа или текстове, написани на лист хартия, под формата на битове и байтове, съхранени в паметта на електронни устройства, или факти, съхранени в съзнанието на човек. Тъй като светът започна да се модернизира, тези данни се превърнаха във важен аспект от ежедневния живот на всеки и различни реализации им позволиха да ги съхраняват по различен начин.
Данни е колекция от факти и цифри или набор от стойности или стойности в специфичен формат, който се отнася до единичен набор от стойности на елемент. След това елементите от данни се класифицират в подпозиции, което е групата от елементи, които не са известни като проста първична форма на елемента.
Нека разгледаме пример, при който името на служител може да бъде разделено на три подпозиции: Първо, Средно и Последно. Обаче ID, присвоен на служител, обикновено ще се счита за един елемент.
Фигура 1: Представяне на елементи от данни
В примера, споменат по-горе, елементи като ID, Възраст, Пол, Първо, Средно, Последно, Улица, Населено място и т.н., са елементарни елементи от данни. За разлика от тях Името и Адресът са групови елементи с данни.
Какво е структура на данните?
Структура на данни е клон на компютърните науки. Изследването на структурата на данните ни позволява да разберем организацията на данните и управлението на потока от данни, за да увеличим ефективността на всеки процес или програма. Структурата на данните е специфичен начин за съхраняване и организиране на данни в паметта на компютъра, така че тези данни да могат лесно да бъдат извлечени и ефективно използвани в бъдеще, когато е необходимо. Данните могат да се управляват по различни начини, като логическият или математическият модел за конкретна организация на данни е известен като структура от данни.
Обхватът на конкретен модел на данни зависи от два фактора:
- Първо, той трябва да бъде достатъчно зареден в структурата, за да отразява определената корелация на данните с обект от реалния свят.
- Второ, формирането трябва да бъде толкова лесно, че човек да може да се адаптира за ефективна обработка на данните, когато е необходимо.
Някои примери за структури от данни са масиви, свързани списъци, стек, опашка, дървета и др. Структурите от данни се използват широко в почти всеки аспект на компютърните науки, т.е. проектиране на компилатор, операционни системи, графики, изкуствен интелект и много други.
Структурите на данни са основната част от много компютърни алгоритми, тъй като позволяват на програмистите да управляват данните по ефективен начин. Той играе решаваща роля за подобряване на производителността на програма или софтуер, тъй като основната цел на софтуера е да съхранява и извлича данните на потребителя възможно най-бързо.
mysql ляво присъединяване
Основни терминологии, свързани със структурите от данни
Структурите на данни са градивните елементи на всеки софтуер или програма. Изборът на подходяща структура от данни за една програма е изключително предизвикателна задача за програмиста.
По-долу са някои основни терминологии, използвани винаги, когато са включени структури от данни:
Атрибути | документ за самоличност | Име | Пол | Длъжност |
---|---|---|---|---|
Стойности | 1234 | Стейси М. Хил | Женски пол | Разработчик на софтуер |
Обекти с подобни атрибути образуват an Набор от обекти . Всеки атрибут на набор от обекти има диапазон от стойности, набор от всички възможни стойности, които могат да бъдат присвоени на конкретния атрибут.
Терминът „информация“ понякога се използва за данни с дадени атрибути на значими или обработени данни.
Разбиране на необходимостта от структури от данни
Тъй като приложенията стават все по-сложни и количеството данни се увеличава всеки ден, това може да доведе до проблеми с търсенето на данни, скоростта на обработка, обработката на множество заявки и много други. Структурите на данни поддържат различни методи за организиране, управление и ефективно съхраняване на данни. С помощта на структурите от данни можем лесно да обхождаме елементите от данни. Структурите на данни осигуряват ефективност, повторна употреба и абстракция.
Защо трябва да научим структури от данни?
- Структурите на данни и алгоритмите са два от ключовите аспекти на компютърните науки.
- Структурите на данни ни позволяват да организираме и съхраняваме данни, докато алгоритмите ни позволяват да обработваме тези данни смислено.
- Изучаването на структури от данни и алгоритми ще ни помогне да станем по-добри програмисти.
- Ще можем да пишем код, който е по-ефективен и надежден.
- Освен това ще можем да решаваме проблемите по-бързо и по-ефективно.
Разбиране на целите на структурите от данни
Структурите на данни отговарят на две допълващи се цели:
Разбиране на някои ключови характеристики на структурите от данни
Някои от важните характеристики на структурите от данни са:
Класификация на структурите от данни
Структурата на данните предоставя структуриран набор от променливи, свързани една с друга по различни начини. Той формира основата на инструмент за програмиране, който обозначава връзката между елементите на данните и позволява на програмистите да обработват данните ефективно.
Можем да класифицираме структурите от данни в две категории:
- Примитивна структура на данните
- Непримитивна структура на данните
Следващата фигура показва различните класификации на структурите от данни.
карта на reactjs
Фигура 2: Класификации на структурите от данни
Примитивни структури от данни
- Тези структури от данни могат да бъдат манипулирани или управлявани директно от инструкции на ниво машина.
- Основни типове данни като Цяло число, плаващо число, знак , и Булева стойност попадат под примитивните структури от данни.
- Тези типове данни също се наричат Прости типове данни , тъй като съдържат знаци, които не могат да бъдат разделени допълнително
Непримитивни структури от данни
- Тези структури от данни не могат да бъдат манипулирани или оперирани директно от инструкции на ниво машина.
- Фокусът на тези структури от данни е върху формирането на набор от елементи от данни, който е или хомогенен (същият тип данни) или разнородни (различни типове данни).
- Въз основа на структурата и подредбата на данните можем да разделим тези структури от данни на две подкатегории -
- Линейни структури от данни
- Нелинейни структури от данни
Линейни структури от данни
Структура от данни, която запазва линейна връзка между своите елементи от данни, е известна като линейна структура от данни. Подреждането на данните се извършва линейно, като всеки елемент се състои от наследници и предшественици, с изключение на първия и последния елемент на данните. Това обаче не е непременно вярно в случай на памет, тъй като подреждането може да не е последователно.
Въз основа на разпределението на паметта, линейните структури от данни се класифицират допълнително в два типа:
The Масив е най-добрият пример за статичната структура на данните, тъй като те имат фиксиран размер и данните му могат да бъдат модифицирани по-късно.
Свързани списъци, стекове , и Опашки са често срещани примери за динамични структури от данни
Типове линейни структури от данни
Следва списъкът с линейни структури от данни, които обикновено използваме:
1. Масиви
Ан Масив е структура от данни, използвана за събиране на множество елементи от данни от един и същи тип данни в една променлива. Вместо да съхраняваме множество стойности от едни и същи типове данни в отделни имена на променливи, можем да ги съхраняваме всички заедно в една променлива. Това твърдение не означава, че ще трябва да обединим всички стойности от един и същи тип данни във всяка програма в един масив от този тип данни. Но често ще има моменти, когато някои специфични променливи от едни и същи типове данни са свързани една с друга по начин, подходящ за масив.
Масивът е списък от елементи, където всеки елемент има уникално място в списъка. Елементите от данни на масива споделят едно и също име на променлива; всеки обаче носи различен индексен номер, наречен долен индекс. Имаме достъп до всеки елемент от данни от списъка с помощта на местоположението му в списъка. По този начин ключовата характеристика на масивите, която трябва да се разбере, е, че данните се съхраняват в съседни места в паметта, което прави възможно на потребителите да преминават през елементите с данни на масива, използвайки съответните им индекси.
Фигура 3. Масив
Масивите могат да бъдат класифицирани в различни типове:
Някои приложения на масива:
- Можем да съхраняваме списък с елементи от данни, принадлежащи към един и същ тип данни.
- Масивът действа като спомагателно хранилище за други структури от данни.
- Масивът също помага за съхраняване на елементи от данни на двоично дърво с фиксиран брой.
- Масивът също действа като хранилище на матрици.
2. Свързани списъци
А Свързан списък е друг пример за линейна структура от данни, използвана за динамично съхраняване на колекция от елементи от данни. Елементите от данни в тази структура от данни са представени от възлите, свързани чрез връзки или указатели. Всеки възел съдържа две полета, информационното поле се състои от действителните данни, а полето за указател се състои от адреса на следващите възли в списъка. Указателят на последния възел на свързания списък се състои от нулев указател, тъй като не сочи към нищо. За разлика от масивите, потребителят може динамично да регулира размера на свързания списък според изискванията.
Фигура 4. Свързан списък
кортеж за сортиране на python
Свързаните списъци могат да бъдат класифицирани в различни типове:
Някои приложения на свързани списъци:
- Свързаните списъци ни помагат да внедрим стекове, опашки, двоични дървета и графики с предварително определен размер.
- Можем също така да внедрим функцията на операционната система за динамично управление на паметта.
- Свързаните списъци също позволяват полиномна реализация за математически операции.
- Можем да използваме Circular Linked List за внедряване на операционни системи или функции на приложения, които изпълняват Round Robin задачи.
- Кръговият свързан списък също е полезен при слайдшоу, където потребителят изисква да се върне към първия слайд след представянето на последния слайд.
- Двойно свързаният списък се използва за внедряване на бутони напред и назад в браузър за придвижване напред и назад в отворените страници на уебсайт.
3. Купчини
А Стек е линейна структура на данните, която следва LIFO (Последен влязъл, първи излязъл) принцип, който позволява операции като вмъкване и изтриване от единия край на стека, т.е. отгоре. Стековете могат да бъдат реализирани с помощта на непрекъсната памет, масив, и несвързана памет, свързан списък. Примери за купища от реалния живот са купчини книги, тесте карти, купчини пари и много други.
Фигура 5. Пример за стек от реалния живот
Фигурата по-горе представлява пример от реалния живот на стек, където операциите се извършват само от единия край, като вмъкване и премахване на нови книги от горната част на стека. Това означава, че вмъкването и изтриването в стека може да се извърши само от върха на стека. Имаме достъп само до върховете на стека във всеки един момент.
Основните операции в стека са както следва:
Фигура 6. Купчина
Някои приложения на стекове:
- Стекът се използва като временна структура за съхранение за рекурсивни операции.
- Стекът също се използва като спомагателна структура за съхранение за извиквания на функции, вложени операции и отложени/отложени функции.
- Можем да управляваме извиквания на функции с помощта на Stacks.
- Стековете също се използват за оценка на аритметичните изрази в различни езици за програмиране.
- Стековете също са полезни при преобразуването на инфикс изрази в постфикс изрази.
- Стековете ни позволяват да проверим синтаксиса на израза в програмната среда.
- Можем да съпоставим скоби с помощта на Stacks.
- Стекове могат да се използват за обръщане на низ.
- Стековете са полезни при решаването на проблеми, базирани на обратно проследяване.
- Можем да използваме Stacks при търсене в дълбочина при обхождане на графика и дърво.
- Стековете се използват и във функциите на операционната система.
- Стековете също се използват във функции UNDO и REDO при редакция.
4. Опашки
А Опашка е линейна структура от данни, подобна на стек с някои ограничения върху вмъкването и изтриването на елементите. Вмъкването на елемент в опашката се извършва в единия край, а премахването се извършва в другия или срещуположния край. По този начин можем да заключим, че структурата на данните на Queue следва принципа FIFO (First In, First Out) за манипулиране на елементите от данни. Внедряването на опашки може да се извърши с помощта на масиви, свързани списъци или стекове. Някои реални примери за опашки са опашка пред гишето за билети, ескалатор, автомивка и много други.
Фигура 7. Пример за опашка от реалния живот
Изображението по-горе е реална илюстрация на гише за билети за кино, което може да ни помогне да разберем опашката, където клиентът, който дойде първи, винаги се обслужва първи. Клиентът, който пристига последен, несъмнено ще бъде обслужен последен. И двата края на опашката са отворени и могат да изпълняват различни операции. Друг пример е линия за хранене, където клиентът се вкарва от задния край, докато клиентът се отстранява отпред, след като предостави услугата, която е поискал.
Следните са основните операции на опашката:
какво е модуло в c++
Фигура 8. Опашка
Някои приложения на опашки:
- Опашките обикновено се използват в операцията за търсене в ширина в Graphs.
- Опашките се използват и в операциите на планировчика на задания на операционните системи, като опашка на буфер на клавиатура за съхраняване на клавишите, натиснати от потребителите, и опашка на буфер за печат за съхраняване на документите, отпечатани от принтера.
- Опашките са отговорни за планирането на процесора, планирането на задачите и планирането на диска.
- Приоритетните опашки се използват при операции за изтегляне на файлове в браузър.
- Опашките се използват и за прехвърляне на данни между периферни устройства и централния процесор.
- Опашките също са отговорни за обработката на прекъсвания, генерирани от потребителските приложения за процесора.
Нелинейни структури от данни
Нелинейните структури от данни са структури от данни, при които елементите от данни не са подредени в последователен ред. Тук вмъкването и премахването на данни не са осъществими по линеен начин. Съществува йерархична връзка между отделните елементи от данни.
Типове нелинейни структури от данни
Следва списъкът с нелинейни структури от данни, които обикновено използваме:
1. Дървета
Дървото е нелинейна структура от данни и йерархия, съдържаща колекция от възли, така че всеки възел на дървото съхранява стойност и списък с препратки към други възли („децата“).
Дървовидната структура на данни е специализиран метод за подреждане и събиране на данни в компютъра, за да се използват по-ефективно. Той съдържа централен възел, структурни възли и подвъзли, свързани чрез ръбове. Можем също да кажем, че структурата на данните на дървото се състои от свързани корени, клони и листа.
Фигура 9. Дърво
Дърветата могат да бъдат класифицирани в различни видове:
Някои приложения на дърветата:
- Дърветата прилагат йерархични структури в компютърни системи като директории и файлови системи.
- Дърветата също се използват за реализиране на навигационната структура на уебсайт.
- Можем да генерираме код като кода на Хъфман, използвайки дървета.
- Дърветата също са полезни при вземането на решения в приложенията за игри.
- Дърветата са отговорни за внедряването на приоритетни опашки за базирани на приоритет функции за планиране на OS.
- Дърветата също са отговорни за анализирането на изрази и изрази в компилаторите на различни езици за програмиране.
- Можем да използваме дървета за съхраняване на ключове за данни за индексиране за система за управление на бази данни (СУБД).
- Spanning Trees ни позволява да маршрутизираме решения в компютърни и комуникационни мрежи.
- Дърветата се използват и в алгоритъма за намиране на път, внедрен в приложенията за изкуствен интелект (AI), роботиката и видеоигрите.
2. Графики
Графиката е друг пример за нелинейна структура от данни, включваща краен брой възли или върхове и ръбовете, които ги свързват. Графиките се използват за справяне с проблеми в реалния свят, в който се обозначава проблемната област като мрежа като социални мрежи, верижни мрежи и телефонни мрежи. Например, възлите или върховете на Graph могат да представляват един потребител в телефонна мрежа, докато ръбовете представляват връзката между тях чрез телефон.
Структурата на данните на Graph, 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].
В зависимост от позицията на върховете и ръбовете, графите могат да бъдат класифицирани в различни типове:
Някои приложения на графиките:
- Графиките ни помагат да представяме маршрути и мрежи в приложения за транспорт, пътуване и комуникация.
- Графиките се използват за показване на маршрути в GPS.
- Графиките също ни помагат да представим взаимовръзките в социалните мрежи и други мрежови приложения.
- Графиките се използват в приложения за картографиране.
- Графиките са отговорни за представянето на потребителските предпочитания в приложенията за електронна търговия.
- Графиките се използват и в комуналните мрежи, за да се идентифицират проблемите, поставени пред местните или общинските корпорации.
- Графиките също помагат да се управлява използването и наличността на ресурси в една организация.
- Графиките се използват и за създаване на карти с връзки към документи на уебсайтовете, за да се покаже свързаността между страниците чрез хипервръзки.
- Графиките се използват и в роботизирани движения и невронни мрежи.
Основни операции на структурите от данни
В следващия раздел ще обсъдим различните типове операции, които можем да изпълняваме, за да манипулираме данни във всяка структура от данни:
- Време за компилиране
- Време за изпълнение
Например, на malloc() функция се използва в езика C за създаване на структура от данни.
Разбиране на абстрактния тип данни
Според Национален институт за стандарти и технологии (NIST) , структурата от данни е подреждане на информация, обикновено в паметта, за по-добра ефективност на алгоритъма. Структурите на данни включват свързани списъци, стекове, опашки, дървета и речници. Те могат да бъдат и теоретична единица, като името и адреса на човек.
От дефиницията, спомената по-горе, можем да заключим, че операциите в структурата на данните включват:
- Високо ниво на абстракции като добавяне или изтриване на елемент от списък.
- Търсене и сортиране на елемент в списък.
- Достъп до елемента с най-висок приоритет в списък.
Всеки път, когато структурата от данни извършва такива операции, тя е известна като an Абстрактен тип данни (ADT) .
Можем да го дефинираме като набор от елементи от данни заедно с операциите върху данните. Терминът „абстрактно“ се отнася до факта, че данните и основните операции, дефинирани върху тях, се изучават независимо от тяхното изпълнение. Това включва какво можем да направим с данните, а не как можем да го направим.
Реализацията на ADI съдържа структура за съхранение, за да съхранява елементите от данни и алгоритмите за фундаментална работа. Всички структури от данни, като масив, свързан списък, опашка, стек и т.н., са примери за ADT.
css за получер
Разбиране на предимствата от използването на ADT
В реалния свят програмите се развиват в резултат на нови ограничения или изисквания, така че модифицирането на програма обикновено изисква промяна в една или няколко структури от данни. Да предположим например, че искаме да вмъкнем ново поле в записа на служител, за да следим повече подробности за всеки служител. В такъв случай можем да подобрим ефективността на програмата, като заменим масив със свързана структура. В такава ситуация пренаписването на всяка процедура, която използва модифицираната структура, е неподходящо. Следователно, по-добра алтернатива е да се отдели структура от данни от информацията за нейното изпълнение. Това е принципът зад използването на абстрактни типове данни (ADT).
Някои приложения на структурите от данни
Следват някои приложения на структурите от данни:
- Структурите на данни помагат при организирането на данните в паметта на компютъра.
- Структурите на данни също помагат при представянето на информацията в базите данни.
- Структурите на данни позволяват внедряването на алгоритми за търсене в данни (например търсачка).
- Можем да използваме структурите на данни, за да внедрим алгоритмите за манипулиране на данни (например текстообработващи програми).
- Можем също така да внедрим алгоритмите за анализиране на данни с помощта на структури от данни (например копачи на данни).
- Структурите на данни поддържат алгоритми за генериране на данни (Например генератор на произволни числа).
- Структурите на данни също поддържат алгоритми за компресиране и декомпресиране на данните (Например помощна програма за zip).
- Можем също да използваме структури от данни, за да внедрим алгоритми за криптиране и декриптиране на данните (например система за сигурност).
- С помощта на структурите на данни можем да изградим софтуер, който може да управлява файлове и директории (например файлов мениджър).
- Можем също така да разработим софтуер, който може да визуализира графики с помощта на структури от данни. (Например уеб браузър или софтуер за 3D изобразяване).
Освен тези, както споменахме по-рано, има много други приложения на структурите от данни, които могат да ни помогнат да изградим всеки желан софтуер.