Низа (информатика)

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

Димензија

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

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

За низата е многу важно да се познава нејзината димензија, за да можеме правилно да ги индексираме нејзините елементи.

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

Секој елемен во низата има онолку индекси колку што има индекси и самата низа. Така елемент на еднодимензионална низа има еден индекс, на дводимензионална – два индекси, на n димензионална –n индекси.

Пример

Ако имаме матрица M со димензија 4x3, тогаш нејзините индекси ќе бидат како на претставената табела:

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 и во сродните јазици ќе пишуваме М[1][3], додека во Паскал М[1,3].

Видови на низи

По видовите на индексите, низите обично ги делиме на прости и асоцијативни. Простите низи за индекси имаат цели броеви кои претставуваат редни броеви на елементите во низата или поднизата. Асоцијативните низи користат објекти од разни типови за индекси, но најчесто зборови. Така, за да индексираме некој елемент од асоцијативна низа, можеме да напишеме niza[“mama”] како би го добиле името на мајката, или niza[“director”] како би го добиле името или податоците на директорот.

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

Податоци од типот низа во различни програмски јазици

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) ); /* или niza = calloc( n, sizeof(double) ); */ /* malloc ја алоцира меморијата и ја враќа адресата од почетокот на заземениот сегмент. оваа адреса ја сместуваме во покажувачот nizа */ if( niza == 0 ){ return 1; /* излеваме од програмата со код за грешка */ } /* ... ја користиме низата ... */ /* задолжително е вака алоцираната низа да ја избришеме од меморијата по завршувањето на користењето */ free( niz );

Динамичко алоцираните низи за време на работата на програмата можат да се избришат како би се алоцирала низа со поголеми или помали димензии. Истата функционалност е имплементирана со функцијата realloc. Поради тоа што во 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++ стандардната библиотека воведува библиотека за работа со мапи, кои претстауваат еден вид на асоцијативни низи.

Паскал

Во Паскал Паскал, низите се вграден тип на променлива која се декларира со користење на специјален резервиран збор и синтакса. Како и во C, и во Паскал се имплементирани динамичките низи.

Во Паскал, како прв елемент на низата се подразбира 1, но може да биде и било кој друг број кој се дефинира при декларирањето заедно со димензијата на низата. Ако низата е имплементирана со помош на динамичка меморија, тогаш таа секогаш започнува со индекс 0, исто како и во C/C++.

Паскал ги користи резервираните зборови array и of за декларирањето на низа:

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

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

var pNiza : ^integer; broj_elem : integer; begin readln(broj_elem); getmem(pNiza, broj_elem * sizeof(integer) ); for i = 0 to broj_elem - 1 do begin pNiza^ := 4; { операторот ^ го има приближно истото значење како и операторот за дереференцирање во C/C++ } { на С ова значи pNiza[i] = 4 } inc(pNiza); { pNiza++; } end; freemem(pNiza, broj_elem * sizeof(integer)); end.

Индексирањето на елементите се врши со употреба на средни загради, но е различно од C за повеќедимензионалните низи:

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

PHP

PHP има посебно развијана поддршка за низите, како за асоцијативните, така и за обичните. Тие исто така претставуваат дел од самиот јазик како и во Паскал. За разлика од картите во C++, PHP не поддржува класите да бидат индекси од елементите од елементите на низата, туку само цели броеви или зборови.

Како и сите останати типови на променливи во PHP, ниту низите не треба да се декларираат, туку само да се иницијализираат со користењето на резервираниот збор array:

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

PHP всушност не ги разликува простите од асоцијативните низи и користи ист резервиран збор array за нив. Асоцијативните низи можат да се создаваат на два начини:

• Со користење на специјална синтакса при иницијализацијата на низата. Под оваа синтакса се подразбира употреба на операторот =>, така што за секој елемент при иницијализацијата се става неговиот индекс, потоа наведениот оператор, а потоа вредноста на елементот.
• Со индексирање на непостоечки елемент на низата, како веќе и да постои и со доделување на вредност на тој нов елемент. За индекс се користи збор, со кој низата автоматски станува асоцијативна.

// прв начин $semejstvo = array( "мама" => "Славица", "тата" => "Милан", "бата" => "Стефан" ); echo "Моите родители се викаат "; echo $semejstvo["мама"]; echo " и "; echo $semejstvo["тата"]; // се отпечатува текстот "Моите родитесли се викаат Славица и Милан"

// втор начин $semejstvo = array(); $semejstvo ["мама"] = "Славица"; $semejstvo ["тато"] = "Милан"; $semejstvo ["бато"] = "Стефан";

PHP има и контролна структура foreach која служи само за низи. Таа поминува преку секој елемент на низата и извршува одредена работа.

Во PHP елементите на низата можат да бидат од различен тип, за разлика од C, C++ и Паскал каде елементите на низата мора да бидат од ист тип, што е одредено и со самата синтакса за декларација на типот. Но ова е слично со однесувањето на други скриптни јазици како што се Javascript, Перл и други.

Javascript

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

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

Javascript не поддржува асоцијативни низи, но операторот средни загради некогаш се користат на начин за да изгледа како да ги поддржува. Така, во Javascript синтаксата Objekt.atribut е еквивалентна со Objekt["atribut"]. Оваа синтакса понекогаш се користи за генерирање на имињата на атрибутите на објект од некоја класа, но не претставува асоцијативна низа.

Примена

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

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

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

Сродни структури на податоци

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

Други сродни податочни структури се мапи, хеш табели, речници и листи.

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