資料結構與算法
文章目錄
- 資料結構與算法
- 1.連結清單
-
- 連結清單結構
- 連結清單的常用方法
-
- 1. appendNode(val)：添加一個新節點
- 2. insertNode(val,position)
- 3. removeAt(position)
- 4.getNodeBypostion(position)
- 5.getDataByPostion(position)
- 6.removeElement(val)
- 7.clearNode()
- 8.nodeToString()
- 9.updateNode(position,newVal)
- 2.雙向連結清單
-
- 節點結構
- 連結清單結構
- 常用方法
-
- 1.appendNode(val)
- 2.getPositionByData(val)
- 3.getNodeByData(val)
- 4.getDataByPosition(position)
- 5.getNodeByPosition(position)
- 6. insertNode(position,val)
- 7.remoNode(position)
- 8.displayList(join)
- 調用
1.連結清單
相比于之前的數組，連結清單是一種存儲空間不連續的結構。數組的存儲是連續的，但是它在移動或者是删除元素時，它後面的元素都要移動相應的位置，是以當資料量比較大時還是比較耗費資源的。連結清單則是存儲空間不連續的一種資料結構，類似于火車，由一個一個節點組成，每個節點包含着指向下一個節點的位址以及資料，當删除或添加時隻需要修改節點中存儲的引用即可。
連結清單結構
//節點資料，包含資料以及下一個節點的位址
class NodeList {
constructor(data) {
this.data = data;
this.next = null;
}
}
//連結清單的結構
class LinkedList {
constructor() {
this.length = 0;
this.head = null;
}
append Node(){
}
……
}
連結清單的常用方法
1. appendNode(val)：添加一個新節點
appendNode(val) {
// 先建立一個新節點，判斷是否有頭節點，如果沒有則設定為頭節點
// 如果有的話則找到最後一個節點并添加
let newNode = new NodeList(val)
if (!this.head) {
this.head = newNode;
} else {
let cur = this.head;
// 找到最後的節點
while (cur.next) {
cur = cur.next;
}
cur.next = newNode
}
this.length++;
}
2. insertNode(val,position)
向連結清單中插入節點，參數為節點的值以及插入位置。正常的插入是先找到待插入位置的pre節點，之後将cur節點的next指向pre的next，最後将pre的next的節點設定為curNode
// 指定位置插入節點
insertNode(val, position) {
// 1.先判斷是否超出邊界
if (position > this.length || position < 0) return false;
let newNode = new NodeList(val)
// position為0則表明将目前節點作為頭節點
if (position === 0) {
newNode.next = this.head;
this.head = newNode
} else {
// 找到position的前一個節點
let previous = this.getNodeByposition(position - 1)
previous.next = newNode.next;
previous.next = newNode
}
this.length++
return true
}
3. removeAt(position)
移除指定位置的節點。正常的删除方法：找到待删除節點的preNode，最後将preNode的next指向preNode的next的next，也就是将curNode節點的上一個節點和下一個節點連在一起，沒有指向的節點會在浏覽器中自動被垃圾回收機制回收。
// 删除指定位置的節點，并傳回被删除的元素的值
removeAt(position) {
// 先判斷index是否在範圍内
if (position >= this.length || position < 0) return false;
// 同樣還要區分是否删除頭節點
let current = this.head
let cur = this.getNodeByposition(position)
if (position === 0) {
this.head = current.next;
} else {
let previous = this.getNodeByposition(position - 1)
previous.next = previous.next.next;
}
this.length--;
return cur
}
4.getNodeBypostion(position)
通過指定位置擷取目前的節點資訊，傳回的是節點類型的資料。
正常方法，将頭指針從頭開始指，将指針向後移動postion次
// 擷取連結清單中對應索引的元素
getNodeByposition(position) {
// 先判斷傳入的position是否正常
if (position < 0 || position > this.length) {
return -1
}
let current = this.head;
while (position--) {
current = current.next
}
return current
}
5.getDataByPostion(position)
通過指定位置來擷取節點的data。正常方法：從頭開始周遊，當指針移動position次時，将node的data傳回。
// 擷取指定索引的值
getDataByPosition(position) {
if (position < 0 || position > this.length) {
return false
}
let current = this.head;
while (position--) {
current = current.next
}
return current.data;
}
6.removeElement(val)
給定值，将連結清單中的改資料的節點删除。正常方法：從頭周遊，将每一個節點的值都與val進行比對，如果相同，就執行删除節點的函數。但這種方法隻考慮到data不相同的情況，如果data相同則隻會删除第一個
// 删除通過值删除連結清單元素
removeElement(val) {
let position = this.getPostionByData(val);
console.log(position);
let previous = this.getNodeByposition(position - 1);
console.log(previous);
let tempNode = previous.next;
if (position > -1) {
previous.next = previous.next.next
return tempNode
}
// 說明沒有找到
else {
return false
}
}
7.clearNode()
清空目前的連結清單。正常方法：将連結清單的長度置零，頭指針置空
// 清空連結清單
clearNode() {
this.head = null;
this.length = 0;
}
8.nodeToString()
将連結清單中每一個節點的資料都列印出來
nodeToString() {
let cur = this.head;
let listStr = '';
while (cur) {
listStr += cur.data + ' '
cur = cur.next
}
return listStr
}
9.updateNode(position,newVal)
将指定位置的節點資料替換。正常方法，先找到指定位置的節點，再将節點資料更新
// 将指定位置的值進行替換
updataNode(position, newVal) {
if (position < -1 || position > this.length) return false;
// 先找到指定位置的節點
let cur = this.getNodeByposition(position);
// 傳回-1則說明沒有找到
if (cur) {
cur.data = newVal
return true;
} else {
return false;
}
}
2.雙向連結清單
雙向連結清單就是在單連結清單的基礎上給連結清單中的每個節點增加一個前驅節點，連結清單可以從頭部周遊，也可以從尾部開始周遊
節點結構
相比于單向連結清單，雙向連結清單中的每個節點都多了一個指向前驅節點的指針。也就是我們可以自由的通路到目前節點的上一個節點以及下一個節點。
// 節點類型
class NodeList {
constructor(val) {
// 包含資料節點，前驅節點以及下一個節點
this.data = val;
this.pre = null;
this.next = null;
}
}
連結清單結構
連結清單中多了一個指向尾部的指針，友善我們從尾部開始周遊
class DoubleLinked {
constructor() {
this.length = 0;
this.head = null;
this.tail = null
}
appendNode(){}
……
}
常用方法
常用的方法與之前的單連結清單類似，但是在細節上稍作變化，常用的比如有：appendNode、insertNode、removeNode、displayList……,使用的輔助方法有：getNodeByPosition、getPositionByData、getDataByPosition、getNodeByData。這裡所說的輔助方法就是可以我們對經常使用的代碼的封裝，友善我們在其它方法中使用
1.appendNode(val)
向連結清單尾部插入元素，插入之前先判斷所插入的是否為頭節點。
appendNode(val) {
if (val == undefined) throw new Error('缺少參數');
let newNode = new NodeList(val)
// 判斷連結清單是否有資料
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
}
// 如果有的話，則向尾部添加
else {
this.tail.next = newNode;
newNode.pre = this.tail;
this.tail = newNode
}
this.length++;
return this.displayList()
}
2.getPositionByData(val)
通過傳遞的值來判斷該元素在連結清單中的索引，比如知道該學生的姓名，但不知道學号，也就是索引。可以從頭部和尾部同時查找，兩個指針同時開始移動，如果連結清單中沒有這個元素才會周遊連結清單。
getPositionByData(val) {
let head = this.head;
let tail = this.tail;
let index = 0;
while (head) {
if (head.data === val) return index;
head = head.next;
if (tail.data === val) return this.length - 1 - index;
tail = tail.pre;
index++;
}
// 否則說明沒有找到，傳回null
return null
}
3.getNodeByData(val)
通過傳遞的值來傳回該值所在的節點，同樣的以學生資訊管理系統為例，我們隻知道這個學生的名字，需要傳回該學生的所有相關資訊，此時就可以使用該方法，傳回該節點，同時該節點中包含前驅指針和後繼指針。
getNodeByData(val) {
// 頭指針和尾指針
let headNode = this.head;
let tailNode = this.tail;
while (headNode) {
if (headNode.data == val) return headNode;
if (tailNode.data == val) return tailNode;
headNode = headNode.next;
tailNode = tailNode.pre;
}
// 沒有找到就傳回null
return null
}
4.getDataByPosition(position)
通過索引來傳回該節點的值，同樣的還是先找到該節點，之後再傳回該節點的值
getDataByPosition(position) {
if (position >= this.length || position < 0) return false;
let middlePosition = Math.floor(position / 2);
let curNode = null;
if (position > middlePosition) {
curNode = this.tail;
let i = this.length - 1;
while (i > position) {
curNode = curNode.pre;
i--
}
} else {
curNode = this.head;
while (position--) {
curNode = curNode.next
}
}
return curNode.data
}
5.getNodeByPosition(position)
傳回指定位置的節點,，比如傳回某個班級中23号同學的資訊。
getNodeByPosition(position) {
if (position >= this.length || position < 0) return false;
// 算法優化，如果大于二分之一，就從尾節點開始周遊
let middlePosition = Math.ceil(position / 2);
// 目前節點
let curNode = null;
if (position >= middlePosition) {
curNode = this.tail;
let i = this.length - 1
// 從後往前執行
while (i > position) {
curNode = curNode.pre;
i--;
}
} else {
curNode = this.head;
while (position--) {
curNode = curNode.next
}
}
return curNode
}
6. insertNode(position,val)
向指定位置插入元素，需要分三種情況進行判斷。先判斷它是否是尾部插入或者是頭部插入，如果是頭部插入的話還需要判斷它是否作為頭節點。最後一種情況則是大多數情況，也就是中間插入。此時隻需要改變前驅節點以及後繼節點的指向即可。
insertNode(position, val) {
if (arguments.length === 1) throw new Error('缺少參數');
if (position >= this.length || position < 0) return '索引越界'
// 判斷是不是尾部插入
if (position === this.length - 1) {
// 尾部插入
return this.appendNode(val);
}
// 判斷是不是頭部插入
else if (position === 0) {
// 判斷是否有頭節點
if (this.head === null) {
this.appendNode(val)
} else {
// 有頭節點的頭部插入
let headNode = new NodeList(val);
headNode.next = this.head;
this.head.pre = headNode;
this.head = headNode;
}
}
// 中間插入，大多數情況
else {
let newNode = new NodeList(val);
let curNode = this.getNodeByPosition(position);
newNode.next = curNode;
newNode.pre = curNode.pre;
curNode.pre.next = newNode;
curNode.pre = newNode;
}
this.length++;
return true
}
7.remoNode(position)
删除指定位置的節點，傳回值為被删除的節點。同樣的還是需要判斷是頭部删除還是尾部删除，中間删除隻需要改變前驅節點和後繼節點的指向即可。
removeNodeByPosition(position) {
// 異常判斷
if (position > this.length - 1 || position < 0) return null;
// 頭部删除
let curNode = this.getNodeByPosition(position)
if (position = 0) {
this.head = this.head.next;
this.head.pre = null;
} else if (position === this.length - 1) {
this.tail = this.tail.pre;
this.tail.next = null;
}
// 移除中間元素
else {
let preNode = curNode.pre;
let nextNode = curNode.next;
preNode.next = nextNode;
nextNode.pre = preNode;
}
this.length--;
return curNode
}
8.displayList(join)
将連結清單中的所有資料以字元串的形式進行拼接并列印。可以接收參數拼接，參數預設為空格。
displayList(join = ' ') {
let curNode = this.head;
let str = '';
while (curNode) {
// 最後一個拼接的後面不用加連接配接的内容
curNode.next !== null ? str += curNode.data + join : str += curNode.data
curNode = curNode.next;
}
return str
}
調用
let linkList = new DoubleLinked()
linkList.appendNode('apple');
linkList.appendNode('banana');
linkList.appendNode('peach');
linkList.appendNode('7777')
linkList.getDataByPosition(2)
linkList.getPositionByData('apple')
console.log(linkList.displayList());
![JavaScript的那些坑之事件代理事件代理事件階段[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)