javascript有沒有數(shù)據(jù)結(jié)構(gòu)

這篇文章主要講解了“javascript有沒有數(shù)據(jù)結(jié)構(gòu)”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“javascript有沒有數(shù)據(jù)結(jié)構(gòu)”吧！

javascript中有數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或者多種特定關(guān)系的數(shù)據(jù)元素集合；數(shù)據(jù)結(jié)構(gòu)能夠有效的管理數(shù)據(jù)對象，提升運(yùn)算性能，JavaScript中的數(shù)據(jù)結(jié)構(gòu)有列表、棧、隊列、鏈表、字典、散列、圖和二叉查找樹。

本教程操作環(huán)境：windows10系統(tǒng)、javascript1.8.5版、Dell G3電腦。

javascript有數(shù)據(jù)結(jié)構(gòu)嗎

javascript有數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)：列表、棧、隊列、鏈表、字典、散列、圖和二叉查找樹

列表

在日常生活中，人們經(jīng)常使用列表：待辦事項列表、購物清單、最佳十名榜單等等。而計算機(jī)程序也在使用列表，在下面的條件下，選擇列表作為數(shù)據(jù)結(jié)構(gòu)就顯得尤為有用：

數(shù)據(jù)結(jié)構(gòu)較為簡單

不需要在一個長序列中查找元素，或者對其進(jìn)行排序

反之，如果數(shù)據(jù)結(jié)構(gòu)非常復(fù)雜，列表的作用就沒有那么大了。

棧

棧是一種特殊的列表，棧內(nèi)的元素只能通過列表的一端訪問，這一端稱為棧頂。想象一下，我們平常在飯館見到的一摞盤子就是現(xiàn)實(shí)世界常見的棧的例子，只能從最上面取盤子，盤子洗干凈后，也只能放在最上面。棧被稱為一種后入先出的數(shù)據(jù)結(jié)構(gòu)。是一種高效的數(shù)據(jù)結(jié)構(gòu)，因?yàn)閿?shù)據(jù)只能在棧頂添加或刪除，所以這樣的操作很快。

使用條件：

只要數(shù)據(jù)的保存滿足后入先出或先進(jìn)后出的原理，都優(yōu)先考慮使用棧

隊列

隊列也是一種列表，不同的是隊列只能在隊尾插入元素，在隊首刪除元素。想象一下，我們在銀行排隊，排在最前面的人第一個辦理業(yè)務(wù)，而后面來的人只能排在隊伍的后面，直到輪到他們?yōu)橹埂?/p>

使用條件：

只要數(shù)據(jù)的保存滿足先進(jìn)先出、后入后出的原理，都優(yōu)先考慮使用隊列

常見應(yīng)用場景：

隊列主要用在和時間有關(guān)的地方，特別是操作系統(tǒng)中，隊列是實(shí)現(xiàn)多任務(wù)的重要機(jī)制

消息機(jī)制可以通過隊列來實(shí)現(xiàn)，進(jìn)程調(diào)度也是使用隊列來實(shí)現(xiàn)

鏈表

鏈表也是一種列表，為什么需要出現(xiàn)鏈表，JavaScript中數(shù)組的主要問題時，它們被實(shí)現(xiàn)成了對象，與其他語言（比如C++和Java）的數(shù)組相對，效率很低。如果你發(fā)現(xiàn)數(shù)組在實(shí)際使用時很慢，就可以考慮使用鏈表來代替它。

使用條件：

鏈表幾乎可以用在任何可以使用一維數(shù)組的情況中。如果需要隨機(jī)訪問，數(shù)組仍然是更好的選擇。

字典

字典是一種以鍵-值對行駛存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，JavaScript中的Object類就是以字典的形式設(shè)計的。JavaScript可以通過實(shí)現(xiàn)字典類，讓這種字典類型的對象使用起來更加簡單，字典可以實(shí)現(xiàn)對象擁有的常見功能，并相應(yīng)拓展自己想要的功能，而對象在JavaScript編寫中隨處可見，所以字典的作用也異常明顯了。

散列

散列（也稱為哈希表）是一種的常用的數(shù)組存儲技術(shù)，散列后的數(shù)組可以快速地插入或取用。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。在散列表上插入、刪除和取用數(shù)據(jù)都非常快，但對于查找操作來說卻效率低下，比如查找一組數(shù)組中的最大值和最小值。這些操作需要求助于其他數(shù)據(jù)結(jié)構(gòu)，比如下面介紹的二叉查找樹。

散列表在JavaScript中可以基礎(chǔ)數(shù)組去進(jìn)行設(shè)計。數(shù)組的長度是預(yù)先設(shè)定的，所有元素根據(jù)和該元素對應(yīng)的鍵，保存在數(shù)組的特定位置，這里的鍵和對象的鍵是類型的概念。使用散列表存儲數(shù)組時，通過一個散列函數(shù)將鍵映射為一個數(shù)字，這個數(shù)字的范圍是0到散列表的長度。

即使使用一個高效的散列函數(shù)，依然存在將兩個鍵映射為同一個值得可能，這種現(xiàn)象叫做碰撞。常見碰撞的處理方法有：開鏈法和線性探測法（具體概念有興趣的可以網(wǎng)上自信了解）

使用條件：

可以用于數(shù)據(jù)的插入、刪除和取用，不適用于查找數(shù)據(jù)

圖

圖由邊的集合及頂點(diǎn)的集合組成。地圖是我們身邊很常見的現(xiàn)實(shí)場景，比如每兩個城鎮(zhèn)都由某種道路相連。上面的每個城鎮(zhèn)可以看作一個頂點(diǎn)，連接城鎮(zhèn)的道路便是邊。邊由頂點(diǎn)對（v1, v2）定義，v1和v2分別是圖中的兩個頂點(diǎn)。頂點(diǎn)也有權(quán)重，也成為成本。如果一個圖的頂點(diǎn)對是有序的，則稱之為有向圖（例如常見的流程圖），反之，稱之為無序圖。

使用場景（用圖對現(xiàn)實(shí)中的系統(tǒng)建模）：

交通系統(tǒng)，可以用頂點(diǎn)表示街道的十字路口，邊可以表示街道。加權(quán)的邊可以表示限速或者車道的數(shù)量。可以用該系統(tǒng)判斷最佳路線及最有可能堵車的街道。

任何運(yùn)輸系統(tǒng)都可以用圖來建模。比如，航空公司可以用圖來為其飛行系統(tǒng)建模。將每個機(jī)場看成頂點(diǎn)，將經(jīng)過兩個頂點(diǎn)的每條航線看作一條邊。加權(quán)的邊可以表示從一個機(jī)場到另一個機(jī)場的航班成本，或兩個機(jī)場間的距離，這取決于建模的對象是什么。

搜索圖的算法主要有兩種： 深度優(yōu)先搜索和廣度優(yōu)先搜索。

二叉樹和二叉查找樹

樹是計算機(jī)科學(xué)中經(jīng)常用到的一種數(shù)據(jù)結(jié)構(gòu)。樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式存儲數(shù)據(jù)。

二叉樹每個節(jié)點(diǎn)的子節(jié)點(diǎn)不允許超過兩個。一個父節(jié)點(diǎn)的兩個子節(jié)點(diǎn)分別稱為左節(jié)點(diǎn)和右節(jié)點(diǎn)，通過將子節(jié)點(diǎn)的個數(shù)限定為2，可以寫出高效的程序在樹中插入、查找和刪除數(shù)據(jù)。

二叉查找樹（BST）是一種特殊的二叉樹，相對較小的值保存在左節(jié)點(diǎn)中，較大的值保存在右節(jié)點(diǎn)中。這一特性使得查找的效率很高，對于數(shù)值型和非數(shù)值型的數(shù)據(jù)，比如單詞和字符串，都是如此。

二叉查找樹實(shí)現(xiàn)方法

function Node(data, left, right) { // 創(chuàng)建節(jié)點(diǎn)
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show
}
function show () { // 顯示樹的數(shù)據(jù)
  return this.data
}
function BST () { // 二叉查找樹類
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder; // inOrder是遍歷BST的方式
}
function insert (data) { // 向樹中插入數(shù)據(jù)
  var n = new Node(data, null, null)
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
  parent = current
  if (data < current.data) {
current = current.left;
if (current == null) {
  parent.left = n;
  break;
}
  } else {
current = current.right;
if (current == null) {
  parent.right = n;
  break;
}
  }
    }
  }
}

遍歷BST的方式有三種：中序遍歷（以升序訪問樹中所有節(jié)點(diǎn)，先訪問左節(jié)點(diǎn)，再訪問根節(jié)點(diǎn)，最后訪問右節(jié)點(diǎn)）、先序遍歷（先訪問根節(jié)點(diǎn)，再以同樣的方式訪問左節(jié)點(diǎn)和右節(jié)點(diǎn)）、后序遍歷（先訪問葉子節(jié)點(diǎn)，從左子樹到右子樹，再到根節(jié)點(diǎn)）

感謝各位的閱讀，以上就是“javascript有沒有數(shù)據(jù)結(jié)構(gòu)”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對javascript有沒有數(shù)據(jù)結(jié)構(gòu)這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！