Tutorijal - Implementacija struktura podataka u programskom jeziku JavaScript

Uvod

Na prvi pogled, JavaScript ne deluje kao jezik koji je "kao stvoren" za implementaciju čvorova i struktura podataka, što je zadatak za koji bi (u praksi), većina programera najverovatnije izabrala neki od jezika kao što su C, C++, Java ili C# (i svakako preporučujemo čitaocima koji cene svoje obrazovanje u oblasti programiranja, da se sa implementacijom struktura podataka prvo upoznaju - upravo kroz neki od navedenih jezika).

Međutim, ako ste rešili "prvi zadatak", to jest, već imate ličnog iskustva u implementaciji struktura podataka u jezicima sa strogom tipizacijom; imate pri tom želju da unapredite svoju veštinu korišćenja skriptnih jezika i upoznati ste (u opštem smislu), sa strukturama podataka o kojima diskutujemo, nastavljamo dalje ....

Pre svega, jasno je da u skriptnim jezicima sa dinamičkom tipizacijom podataka (kao što su JavaScript i Python) - takođe postoji potreba za složenim strukturama podataka iz "domaće radinosti", i stoga ćemo se u nastavku pozabaviti načinima za implementaciju složenijih struktura podataka u skriptnim jezicima, a usput ćemo verovatno uvideti i to da celo iskustvo takođe može biti vrlo zabavno (nešto nalik izradi montažnih kuća, u poređenju sa klasičnim načinima gradnje). :)

Osnovna struktura čvora

Za primere u članku (koji između ostalog demonstriraju i upotrebu klasa u JavaScript-u), implementiraćemo čvorove kakvi se mogu koristiti u binarnim stablima pretrage, ali (uz manje izmene), i u stekovima, redovima za čekanje i (naravno), mnogim drugim strukturama podataka).

Osnovna klasa koja definiše čvor, može se implementirati na sledeći način:

		
class Cvor {

	constructor (vrednost) {
		this.vrednost = vrednost;
		this.levi     = null;
		this.desni    = null;
	}
}
		
	

Vidimo da polja vrednost, levi i desni nemaju eksplicitno definisan tip (u 'tipičnom JS maniru'), i takođe vidimo da se konstruktor ne definiše kao u drugim programskim jezicima (koje smo prethodno koristili), ali, sa druge strane, upotreba rezervisane reči constructor, verovatno ne ostavlja mesta sumnji po pitanju toga o kakvoj se metodi radi. :)

Sada se može pozvati sledeći kod:

		
C1 = new Cvor(12);
C2 = new Cvor(8);
C3 = new Cvor(18);

C2.levi  = C1;
C2.desni = C3;
		
	

.... i svi čvorovi će biti uredno definisani (praktično: čvorovi C1 i C3 postaju "potomci" čvora C2 i "listovi" stabla).

Međutim, nije nimalo teško setiti se i toga da je moguće napisati (a takođe i pozvati), i naredbe dodele kao što su ....

		
C1.levi  = 12;
C1.desni = "Obedska bara";
		
	

.... i takva primedba sasvim je na mestu.

U opštem smislu, "slobodna" interpretacija tipova podataka svojstvena programskom jeziku JS, može delovati problematično, ali (kao što smo već nagovestili) - pod uslovom da sami pazimo da ne dođe do naredbi dodele kakve smo videli na slici #3 - stvari u praksi ipak funkcionišu sasvim dobro.

Implementacija steka

U prethodnom članku o nizovima u JS-u, prikazali smo (preko primera), način upotrebe metoda push i pop: prva metoda u niz dodaje novi element (na kraj niza), a druga vraća referencu na poslednji (dodati) element i uklanja element iz niza, što u potpunosti odgovara principu LIFO (last in - first out), po kome stek funkcioniše.

Ako "zažmurimo" - i "pravimo se da ne znamo" da je moguće u svakom trenutku pristupiti proizvoljnom elementu niza (što svakako nije odlika tipičnog steka) - shvatićemo da na raspolaganju (praktično) imamo sasvim funkcionalan stek:

		
STEK = [];
STEK.push(C1);  // STEK - [C1]
STEK.push(C2);  // STEK - [C1, C2]
STEK.push(C3);  // STEK - [C1, C2, C3]

vrhSteka = STEK.pop();           // STEK - [C1, C2] 
console.log(vrhSteka.vrednost);  // 18

vrhSteka = STEK.pop();           // STEK - [C1] 
console.log(vrhSteka.vrednost);  // 8

vrhSteka = STEK.pop();           // STEK - [] 
console.log(vrhSteka.vrednost);  // 12
		
	

I na ovom mestu (kao i do sada), vidimo "liberalni JS pristup" koji ne zahteva preciznu deklaraciju steka (koji će "nositi" objekte određene klase), ali, u praktičnom smislu, vidimo takođe i programski kod koji je veoma nalik na programski kod iz nekog od 'kompajliranih' jezika, koji od programera zahtevaju da sami precizno deklarišu tipove podataka.

Praktičan savet je (ponovo): potrebno je da pazimo šta radimo i ne treba da izvršavamo naredbe koje ni inače (preko drugih jezika), ne bismo izvršavali nad stekovima.

Implementacija reda za čekanje

Za implementaciju reda za čekanje, koji funkcioniše po principu FIFO (first in - first out), ne može se koristiti isti pristup kojim smo se vodili pri implementaciji steka, ali, svakako se možemo "snaći".

Elementi se i ovoga puta mogu dodavati preko metode push, a za uklanjanje, može se koristiti metoda shift koja (da se podsetimo), iz niza (odnosno, u našem slučaju, iz 'reda za čekanje' :)), uklanja prvi element i vraća referencu na navedeni element.

		
RED = [];
RED.push(C1);  // RED - [C1]
RED.push(C2);  // RED - [C1, C2]
RED.push(C3);  // RED - [C1, C2, C3]

pocetakReda = RED.shift();          // RED - [C2, C3] 
console.log(pocetakReda.vrednost);  // 12

pocetakReda = RED.shift();          // RED - [C3] 
console.log(pocetakReda.vrednost);  // 8

pocetakReda = RED.shift();          // RED - [] 
console.log(pocetakReda.vrednost);  // 18
		
	

Da ponovimo još jednom (znate šta sledi): ako ne budemo (nepotrebno) "čeprkali" po unutrašnjim elementima reda, cela struktura će funkcionisati onako kako očekujemo.

Implementacija stabla pretrage

Za implementaciju stabla pretrage, koristićemo klasu u kojoj je jedno od polja, referenca na koreni čvor.

Pored osnovne implementacije, razmotrićemo takođe (ali - samo u svojstvu zanimljivog fenomena (jer nije u pitanju pristup koji je preporučljivo primenjivati u praksi)), implementaciju koja podrazumeva kreiranje samo jednog (jedinog) objekta klase Cvor:

		
const KOREN = new Cvor(10);
		
	

Pod uslovom da se promenljiva KOREN ne dereferencira, uvek će postojati način da se pristupi korenom čvoru stabla (što omogućava da se i ostali čvorovi dodaju lako).

Međutim, u praksi (kao što smo takođe prethodno naveli, i kao što smo već videli u prethodnim primerima implementacije struktura podataka u drugim jezicima), koreni čvor će biti definisan kao zasebna referenca (tj. polje) - unutar klase (koja tipično obuhvata i mnoga pomoćna polja, i naravno - metode):

		
class Stablo {
	
	constructor(vrednost) {
		this.Koren  = new Cvor(vrednost);
		this.Brojac = 0;
	}
}
		
	

Kao i "inače", metode se mogu implementirati unutar klasa (prikazaćemo samo primer uprošćene metode za dodavanja čvorova):

		
class Stablo {
	
	....

	function dodavanje(cvor, vrednost) {
		if (cvor == null) {
			return new Cvor(vrednost);
		}

		if (vrednost < cvor.vrednost) {
			cvor.levi = dodavanje(cvor.levi, vrednost);
		}
		else {
			if (vrednost > cvor.vrednost) {
				cvor.desni = dodavanje(cvor.desni, vrednost);
			}
			else {
				alert("Vrednost već postoji u stablu!");
				return cvor;
			}
		}

		return cvor;
	}
}
		
	

Metoda dodavanje poziva se na sledeći način:

		
let stablo = new Stablo(12);
Stablo.dodavanje(Stablo.Koren, 10);
		
	

Ako pogledamo metodu dodavanje, jasno je da su delovi koji se tiču balansiranja čvorova izostavljeni (a očigledno fale i metode za pretragu, uklanjanje čvorova i sl).

Implementaciju navedenih (preostalih) metoda, ostavljamo čitaocima - za vežbu. :)

Za kraj ....

Za kraj ostaje da vas još jednom pozovemo da dovršite samostalno neku od započetih implementacija iz članka (ukoliko imate dovoljno slobodnog vremena), a takođe želimo da se osvrnemo, još jednom, na opšti pristup koji smo preporučili na početku.

Pod uslovom da već imate prethodnog iskustva sa implementiranjem struktura podataka (po mogućnosti, "baš" u C-u, ali, i ostali jezici koje smo naveli na početku poslužiće sasvim dobro), proces implementacije struktura podataka u JavaScript-u, neće biti težak.

Naprotiv, biće (gotovo je sigurno da je tako) - znatno lakši.

I upravo je u tome stvar (kao što smo jednom prilikom već naveli): ukoliko se na početku usmerite na teže jezike i teže primere, i uspete da dobro savladate tehnike (doduše, nemojte baš ni preterivati, pogotovo ako ste veoma mlad polaznik), upoznavanje sa jezicima koji koriste ponešto pojednostavljenu sintaksu (kakvi su JS i Python), možda se neće desiti "samo od sebe", ali, biće mnogo (mnogo!) lakše nego kada biste primenili 'obrnuti pristup' (što nikako ne preporučujemo).

U svakom slučaju, programiranje se najbolje uči - pisanjem programa. :)