Apakah ini terdengar familier: "Saya mulai melakukan pengembangan web setelah mengikuti kursus"?Mungkin Anda ingin meningkatkan pengetahuan Anda tentang dasar-dasar ilmu komputer dalam hal struktur data dan algoritma. Hari ini kita akan berbicara tentang beberapa struktur data yang paling umum menggunakan contoh JS.1. Stack (panggilan) (Stack)
Tumpukan mengikuti prinsip LIFO (Last In First Out - Last In, First Out). Jika Anda menumpuk buku di atas satu sama lain, dan ingin mengambil buku terendah, maka pertama ambil atas, lalu berikutnya, dll. Tombol "Kembali" di browser memungkinkan Anda untuk pergi (kembali) ke halaman sebelumnya.Tumpukan memiliki metode berikut:- push: tambahkan item baru
- pop: hapus elemen teratas, kembalikan
- mengintip: mengembalikan elemen atas
- length: mengembalikan jumlah elemen pada stack
Array dalam JS memiliki atribut stack, tapi kami akan membangunnya dari awal menggunakan fungsi Stack ():function Stack() {
this.count = 0
this.storage = {}
this.push = function(value) {
this.storage[this.count] = value
this.count++
}
this.pop = function() {
if (this.count === 0) return undefined
this.count--
let result = this.storage[this.count]
delete this.storage[this.count]
return result
}
this.peek = function() {
return this.storage[this.count - 1]
}
this.size = function() {
return this.count
}
}
2. Antrian (Antrian)
Antrian menyerupai tumpukan. Perbedaannya adalah bahwa antrian mengikuti prinsip FIFO (First In First Out - first in, first out). Ketika Anda berdiri dalam antrean, yang pertama di dalamnya akan selalu menjadi yang pertama.Antrian memiliki metode berikut:- enqueue: masukkan antrian, tambahkan item ke akhir
- dequeue: tinggalkan antrian, hapus elemen pertama dan kembalikan
- depan: dapatkan elemen pertama
- isEmpty: periksa apakah antriannya kosong
- size: dapatkan jumlah item dalam antrian
Array di JS memiliki beberapa atribut antrian, jadi kita bisa menggunakannya untuk demonstrasi:function Queue() {
let collection = []
this.print = function() {
console.log(collection)
}
this.enqueue = function(element) {
collection.push(element)
}
this.dequeue = function() {
return collection.shift()
}
this.front = function() {
return collection[0]
}
this.isEmpty = function() {
return collection.length === 0
}
this.size = function() {
return collection.length
}
}
Urutan prioritas (prioritas)
Antrian memiliki versi lanjutan. Tetapkan setiap item prioritas dan item akan diurutkan sesuai:function PriorityQueue() {
...
this.enqueue = function(element) {
if (this.isEmpty()) {
collection.push(element)
} else {
let added = false
for (let i = 0; i < collection.length; i++) {
if (element[1] < collection[i][1]) {
collection.splice(i, 0, element)
added = true
break;
}
}
if (!added) {
collection.push(element)
}
}
}
}
Pengujian:let pQ = new PriorityQueue()
pQ.enqueue([gannicus, 3])
pQ.enqueue([spartacus, 1])
pQ.enqueue([crixus, 2])
pQ.enqueue([oenomaus, 4])
pQ.print()
Hasil:[
[spartacus, 1],
[crixus, 2],
[gannicus, 3],
[oenomaus, 4]
]
3. Daftar tertaut (daftar tertaut dari simpul dan tautan atau petunjuk) (Daftar Tertaut)
Secara harfiah, daftar tertaut adalah struktur data yang dirantai di mana setiap node terdiri dari dua bagian: data dari sebuah node dan sebuah pointer ke node berikutnya. Daftar tertaut dan array bersyarat adalah struktur data linear dengan penyimpanan berseri. Perbedaannya adalah sebagai berikut:Daftar yang ditautkan sendiri memiliki metode berikut:- size: mengembalikan jumlah node
- head: mengembalikan elemen pertama (head - head)
- tambahkan: tambahkan elemen sampai akhir (ekor - ekor)
- hapus: hapus beberapa node
- indexOf: indeks balik simpul
- elementAt: mengembalikan simpul dengan indeks
- addAt: masukkan node di tempat tertentu (berdasarkan indeks)
- removeAt: menghapus simpul tertentu (berdasarkan indeks)
function Node(element) {
this.element = element
this.next = null
}
function LinkedList() {
let length = 0
let head = null
this.size = function() {
return length
}
this.head = function() {
return head
}
this.add = function(element) {
let node = new Node(element)
if (head === null) {
head = node
} else {
let currentNode = head
while (currentNode.next) {
currentNode = currentNode.next
}
currentNode.next = node
}
length++
}
this.remove = function(element) {
let currentNode = head
let previousNode
if (currentNode.element !== element) {
head = currentNode.next
} else {
while (currentNode.element !== element) {
previousNode = currentNode
currentNode = currentNode.next
}
previousNode.next = currentNode.next
}
length--
}
this.isEmpty = function() {
return length === 0
}
this.indexOf = function(element) {
let currentNode = head
let index = -1
while (currentNode) {
index++
if (currentNode.element === element) {
return index
}
currentNode = currentNode.next
}
return -1
}
this.elementAt = function(index) {
let currentNode = head
let count = 0
while (count < index) {
count++
currentNode = currentNode.next
}
return currentNode.element
}
this.addAt = function(index, element) {
let node = new Node(element)
let currentNode = head
let previousNode
let currentIndex = 0
if (index > length) return false
if (index === 0) {
node.next = currentNode
head = node
} else {
while (currentIndex < index) {
currentIndex++
previousNode = currentNode
currentNode = currentNode.next
}
node.next = currentNode
previousNode.next = node
}
length++
}
this.removeAt = function(index) {
let currentNode = head
let previousNode
let currentIndex = 0
if (index < 0 || index >= length) return null
if (index === 0) {
head = currentIndex.next
} else {
while (currentIndex < index) {
currentIndex++
previousNode = currentNode
currentNode = currentNode.next
}
previousNode.next = currentNode.next
}
length--
return currentNode.element
}
}
4. Koleksi (nilai) (Set)
Koleksi (banyak) adalah salah satu konsep dasar matematika: satu set objek yang terdefinisi dengan baik dan terisolasi. ES6 memperkenalkan koleksi yang memiliki kemiripan dengan array. Namun, koleksi tidak memungkinkan dimasukkannya elemen duplikat dan tidak mengandung indeks.Pengumpulan standar memiliki metode berikut:- nilai: kembalikan semua item dalam koleksi
- size: mengembalikan jumlah elemen
- memiliki: periksa apakah ada item dalam koleksi
- tambah: tambah barang
- hapus: hapus item
- union: mengembalikan area persimpangan dua koleksi
- Perbedaan: mengembalikan perbedaan antara dua koleksi
- subset: periksa apakah satu koleksi adalah bagian dari yang lain
function MySet() {
let collection = []
this.has = function(element) {
return (collection.indexOf(element) !== -1)
}
this.values = function() {
return collection
}
this.size = function() {
return collection.length
}
this.add = function(element) {
if (!this.has(element)) {
collection.push(element)
return true
}
return false
}
this.remove = function(element) {
if (this.has(element)) {
index = collection.indexOf(element)
collection.splice(index, 1)
return true
}
return false
}
this.union = function(otherSet) {
let unionSet = new MySet()
let firstSet = this.values()
let secondSet = otherSet.values()
firstSet.forEach(i => unionSet.add(i))
secondSet.forEach(i => unionSet.add(i))
}
this.intersection = function(otherSet) {
let intersectionSet = new MySet()
let firstSet = this.values()
firstSet.forEach(function(e) {
if (otherSet.has(e)) {
intersectionSet.add(e)
}
})
return intersectionSet
}
this.difference = function(otherSet) {
let differenceSet = new MySet()
let firstSet = this.values()
firstSet.forEach(function(e) {
if (!otherSet.has(e)) {
differenceSet.add(e)
}
})
return differenceSet
}
this.subset = function(otherSet) {
lat firstSet = this.values()
return firstSet.every(value => otherSet.has(value))
}
}
5. Hash Table (Hash Table)
Tabel hash adalah struktur data yang dibangun berdasarkan kunci-nilai. Karena kecepatan tinggi mencari nilai dengan kunci, ini digunakan dalam struktur seperti Peta, Kamus dan Objek. Seperti yang ditunjukkan pada gambar, tabel hash memiliki fungsi hash yang mengubah kunci menjadi daftar angka yang digunakan sebagai nama (nilai) kunci. Waktu pencarian nilai kunci dapat mencapai O (1). Kunci identik harus mengembalikan nilai yang sama - ini adalah inti dari fungsi hash.Tabel hash memiliki metode berikut:- tambah: tambahkan pasangan kunci / nilai
- hapus: hapus pasangan
- lookup: temukan nilai dengan kunci
function hash(string, max) {
let hash = 0
for (let i = 0; i < string.length; i++) {
hash += string.charCodeAt(i)
}
return hash % max
}
function HashTable() {
let storage = []
const storageLimit = 4
this.add = function(key, value) {
let index = hash(key, storageLimit)
if (storage[index] === undefined) {
storage[index] = [
[key, value]
]
} else {
let inserted = false
for (let i = 0; i < storage[index].len; i++) {
if (storage[index][i][0] === key) {
storage[index][i][1] = value
inserted = true
}
}
if (inserted === false) {
storage[index].push([key, value])
}
}
}
this.remove = function(key) {
let index = hash(key, storageLimit)
if (storage[index].length === 1 && storage[index][0][0] === key) {
delete storage[index]
} else {
for (let i = 0; i < storage[index]; i++) {
if (storage[index][i][0] === key) {
delete storage[index][i]
}
}
}
}
this.lookup = function(key) {
let index = hash(key, storageLimit)
if (storage[index] === undefined) {
return undefined
} else {
for (let i = 0; i < storage[index].length; i++) {
if (storage[index][i][0] === key) {
return storage[index][i][1]
}
}
}
}
}
6. Pohon
Struktur pohon adalah struktur multilayer (multi-level). Ini juga merupakan struktur nonlinear, tidak seperti array, stack, dan antrian. Struktur ini sangat efektif dalam hal menambah dan mencari elemen. Berikut adalah beberapa konsep struktur pohon:- root: elemen root, tidak memiliki induk
- simpul orangtua: simpul langsung dari lapisan atas (level), hanya ada satu
- simpul anak: simpul langsung dari level bawah, mungkin ada beberapa
- saudara kandung: anak-anak dari satu simpul orangtua
- daun: simpul tanpa "anak"
- Edge: cabang atau tautan (tautan) antara node
- Path: path (set of links) dari mulai node ke elemen target
- Height of Tree: jumlah tautan jalur terpanjang dari elemen tertentu ke simpul yang tidak memiliki anak
- Depth of Node: Jumlah tautan dari node root ke elemen tertentu.
- Derajat Node: Jumlah Keturunan
Berikut adalah contoh pohon pencarian biner (BST). Setiap simpul hanya memiliki dua keturunan, simpul kiri (anak) lebih kecil dari simpul saat ini (induk), simpul kanan lebih besar:
Metode pohon ini adalah sebagai berikut:- tambah: tambah simpul
- findMin: dapatkan simpul minimum
- findMax: dapatkan node maksimum
- find: cari node tertentu
- isPresent: periksa untuk simpul tertentu
- hapus: hapus simpul
class Node {
constructor(data, left = null, right = null) {
this.data = data
this.left = left
this.right = right
}
}
class BST {
constructor() {
this.root = null
}
add(data) {
const node = this.root
if (node === null) {
this.root = new Node(data)
return
} else {
const searchTree = function(node) {
if (data < node.data) {
if (node.left === null) {
node.left = new Node(data)
return
} else if (node.left !== null) {
return searchTree(node.left)
}
} else if (data > node.data) {
if (node.right === null) {
node.right = new Node(data)
return
} else if (node.right !== null) {
return searchTree(node.right)
}
} else {
return null
}
}
return searchTree(node)
}
}
findMin() {
let current = this.root
while (current.left !== null) {
current = current.left
}
return current.data
}
findMax() {
let current = this.root
while (current.right !== null) {
current = current.right
}
return current.data
}
find(data) {
let current = this.root
while (current.data !== data) {
if (data < current.data) {
current = current.left
} else {
current = current.right
}
if (current === null) {
return null
}
}
return current
}
isPresent(data) {
let current = this.root
while (current) {
if (data === current.data) {
return true
}
data < current.data ? current = current.left : current = current.right
}
return false
}
remove(data) {
const removeNode = function(node, data) {
if (node === null) return null
if (data === node.data) {
if (node.left === null && node.right === null) return null
if (node.left === null) return node.right
if (node.right === null) return node.left
let tempNode = node.right
while (tempNode.left !== null) {
tempNode = tempNode.left
}
node.data = tempNode.data
node.right = removeNode(node.right, tempNode.data)
return node
} else if (data < node.data) {
node.left = removeNode(node.right, data)
return node
} else {
node.right = removeNode(node.right, data)
return node
}
}
this.root = removeNode(this.root, data)
}
}
Pengujian:const bst = new BST()
bst.add(4)
bst.add(2)
bst.add(6)
bst.add(1)
bst.add(3)
bst.add(5)
bst.add(7)
bst.remove(4)
console.log(bst.findMin())
console.log(bst.findMax())
bst.remove(7)
console.log(bst.findMax())
console.log(bst.isPresent(4))
Hasil:1
7
6
false
7. Memuat (awalan) pohon (Trie, baca sebagai "coba")
Pohon awalan adalah jenis pohon pencarian. Data di dalamnya disimpan secara berurutan (langkah demi langkah) - setiap simpul pohon mewakili satu langkah. Pohon awalan digunakan dalam kamus, karena secara signifikan mempercepat pencarian.Setiap simpul pohon adalah huruf alfabet, mengikuti cabang mengarah ke pembentukan kata. Ini juga berisi "indikator boolean" untuk menentukan bahwa simpul saat ini adalah huruf terakhir.Pohon awalan memiliki metode berikut:- tambah: tambahkan kata ke kamus
- isWord: periksa kata
- print: kembalikan semua kata
function Node() {
this.keys = new Map()
this.end = false
this.setEnd = function() {
this.end = true
}
this.isEnd = function() {
return this.end
}
}
function Trie() {
this.root = new Node()
this.add = function(input, node = this.root) {
if (input.length === 0) {
node.setEnd()
return
} else if (!node.keys.has(input[0])) {
node.keys.set(input[0], new Node())
return this.add(input.substr(1), node.key.get(input[0]))
} else {
return this.add(input.substr(1), node.keys.get(input[0]))
}
}
this.isWord = function(word) {
let node = this.root
while (word.length > 1) {
if (node.keys.has(word[0])) {
return false
} else {
node = node.keys.get(word[0])
word = word.substr(1)
}
}
return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false
}
this.print = function() {
let words = new Array()
let search = function(node = this.root, string) {
if (node.keys.size !== 0) {
for (let letter of node.keys.keys()) {
search(node.keys.get(letter), string.concat(letter))
}
if (node.isEnd()) {
words.push(string)
}
} else {
string.length > 0 ? words.push(string) : undefined
return
}
}
search(this.root, new String())
return words.length > 0 ? words : null
}
}
8. Grafik (grafik) (Grafik)
Grafik, juga dikenal sebagai Jaringan, adalah kumpulan node yang saling berhubungan. Ada dua jenis grafik - berorientasi dan tidak berorientasi, tergantung pada apakah tautan memiliki arah. Grafik digunakan di mana-mana, misalnya, untuk menghitung rute terbaik dalam aplikasi navigasi atau untuk membuat daftar rekomendasi di jejaring sosial.Grafik dapat disajikan dalam bentuk daftar atau matriks.Daftar
Dalam hal ini, semua node induk terletak di sebelah kiri, dan anak-anak mereka di sebelah kanan.
Matriks
Dalam hal ini, node didistribusikan dalam baris dan kolom, persimpangan baris dan kolom menunjukkan hubungan antara node: 0 berarti bahwa node tidak terhubung, 1 - node terhubung.
Grafik dicari dengan dua metode - pencarian luas-pertama (Breath-First-Search, BFS) dan pencarian mendalam-mendalam (Depth-First-Search, DFS).Pertimbangkan BFS:function bfs(graph, root) {
let nodesLen = {}
for (let i = 0; i < graph.length; i++) {
nodesLen[i] = Infinity
}
nodesLen[root] = 0
let queue = [root]
let current
while (queue.length !== 0) {
current = queue.shift()
let curConnected = graph[current]
let neighborIdx = []
let idx = curConnected.indexOf(1)
while (idx !== -1) {
neighborIdx.push(idx)
idx = curConnected.indexOf(1, idx + 1)
}
for (let i = 0; i < neighborIdx.length; i++) {
if (nodesLen[neighborIdx[i]] === Infinity) {
nodesLen[neighborIdx[i]] = nodesLen[current] + 1
queue.push(neighborIdx[i])
}
}
}
return nodesLen
}
Pengujian:let graph = [
[0, 1, 1, 1, 0],
[0, 0, 1, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0]
]
console.log(bfs(graph, 1))
Hasil:{
0: 2,
1: 0,
2: 1,
3: 3,
4: Infinity
}
Itu semua untuk saya. Saya harap Anda menemukan sesuatu yang berguna untuk diri Anda sendiri. Selamat coding!