JS數據結構與算法總結 （第一篇）

一.數據結構簡介（序）：

程序設計 = 數據結構 + 算法。

數據 = 符號

(1). 其可以輸入到計算機中。

(2). 能夠被計算機識別和處理。

數據分為：

(1).數據元素：數據的基本單位，也稱為結點或者記錄。

(2).數據對象: 相同特性的數據元素的集合，是數據的一個子集。

(3).數據項: 獨立含義的數據的最小單位。

數據的目的是存儲，存儲的目的是后期的再利用。

數據結構的主要作用是:闡述關系。

如何存儲具有復雜關系的數據更有助于后期對數據的再利用。

結構:

簡單的理解就是關系，不同的數據元素之間不是獨立的。而是存在特定的關系。

(1). 邏輯結構:

數據對象中數據元素之間的互相關系。

四種:

集合結構、線性結構、樹形結構、圖形結構.

集合結構: 數據元素同屬于個集合， 他們之間沒有其他的關系。他們的共同屬性是:“同屬于一個集合”。

線性結構: 最典型的數據關系是一對一。線性結構是種有序數據的集合。除了第一個和最后一個數據元素之外，其他數據元素都是首尾相接的。

1.必存在一個第一個元素。

2.必存在最后的一個元素。

3.除最后一個元素外，其他的數據元素均有一個唯一的后續”。

4.除第一個元素之外，其他數據元素均有一個唯一的前驅。

比如：數組， 棧，隊列，等都是一個線性結構。

樹形結構：數據元素一對多的關系。如 Dom Tree。

圖形結構：多對多的關系。如 地圖。

（2）.物理結構： 數據元素存儲到計算中的存儲器（內存）。數據的存儲結構應該正確的反應數據元素之間的邏輯關系。包括順序存儲和鏈式存儲。

順序存儲： 該結構是把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元中，結點之間的邏輯關系由存儲單元的鄰接關系來體現。

鏈式存儲： 在計算機中用一組任意的存儲單元存儲線性表的數據元素(這組存儲單元可以是連續的,也可以是不連續的)。它不要求邏輯上相鄰的元素在物理位置上也相鄰.因此它沒有順序存儲結構所具有的弱點,但也同時失去了順序表可隨機存取的優點。

二.算法簡介（序）：

算法（Algorithm）是指解題方-而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。簡單來說，算法是解決問題的方法和步驟。數據結構的實現離不開算法。

聲明： JS數組不是真正意義上的數組。

傳統數組是在內存中用一串連續的區域存放具有相同類型的元素。

但是，如一個js數組如下：

const arr = [123,'a',"啦啦"];

可以看出 JS 數組元素是可以任意類型的，內存地址是不連續的。所以它不是真正意義上的數組。但是它好用呀。

數組的優點：

（1）按照索引查詢元素速度快；

（2）能存儲大量數據；

（3）按照索引遍歷數組方便；

（4）定義簡單，而且訪問靈活；

數組的缺點：

（1）根據內容查找元素速度很慢；

（2）數組的大小一經確定不能改變，不適合動態存儲；

（3）數組只能存儲一種類型的數據；

（4）增加、刪除元素效率慢；

（5）未封裝任何方法，所有操作都需要用戶自己定義；

三.棧與隊列：

（1）內存中的堆棧和數據結構中的堆棧不是一個概念， 內存中的堆棧是真實存在的物理區,數據結構中的堆棧是抽象數據存儲結構。

（2）棧又名堆棧，它是一種運算受限的線性表。它遵循后進先出（LIFO）原則。

（3）受限制意思就是在新增數據、刪除數據、查找等操作時，不能隨心所欲，必須遵循一定的限制(規則)。

（4）向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面,使之成為新的棧頂元素。

（5）從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為

新的棧頂元素

//定義一個類，相當函數 class Stack{ // 構造方法 constructor(){ this.items = []; } //添加方法，入棧頂 push(ele){ this.items.push(ele); } //出棧 pop(){ //pop() 方法用于刪除并返回數組的最后一個元素。 return this.items.pop(); } //返回棧頂元素 peek(){ return this.items[this.items.length-1]; } //判斷是否為空 isEmpty(){ return this.items.length===0; } //返回元素個數 size(){ return this.items.length() } //清空 clear(){ this.items = []; } }

let arr = [1,2,3];

arr.length = 0;

arr = [];

arr.splice(0,arr.length);

執行上下文： 就是當前JavaScript代碼被解析和執行是所在環境的抽象概念，JavaScript中運行任何的代碼都是在執行上下文中運行。（執行環境）。分為以下三種：

（1） 全局執行上下文： 默認的，最基礎的執行上下文。共兩個過程：1.創建全局對象，在瀏覽器中這個全局對象就是window對象。2.將this指針指向這個全局對象。

（2）函數執行上下文： 每次調用函數時，都會為該函數創建一個新的執行上下文。每個函數都擁有自己的執行上下文，但是只有在函數被調用的時候才會被創建。

（3）Eval函數執行上下文： eval() 函數可計算某個字符串，并執行其中的的 JavaScript 代碼。運行在eval函數中的代碼也獲得了自己的執行上下文。

執行棧： 執行棧，也叫調用棧，遵循LIFO原則。用于存儲在代碼執行期間創建的所有執行上下文。如下代碼：

const one = ()=>{ two(); console.log('I am one'); } const two = () =>{ console.log('I am two'); } one();

結果：

·當上述代碼在瀏覽器中加載時，JavaScript 引擎會創建一個全局執行上下文并且將它推入到當前的執行棧。

·?當調用 one函數時，JavaScript 引擎會為該函數創建了一個新的執行上下文并將其push推到當前執行棧的棧頂。

·?當在 one() 函數中調用 two() 函數時，Javascript 引擎為該函數創建了一個新的執行上下文并將其推到當前執行棧的棧頂。

·?當two() 函數執行完成后，它的執行上下文從當前執行棧中彈出。上下文控制權將移到當前執行棧的下一個執行上下文，即 one() 函數。

從上可以知道，函數的調用的本質為壓棧與出棧操作。

函數在調用棧里邊有一個特例，叫做遞歸。

遞歸，就是在運行的過程中調用自己。會產生一個叫遞歸棧。

先進棧，到條件后就出棧。如果不出棧，由于遞歸調用次數過多，堆棧溢出。因為堆棧的大小是系統控制的，無法改變。

遞歸例子，算階乘：

const factorial = (n) =>{ //判斷出口 if(n===1){ return 1; } //遞歸 return n*factorial(n-1); } //輸出3階乘 console.log(factorial(3));

結果：

遞歸例子，斐波那契數列：

斐波那契數列指的是這樣一個數列：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…

第3項開始，每一項都等于前兩項之和。

現在求輸入第幾項后輸出數列對應的數字：

const Fibonaqi = n=>{ if(n<2){ return n; } return Fibonaqi(n-1)+Fibonaqi(n-2); } console.log(Fibonaqi(5));

這代碼有個問題，會進行非常多重復的計算，需要同時保存多個調用幀，可能導致消耗內存，爆棧。假如 n 為 5 執行過程如下：

Fib(5)=Fib(4)+Fib(3) =5 Fib(4)=Fib(3)+Fib(2) =3 Fib(3)=Fib(2)+Fib(1) =2 Fib(2)=Fib(1)+Fib(0) =1 Fib(1)= 1 Fib(0)= 0

可采用尾遞歸方式解決。首先理解概念：

尾調用： 尾調是在函數的執行過程中最后一個動作是一個函數的調用，即這個調用的返回值被當前函數直接返回。如下：

function g(x) { } function f(x) { return g(x) }

尾遞歸： 而尾遞歸指最后的尾調用位置上是這個函數本身。首先執行計算出一次的結果，然后執行遞歸調用，將當前步驟的結果值傳遞給下一個遞歸步驟。每次遞歸都不會增加調用棧的長度，只是更新當前的堆棧幀，只存在一個調用幀，避免了內存的消耗。

尾遞歸實現斐波那契數列：

int Fibonaqi(int n, int ret1, int ret2) { if (n ==0 ) { //結果 return ret1; } else { return Fib(n - 1, ret2, ret1 +ret2); } }

執行過程：

Fib (5, 0,1)=Fib (4, 1, 1) =1 Fib (4,1,1)=Fib (3, 1,2) =1 Fib (3, 1,2)=Fib (2,2, 3) =2 Fib (2,2,3)=Fib (1,3, 5) =3 Fib(1,3,5)=Fib (0,5, 8) =5

尾遞歸的階乘，這個好理解點：

int facttail(int n, int a) { if (n < 0) return 0; else if (n == 0) return 1; else if (n == 1) return a; else return facttail(n - 1, n * a); }

隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。遵循 FIFO，先進先出。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

//定義一個類，實質也是一個函數 class Queue{ //定義一個構造方法 constructor(){ //實例對象 this.items = []; } //入隊方法 enqueue(ele){ this.items.push(ele); } //出隊方法 dequeue(){ //shift()方法可用于把數組的第一個元素從其中刪除，并返回第一個元素的值。 return this.items.shift(); } //查看隊首元素 front(){ return this.items[0]; } //查看隊尾 rear(){ return this.items[this.items.length-1]; } //查看隊尾是否為空 isEmpty(){ return this.items.length === 0; } //查看長度 size(){ return this.items.length; } //清空隊列 clear(){ this.items = []; } }

使用看：

const queue = new Queue(); queue.enqueue(2); queue.enqueue(5); queue.enqueue(5); console.log(queue); console.log(queue.size());

運行結果正確：

首先JavaScript是單線程的，同一個時間只能做一件事。

為什么 JavaScript 是單線程 ？這主要和js的用途有關，js是作為瀏覽器的腳本語言，主要是實現用戶與瀏覽器的交互，以及操作dom；這決定了它只能是單線程，否則會帶來很復雜的同步問題。比如，假定JavaScript同時有兩個線程，一個線程在某個 DOM 節點上添加內容，另一個線程刪除了這個節點，這時瀏覽器就不知道以哪個線程為準。

為了利用多核 CPU 的計算能力，HTML5 提出 Web Worker 標準，允許 JavaScript

腳本創建多個線程，但是子線程完全受主線程控制，且不得操作 DOM。所以，這個新標準并沒有改變 JavaScript 單線程的本質。

單線程就意味著，所有任務需要排隊，前一個任務結束，才會執行后一個任務。 如果前一個任務耗時很長，如發起一個請求， 網絡很慢，那后面的那個任務是不是就要一直等著。這樣就很不好，那肯定不可以呀，所以js這樣解決。

如在I0的時候，(輸入輸出的時候) ,主線程不去管IO，掛起處于等待中的任務，先運行排在后面的任務，等待I0設備返回了結果，再回過頭，把掛起等待的任務繼續執行下去。

于是所有的任務可以分為: 同步任務，異步任務。

同步任務: 在主線程上排隊執行的任務，只有前一個任務執行完畢以后，才能夠去執行下一個任務。

異步任務: 不進入主線程，而是進入任務隊列，（任務隊列就是主線程維護的一個任務隊列，保存著異步代碼），只有任務隊列通知主線程，某個異步任務可以執行了，這個任務才會進入主線程執行。

有下面的代碼，說出輸出順序：

console.log(1); setTimeout(()=>{ console.log(2); },60) setTimeout(()=>{ console.log(3); },0) console.log(4);

答案如下：1,4,3,2

最先執行的是同步代碼，執行完畢以后，立即出棧，讓出主線程。

同步代碼執行完畢，立即出棧，此時主線程是處于空閑狀態了。

則此時主線程去讀取任務隊列，隊列遵循的原則是先進先出。但是，有個條件，觸發條件相等既優先級一樣，會遵循先進先出。就是誰先進隊列誰先出去主線程運行。但是如果觸發條件不相同，則優先執行到達觸發條件的代碼先出去。明顯等待0秒的優先級更高，主線程有空就立即執行。

主線程執行完畢以后，從事件隊列中去讀取任務隊列的過程，我們稱之為事件循環。(Event Loop)

判斷以下代碼輸出：

// 宏任務 setTimeout(()=>{ console.log('1'); },0) // 同步任務 const promise = new Promise((resolve,reject)=>{ console.log('2'); resolve(); //微任務 }).then(()=>{ console.log('3'); })

結果：

任務隊列里又存在著宏任務隊列和微任務隊列，執行完同步任務后，先執行微任務再執行宏任務。

常見宏任務隊列：lO、定時器、事件綁定、ajax …等

常見微任務隊列：Promise.then catch、 finally、 process.nextTick…等

四.鏈表：

官方解釋是：

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構，操作復雜。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)。

使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點，同時鏈表由于增加了結點的指針域，空間開銷比較大。鏈表最明顯的好處就是，常規數組排列關聯項目的方式可能不同于這些數據項目在記憶體或磁盤上順序，數據的存取往往要在不同的排列順序中轉換。鏈表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。鏈表可以在多種編程語言中實現。

簡單來說就是：

鏈表： 內存地址可以是連續的，也可以是不連續的。把數據元素存放在任意的存儲單元里，指針來存放數據元素的地址。

數組： 大小是固定的，一經聲明就要占用整塊的連續的內存空間。如果說，聲明的數組過大，系統可能沒有足夠的連續的內存空間用于分配，(out of memory)內存不足。如果聲明的數組過小，當不夠用時，又需要去重新一塊更大的內存，還要數據拷貝。但是數組查找元素很快。

單向鏈表結構圖：

鏈表的每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用(有些語言稱為指針或者鏈接)組成。

總而言之：

插入和刪除： 鏈表性能更好。

查詢和修改： 數組性能更好。

// 結點的類 class Node { constructor(element){ this.element = element; this.next = null; } } // 鏈表類 class LinkedList { constructor(){ //有個鏈表頭 this.head = null; //鏈表長度 this.length = 0; } // 實現在鏈表尾部追加元素 append(element){ //新建一個結點 let node = new Node(element); //先看鏈表是不是空 if(this.length===0){ //為空這個結點就為表頭 this.head = node; }else{ //變量,當前結點，通過從head開始遍歷找到最后的結點 let current = this.head; while(current.next){ current = current.next; } //循環結束，則current為最后一個結點 //添加新結點 current.next = node; } // 長度加1 this.length+=1; } //獲取鏈表頭 getHead(){ return this.head; } //toString方法,就是輸出鏈表內容 toString(){ let current = this.head; let linkString = ''; //遍歷鏈表，把每個結點內容用linkString拼接起來 while(current.next){ linkString+= ','+current.element; current = current.next; } //添加最后一個結點內容 linkString+= ','+current.element; //返回內容 return linkString.slice(1); } //插入在任意位置插入元素，element是內容，position是位置 insert(element,position){ //先判斷位置是有效值 if(position<0||position>this.length){ return false; } // 以下是位置有效 // 記錄索引 let index = 0; //當前結點 let current = this.head; //上一個結點 let previous = null; //創建元素 let node = new Node(element); //判斷插入是不是第一個 if(position===0){ node.next=this.head; this.head=node; }else{ while(indexthis.length){ return false; } //當前結點從頭開始 let current = this.head; let index = 0; //老樣子遍歷 while(indexthis.length){ return false; } // 以下是位置有效 // 記錄索引 let index = 0; //當前結點 let current = this.head; //上一個結點 let previous = null; //判斷插入是不是第一個 if(position===0){ //頭結點變為第二個 this.head = this.head.next; }else{ while(index

測試下：

const linkedList = new LinkedList(); //添加1,2,3,4, linkedList.append(1); linkedList.append(2); linkedList.append(3); linkedList.append(4); //刪除第二個 linkedList.removeAt(2); //輸出長度 console.log(linkedList.length); //輸出內容 console.log(linkedList.toString()); console.log(linkedList);

結果沒問題：

首先知道，JS是基于對象設計和開發出來的語言。而面向對象有三大特點: (封裝、 繼承于多態)。但是基于對象是使用對象，我們無法利用現有的對象模板去產生新的對象類型，繼而去產生一個新的對象，也就是說基于對象是沒有繼承的特點。但是面向對象對象實現了繼承和多態，基于現象是沒有實現這些的。

oop面向對象的支持兩種繼承方式:接口繼承、實現繼承。

ECMAscript是無法去實現去接口繼承的，JS只支持實現繼承。實現繼承主要依靠原型鏈去實現。

接下來簡單介紹 prototype 和 _ _ proto _ _ 。

所有的引用類型(數組、函數、對象)可以自由的擴展屬性(nul除外）。

所有的引用類型都有一個_ _ proto _ _屬性(隱式原型，其實就是一個普通的對象。

所有的函數都有一個prototype 屬性，(顯式原型，它也是一個普通的對象)。

所有的引用類型，它的_ _ proto _ _屬性指向它的構造函數的prototype屬性。

當你試圖得到一個對象的屬性時，如果這個對象的本身不存在這個屬性，那么就會去它的_ _ proto _ _屬性中去尋找(去它的構造函數的protorype屬性)中去尋找。

當調用這個對象本身并不存在的屬性或者是方法時，它會一層層地往上找，一直找到null為止，null表示空的對象{ }。

//有一個構造函數 function People(name,age){ this.name = name; this.age = age; //它有一個say函數方法 this.say = function(){ console.log('哈哈哈，你也能用我啦~'); } } // 空的構造方法 function Xiaoming(){} // 我想讓Xiaoming也有People里面的say方法。 // 利用原型鏈機制，讓一個引用類型繼承另一個引用類型的屬性和方法 Xiaoming.prototype = new People('小明',18); var xiaoming = new Xiaoming(); xiaoming.say(); //它會像鏈子一樣一層一層往上找，直到找到null，找到null則無路可走了證明找到了

運行結果：

五.哈希表：

哈希：

hash，一般可以稱為散列。其是把任意長度的輸入通過散列算法變換成固定長度的輸出，那么輸出的值就是散列值。這種轉換是一種壓縮映射。 映射表達是一 一對應的關系， 也就是說，散列值的空間通常會小于輸入的空間。而且注意的是，哈希算法不能從結果去推算出輸入，也就是說哈希算法是不可逆的。既然哈希特性是不可逆，那么哈希算法是可以當作一種加密算法存在的。哈希算法可以運用在加密算法上。

眾所周知，數組的查詢效率很高，但是，有個前提，那就是按照索引進行查找效率才高，如果是按照內容查找的話效率還是比較低的。

如下：

//有一個數組 const arr = [ {name:'xiaoming',age:18}, {name:'xiaobai',age:20} ] //直接從索引找xiaoming，速度快 console.log(arr[0]); //按照內容找xiaoming，速度慢 for(let i=0;i

那有沒有一種方法，能將名字name作為索引，來提高查找速度呢？就是將字符串作為數組的索引。當然，肯定有呀，那就是----哈希表。

哈希表通常是基于數組實現的，但是相對于數組，它有很多的優勢。那就是它可以提供非常非常快速的插入、刪除、查找等操作。其實哈希表的結構就是數組，但是它和數組的也有不一樣的地方就是哈希表對于索引的一種轉換。這種轉換我們通常稱之為哈希函數。

一個單詞如何轉換為數字索引呢？

我們可以通過ASCLL碼轉換，每個字母都有一個對應的ASCLL碼，我們可以通過把每個碼相加的和作為其的數字索引。

如，有一個 name：xiao，那么xiao的ASCLL碼和如下：

xiao = x + i + a + o = 120+105+97+111 = 433

那么，我們可以這樣存：

arr[433] = {name:'xiao',age:20} ;

這樣就可以通過索引快速查找。可以更好理解以下哈希表概念：

哈希表：

哈希表(Hash table) ，也叫散列表，是根據關鍵碼值(Key value) 而直接進行訪問的數據結構。

它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。

這個起到映射作用的叫做散列函數(Hash Function) ,存放記錄的數組叫做哈希表(或者散列表)。

給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數后若能得到包含該關鍵字的記錄在表中的地址。

發現一個問題，上面每個碼相加的和作為其的數字索引的這個哈希函數得的結果會出現重復，比如 xiao 和 xioa 得到的關鍵碼是一樣的。總而來說就是對不同的關鍵字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，這種現象稱為沖突，這個后面可能講。

class HashTable{ constructor(){ // 用數組表示哈希表 this.table = []; } // 哈希函數 loseloseHashCode(key){ let hash = 0; for(let i=0;i

測試測試：

onst hashtable = new HashTable(); //添加兩個元素 hashtable.put('小明','age:18'); hashtable.put('小紅','age:20'); // 找小明的年紀 console.log(hashtable.get('小明'));

結果：

通過哈希函數得的重復的結果會產生覆蓋問題，就是后面添加的覆蓋前面添加的。這樣一來前面的數據不就丟失了？那咋辦呢？如下：

線性探測法：

假如如下圖，我們要存一個35，哈希函數就是對其除10取余，經過哈希化得到的是index = 5,但是在插入的時候，發現這個5位置已經有了值78,那怎么辦呢，那我們可以去index+1的位置，看看有沒有空的位置，不空的話繼續往下一點點的查找合適的位置來放置35。總結就是尋找空白的位置來放置沖突的數據項。

這樣的話查找的時候也是一樣，看看對應的關鍵碼位置的值是不是自己想要的，如果不是就往下一點一點查找對比是不是自己想要的，如果一直查到空的位置都沒有，那就停下查找了。因為既然有的話它會放在這個空位置的。當然，這個方法缺點也很明顯，那就是萬一很多連續的數據一起的，那就要找很久，耗性能。 需要注意的是對于利用開放地址法處理沖突所產生的哈希表中刪除一個元素時不能直接地刪除，因為這樣將會截斷其他具有相同哈希地址的元素的查找地址，通常可以采用設定一個特殊的標志以示該元素已被刪除。

鏈地址法：

鏈地址法前面也是一樣的，通過哈希函數計算關鍵碼然后插入數值，不同的是它是插入是鏈表。就是說如果有關鍵碼一樣的，就插在這個關鍵碼地址對應的鏈表上。

就是下面這種感覺：

六.樹：請看第二篇~

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。