Структури от данни - същност и класификация


Категория на документа: Информатика


Тема 5
Структури от данни - същност и класификация. Стандартни структури от данни - масиви, низове, записи, множества. Рекурсивни алгоритми и структури от данни

Данните в програмите се съхраняват в променливи. Те се характеризитат с уникално име и тип на данните. Типът също се свърва с име от множество на допустими значения и операции извършвани в/у тези значения,следователно данните са тясно свързани с типа на данните в езиците на програмиране. Те са значенията който имат програмни променливи, те имат тип и определена форма. Тази форма ни позволява да определим типът на данните, а типът наданните, за да получим корекно значение. Структурата от данни се състои от елемент или елементи от данни и връзки м/у тях. В структури се обидиняват логически свързани помежду си данни. Със Структури от данни се свързват операции който са насочени към създаването им (конструктури), достъп до данните (селектори), модифициране на структурата им и знанията им (модификатори), преобразуването им (преобразоватори), и т.н. При езиците за програмиране, най-често декларацията играе роляна на конструктур на структурата от данни. Класификацията на структурата от данни може да се извърши по много признаци: 1)Видове структурата от данни в зависимост от типовете данни в езика за програмиране. В паскал: -прости(скаларни): цели(integer), реални(real), логически(boolean), символни(cmar), потребителски; -структурни: масив, запис, множество, символен низ(string), файл; -указателни Простите(имат едно значение) и структурните(имат много значения) типове от данни са стандартни. Посредством указателните и структурните типове от данни могът да се съсдадат потребителски типове от данни,към които се включват абстракните типове от данни. 2) В зависимост от логическата взаемовръзка м/у елементите структури от данни. Те се делят на: -линейни:мястото на елементите в тази структура е значимо. Те са подредени последователно, т.е. един след друг. Към тях спадат списаците, стековете, опашките, символните низове, масивите, зписите и файловете. -йерхични-характерно за тях е че м/у елементите им съществува съподчиненост (връзка родител-дете). Началото на всички операции е от корена. -Мрежови- характерно за тях е че м/у елементите им няма подреденост и йерария. -Множество-при него липсва връзка м/у елементите. Обидинението им се извършва на база на техните общи характеристики. Всеки елемент в множеството се идентифицира на база на ключови характеристики. Към тези СД се причисляват хеш-таблиците и множества като СД. 3) Според начина им на съхраняване СДСА: -вътрешни:съхраняват се в ОП докато се изпълнява програмата. -външни: съхраняват се във файл или файлове. 4)Според това, зали може да се променя броя на елементите им, размера и типа на елемента, СД са: -статични:масив, запис, символен низ, множество; -динамични:дърво, граф, стек, опашка, списък, динамичен масив и др. За реализация на динамичните СД се използват показатели. 5) В зависимост от това дали СД са независими от реализацията си, се делят на: -абстрактни СД; -Традиционни СД; 6)Рекурсивни и нерекурсивни и др. Признаци Стандартни структури от данни :масиви, множества, записи, файлове,низове. В езиците за програмиране освен пряко простите типове данни се използват и като елементарни градивни елементи, с които се конструират(дефинират) по-сложни типове, наречени основни(структурни) типове данни, като за тази цел съществуват специални механизми за структуриране на данните. Те са четири вида: масив, запис, множество, файл, низове. Структурираният тип се характеризира с известен брой компоненти от определен тип или типове, с начина на наредба, на структуриране на тези компоненти и с факта че има повече от една стойност. Ако типа на съставящите компоненти е структуриран, то в резултат се получава структуриран тип с повече от едно ниво на структуриране. Масиви: Чрез масивите се дефинира множество от компоненти, които имат един и същ тип и за които се определя линейна подредба. Затова се казва, че масивът е съвкупност от еднотипни елементи. Предварително трябва да се укаже броя на елементите и техния тип, като във всеки момент променливите от този тип могат да имат само по една стойност.Декларирането на масив става по следния начин: example : array [1..100] of integer; Където "example" е името, чрез което ще се обръщаме към масива; "array" е ключова дума за масив; [1..100] - началото и края на индекса на елементите и съответно броя им (в случая започва от 1 до 100, следователно имаме 100 елемента); "of integer" указва от какъв тип са елементите на самия масив.
Използването на масиви улеснява програмирането - еднакви по рода си променливи се обединяват под формата на една чрез масива (т.нар. съставна променлива). Достъпът до стойностите на отделните й компоненти се извършва с името й, като в квадратни скоби след него се добавя поредния номер на елемента от масива (например p:=example[12]; ще присвои на променливата р стойността на 12тия елемент на масива). В общия случай номерът на компонента от масива представлява стойност на израз и е прието да се нарича индекс. Ако при описанието на масива е зададен един индекс, то той се нарича едномерен(представят се вектори), ако са два - двумерен(матрици), ако са n - n мерен. Размерността се ограничава само от реалния обем ОП. Разликата при създаване на многомерни масиви се състои в това, че при декларирането им се указва последователност от индекси (p:array [1..10,1..10,1..5] of real; - създава тримерен масив с 10х10х5 елемента). Достъпът до съответните елементи се получава чрез изреждане на индексите - например p[3,3,4]. Тъй като елементи на един масив могат да бъдат от всеки допустим тип, за един масив може да се използва друг - масив от масиви. Елементите на масив се разполагат в последователни клетки от ОП. Елементите с по-малка стойност на индекса се разполагат в клетките с по-малки адреси. Многомерните масиви се разполагат така, че най-десния индекс да нараства най-бързо. Действията с масиви могат да са: "копиране" А:=С; т.е присвояване на всички елементи на масива С на съответните елементи на А, като стойностите на елементите в С остават непроменени. Индексираните елементи на масива се наричат "индексирани променливи" и могат да се използват в програмата както простите променливи. Въвеждането и извеждането на стойности в масив става поелементно, като за целта се използват цикли(FOR, REPEAT .. UNTIL, WILE .. DO) за обхождане на елементите му. Когато става дума за n-мерен масив, се налага използването съответно на n вложени цикъла за обхождане на всички индекси. Едни от най-важните задачи реализирани с масиви са търсенето и сортирането. Множества: Тип множество е линейна съвкупност от елементи със общи свойства. Между елементите няма никаква връзка, неподредено множество. Нямаме последователен достъп и цикличен достъп до всеки елемент. Типът множество определя съвкупността от всички подмножества на даден скаларен тип(базов). Това означава че всяка възможна стойност на типа множество може да съдържа нула или всички елементи на базовото множество. Формат: SET OF скаларен тип; Базовия тип не може да има повече от 256 възможни стойности и поредните номера трябва да са от 0 до 255. Поради тази причина базовият тип не може да бъде sortint; integer; longint; word. Всеки тип множество може да съдържа стойността [], която се нарича празно множество. Основните операции: -Принадлежност: <променлива от тип множество> IN <множество>; -Обединение: '+'; -Сечение: '*'; -Разлика: '-'; Запис: Предоставят се възможности за описание и опериране с обекти, съставени от няколко компонента, не непременно от един и същ тип. Това се извършва чрез типа запис. Дефинирането на тип запис започва със служебната дума RECORD и завършва с END, които играят ролята на операторни скоби, между които се изграждат елементите на записа, определени с техния тип. Елементите на записа се наричат негови полета.
TYPE
<име на типа>= RECORD

<име на полето> : <тип на полето>;

..............................

<име на полето> : <тип на полето>;
[CASE идентификатор на признак: идентификатор на скаларен тип) OF вариант;
END;
След като типа запис бъде дефиниран, трябва да се създаде променлива от този тип, с която да работим: VAR <име на променлива от тип запис> : <име на типа>;
Вариантната част на един тип запис позволява да се дефинира повече от един списък полета за този тип запис. Всеки списък за полета от тип запис е вариант. Вариантите от един тип запис се препокриват в паметта и могат да бъдат достъпни по всяко време. Всеки един вариант се определя от константа. Всяка константа трябва да се различава уникално от другите, да е от скаларен тип и съвместим с типа на полето за признака. Стойността на полето за признак определя коя вариантна част е активна в даден момент. При действията с цели записи единствената допустима операция е присвояването на една пром. на друга, при което двете променливи трябва да са еднотипни, т.е. броят и типът на полетата им да съвпадат. Достъпът(обръщението) до него става с т.нар. уточнено(съставно) име. То съдържа името на променливата от тип запис и името на полето в следния вид: <име на променлива от тип запис>.<име на полето> (например test.pole_1). Въвеждането и извеждането на запис се извършва поотделно(поелементно). Обръщението към поле на запис е неудобно, когато има множество полета. Оператора за колективна обработка на полета на запис WITH улеснява този процес. Веднъж указали името на променливата, можем да работим с нейните полета, указвайки само техните имена. WITH <променлива от тип запис> DO <оператор> Полетата на един запис могат да бъдат и от тип запис - получава се вложен запис. Достъпът до отделния елемент на масива става чрез индекс, а достъпа до отделните полета с уточнено име.Пр: Massp[i].name; Файлове: В практиката на програмирането често се срещат задачи, които боравят с голямо количество относително рядко променящи се данни. Въвеждането на цялото количество от данни от клавиатурата в ОП при всяко ново изпълнение на една такава програма е немислимо. За решаването на този проблем се реализира концепцията на файловете, която позволява информацията въведена от клавиатурата или получена в хода на изпълнение на програмата, да бъде трайно съхранена върху магнитен носител(диск или дискета) и да бъде прочетена оттам впоследствие, когато е нужно на работещата програма да извлича данни. Файлът е структуриран тип данни, разположени върху външно запомнящо устройство. Той е последователност от компоненти от един и същи тип(базов). Дефинирането на типа файл започва със служебната дума FILE OF, след което се задава типа на компонентите на файла. Броят на компонентите-т.нар. дължина на файла - не се фиксира предварително.
TYPE

<име на типа>= FILE OF <тип на компонентите>;
VAR <име на променлива от тип файл> : <име на типа>;

За дефинирането на файлове, чиито компоненти са от тип RECORD:

TYPE <тип на компонентите> = RECORD

<име на поле> : <тип на поле>;

................................................

<име на поле> : <тип на поле>;
END;
VAR F: FILE OF <тип на компонентите>; {пром. от тип файл} R: <тип на компонентите>;{пром от тип запис} Променливите от тип файл не могат да участват в изрази в програмата. Файловете се извикват в ОП само когато това е необходимо. След края на всички компоменти на файла се записва "край на фаил" (EOF - End Of File). Файлът може да бъде : "отворен / затворен за запис" "отворен / затворен за четене" "отворен / затворен за четене и запис". Променливата от тип файл съществува само в програмата(нарича се вътрешен файл). На нея може да се съпостави "външен файл" - файл върху диска. 1. Свързване. чрез оператора ASSIGN(F,S) , където F е името на вътрешния, а S - стринг задаващ името на външния файл 2. Отваряне на файл. оператор: "openf(f, filename, mode);" където f е името на декларираната променлива от тип файл, filename е стринга, задаващ име на външния файл, а за mode се избира "r"(read), "w"(write) или "a"(append) в зависимост от операциите, които ще се извършват. Оператора: rewrite(f), чрез който всички компоненти на файла(ако такива съществуват) се унищожават, 3. Запис във файл. Възможно е само когато файлът е отворен за запис и главата за четене/запис на дисковото устройство(указател на файла) е позиционирана върху признака за край на файл.

оператора:WRITE(F, A); 4. Затваряне на файл. оператора: CLOSE(F); 5. Четене от файл. възможна е само тогава, когато файлът е отворен за четене и указателят сочи някой от компонентите на файла. оператора: READ(F, A); променливата А ще получи стойността на тази компонента на файла, върху началото на която е бил позициониран указателят. След изпълнението на оператора, указателят ще сочи началото на следващата компонента, а ако следващата компонента няма - то той ще сочи признака за край на файла. -отваряне на файл за четене(подготовка за четене от началото на файла) Ако файлът не е празен, то след изпълнението на оператора : RESET(F) указателят ще сочи началото на първата компонента на файла. Ако файлът е празен, то указателят ще сочи признака за край на файла, който ще бъде разположен в самото начало на файла. Ако върху диска не съществува външен файл, с името, зададено в оператор ASSIGN, то при изпълнението на RESET(F) ще се изведе съобщение за В/И грешка и при изпълнението на програмата ще се преустанови. 6.Разпознаване на край на файл. Булевата функция EOF(F) има стойност TRUE <=> е достигнат краят на файла. Има още една възможност за достъп до компонентите на файл.- т.нар. пряк(директен) достъп. Файла е наредена последователност от еднотипни компоненти. Тези компоненти имат поредни номера 0,1,2.3... и чрез оператора SEEK(F, N); указателят се позиционира в началото на компонентата, с номер N. Ако броят на компонентите на файла е N, то при изпълнението на оператора: SEEK(F,N) указателят ще бъде позициониран върху признака за край на файла и булевата функция EOF(F) ще бъде TRUE. За организиране на пряк достъп до компонентите на файл се използват две функции FILESIZE(F) и FILEPOS(F). Първата дава броя на компонентите на файла, а втората дава поредния номер на тази компонента от файла F. Текстовите файлове, които най-често използваме, са стандартния входен файл input(отваря се за четене-клавиатура) и изходния output(отваря се за извеждане-монитор). Четенето на записи става с read(част от ред) и readln(цял ред). При извикване на writeln той се въвежда автоматично. Проверката за това дали е завършил реда става с булевата функция eoln(True за да/False за не) а за край на файла eof(f); Извеждането на записи от файл става чрез write(f, E1,...,En) и подобната и writeln... Отварянето на текстовите файлове за първоначално създаване се извършва с процедурата rewrite(f), а добавянето на ред към края на файла става с процедурата Append(var f:text). Низове: Едномерни масиви , елементите, на които са от тип символен. Отбелязват се като тип STRING и имат максимална дължина 255 символа.В ОП се представят като едномерни масиви като в нулевият елемент се посочва текущата дължина на символния низ. 1)Присвояване на значения,запис с оператор VSTR:='....'; 2)Селектор, достъп до символния низ с оператор: VSTR[]
3)Обидинение на СН с оператор: VSTR:= VSTR+' niz'; 4)Нулиране на СН с оператор: VSTR:='' 5)Сравнение на СН с оператор: Vb:=VS+R=/>=/<=VS+R 6)Четене и писане на СН с оператор: Readln(VS+R); и Writeln(VS+R);Оператори за обработка на СН, реализирани като стадартни функции. 1)дава текуща дължина на СН, която се задава като нейн аргумент: f length(vs:STING):integer; 2)Обидиняване на СН: f concat (S1[S2,...]:STING): STING; 3)Копиране на подниз от низ: f COPY (VSTR:string; POZ:integer; dpodniz:integer):string 4)изтрване на част от низ: DELETE(VAR S:string; POZ:integer; Duljina:integer); 5)Вмъкване на низ в друг низ от зададена позиция: P insert(iztochnik:string; Poz:integer; VAR S: string);
6)Проверка дали един низ е подниз на друг-това е функция която връща позицията от която започва първият низ във втория, в противен случеи резултатът е 0: f POS (S1,S:STRING):byte;
Рекурсивни алгоритми.Структури от данни. Един обект е рекурсивен ако той частично се съдържа в себе си или е дефиниран в себе си.Мощността на рекурсията е възможността и за дефиниране на безкрайно множество обекти, чрез безкраен брой команди. Една рекурсия на програма Р може да се дефинира: Р=po[Si,P] Рекурсивна структура от данни е тази която се дефинира чрез обращение към себе си. При дефиниране на РСД в езиците за прогамиране се използват рекурсивни типове от данни реализирани чрез оказатели. Това показва, че РСД са динамични по своя характер. Аналогично на рекурсивните алгоритми, при тях може да има пряка или не пряка рекурсия.Динамичните СД са свързани с динамичната памет(heap).

??

??

??

??





Сподели линка с приятел:





Яндекс.Метрика
Структури от данни - същност и класификация 9 out of 10 based on 2 ratings. 2 user reviews.