Четв, 1- ви Окт.
Referatite.org е архив от реферати, курсови и дипломни работи,

казуси, теми, есета и всичко необходимо на ученика и студента
ХИТОВИ РЕФЕРАТИ
Начало / Реферати / Информационни технологии

Линейни структури от данни


Линейни структури от данни

1.Масиви

Да разгледаме следния пример: дадена е функцията

която е полином от 5-та степен. Тя е еднозначно определена от коефициентите (3, 2, 0, -1, 5, 6). В общия случай полином от n-та степен е еднозначно определен от коефициентите (a0,a1, ..,an), като от значение е тяхната наредба.

Втори пример: най-общия запис на система алгебрични уравнения е следния:

Системата еднозначно е определена от матрицата А и вектора стълб .

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

Представяне на масиви

Задачата може да се формулира така: на всеки елемент от масива еднозначно да се съпостави поле от паметта на компютъра т.е. на индексите на елемента еднозначно да се съпостави адрес на поле от паметта. Тъй като клетките на паметта на компютъра са последователно номерирани за решаване на задачата е достатъчно да се намери метод за линеаризиране на n-мерни масиви. В най- простия случай, когато масивът е едномерен съответствието h1 e:

където i е поредния номер(индекс) на i- тия елемент на масива, а q( базов адрес ) е началния адрес на първата клетка от областта на компютърната памет в която се разполага масива.


a1 a2 an



q q+1 q+n-1



при представяне на двумерни масиви в ОП се постъпва по следния начин: най-напред разполагаме елементите на 1-вия ред, след това елементите от 2- рия ред и т.н. Ако предположим, че базовия адрес е q, поредния номер на елемента aij ще получим по формулата:

(1)

може да се формулира и обратната задача: по зададен линеен номер к на елемент от масива да се намерят неговите индекси( еднозначно ли е решението? )

ще докажем това твърдение:

доказателство:

от (1) следва k=q+(i-1)m+(j-1) или

mi+j=k+m-q+1 (2)

да допуснем, че има две двойки (i1,j1), (i2,j2), които удовлетворяват (2).

mi1+j1=mi2+j2 или m(i1-i2)=j2-j1

т.е равенство е възможно само при i1=i2 и j1=j2.

Аналогично може да се осъществи линеаризацията на тримерни масиви {aijk} i=1,..,M; j=1,,N; k=1,,K

h3(i,j,k)=q+(k-1)MN+(j-1)M+(i-1) (3)

Представяне на двумерни триъгълни масиви

Един двумерен масив А с n реда и n стълба е:

а) долнотриъгълен, ако A(i,j)=0 за j>i

b) горнотриъгълен, ако A(i,j)=0 за i>j


Материала е изпратен от: Ивайло Георгиев




Изтегли материала