1. Основните типове данни char, int, float, double, типа void и ф-ционалния тип. Тези типове са предварително деф в езика и се поддържат от неговото ядро. Чрез аритметичните типове int, car float и double се представят числени данни. Тези типове могат да се използват в комбинация с някои модофикатори signed, unsigned, short и long, които определят техните аспекти. При използването на тези модофикатори името на типа може да бъде пропуснато, кото подразбиращият се тип в този случаи е типа int. Типът void има смисъл на неопределен тип, а ф-ционалният тип се използва за представяне на данни, които се интерпретират като ф-ция или като начални адреси на ф-ции. Променливите типове данни са данни, чиято стойност може да се промея по време на изпълнение на програмата. Променливите имат три х-ристики: тип, име и стойност. Предо да бъдат използвани те трябва да бъдат деф. Общият бид на това е: <тип> <име на променлива> [= <стойност>]; задължителните елем на деф от типа и името на променливата. Деф на променливи може да бъде съпроводено от инициализацията, т.е. Задаване на начална стойност. В основата на действие на рс лежи използването на двоичната бройна с-ма, т.е. Използването на 0 и 1. Това е така, т.к. CPU на РС разпознава само два вида импулси единият от който е на високо ниво на напрежение, а другият на наниско ниво на напрежение. Високото ниво на напрежение се приема за логическа единица, а ниското за нула. 1-цата и 0-та се използват в различна комбинация. 10чната бр с-ма се изпозва в ежедневната работа и класическата математика. Тя изпозва десет цифри от 0 до 9. 2чната бр с-ма използва само две цифри за да представи всички възможни числа. Тези цифри са 0 и 1. Пример за това е 0101000101. Много важно нещо, което трябва да се има предвид е ролята на цифрата 0. Всяка бр с-ма използва тази цифра. Трябва да се забележи, че всеки път когато цифрата 0 се появява в лявата част на поредицата от цифри, тя може да се добави и премахне без да се промени числото. Наприм при 10чната бр с-ма, числото 0927 = 927. При 2чната 00010101 = 10101. Някой хора добавят 0 в лявата част на дадено число за да запълнят местата и да подчертаят, че няма значещи цифри. Друга важна концепция е когато се работи с 2чни числа е че степента на числото 2^0 и 2^3 са примеро на числа представени чрез степен. Техните стойности са съответно 2^0=1 и 2^3=8. При 10чната бр с-ма също се ползват степени, но с основа 10. Напр 23605 => 2.10^4+3.10^3+6.10^2+0.10^1++5.10^0. Въпреки че имаме 0.10^1-0 това не означава, че трябва да пренебрегваме числото, а да го запазим. Ако го изхвърлим ще получим числото 2365, а то е грашно. Същия метод се използва при 2чната бр с-ма при степен с основа 2.

2. Масивът е стр-ра от данни, състояща се от множество последоватени наредени елем от един и същи тип, достъпът до който се осъществява чрез индекси.масивите могат да бъдат едномерни и многомерни, в зависимост от броя чрез които се адресира един елем. Съществура мног тясна връзка м/у масивите и един специален тип променливи, наречени указатели. Тази връзка се изразява във възможността достъпът до елем на масивите да се осъществява както чрез индекси, така и чрез указатели. Деф на един масив вкл типа на елем, името на масива и неговия размер. Памет се заделя по време на компилация, поради което техните размери трябва да бъдат const или const изрази. int x[10]; - това е едномерен масив с име x, състоящ се от 10 елем които са от тип int. Освен едномерни, масивите могат да бъдат и многомерни. При деф на многмерни масиви се задават техните размерности, които могат да бъдат, 2,3 или повече, адостъпът до отделните елем става ч/з съответния брой индекси. При работа с масив трябва да се има предвид, че компилатора не прави проверка дали стойностите на индексите, ч/з които се адресират елем, са в рамките на границите на масивите зададени в техните ф-ции. Това е лошо защото при допускане на грешка тя е труднооткриваема. Операциите вкл и изкл на елем в масива са недопустуми, т.е. масива е статична стр-ра от данни. Масива се разгл като крайна редица от елем от един и същ тип с пряк достъп до всеки елем, осъществява се ч/з индекс с цели стойности, започващи от 0 и нарастващи с 1 до указаната горна граница. Нека Т е име или деф на произволен тип, различен от псевдоним, void и ф-ционален. За типа Т и const израз от интегрален или от изборен тип с положителна стойност size, T[size] е тип масив от тип size елем от тип T. Елем се индексират от 0 до size-1. Т се нарича базов на типа, а size горна граница за типа. Множеството от стойности на типа Т[size] се състои от всички редици от по size елем, които са произволни const от типа Т. Достъпът до елем на редиците е пряк и се осъществява с помоща на индекс със стойност 0, до последния с индекс със стойност size-1, а до всеки от останалите елем с индекс със стойност 1 по-голяма от тази на индекса на предишния елем.

3. Единствения начин да извличем данни от стекове и опашки ч/р отраняване на елем.По-добре е да използваме всички данни, запазени в свързан списък,без непременно да отсраняваме елем от този списък. Нека разгл следните операции в/у такъв списък, добавяне на нов елем в неговия край ч/з ф-ция append, обхождане на списъл ч/з ф-циите iteraterStart и iterator, търсене на елем в списъка ч/з ф-циията find. Целият списък ще бъде изтрит от деструктор, когато вече не е необходим. Можем също да искаме да вмъкнем и изртиваме елем на списъка. Свързаните списъци ни позволяват да правим това по един ефективен начин. Вместо да пишем изцяло нов клас, ще използваме принципа на наследяване, за да създадем лесно нова прогр. Този клас ще е базов за един произволен клас, който има 3 ф-ции в допълнение към тези от неговия базов клас. Паметта на РС може да се разгл като много голям масив, ще използваме масив с фиксирана дължина и наш собсрвен преграмен код, за да заделим памет за свързан списък в този масив. Възлите от списъка ще бъдат елем на масива. Всеки от тях ще съдържа ноне next от int, което ще е стойността на индекса на възела, към който дадения възел сочи. Всички елем на масива, които не се използват в свързания списък, ще бъдат свързани заедно, образувайки друг свързан списък, известен като свободен. Двата списъка взаимно се допълват. Първоначално всички елем на масива принадлежат на свободния списък. Разполагането на възел води до преместването на елем от свободния в нашия потреб списък. Вместо указатели сега използваме цели числа, първият възел от потреб списък е сентинелът. Съхраняваме стойности на индексите, както и самия масив, като скрити полета от данни. Използването на целочислени стойности на индекси вместо указатели, като възлите са реализирани с елем на масив е приложима не само за свързани списъци, но 1 същ и за дървета и други стр-ри от данни. Едно предимство на този подход за реализацияна стр-рите от данние че можем лесно и ефективно да ги копираме не само в паметта но и във файлове. Недостатък е фиксираниятразмер на масива, вмъкването на нов елем е невъзможно, а масивът е пълен. Употребата на указатели ни се стурава по удобна, понеже така или иначе имаме нужда от указатели, за да бъде приложната прогр по-близка до това, с което сме свикнали. Обаче целочислените стойности на индексите имат предимството, че са свързани с началото на масива, докато указателите са абсолютни адреси. Често се налага да сорт свързан списък. Можем да преобразуваме несорт списък в сорт ч/з пренареждане на него-вате възли. Има дваначина единият е на базата на бързото сорт, а другиятна базата на сорт ч/з слизане. Бързото сорт построява две части- едната е елем/и, не по-големи от оста, а другата с елем/и, не по-малки от нея, след това също се прилага и към всяка от частите и накрая се долепят получените сорт части. Сорт ч/з сливане разделя цялата редица на две половини, след това същото се прилага към тези две подредици и накрая се сливат получените сорт подредици в една. Когато сорт масив, предпочита се бързото сорт, защото то не изисква никакъв допълнителен масив, както е при сорт ч/з сливане. Този недостатък на сорт ч/з сливане не важи за свързаните списъци, защото те са по-гъвкави от масивите преместването на елем от един списък в друг може да се извърши много ефективно, без никакви операции за разпределяне на памет. Що се отнася до оста, необходима при бързото сорт, в свързан списък не може да я намираме толкова ефективна, колкото в масив. По тези причини се предпочита сорт ч/з сливане.

4. Крайна, празна редица от символи, заградена в кавички, се нарича символиен низ, знаков низ или само низ. Броят на символите в редицата се нарича дължина на низа. Низ с дължина 0, се нарича празен. Низ, който се съдържа в даден низ, се нарича негов подниз. Конкатенация на два низа е низ, получен като в края на първия низ се запише втория или сенарича още слепване на низове. Сравняването на два низа става като се сравнява всеки символ от първия низ със символа от съответната позиция на втория низ. Сравняването продължава докато се намерят два различни символа или докрая на поне един от символните низове. Ако кодът на символите от първия низ е по-малък от съответния код на втория низ, то се приема, че първия низ е по-малък от втория и обратно. А когато при сравняването и двата низа са изчерпани, казва ме че те са равни. Този тип сравняване се нарича лексикографско. Символните низове могат да се предствят по два начина като едномерни масиви от символи char abc[100]; като се определи променливата abc като масив от 100 символа, и като указателикъм тип char:

char wav[s] = {`a`,`b`,`c`}; деф масива от символи wav и го инициализира. Т.к. се указани по-малко от 5 символа, останалите се попълават с нулевия символ, `` или char wav[5]={`a`,`b`,`c`,``,``}; Всички действия за работа с едномерен масив са валидни и за масиви от символи с изкл на извеждането, ще бъде езведено не цифра, а потока от текст. Низът се разгл като редица от символи, завършваща с нулевия символ , наречен знак за край на низ. Това помага, че не е необходимо с всеки низ да пази в отделна променлива дължината му, т.к. знака , позволява да се определи краят му. Типът char[size], където size е const с положителна стойност, може да бъде използван за задаване на тип низ с max дължина size-1. Множеството от стойности на типа низ char[size] се състои от всички низове с дължина 0,1,2,...,size-1, което е подмножество от стойности на типа char[size]. Всички елем от стойности на даден нис са const. Променлива величина, множоството от допустими стойносто на която съвпада с множеството стойности на даден низ е променлива на този низ. Сентинелът може да бъде полезен, когато извършваме последователно търсенев масив. int a[N], n, i,x; изпозват се само първите n елем. Ако искаш да претърсим елемза наличието на х сред тях, трябва да направим: a[n]=x; i=0; while (x!=a[i]) i++; Елем a[n] се използва като сентинен. Въпреки че в цикъла няма явна преверка дали i е по-малко от n, процесът на търсене ще завърши успешно. И в двата случия проверката дали х е намерен трябва да се направи след изпълнението на тези фрагменти. Използването на сентинел е особено елегантно, когато търсенето по разгл начин се прави с цел да се разположи стойността х в масива непосредствено след елем, които трябва да бъдат обходини, ако тази стойност не бъде намерена в процеса на търсене.

5. В информатиката стековете са полезни за много цели. Такъв стек е подобен на стек от ежедневието. Във всеки момент да добавяме нов обект на върха на стека и ако стекът не е празен, да остраняваме обекта, който е на върха. Действието добавяне чесо се нарича вкарване на елем с стек (push). Премахването на елем от стека се нарича изкарване (pop). След въвеждане на някакви цели числа следвани от нечислов символ, същите чиса се появяват на изхода в обратен ред, което е в съотвествие с принципа последен влязъл пръв излязъл LIFO. С принципа на капсулиране можем да реализираме стек като клас с член-ф-ция push и pop. С помоща на клас-шаблон нашият стек може да се използва не само за елементи от тип int, но и за елем от други типове. Операциите push и pop могат да се срещат в какъвто и да е ред. В много езици за програмиране, можем да използваме локални премонливи с ограничен обсег и продължителност на действие. Тогава генериращият код използва стек, така че най-късно въвежданите променливи изчезват първи. Всъщност този стек се използва не само за локални променливи, но и за други цели, като адрси към които трябва да се върне ф-ция след изпълнението си. За да представим елем на стек, вместо елем на масив можем да използваме записи, съдържащи указатели към други записи. Такъв списък от записи се нарича свързан списък, а записите възли или елем. Ако вмъкване и отстраняваме елем само от началото на списъка, имали друга реализация на стек, което можем да наречем свързан стек. Има единствен указател, който не е част от запис, той ще начало на свързания списък. Логически стъпки за образуване на стек: данните пристигат една по една. Алгоритъма държи началото на стека чрез променливата указател и трябва да добави новопристигаща данна. За да може данната да бъде записана в стека тя трябва да е записана като съдържанеи на елем на стека. Това изискава да бъде образуван да се впише в съответното поле. Новообразуваният елемент трябва да бъде контролиран адрес. Такава операция да се извърши с помоща на допълнителната променлива указател. Вкл на елем към стека новият елем се прикачва с каря си към първия елем към стека. След тази операция вече имаме достъп до стека. Указателя за началото на стека вече да бъде откачен от досекашния първи елем на стека и да започне да сочи там където е навият първи елем.

11. Абстрактната стр-ра дърво е граф. Теорията на графите е дял от съвременната математ, който продължава интензивно да се развива. Графите са абстрактни матем обекти. Граф се деф посредством две независими множества това на възлите и това на ребрата. 0На графичното изображение на граф, ребрата имат два края, като всеки край е възел, т.е. реброто се изразява с двойка възли. Нали-чието на ребро между два възела ги определя като съседни. От един възел до друг възел съществува път, ако в множеството на ребрата съществува такова подмн-ство от последователно преминаващи от възел на възел ребра, което позволява да се свържат тези два възела. Свързаността на възлите посредством ребра определя дали в един граф има свързани компоненти. Ако всички възли на графа са свързани помежду си с ребра, графът се нарича свързан. Дърветата са вид графи. Ето някой техни съществени свойства: дърветата са свързани графи; графът-дърво няма цикли; в дърветата има зависимост м/у броя на възлите и броя на ребрата, а именно броят на възлите е с единица по-голям от този на ребрата; в граф-дърво, от всеки възел до всеки възел има единствен път. Дърветата са добра абстракция за стр-ритане на данните, защото могат да бъдат представяне по-подреден начин, като кореново дървета. То има листа, стр-рата има нива и височина т.к. то има някаква долпълнителна стр-рираност. Под степен на възел се разбира броят на ребрата от даден възел към възлите от по-долното ниво, а под степен на дървото се разбира стента на възела с най-голяма степен. Ако възелът съдържа иказатели към други възли, за тези възли казваме, че са негови наследници или деца. Двоично дърво е кореново дърво от степен две. Наредено двоично дърво е такова дърво, за което има значение кое е ляво поддърво и кое дясно поддърво. Една от основните операции е обхождане на дървета. Обхождането на стек започва: ако не е празно началото, обхожда се напред и все напред, докато не се стигне края. За да се обходи дърво то трябва да бъде построено. Ще трябва да въведем помощен указател, които да обхожда възлите. Обхождането трябва да се основава на правило: да не прескочи някой възел, да не повтаря операцията с някой вече посетен възел. За да организираме п-са на обхождане, трябва да се възползваме от това че дървото е рекурсивен обект. Съществу-ват три рекурсивни схеми а обхождане инфиксна,префиксна и постфиксна. На едно от поле-тата с данни на възела често се гледа като на ключ, който се използва при операции за тър-сене. Ако във всеки възел има само едно полес данни,ще разгл тези полета като ключове. Вме-сто да опечатвам ключовете, които се съхраняват в дървото, можехме да обходим дървото по същия начин но за други цели. Т.к. коренът на всяко поддърво се посещава след всички възли от левото поддърво и преди тези от дясното поддърво, изра-зяваме този начин за обхождане на всички възли чрез понятието инфлексно обхождане, за наре-дената тройка, ляво поддърво, посетен възел, дясно поддърво или съкратено LVR. Други полезни начини за обхождане на възлите на двоично дърво на префиксно обхождане на VLR и суфиксно обхождане LRV. Тема-та за обхождането на двоично дърв е свързана с интерпрета-цията на аритметичните изрази.

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

8. При сорт ч/р пряка селекция броя на сравняванията не зависи от първоначалната наредба на елем. Това не е така при някой други методи за сорт. Следната редица има 12 елем или е с дължина n=12. 10 21 91 35 50 69 80 83 90 95100120 Елем 91 не е на мястото си. Ако започнем отляво на дясно да сравняваме всеки два елем и ги разменяме, когато левият е по-голям от десния, тогава 92 се разменя с 35, после с 50 и т.н., докато стигне до своята правилна позиция между 90 и 95. после ве всички елем са наредени в наразстваш ред. Ако се движим отляво на надясно и ако след размяната на елем на позиции к и к+1 не се извършва никакви размени по време на това обхождане всички елем на позии к+1,...,n-1 ще бъдат подредени, така че само елем на позиции 0,1,...,к могат все още да не бъдат на местата си. Този начин на сорт се метод на мехурчето. Тази ф-ция за сортиране работи добре за елем, които трябва да се преместят на голямо разстояние надясно. Нейното поведение не е толкова добро, ако елем трябва да се преместят на голямо разстояние наляво. Това асиметрично поведение може дас е избегне, ако местим елем ту наляво, ту надясно, запазвайки принципа на метода на мехурчето да разменя само съседни елем. Те и двата метода са устойчиви. Сорт чрез вмъкване е добър начален тласък за разработване на много бърз алгоритъм, известен като сорттировка на Шел. Последователно сорт всички елем, които са на разстояние h позиции един от друг, започвайки с голяма стойност на h позиции един от друг се нароча h-сорт. Този метод се основава на идеята, че първоначално когато h е голямо всяка редица, която трябва да сорт е малка докато по-късно, при малки стойности на h елем често ще бъдат вече подредени. Т.к. h постепенно намалява този метод се нарича още сорт ч/з вмъкване с намаляваща стъпка. Действието на алголитъма за сорт на Шел е значително по-добре отколкото на повечето други елемнтарни алгоритми за сорт. Той никога не извършва повече от nn на брой сравнения. Сорт на Шел също не е устойчиво на сорт.

7. За сорт използваме ф-ция-шаблон, която разменя местата на обектите x и y от даден тип само ако е в сила y>x. Ще сорт наредена двойка (x,y), така че извършване на тази операция да е изпълнено xy. Да предположим че R и S са записи съдържащи име и число, искаме да използваме числото като ключ:

Сравнявайки 1234 и 987 се вижда че ключът на R е по-голям от този на S, трябва да разменим местата на R и S. Използвайки R и S от тип record и ф-ция за размяна swap на стойности с параметри псевдоними if(R>S) swap(R,S); Ако искаме да си разменим ни по ключ името вместо числото, трбва да: int operator>(record&S) {return strsmp(name, S.name)>0;} Идеята всички обекти да бъдат сорт на правилните им позиции, най-лесно става с шаблон, но до три-четири обекта. Само при типа record елем, които сорт, съдържа други данни освен ключевете. При типа point целият елем се използва за пресмятане на ключа, а елем от типа int на масив са едновременно и ключове. При положенията за обработка на данни. Обикновено сорт запис с ключове, които са само част от тях. В такива пролижения може да има записи със съвпадащи ключове. Ако единственото изискване е ключевете да бъдат разположени в нарастващ ред, но може да получим следното:

Ако сравним внимателно положението преди и след сорт, ще забележим че редът на записите с еднакви ключове 1234 не е запазен. Ако това са случи, казваме че п-са на сорт е неустойчив. За да обясним метода за сорт ч/з пряка селекция е добре да ползваме пример: 109 75200 25 38 19150 11 20 След като разменим най-малкия елем 11 с първия елем 109. Сега първия елем на редицата е най-малкият, така че по-нататък можем да ограничим с останалите елем. Прилагаме същата процедура към подредицата, която започва от втория елем 75, избираме най-малък елем 19 и го разменяме със 75. Този метод на сорт се нарича пряка селекция. Имаме редица от елем в нарастващ ред, в която да бъде вмъкнат нов елем точно на мястото му , така че нарастващия ред да се запази. Тогава намираме това място, преместваме всички елем с по-гоями ключове с една позиция надясно, за да направим място за новия елем и го поставяме там. Така броят на елем нараства с единица. Ето защо трябва да правим разлика м/у големия физически размер на масива и по-малко чиско n, показващо броя на действи-телно използваните елем преди вкл. Тази ф-ция работи правил-но дори ако започнем от празен масив или от масив с един елем. Не е проблем, ако елем, който трябва да вмъкнем,е по-малък от най-макият елем или по-голям от най-големия. При пръв поглед сме склонни да използ-ваме два цикъла-един за нами-ране на позиция и друг освобо-ждаване на място, премества-йки надясно елем на масива. Ф-цията insert е полезна за много цели. Едната от тях е алгори-тъма за сорт, наречен сорт ч/з вмъкване. Това сорт е неефк-тивно, но изучаването му е добра подготовка за много по-ефективни алгоритми.