ГЛАВА  ТРЕТА  -  СТРУКТУРИ ОТ ДАННИ

 

3.1. Данни. Величини. Понятие за структура от данни

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

Ако за решаване на задачата се използва компютър, моделът се описва с алгоритми и данни. При обработката на информацията се разграничават две основни страни на обработката: обект на обработ­ката (данна) и процедура на обработката (алгоритъм). Според швейцарският професор Н. Уирт структурата от данни и алгоритъма са основните елементи на всяка компютърна програма. Изборът на структурата от данни и съставянето на алгоритми за тяхната обработка ни дава ключа, за да проверим дали програмата прави точно това, за което е създадена.

Термините “информация” и “данни” са тясно свързани. Трябва да се отчете факта, че данната е категория на информацията. Съществуват различни определения за понятието данна. Данна е систематизирана информация във вид удобен за обработка с компютър; данните носят конкретна информация за конкретен обект; информацията, която е достъпна за приемане и обработка от компютъра е абстрактно отражение на реалния свят и се нарича данна. Анализът на цитираните определения за понятието “данна” дава основание да препоръчаме следното определение: данните са систематизирана информация във вид удобен за обработка с помощта на компютър. Понятието данна е тясно свързано с понятието величина. Величина е абстрактен информационен обект, основно средство за изразяване на определени свойства на реалния свят. Данната може да се разглежда като стойност на величината. Едно от средствата, предвидени от почти всички езици за програмиране, е възможността да се прави обръщение към величините с помощта на име (наречено още идентификатор). За имена на величини се използват букви, а понякога и цифри – . Някои от величините са константи. Те имат една и съща стойност в рамките на конкретна програма, в която са дефинирани. Известно е, че числото  съдържа стойността 3,14159. Други величини с имена са променливи. Те могат да променят стойността си в рамките на програмата.

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

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

Под структура от данни се разбира организирана информация, която може да бъде описана, създадена и обработена с помощта на програма.

В най-елементарен вид структурността на данните е дадена в организацията на оперативната памет на компютъра (разделена на байтове и машинни думи) и наличие на типове в езиците за програмиране. Средствата на езика за програмиране, които служат за представяне на съвкупност от сведения, се наричат структура от данни. Данните винаги имат структура, която се нарича формат. Освен това данните винаги се пазят в структури от данни. Eто защо между тях има хоризонтални и вертикални връзки. Структурите от данни и алгоритмите образуват програмите. Регистрите и думите от оперативната памет образуват структурите от данни. Алгоритмите, във вид на правила, заложени в компютъра, интерпретират и обработват данните. Всеки компютър може да работи само с един вид данни - отделни типове и може да въздейства върху тях в съответствие с единна система от алгоритми - инструкциите на централния процесор.

Задачите, които хората решават с помощта на компютъра, рядко се изразяват в битове. Данните са най-често във формата на числа, знаци, текстове, събития, символи и по-сложни структури, а алгоритмите са разнообразни и зависят от конкретната задача. Въпросът е: как компютърът може да решава задача от обширен спектър, като винаги работи с фиксирани правила? Обяснението идва от това, че компютърът е универсално устройство, чиято природа може напълно да се трансформира от зададената му програма. Основните архитектурни принципи са формулирани от Джон фон Нойман. В определен момент потокът от информация представлява данни, обработвани от програма, а в следващия момент същата информация се интерпретира като програма. Ето защо една програма най-напред се формулира в термините на познати понятия, а след това друга програма, наречена компилатор, пренася тези понятия към намиращите се в компютъра устройства, по такъв начин става възможно да бъдат конструирани системи с всякаква сложност. Програмистът създава йерархия от абстракции, първоначално разглежда програмата в най-общ вид, а след това се занимава с всяка нейна част, като не обръща внимание на вътрешните подробности на останалите части. Процесът на абстрахиране не се използва само за удобство. Той е необходим, защото не е възможно да се създадат сравнително големи програми, ако трябва да се работи върху тях като върху неделима хомогенна маса от битове. Без абстрахиране на високо ниво програмата не би могла да бъде разбрана дори от създателя си.

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

 

3.2. Тип на данните

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

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

В някои езици за програмиране компютърът прави своя извод за типа на константата или променливата по начина, който е записана присвоената стойност, наличието на десетичната точка. Други езици изискват от програмата явно да задава типа на всяка променлива. Явното деклариране на типовете на данните може да изглежда излишно, като знаем, че може да бъде избегнато, но то дава едно важно предимство. Въпреки, че стойността на една променлива по време на изпълнението на програмата евентуално се мени, нейният тип никога не се мени, следователно компютърът може да не прави проверка и да се увери, че операциите с тази променлива не са в противоречие с нейния декларативен тип. Такава проверка за непротиворечивост е осъществи­ма чрез анализ на текста на програмата, който остава в сила за всички възможни пресмятания, извършвани от програмата. За разлика от този анализ “пробното пускане” на компилираната програма може да провери само дали нейната работа е правилна за конкретните избрани входни стойности.

Понятието “тип на данните” е разширено главно посредством езика за програмиране Pascal и сега обхваща и описанието на структури от данни. Всяка структурна променлива съдържа няколко елемента, но към нея се обръщаме като към цяло. В календара, например, трябва да имаме възможност да посочим конкретна дата, но ни е необходим и начин за посочване на месеци и години. Декларирането на типа структурна променлива задава броя на елементите, които образуват променливата и дава възможност на компютъра да задели необходи­мата памет, показва и как да бъде осигурен достъп до тези елементи.

Типовете данни са обособени в три групи:

-       скаларни (прости);

-       структурирани;

-       указатели.

  Към простите типове данни се отнасят:

-       целочислен;

-       реален;

-       символен;

-       булев.

  Данните от този тип се характеризират с това, че:

-       променливите и изразите могат да бъдат сравнявани с операциите за сравнение;

-       при извикване на функциите могат да върнат стойности от скаларен тип.

Простите типове данни са подредени и изброими, което е важна тяхна характеристика. Изключение прави реалния тип данни, който не е изброим.

Стандартният тип данни е предварително (системно) определен, но смисълът на определящата го стандартна дума може да бъде променен в рамките на всякаква конкретна програма.

 

3.3. Прости типове данни

 

Целочислен тип на данните (INTEGER)

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

 

Реален тип на данните (REAL)

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

 

Символен тип на данните (CHAR)

Стойностите на променлива от символен тип представляват крайно и подредено множество от символи. Символите от това множество се наричат символни константи. Променлива с множество от допустими стойности символи, се нарича символна променлива. За различните версии на езика за програмиране Pascal съществуват различни множества от допустими знаци. Често се срещат и използват два вида символи - графични и управляващи. Графичните символи имат графично представяне. Означават се, като символът се огражда с апостроф - ’А’, ’9’, ’+’, ’0’, ’?’. Управляващите символи се въвеждат и съхраняват в паметта на компютъра, но нямат графично представяне във вид на един символ.

  На всеки символ от множеството на тип CHAR е поставено цяло число от 0 до 255, наречено код. Най-често използваният код е ASCII (American Standard Code for Information Interchange), създаден в САЩ и станал световен стандарт.

 

Представяне на символите в различни бройни системи

Числовото представяне на символите в паметта на компютъра улеснява операциите с променливи от тип CHAR. Например сравняването на две символни стойности. Изразът ’а’ >= ’А’ се преобразува в паметта на компютъра в израза 97 >= 65. На всеки символ съответства представяне в двоична и шестнадесетична бройна система. Обобщено ASCII кодът съдържа група от символи, които имат следните десетични представяния.

 

Управляващите символи са функционални кодове, които намират приложение при трансформирането на данни, както и при устройствата за вход и изход.

 

3.4. Структурни типове данни

 

Масив (ARRAY)

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

 

Позицията на всеки елемент от таблицата (2) е определена от номер на ред и номер на колона, в която е разположен елемента. Например елемент от ред 2 и колона 3 е 3 и т.н. Числова таблица (2) е прието да се нарича матрица, а в езиците за програмиране – двумерен числов масив. Двумерният числов масив се използва най-често за съхраняване на данни върху запомнящото устройство на компютрите (фиг. 3.1). Когато дължината на стълба или реда m е известна, то за съхраняването на елемента A[i,j] трябва да се определи мястото му върху записващото устройство като се използва израза:

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

Масиви, чиито елементи са определени от един, два и т.н. индекси, се наричат едномерни, двумерни и т.н. n-мерни масиви.

Освен числови, масивите могат да бъдат и друг тип - например масив от текстов тип. Той е двумерен и има два реда и три колони.

 

 

 

Основни операции в масивите са търсене и сортиране на елементите в масива. Сортирането се извършва чрез селекция, размяна и вмъкване. Използват се още методи на бързо сортиране, пирамидално сортиране и др. Отделните елементи на масива са еднакво достъпни.

 

Запис (RECORD)

В програмите често се налага да се съхранява информация за някакъв обект, който съдържа данни от различен тип. Например обекта “личен автомобил” съдържа следните данни: регистрационен номер, собственик, година на производство и цена. Тези данни са важни и характеризират дадения обект. Възможен начин за обработка на голям брой данни, например за личните автомобили, е записването на данните в структурата масив. Данните за личните автомобили не могат да се запишат в масив, тъй като са разнородни, т.е. от различен тип. Те съдържат символен тип за името на собственика, целочислен тип за година на производство и реален тип за цената и буквено-цифрени данни за регистрационния номер. В случая се използва друга статична структура - запис.

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

Структурата запис може да се разгледа със следния пример:

 

Регистрац. N:

Собственик

Год. на производство

Цена

С 1584

Иван Петров

1995

683400.00

В 5047

Никола Даскалов

1992

734238,40

Н 6382

Христо Петров

1996

361000.00

 

Един ред на таблицата съответства на запис. Записът се състои от четири полета с различен тип данни. Полето с име “Регистрационен номер” има буквено-цифрово съдържание. Полето с име “Собственик” има символен тип данни. Полето с име “Година на производство” има целочислен тип данни. Полето с име “Цена” има реален тип данни.

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

Структурата “запис” е съставна структура от данни и показва:

-                    как от стойностите на отделните типове се изгражда съставна стойност;

-                    как от стойностите на съответните типове могат да се извличат стойностите от изграждащите го типове.

Достъпът до полетата се извършва чрез името на полето.

 

Файл (FILE)

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

Файлът може да бъде всякакъв вид информация - от документ, създаден от текстов редактор, до изходния код на някаква програма. Обикновено файлът се съхранява във външната памет на компютъра - твърд диск, дискета, CD-ROM устройство. При необходимост файлът се копира в оперативната памет за обработка. Най-често елементите на файла са от тип запис.

Файловете се съхраняват във външната памет на компютъра и образуват съвкупност, която се нарича директория или папка. Всяка операционна система за компютъра има създадени собствени правила за вида на имената на файловете с цел оформяне на директория (папка).

Файлът е основна структура от данни в програмирането и е предназначена за:

- съхраняване на програми. Файловете съхраняват програмата или компилираната програма, когато тя не се изпълнява.

- съхраняване на данни. Файловете съхраняват данните за дадена програма, когато тя не се изпълнява.

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

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

- пренасочване на изход. Вместо на екран или принтер изходната информация може да се запише във файл.

Използват се два основни вида файлове:

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

- Текстов файл. За разлика от двоичните файлове, текстовите могат да бъдат директно обработ­вани от входно-изходните устройства за текстова информация, като принтер или монитор; могат да бъдат обработвани от текстообработващи програми. Обменът на данни между клавиатурата на компютъра, екрана на монитора и печатащото устройство, от една страна, и оперативната памет, от друга страна, става чрез текстовите файлове.

Операциите, които се извършват с файлове са: отваряне на файл за четене и запис; четене на елемент; запис на елемент и затваряне на файл. Освен горните операции се използва операцията изтриване на елемент от файла или обхождане на файла с цел намиране на даден елемент.

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

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

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

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

Начинът, по който се търсят записи във файла определя методът на достъп: последователен или достъп чрез ключ.

Управлението на файловете се извършва от специална система, наричана файлова система. Всяка файлова система включва ядро от основни операции и набор от различни методи за достъп.

 

 

 

Въпроси за самоподготовка.

 

1. Какво е определението за данна и величина?

 

2. Видове типове данни и обща характеристика?

 

3. Характеризирайте накрако  типовете данни  “масив” и “запис”?

 

4. Какво наричаме файл и какво е неговото предназначение?