Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Примери за класификация и структура на данните

Както следва от горната дефиниция, структурирането на данни предполага съществуването (или установяването) на някакъв вид връзка (връзка) между тях. В зависимост от естеството на тези взаимоотношения, съществуват няколко класификационни атрибути на структурите за данни.

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

В подредените структури елементите са подредени в съответствие със стойността на дадена характеристика. Най-простата характеристика е поредният номер на елемента: установяването на ред в съответствие с номера се нарича номериране. Освен това, ако целият комплект има един общ идентификатор (например М), тогава на индивидуалните данни се присвояват собствени идентификатори - индекси (например М5 или Мб). Най-често индексът се дава като цяло число, въпреки че това не е задължително - всеки символ от крайната азбука може да действа като индекс. Лексикографският ред на индексите определя връзката между елементите на структурата, т.е. елементът М 6 следва елемента М5, а елементът М а е разположен пред елемента МЬ. Пример за структури, в които се извършва подреждане чрез номер на елемент, са масиви. Последователният номер на даден елемент може да се счита за външна функция, която може да бъде присвоена на елемент, независимо от неговата стойност. Например регистрационният номер на документ се определя само от момента, в който той пристигне в институцията, а не от съдържанието му. Освен номерирането, структурите от данни използват подреждане по стойност на дадена вътрешна характеристика, например поставяне на имена по азбучен ред или група предприятия в низходящ ред на тяхната рентабилност - това нареждане се нарича класиране.

Пример за неподредени структури са множества, в тях не е дефиниран редът на елементите; единственото нещо, което може да бъде зададено за всяка конкретна информация, е тяхната принадлежност (или непринадлежност) към избрания набор.

Следващата класификационна характеристика на структурата е хомогенността. Хомогенните включват структури, съдържащи елементарни данни само от един тип. Хетерогенните структури съчетават данни от различни типове. Примери за хомогенни структури са масиви, комплекти, стекове. За хетерогенните структури са записите.

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

В линейните структури всички елементи са равни. Те включват масив, набор, стак, опашка.

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

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

масив

Масивът е подреден линеен набор от хомогенни данни.

Коментари относно определението:

• Терминът „поръчано“ означава, че елементите на масива са номерирани;

· Терминът "линеен" означава равенство на всички елементи;

Терминът "хомогенен" означава следното: в случай, когато масив е формиран от елементарни данни, той може да бъде данни само от един тип, например масив от числа или масив от символи; Възможно е обаче елементите на масива да бъдат сложни (структурни) данни, например масив от масиви - в този случай, "хомогенни" означава, че всички елементи имат еднаква структура и размер.

Броят на индексите, определящи позицията на даден елемент в масив, се нарича размерност на масива.

Така че, ако индексът е уникален, масивът се нарича едноизмерен; често такъв масив се нарича още вектор, ред или колона. За да се запишат елементи от едномерен масив, се използва обозначението i ; в езиците за програмиране се приемат символите m (i) или m [i].

Масив, чиито елементи имат два индекса, се нарича двуизмерен или матричен. Пример за обозначение: G [3,5]; докато първият индекс е номерът на реда, а вторият индекс е номерът на колоната в пресечната точка, на която се намира този елемент.

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

Максималната стойност на индексите определя размера на масива. Размерът на масива е посочен в блока за описание на програмата, тъй като по време на изпълнението на програмата необходимото количество памет е запазено за съхранението на елементите на масива. Ако по време на изпълнението на програмата размерът на масива не се промени (или не може да се промени), тогава в този случай се говори за масиви с фиксиран размер; ако определянето на размера на масива или тяхната промяна се случи в хода на програмата, тогава такива масиви се наричат динамични (динамично описани).

Допустимият набор от операции върху елементите на масив се определя от вида на данните (елементарни или структурирани), от които се формира масивът. В някои програмни езици, в масива като цяло, операцията по присвояване М е дефинирана: = <expression> - в този случай на всички елементи на масива се присвоява същата стойност, равна на изчислената стойност на израза; операция по присвояване е възможна и за два масива от един и същи тип, размер и размер M2: = M1 - стойностите са елементно разпределени (M2 (i, j, k ...): = M1 (i, j, k ...)).

Специално място заемат символни масиви - те се наричат низове или низ (например String в PASCAL). С тях е възможен цял набор от операции, които не са дефинирани за единични данни. На първо място, това е операцията на конкатенация (обединение) на низове с образуването на нов низ. Освен това има операции по подмяна на част от низа, както и определяне на нейните числени характеристики.

Стек, завой

Стекът (магазина) и опашката са подредени, линейни, нееднородни структури. Тези структури се изпълняват под формата на специално организирани зони на компютърна оперативна памет или като независими блокове памет. В стека, клетките на паметта (или регистрите на паметта на стека) са свързани помежду си по такъв начин, че когато данните се въвеждат в първата клетка, съдържанието на всички останали се измества към следващите надолу, и когато се чете, съдържанието се измества нагоре през клетките, както е показано на фиг. 6.2. С други думи, влизането в стека е възможно само през първата клетка (горната част на стека), така че първата въведена последна информация ще бъде извлечена първо, като пътник на пренаселен автобус.

* Често стакът се нарича LIFO тип памет ( L ast- I n F irst- O ut: “последно в, първо излизане”).

Единствената разлика между опашката и стека е, че информацията се извлича по реда „първи в, първи изход“, т.е. от дъното на стека.

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

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

дърво

Дърво или йерархия е пример за нелинейна структура. В него елементът на всяко ниво (с изключение на най-високия) е включен в един и само един елемент на следващото (по-високо) ниво. Елементът на най-високото ниво се нарича корен, а най-ниското ниво се нарича листа.

Схемата на такава структура е показана на фигурата. Отделните елементи могат да бъдат хомогенни или не. Пример за такава организация са файловите структури на външни устройства за съхранение на компютър.

граф

Често връзките между данните са представени като графика - колекция от точки и линии, в която всяка линия свързва две точки. В компютърната наука, точка придобива значението на елемент от структура (система, данни и т.н.) и линии, значението на връзката между елементите. Да се ​​запознаем с редица термини, свързани с използването на графики.

Точките се наричат върхове на графиката, линии - ръбове. Ако един ръб свързва два върха, те казват, че ръбът е инцидентен към тези върхове, а самите върхове се наричат съседни. Броят на ръбовете, инцидентни на връх, се нарича степен на върха. Ако две ръбове са инцидентни към една и съща двойка върхове, те се наричат кратни. Ръбът, в който двата върха съвпадат, се нарича цикъл.

На фиг. 6.3, a. графиката 1 се определя от списъка на върховете {1,2,3,4} и списъка на ръбовете, в който за всеки ръб посочваме чифт върхове, които са инцидентни на него: a (1,2); b (1,4); c (2, .4); 6 (2.3); e (3.4); f (2,3); g (4.4).

Съседните двойки върхове: (2,3), (2,4), (1,2), (1,4), (3,4). Rib d е линия; краища d и f са кратни. Степените на върховете 2 и 4 са 4; пикове 3 -3; върхове 1 - 2 .

Ръбът, свързващ върховете, може да има посока - тогава той се нарича ориентиран и се представя със стрелка. Графиката, в която всички ръбове са ориентирани, се нарича ориентирана; Ръбовете му често се наричат дъги. Дъгите се наричат кратни, ако свързват същите върхове и съвпадат по посока. При маркиране на дъга върхът винаги се посочва първо, от който започва, например на фиг. 6.3, б (2, 3).

Маршрутът е поредица от ръбове, в които краят на предишния ръб съвпада с началото на следващия, например a , c, e на колона 1. Маршрут, в който крайният връх съвпада с първоначалния, се нарича цикъл, например c , e, d на колона 2 Графиката се нарича свързана, ако има маршрут между две от неговите върхове. Свързан граф с n върхове съдържа поне n −1 краища.

Според класификацията, разгледана по-рано, графиката е подредена, нелинейна, нехомогенна структура. Концепцията за графика, поради нейната яснота и висока общност в компютърните науки, действа като основно средство за описване на структури от данни, системи и реда на предприетите действия. Пример за това е блокова диаграма на програмата.

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

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





Вижте също:

Ентропийни свойства

Дефиниране на обект

Проблем на алгоритмичната разрешимост

Дискретни устройства без памет

Ефектът от шума върху честотната лента на канала

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru