Низ (структура података)

Низ у програмирању представља сложени тип података, сачињен од неколицине других података истог или различитих типова. Сваки податак у низу се назива његовим елементом, а сваки елемент има свој индекс, односно објекат преко којег прилазимо том елементу у низу.

Димензија

Низ може бити једнодимензионалан (када га зовемо једноставно низ), дводимензионалан (када га називамо матрицом због аналогије са истоименим математичким појмом), и вишедимензионалан (коцка, четвородимензионална коцка итд.).

Код једнодимензионалног низа, димензија се поистовјећује са дужином низа. Нпр. кажемо да је низ димензије n. Код више димензионалних низова, међутим, не постоји појам дужине, него се увијек каже да је низ димензија m x n x ... x z или (m,n,...,z).

За низ је битно познавати његове димензије да бисмо могли исправно индексирати односно дохватати његове елементе.

Индексирање елемената

Сваки елемент низа има онолико индекса колико сам низ има димензија. Тако, елемент једнодимензионалног низа има један индекс, а n-димензионални низ има n индекса. Сам индекс је обично цио број, али може бити било који објекат.

Примјер

Ако имамо матрицу M димензија 4 x 3, онда су његови индекси организовани као у доњој табели:

M(1,1)	M(1,2)	M(1,3)
M(2,1)	M(2,2)	M(2,3)
M(3,1)	M(3,2)	M(3,3)
M(4,1)	M(4,2)	M(4,3)

Дакле, индексирање се врши тако што се прво наведе индекс реда који нам треба а затим индекс елемента у том реду. Исто важи и за низове других димензија.

У различитим програмским језицима, а нарочито оним који су преузели синтаксу програмског језика C, низови се индексирају користећи оператор средње заграде ([] ). Тако, умјесто да пишемо M(1,3) као у горенаведеном примјеру, у C-у и сродним језицима ћемо писати M[1][3] а у Паскалу M[1,3].

Врсте низова

По врсти индекса низа, низове обично дијелимо на просте и асоцијативне низове. Прости низови имају цијеле бројеве за индексе који представљају редне бројеве елемената у низу или поднизовима. Асоцијативни низови користе објекте разних типова за индексе, али најчешће ријечи (ниске). Тако, да бисмо индексирали неки елемент асоцијативног низа, можемо рећи niz("мама") да бисмо добили име мајке, или niz["директор"] да бисмо добили име или податке директора итд.

Сви програмски језици који подржавају низове подржавају просте низове. Али не подржавају сви и асоцијативне низове. Од оних који их подржавају, неки их имају уграђене у сам језик (нпр. PHP) а неки у посебне библиотеке (нпр. C++). Чест назив за асоцијативне низове је мапа.

Низови у различитим програмским језицима

C

У програмском језику C низови се имплементирају преко показивача. Отуда и посебна синтакса коју C користи за низове, за разлику од осталих програмских језика.

C не подржава асоцијативне низове. Подржава само обичне низове, и у њима индекс првог елемента је 0. Посљедично, ако је димензија низа n, индекс посљедњег елемента биће n-1. Исто тако, код матрица горњи лијеви елемент имаће индекс (0,0), а доњи десни имаће индекс (m-1,n-1).

Низ се у C-у може формирати на статички и динамички начин.

Под статичким подразумијевамо декларацију низа са фиксним димензијама које не можемо мијењати до краја постојања промјенљиве. Програм ће сам бринути о алоцирању одговарајућег меморијског простора као и о ослобађању истог на крају постојања промјенљиве. Декларација изгледа на сљедећи начин:

<тип елемента> <назив_промјенљиве>[<величина_низа>];

На примјер, да бисмо декларисали низ x од 10 цјелобројних елемената, писали бисмо сљедећи код:

int x[10];

Да бисмо декларисали матрицу M од 6x4 реалних бројева, писали бисмо сљедеће:

double M[6][4];

При декларацији статичког низа имамо могућност да га иницијализујемо, тј. да додијелимо почетне вриједности његовим елементима, користећи витичасте заграде:

double y[5] = {1, 2, 4, 5, 7};

Под динамичким низом подразумијевамо декларацију показивача одговарајућег типа а затим ручно алоцирање меморије користећи неку од системских функција (malloc, calloc и других). Слиједе примјери:

double * niz; /* декларација показивача */
int n = 20; /* декларација дужине низа */
niz = malloc(n * sizeof(double) );
              /* malloc алоцира меморију и враћа адресу почетка заузетог сегмента.
                 ову адресу смјештамо у показивач niz */

/* ... користимо низ ... */

/* обавезни смо овако алоцирани низ да избришемо из меморије по завршетку кориштења */
free(niz );

Динамички алоцирани низови се могу за вријеме рада програма обрисати да би се алоцирао низ већих или мањих димензија. Такође, пошто је у C-у обавезно декларисати промјенљиве на почетку блока, тако и статички низови морају имати дужину која је унапријед позната. Динамички алоцирани, међутим, не морају; само показивач се мора декларисати на почетку блока, а функција за алоцирање се може позвати у било ком тренутку касније, када сазнамо колики нам низ треба.

Елементима низа прилазимо користећи сличну синтаксу као и код декларације статичког низа, користећи оператор средње заграде:

int niz[20]; /* декларишемо један статички низ */
int n; /* декларишемо једну помоћну промјенљиву */
niz[0] = 17; /* додјељујемо број 17 првом елементу низа */
niz[1] = 18;
n = niz[0]; /* додјељујемо промјенљивој n вриједност првог елемента низа */

На исти начин се прилази и елементима вишедимензионалног низа:

int M[10][3]; /* декларишемо матрицу од 10x3 елемената
int n; /* декларишемо помоћну промјенљиву n */
M[0][2] = 17; /* трећем елементу првог реда додјељујемо број 17 */
n = M[0][2]; /* промјенљивој n додјељујемо трећи елемент првог реда */

C++

C++ користи исту синтаксу за декларисање статичких низова као и C. За динамичко алоцирање, међутим, C++ уводи нову кључну ријеч new која се користи и за низове, опет уз употребу средњих заграда:

int M[7][8]; // декларација статичке матрице
int * niz; // декларација показивача за низ
niz = new int[20]; // алокација помоћу оператора new
delete [] niz; // брисање низа из меморије се врши уз помоћ кључне ријечи delete и средњих заграда

Поред подршке за обичне низове, стандардна библиотека C++-а уводи и библиотеку за рад са мапама, које представљају врсту асоцијативних низова.

Паскал

У Паскалу, низови су уграђени тип промјенљиве који се декларишу користећи специјалне кључне ријечи и синтаксу и физички немају никакву везу са показивачима.

Подразумијевани Индекс првог елемента низа у Паскалу је 1, али може бити и било који други број, што се дефинише при декларацији, скупа са димензијом низа.

Паскал користи кључне ријечи array и of за декларацију низа. Слиједи примјер:

niz: array[1..10] of integer;
matrica: array[2..6,0..3] of real;

Наравно, као и остале промјенљиве и низови морају бити декларисани у блоку за декларацију, var.

Индексирање елемента постојећег низа се врши користећи оператор средње заграде, али нешто другачије него у C-у кад говоримо о вишедимензионалним низовима. Слиједи примјер:

niz[1] = 10; {* код једнодимензионалних низова синтакса је иста као у C-у *}
matrica[3,2] = 4; {* код вишедимензионалних низова синтакса је различита од C-ове *}
matrica[0,1] = 10; {* грешка! matrica је дефинисана да има индексе од 2 до 6 по првој димензији и од 0 до 3 по другој*}

PHP

PHP има изузетно развијену подршку за низове, како асоцијативне тако и обичне. Они такође представљају дио самог језика, као и у Паскалу. За разлику од C++-ових мапа, PHP не подржава објекте класа да буду индекси елемената низа, него само цијели бројеви или ријечи (ниске).

Као и сви остали типови промјенљивих у PHP-у, ни низови се не морају унапријед декларисати, али се морају иницијализовати, користећи кључну ријеч array.

$niz = array(); // промјенљива niz постаје низ од нула елемената
$niz2 = array(10, 20, 30 ); // декларишемо низ од 3 елемента, 10, 20 и 30

PHP заправо обичне низове не разликује од асоцијативних, и користи исту кључну ријеч array и за њих. Асоцијативни низови се креирају на два начина:

• Користећи специјалну синтаксу у иницијализацији низа. Ова синтакса подразумијева кориштење оператора =>, тако што се за сваки елемент у иницијализацији стави његов индекс, затим већ споменути оператор, затим вриједност елемента.
• Индексирајући непостојећи члан низа, као да већ постоји, и додјељујући вриједност том новом елементу. За индекс се користи ријеч, чиме низ аутоматски постаје асоцијативан.

Погледајмо примјере за оба начина:

// први начин
$porodica = array("мама“ => „Славица“, „тата“ => „Миодраг“, „бата“ => „Срећко“ );
echo „Моји родитељи се зову ";
echo $porodica["мама"];
echo " и ";
echo $porodica["тата"];
// Штампа се текст „Моји родитељи се зову Славица и Миодраг“

// други начин
$porodica = array();
$porodica["мама"] = „Славица";
$porodica["тата"] = „Миодраг";
$porodica["бата"] = „Срећко";

PHP има и контролну структуру foreach која служи искључиво за низове. Она пролази кроз сваки елемент низа и обавља одређену радњу.

У PHP-у елементи низа могу бити различитог типа, што није карактеристика C-а, C++-а и Паскала-а код којих елементи низа морају имати сви исти тип, што је одређено и самом синтаксом декларације типа. Ово, међутим, личи на понашање већине других скриптних језика, као што је Јаваскрипт, Перл и други.

Јаваскрипт

Јаваскрипт низове посматра као објекте уграђене класе Array. Као такви, низови имају своје методе, атрибуте, подлијежу оператору delete а креирају се позивањем конструктора класе Array оператором new. Слиједе примјери:

var niz = new Array(); // креирамо низ
niz[0] = 10; // нови елемент правимо тако што му једноставно додијелимо вриједност на жељеном индексу
niz[100] = 20; // елементи се не морају креирати „редом“, него можемо да додијелимо вриједност
                       // директно n-том елементу, да би низ аутоматски порастао на дужину n+1
alert(niz.length); // атрибут length увијек осликава тренутну дужину низа
delete niz; // бришемо низ из меморије браузера

Јаваскрипт не подржава асоцијативне низове, али се оператори средњих заграда понекад користе на начин да личи да подржава. Наиме, у Јаваскрипту је синтакса Objekat.atribut еквивалентан са Objekat["atribut"]. Ова синтакса се понекад користи за генерисање имена атрибута објекта неке класе, али не представља асоцијативне низове.

Примјена

Низови се користе у многим ситуацијама када је потребно најприје у меморији сачувати читаву групу података да би се над њом могла обавити одређена операција. Типичан примјер је сортирање елемената неког скупа - да бисмо провјерили да ли постоји већи елемент од неког елемента, морамо их све имати на располагању. А да бисмо их све имали на располагању, морамо имати неку структуру података згодну за то. То може бити бинарно стабло, динамичка листа, али може и низ, ако је број података релативно мали.

Друге примјене низова су:

• рад са математичким матрицама (вишедимензионални низови)
• рад са табелама за претраживање
• било која ситуација када имамо скуп сродних података за чување у меморији ради касније употребе

Сродне структуре података

Најсроднија структура података низу је динамичка листа. У различитим програмским језицима она се имплементира на различите начине, али је основна сличност са низовима њена линеарност. Штавише, у неким скриптним језицима се обични низови имплементирају преко динамичке листе, да не би били ограниченог капацитета.

Асоцијативни низови се у већини језика имплементирају преко бинарног стабла јер оно има брз алгоритам претраге, што је неопходно за брз проналазак елемента са одређеним индексом.