javascript有資料結構嗎

WBOY
發布: 2022-06-17 11:01:22
原創
2039 人瀏覽過

javascript中有資料結構,資料結構是指彼此之間存在一種或多種特定關係的資料元素集合;資料結構能夠有效的管理資料對象,提升運算效能,JavaScript中的資料結構有列表、棧、佇列、鍊錶、字典、雜湊、圖和二元查找樹。

javascript有資料結構嗎

本教學操作環境:windows10系統、javascript1.8.5版、Dell G3電腦。

javascript有資料結構嗎

javascript有資料結構

#資料結構:列表、堆疊、佇列、鍊錶、字典、雜湊、圖和二元查找樹

清單

在日常生活中,人們經常使用清單:待辦事項清單、購物清單、最佳十名榜單等等。而電腦程式也在使用列表,在下面的條件下,選擇列表作為資料結構就顯得特別有用:

資料結構較為簡單

不需要在一個長序列中尋找元素,或者對其進行排序

反之,如果資料結構非常複雜,列表的作用就沒有那麼大了。

堆疊

堆疊是一種特殊的列表,堆疊內的元素只能透過列表的一端訪問,這一端稱為棧頂。想像一下,我們平常在飯館見到的一疊盤子就是現實世界常見的棧的例子,只能從最上面取盤子,盤子洗乾淨後,也只能放在最上面。棧被稱為一種後入先出的資料結構。是一種高效率的資料結構,因為資料只能在堆疊頂部新增或刪除,所以這樣的操作很快。

使用條件:

只要資料的保存滿足後入先出或先進後出的原理,都優先考慮使用堆疊

##佇列

隊列也是一種列表,不同的是隊列只能在隊尾插入元素,在隊首刪除元素。想像一下,我們在銀行排隊,排在最前面的人第一個辦理業務,而後面來的人只能排在隊伍的後面,直到輪到他們為止。

使用條件:

只要資料的保存符合先進先出、後入後出的原理,都優先考慮使用佇列

常見應用程式場景:

佇列主要用在和時間有關的地方,特別是作業系統中,佇列是實作多任務的重要機制

訊息機制可以透過佇列來實現,行程調度也是使用佇列來實作

鍊錶

鍊錶也是一種列表,為什麼需要出現鍊錶,JavaScript中數組的主要問題時,它們被實現成了對象,與其他語言(如C 和Java)的陣列相對,效率很低。如果你發現數組在實際使用時很慢,就可以考慮使用鍊錶來取代它。

使用條件:

鍊錶幾乎可以用在任何可以使用一維陣列的情況中。如果需要隨機訪問,數組仍然是更好的選擇。

字典

字典是一種以鍵-值對行駛儲存資料的資料結構,JavaScript中的Object類別就是以字典的形式設計的。 JavaScript可以透過實作字典類,讓這種字典類型的物件使用起來更簡單,字典可以實作物件擁有的常見功能,並且相應地拓展自己想要的功能,而物件在JavaScript編寫中隨處可見,所以字典的作用也異常明顯了。

雜湊

雜湊(也稱為雜湊表)是一種的常用的陣列儲存技術,散列後的數組可以快速插入或取用。散列使​​用的資料結構叫做散列表。在散列表上插入、刪除和取用資料都非常快,但對於查找操作來說卻效率低下,例如查找一組數組中的最大值和最小值。這些操作需要求助於其他資料結構,例如下面介紹的二元查找樹。

散列表在JavaScript中可以基礎陣列去進行設計。數組的長度是預先設定的,所有元素根據和該元素對應的鍵,保存在數組的特定位置,這裡的鍵和物件的鍵是類型的概念。使用散列表儲存數組時,透過一個雜湊函數將鍵映射為一個數字,這個數字的範圍是0到散列表的長度。

即使使用一個高效的雜湊函數,依然存在將兩個鍵映射為同一個值得可能,這種現象叫做碰撞。常見碰撞的處理方法有:開鏈法與線性偵測法(具體概念有興趣的可以網路上自信了解)

使用條件:

可以用於資料的插入、刪除、取用,不適用於查找資料

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

使用場景(用圖表對現實中的系統建模):

交通系統,可以用頂點表示街道的十字路口,邊可以表示街道。加權的邊可以表示限速或車道的數量。可以用此系統判斷最佳路線及最有可能塞車的街道。

任何運輸系統都可以用圖來建模。例如,航空公司可以用圖來為其飛行系統建模。將每個機場看成頂點,將經過兩個頂點的每條航線視為一條邊。加權的邊可以表示從一個機場到另一個機場的航班成本,或兩個機場間的距離,這取決於建模的物件是什麼。

搜尋圖的演算法主要有兩種: 深度優先搜尋和廣度優先搜尋。

二元樹和二元查找樹

#樹是電腦科學中常用到的一種資料結構。樹是一種非線性的資料結構,以分層的方式儲存資料。

二元樹每個節點的子節點不允許超過兩個。一個父節點的兩個子節點分別稱為左節點和右節點,透過將子節點的個數限定為2,可以寫出高效率的程式在樹中插入、尋找和刪除資料。

二元查找樹(BST)是一種特殊的二元樹,相對較小的值保存在左節點中,較大的值保存在右節點中。這項特性使得查找的效率很高,對於數值型和非數值型的數據,例如單字和字串,都是如此。

二元尋找樹實作方法

function Node(data, left, right) { // 创建节点
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show
}
function show () { // 显示树的数据
  return this.data
}
function BST () { // 二叉查找树类
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder; // inOrder是遍历BST的方式
}
function insert (data) { // 向树中插入数据
  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的方式有三種:中序遍歷(以升序訪問樹中所有節點,先訪問左節點,再訪問根節點,最後訪問右節點)、先序遍歷(先訪問根節點,再以同樣的方式訪問左節點和右節點)、後序遍歷(先訪問葉子節點,從左子樹到右子樹,再到根節點)

【相關推薦:javascript影片教學web前端

以上是javascript有資料結構嗎的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板