国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業(yè)教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 你熟悉哪些數(shù)據(jù)結構?

你熟悉哪些數(shù)據(jù)結構?

來源:千鋒教育
發(fā)布人:qyf
時間: 2022-09-20 17:49:25 1663667365

  1. 棧(stack)

  棧(stack)是限制插入和刪除只能在一個位置上進行的表,該位置是表的末端,叫做棧頂(top)。它是后進先出(LIFO)的。對棧的基本操作只有 push(進棧)和 pop(出棧)兩種,前者相當于插入,后者相當于刪除最后的元素。

QQ截圖20220920174215

  2. 隊列(queue)

  隊列是一種特殊的線性表,特殊之處在于它只允許在表的前端(front)進行刪除操作,而在表的后端(rear)進行插入操作,和棧一樣,隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾,進行刪除操作的端稱為隊頭。

  3. 鏈表(Link)

  鏈表是一種數(shù)據(jù)結構,和數(shù)組同級。比如,Java 中我們使用的 ArrayList,其實現(xiàn)原理是數(shù)組。而LinkedList 的實現(xiàn)原理就是鏈表了。鏈表在進行循環(huán)遍歷時效率不高,但是插入和刪除時優(yōu)勢明顯。

  4. 散列表(Hash Table)

  散列表(Hash table,也叫哈希表)是一種查找算法,與鏈表、樹等算法不同的是,散列表算法在查找時不需要進行一系列和關鍵字(關鍵字是數(shù)據(jù)元素中某個數(shù)據(jù)項的值,用以標識一個數(shù)據(jù)元素)的比較操作。

  散列表算法希望能盡量做到不經過任何比較,通過一次存取就能得到所查找的數(shù)據(jù)元素,因而必須要在數(shù)據(jù)元素的存儲位置和它的關鍵字(可用key表示)之間建立一個確定的對應關系,使每個關鍵字和散列表中一個唯一的存儲位置相對應。因此在查找時,只要根據(jù)這個對應關系找到給定關鍵字在散列表中的位置即可。這種對應關系被稱為散列函數(shù)(可用 h(key)表示)。

  用的構造散列函數(shù)的方法有:

  (1)直接定址法: 取關鍵字或關鍵字的某個線性函數(shù)值為散列地址。

  即:h(key) = key 或 h(key) = a * key + b,其中 a 和 b 為常數(shù)。

  (2)數(shù)字分析法

  (3)平方取值法: 取關鍵字平方后的中間幾位為散列地址。

  (4)折疊法:將關鍵字分割成位數(shù)相同的幾部分,然后取這幾部分的疊加和作為散列地址。

  (5)除留余數(shù)法:取關鍵字被某個不大于散列表表長 m 的數(shù) p 除后所得的余數(shù)為散列地址,即:h(key) = key MOD p p ≤ m

  (6)隨機數(shù)法:選擇一個隨機函數(shù),取關鍵字的隨機函數(shù)值為它的散列地址,即:h(key) = random(key)

  5. 排序二叉樹

  首先如果普通二叉樹每個節(jié)點滿足:左子樹所有節(jié)點值小于它的根節(jié)點值,且右子樹所有節(jié)點值大于它的根節(jié)點值,則這樣的二叉樹就是排序二叉樹。

  5.1 插入操作

  首先要從根節(jié)點開始往下找到自己要插入的位置(即新節(jié)點的父節(jié)點);具體流程是:新節(jié)點與當前節(jié)點比較,如果相同則表示已經存在且不能再重復插入;如果小于當前節(jié)點,則到左子樹中尋找,如果左子樹為空則當前節(jié)點為要找的父節(jié)點,新節(jié)點插入到當前節(jié)點的左子樹即可;如果大于當前節(jié)點,則到右子樹中尋找,如果右子樹為空則當前節(jié)點為要找的父節(jié)點,新節(jié)點插入到當前節(jié)點的右子樹即可。

  5.2 刪除操作

  刪除操作主要分為三種情況,即要刪除的節(jié)點無子節(jié)點,要刪除的節(jié)點只有一個子節(jié)點,要刪除的節(jié)點有兩個子節(jié)點。

  對于要刪除的節(jié)點無子節(jié)點可以直接刪除,即讓其父節(jié)點將該子節(jié)點置空即可。

  對于要刪除的節(jié)點只有一個子節(jié)點,則替換要刪除的節(jié)點為其子節(jié)點。

  對于要刪除的節(jié)點有兩個子節(jié)點,則首先找該節(jié)點的替換節(jié)點(即右子樹中最小的節(jié)點),接著替換要刪除的節(jié)點為替換節(jié)點,然后刪除替換節(jié)點。

  5.3 查詢操作

  查找操作的主要流程為:先和根節(jié)點比較,如果相同就返回,如果小于根節(jié)點則到左子樹中遞歸查找,如果大于根節(jié)點則到右子樹中遞歸查找。因此在排序二叉樹中可以很容易獲取最大(最右最深子節(jié)點)和最小(最左最深子節(jié)點)值。

tags:
聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業(yè)內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT