Home-theater-designers
Podatkovne strukture so temeljni vidik računalništva in programiranja, ne glede na jezik, ki ga uporabljate. Če jih dobro poznate, vam lahko pomagajo učinkovito organizirati, upravljati, shranjevati in spreminjati podatke. Prepoznavanje ustrezne strukture podatkov za vaš primer uporabe lahko izboljša zmogljivost z veliko mejo.
Vendar ima JavaScript privzeto samo primitivne podatkovne strukture, kot so matrike in objekti. Toda z uvedbo razredov ECMAScript 6 (ES6) lahko zdaj s pomočjo primitivnih podatkovnih struktur ustvarite podatkovne strukture po meri, kot so skladi in čakalne vrste.
Windows 10 izklopi obvestila po pošti
Struktura podatkovnega sklada
Podatkovna struktura sklada vam omogoča potiskanje novih podatkov na obstoječe podatke na način LIFO (zadnji vhod, prvi odhod). To linearno strukturo podatkov je enostavno prikazati s preprostim primerom. Razmislite o kupu krožnikov na mizi. Ploščo lahko dodate ali odstranite samo z vrha sklada.
Evo, kako lahko z nizom JavaScript in Razredi ES6 :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}Raziščimo in sestavimo nekatere operacije, ki jih lahko izvedete v nizu.
Potisna operacija
Potisna operacija se uporablja za vstavljanje novih podatkov v sklad. Podatke morate posredovati kot parameter, medtem ko kličete potisno metodo. Pred vstavljanjem podatkov se zgornji kazalec sklada poveča za eno, novi podatki pa se vstavijo na zgornji položaj.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}Pop operacija
Operacija pop se uporablja za odstranitev zgornjega podatkovnega elementa sklada. Med izvajanjem te operacije se zgornji kazalec zmanjša za 1.
pop() {
if (this.top <0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}Peek Operacija
Operacija pokukanja se uporablja za vrnitev vrednosti, ki je prisotna na vrhu sklada. Časovna zapletenost pri pridobivanju teh podatkov je O (1).
Nauči se več: Kaj je zapis Big-O?
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}Struktura podatkov povezanega seznama
Povezani seznam je linearna struktura podatkov, sestavljena iz številnih vozlišč, povezanih med seboj s pomočjo kazalcev. Vsako vozlišče na seznamu vsebuje podatke in spremenljivko kazalca, ki kaže na naslednje vozlišče na seznamu.
Več o tem: Uvod v kazalce za programerje
Za razliko od sklada, izvedbe povezanih seznamov v JavaScript zahtevajo dva razreda. Prvi razred je Vozlišče razred za ustvarjanje vozlišča, drugi razred pa je LinkedList razred za izvajanje vseh operacij na povezanem seznamu. Kazalec glave kaže na prvo vozlišče povezanega seznama, kazalec repa pa na zadnje vozlišče povezanega seznama.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}Tu je nekaj osnovnih operacij, ki jih lahko izvedete na povezanem seznamu:
Dodajanje operacije
Operacija dodajanja se uporablja za dodajanje novega vozlišča na konec povezanega seznama. Podatke morate posredovati kot parameter za vstavljanje novega vozlišča. Najprej ustvarite nov objekt vozlišča z datoteko nov ključno besedo v JavaScript.
Če je povezan seznam prazen, bosta kazalec glave in repa kazala na novo vozlišče. V nasprotnem primeru bo le kazalec repa kazal na novo vozlišče.
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
return this;
}Vstavi operacijo
Če želite v določeno kazalo vstaviti novo vozlišče, lahko uporabite operacijo vstavljanja. Ta metoda ima dva parametra: podatke za vstavljanje in indeks, pri katerem jih je treba vstaviti. V najslabšem primeru ima ta metoda časovno zapletenost O (N), saj bo morda morala prečkati celoten seznam.
insert(data, index) {
if (index this.size) return undefined;
if (index === 0) {
this.head = new Node(data, this.head);
!this.tail ? (this.tail = this.head) : null;
this.size++;
return this;
}
if (index === this.size) return this.append(data);
let count = 0;
let beforeNode = this.head;
while (count !== index) {
beforeNode = beforeNode.next;
count++;
}
const newNode = new Node(data);
let afterNode = beforeNode.next;
newNode.next = afterNode;
beforeNode.next = newNode;
this.size++;
return this;
}Operacija brisanja
Operacija brisanja se premika po povezanem seznamu, da dobi sklic na vozlišče, ki ga je treba izbrisati, in odstrani povezavo prejšnjega vozlišča. Podobno kot operacija vstavljanja ima tudi operacija brisanja časovno kompleksnost O (N) v najslabšem primeru.
deleteNode(index) {
if (index === 0) {
const removedHead = this.head;
this.head = this.head.next;
this.size--;
this.size === 0 ? (this.tail = null) : null;
return removedHead;
}
if (index === this.size - 1) {
if (!this.head) return undefined;
let currentNode = this.head;
let newTail = currentNode;
while (currentNode.next) {
newTail = currentNode;
currentNode = currentNode.next;
}
this.tail = newTail;
this.tail.next = null;
this.size--;
this.size === 0 ? ([this.head, this.tail] = [null, null]) : null;
return currentNode;
}
if (index this.size - 1) return undefined;
let count = 0;
let beforeNode = this.head;
while (count !== index - 1) {
beforeNode = beforeNode.next;
count++;
}
const removedNode = beforeNode.next;
let afterNode = removedNode.next;
beforeNode.next = afterNode;
removedNode.next = null;
this.size--;
return removedNode;
}Struktura podatkov čakalne vrste
Podatkovna struktura čakalne vrste je podobna skupini ljudi, ki stoji v čakalni vrsti. Oseba, ki prva vstopi v čakalno vrsto, je postrežena pred drugimi. Podobno ta linearna struktura podatkov sledi pristopu FIFO (prvi vstopi, prvi izstopi) za vstavljanje in odstranjevanje podatkov. To strukturo podatkov je mogoče znova ustvariti v JavaScript z uporabo povezanega seznama na ta način:
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}Tako lahko vstavite in odstranite podatke iz čakalne vrste v JavaScript:
igre, ki ne potrebujejo adobe flash playerja
Operacija čakalne vrste
Operacija čakalne vrste v čakalno vrsto vstavi nove podatke. Med klicem te metode, če je podatkovna struktura čakalne vrste prazna, sprednji in zadnji kazalec kažeta na novo vstavljeno vozlišče v čakalni vrsti. Če čakalna vrsta ni prazna, se novo vozlišče doda na konec seznama, zadnji kazalec pa kaže na to vozlišče.
enqueue(data) {
const newNode = new Node(data);
if (!this.front) {
this.front = newNode;
this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
return this;
}Dequeue Operacija
Operacija odlaganja odstrani prvi element v čakalni vrsti. Med operacijo mirovanja se kazalec glave premakne naprej na drugo vozlišče na seznamu. To drugo vozlišče zdaj postane glava čakalne vrste.
dequeue() {
if (!this.front) return undefined;
if (this.front === this.rear) this.rear = null;
const dequeuedNode = this.front;
this.front = this.front.next;
this.size--;
return dequeuedNode;
}Naslednji korak po podatkovnih strukturah
Podatkovne strukture so lahko težaven koncept, še posebej, če ste začetnik programiranja. Toda tako kot vsaka druga veščina vam lahko praksa pomaga resnično razumeti in ceniti učinkovitost shranjevanja in upravljanja podatkov v vaših aplikacijah.
Algoritmi so prav tako uporabni kot podatkovne strukture in bi lahko postali naslednji logični korak na vaši programski poti. Zakaj torej ne bi začeli z algoritmom razvrščanja, kot je razvrščanje mehurčkov?
Deliti Deliti Cvrkutati E-naslov Uvod v algoritem razvrščanja mehurčkovAlgoritem razvrščanja mehurčkov: odličen uvod v razvrščanje nizov.
Preberite Naprej Sorodne teme- Programiranje
- JavaScript
- Programiranje
- Vadnice za kodiranje
Nitin je navdušen razvijalec programske opreme in študent računalniškega inženiringa, ki razvija spletne aplikacije z uporabo tehnologij JavaScript. Dela kot samostojni spletni razvijalec in v prostem času rad piše za Linux in programiranje.
Več od Nitin RanganathNaročite se na naše novice
Pridružite se našemu glasilu za tehnične nasvete, ocene, brezplačne e -knjige in ekskluzivne ponudbe!
Kliknite tukaj, če se želite naročiti