本篇內(nèi)容主要講解“有哪些JAVA必須掌握的數(shù)據(jù)結(jié)構(gòu)和算法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“有哪些JAVA必須掌握的數(shù)據(jù)結(jié)構(gòu)和算法”吧!

創(chuàng)新互聯(lián)公司自成立以來，一直致力于為企業(yè)提供從網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、成都做網(wǎng)站、電子商務(wù)、網(wǎng)站推廣、網(wǎng)站優(yōu)化到為企業(yè)提供個(gè)性化軟件開發(fā)等基于互聯(lián)網(wǎng)的全面整合營(yíng)銷服務(wù)。公司擁有豐富的網(wǎng)站建設(shè)和互聯(lián)網(wǎng)應(yīng)用系統(tǒng)開發(fā)管理經(jīng)驗(yàn)、成熟的應(yīng)用系統(tǒng)解決方案、優(yōu)秀的網(wǎng)站開發(fā)工程師團(tuán)隊(duì)及專業(yè)的網(wǎng)站設(shè)計(jì)師團(tuán)隊(duì)。

常見的數(shù)據(jù)結(jié)構(gòu)

鏈表

LinkedHashSet LinkedList 底層數(shù)據(jù)結(jié)構(gòu)由鏈表和哈希表組成。
數(shù)據(jù)的添加和刪除都較為方便，就是訪問比較耗費(fèi)時(shí)間。

數(shù)組

ArrayList 訪問數(shù)據(jù)十分簡(jiǎn)單，而添加和刪除數(shù)據(jù)比較耗工夫

堆

• 堆是一種圖的樹形結(jié)構(gòu)，被用于實(shí)現(xiàn)“優(yōu)先隊(duì)列",優(yōu)先隊(duì)列是一種數(shù)據(jù)結(jié)構(gòu)，可以自由添加數(shù)據(jù)，但取出數(shù)據(jù)時(shí)要從最小值開始按順序取出

• 堆的特點(diǎn)：
  ①堆中的每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)
  ②子結(jié)點(diǎn)必定大于父結(jié)點(diǎn)
  ③把新數(shù)據(jù)放在最下面一行靠左的位置。當(dāng)最下面一行里沒有多余空間時(shí)，就再往下另起一行，把數(shù)據(jù)加在這一行的最左端
  ④如果子結(jié)點(diǎn)的數(shù)字小于父結(jié)點(diǎn)的，就將父結(jié)點(diǎn)與其左右兩個(gè)子結(jié)點(diǎn)中較小的一個(gè)進(jìn)行交換
  堆中最頂端的數(shù)據(jù)始終最小，所以無論數(shù)據(jù)量有多少，取出最小值的時(shí)間復(fù)雜度都為O（1）
  可知樹的高度為log2n，那么重構(gòu)樹的時(shí)間復(fù)雜度便為O（logn）

棧 （LIFO）

略

隊(duì)列 (FIFO)

略

哈希表 HashSet

• TreeSet底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹

• 哈希函數(shù)（Hash）計(jì)算key,哈希值除以數(shù)組的長(zhǎng)度5，求得其余數(shù)。這個(gè)余數(shù)就是key的編號(hào)即位置

• 如果發(fā)生哈希沖突，就使用鏈表進(jìn)行存儲(chǔ)（鏈地址法）給數(shù)組設(shè)定合適的空間非常重要
  除了鏈地址法以外，還有幾種解決沖突的方法。其中，應(yīng)用較為廣泛的是“開放地址法”。這種方法是指當(dāng)沖突發(fā)生時(shí)，立刻計(jì)算出一個(gè)候補(bǔ)地址（數(shù)組上的位置）并將數(shù)據(jù)存進(jìn)去。如果仍然有沖突，便繼續(xù)計(jì)算下一個(gè)候補(bǔ)地址，直到有空地址為止?？梢酝ㄟ^多次使用哈希函數(shù)或“線性探測(cè)法”等方法計(jì)算候補(bǔ)地址。

二叉樹

• 特點(diǎn)：
  ①第一個(gè)是每個(gè)結(jié)點(diǎn)的值均大于其左子樹上任意一個(gè)結(jié)點(diǎn)的值
  ②是每個(gè)結(jié)點(diǎn)的值均小于其右子樹上任意一個(gè)結(jié)點(diǎn)的值
  ③二叉查找樹的最小結(jié)點(diǎn)要從頂端開始，往其左下的末端尋找。此處最小值為3。
  ④二叉查找樹的最大結(jié)點(diǎn)要從頂端開始，往其右下的末端尋找
  添加數(shù)據(jù)的時(shí)候 與頂端數(shù)據(jù)比較 如果比他小就往左移，左邊沒有節(jié)點(diǎn)了就把插入的數(shù)據(jù)作為新節(jié)點(diǎn)添加到左下方，大于他則往右移（左小右大）

刪除數(shù)據(jù)的時(shí)候 如果節(jié)點(diǎn)沒有子節(jié)點(diǎn) 直接刪 如果有一個(gè) 刪了后子節(jié)點(diǎn)補(bǔ)上，如果有兩個(gè)，刪掉后從左子樹中中找最大的補(bǔ)上

比較的次數(shù)取決于樹的高度。所以如果結(jié)點(diǎn)數(shù)為n，而且樹的形狀又較為均衡的話，比較大小和移動(dòng)的次數(shù)最多就是log2n。因此，時(shí)間復(fù)雜度為O（logn）。但是，如果樹的形狀朝單側(cè)縱向延伸，樹就會(huì)變得很高，此時(shí)時(shí)間復(fù)雜度也就變成了O（n）。

常見的算法整理

排序

• 冒泡排序
  冒泡排序就是重復(fù)“從序列右邊開始比較相鄰兩個(gè)數(shù)字的大小，再根據(jù)結(jié)果交換兩個(gè)數(shù)字的位置”這一操作的算法。在這個(gè)過程中，數(shù)字會(huì)像泡泡一樣，慢慢從右往左“浮”到序列的頂端，所以這個(gè)算法才被稱為“冒泡排序”
  冒泡排序的時(shí)間復(fù)雜度為O（n2）

• 選擇排序
  選擇排序就是重復(fù)“從待排序的數(shù)據(jù)中尋找最小值，將其與序列最左邊的數(shù)字進(jìn)行交換”這一操作的算法。在序列中尋找最小值時(shí)使用的是線性查找
  每輪中交換數(shù)字的次數(shù)最多為1次。如果輸入數(shù)據(jù)就是按從小到大的順序排列的，便不需要進(jìn)行任何交換。選擇排序的時(shí)間復(fù)雜度也和冒泡排序的一樣，都為O（n2）。

• 插入排序
  插入排序的思路就是從右側(cè)的未排序區(qū)域內(nèi)取出一個(gè)數(shù)據(jù)，然后將它插入到已排序區(qū)域內(nèi)合適的位置上
  時(shí)間復(fù)雜度和冒泡排序的一樣，都為O（n2）。

• 堆排序
  首先堆中存儲(chǔ)所有的數(shù)據(jù)，并按降序來構(gòu)建堆，然后從降序排列的堆中取出數(shù)據(jù)時(shí)會(huì)從最大的數(shù)據(jù)開始取，所以將取出的數(shù)據(jù)反序輸出，排序就完成了。
  堆排序的時(shí)間復(fù)雜度為O（nlogn）。

• 歸并排序
  歸并排序算法會(huì)把序列分成長(zhǎng)度相同的兩個(gè)子序列，當(dāng)無法繼續(xù)往下分時(shí)（也就是每個(gè)子序列中只有一個(gè)數(shù)據(jù)時(shí)），就對(duì)子序列進(jìn)行歸并。歸并指的是把兩個(gè)排好序的子序列合并成一個(gè)有序序列。該操作會(huì)一直重復(fù)執(zhí)行，直到所有子序列都?xì)w并為一個(gè)整體為止。
  運(yùn)行時(shí)間復(fù)雜度為O（nlogn）

• 快速排序
  快速排序算法首先會(huì)在序列中隨機(jī)選擇一個(gè)基準(zhǔn)值（pivot），然后將除了基準(zhǔn)值以外的數(shù)分為“比基準(zhǔn)值小的數(shù)”和“比基準(zhǔn)值大的數(shù)”這兩個(gè)類別。解決子問題的時(shí)候會(huì)再次使用快速排序，甚至在這個(gè)快速排序里仍然要使用快速排序。只有在子問題里只剩一個(gè)數(shù)字的時(shí)候，排序才算完成。
  整體的時(shí)間復(fù)雜度為O（nlogn）。

數(shù)組查找

• 線性查找
  線性查找需要從頭開始不斷地按順序檢查數(shù)據(jù)，因此在數(shù)據(jù)量大且目標(biāo)數(shù)據(jù)靠后，或者目標(biāo)數(shù)據(jù)不存在時(shí)，比較的次數(shù)就會(huì)更多，也更為耗時(shí)。若數(shù)據(jù)量為n，線性查找的時(shí)間復(fù)雜度便為O（n）。

• 二分查找（略）

圖的搜索

• 廣度優(yōu)先搜索
  廣度優(yōu)先搜索是一種對(duì)圖進(jìn)行搜索的算法。假設(shè)我們一開始位于某個(gè)頂點(diǎn)（即起點(diǎn)），此時(shí)并不知道圖的整體結(jié)構(gòu)，而我們的目的是從起點(diǎn)開始順著邊搜索，直到到達(dá)指定頂點(diǎn)（即終點(diǎn)）。在此過程中每走到一個(gè)頂點(diǎn)，就會(huì)判斷一次它是否為終點(diǎn)。廣度優(yōu)先搜索會(huì)優(yōu)先從離起點(diǎn)近的頂點(diǎn)開始搜索

• 深度優(yōu)先搜索
  深度優(yōu)先搜索和廣度優(yōu)先搜索一樣，都是對(duì)圖進(jìn)行搜索的算法，目的也都是從起點(diǎn)開始搜索直到到達(dá)指定頂點(diǎn)（終點(diǎn)）。深度優(yōu)先搜索會(huì)沿著一條路徑不斷往下搜索直到不能再繼續(xù)為止，然后再折返，開始搜索下一條候補(bǔ)路徑。

• 貝爾曼-福特算法（略）
  貝爾曼-福特（Bellman-Ford）算法是一種在圖中求解最短路徑問題的算法

• 狄克斯特拉算法（略）

• A*算法（略）

安全算法

• 共享密鑰加密

• 公開密鑰加密

• 混合加密

• 迪菲-赫爾曼交換

其他算法

• k-means 算法

• 歐幾里得算法

• 素性測(cè)試

• 網(wǎng)頁排名

• 漢諾塔

【拓展】

1. 圖的表示：鄰接矩陣和鄰接表
   遍歷算法：深度搜索和廣度搜索(必學(xué))
   最短路徑算法：Floyd，Dijkstra（必學(xué)）
   最小生成樹算法：Prim，Kruskal（必學(xué)）
   實(shí)際常用算法：關(guān)鍵路徑、拓?fù)渑判颍ㄔ砼c應(yīng)用）
   二分圖匹配：配對(duì)、匈牙利算法（原理與應(yīng)用）
   拓展：中心性算法、社區(qū)發(fā)現(xiàn)算法（原理與應(yīng)用）

2.圖還是比較難的，不過我覺得圖涉及到的挺多算法都是挺實(shí)用的，例如最短路徑的計(jì)算等，圖相關(guān)的，我這里還是建議看書的，可以看《算法第四版》。

3、搜索與回溯算法

貪心算法（必學(xué)）
啟發(fā)式搜索算法：A*尋路算法（了解）
地圖著色算法、N 皇后問題、最優(yōu)加工順序
旅行商問題

這方便的只是都是一些算法相關(guān)的，我覺得如果可以，都學(xué)一下。像貪心算法的思想，就必須學(xué)的了。建議通過刷題來學(xué)習(xí)，leetcode 直接專題刷。

4、動(dòng)態(tài)規(guī)劃

樹形DP：01背包問題
線性DP：最長(zhǎng)公共子序列、最長(zhǎng)公共子串
區(qū)間DP：矩陣最大值（和以及積）
數(shù)位DP：數(shù)字游戲
狀態(tài)壓縮DP：旅行商

我覺得動(dòng)態(tài)規(guī)劃是最難的一個(gè)算法思想了，記得當(dāng)初第一次接觸動(dòng)態(tài)規(guī)劃的時(shí)候，是看01背包問題的，看了好久都不大懂，懵懵懂懂，后面懂了基本思想，可是做題下不了手，但是看的懂答案。一氣之下，再leetcdoe專題連續(xù)刷了幾十道，才掌握了動(dòng)態(tài)規(guī)劃的套路，也有了自己的一套模板。不過說實(shí)話，動(dòng)態(tài)規(guī)劃，是考的真他媽多，學(xué)習(xí)算法、刷題，一定要掌握。這里建議先了解動(dòng)態(tài)規(guī)劃是什么，之后 leetcode 專題刷，反正就一般上面這幾種題型。

5、字符匹配算法

正則表達(dá)式
模式匹配：KMP、Boyer-Moore

6、流相關(guān)算法

最大流：最短增廣路、Dinic 算法
最大流最小割：最大收益問題、方格取數(shù)問題
最小費(fèi)用最大流：最小費(fèi)用路、消遣

到此，相信大家對(duì)“有哪些JAVA必須掌握的數(shù)據(jù)結(jié)構(gòu)和算法”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

分享文章：有哪些JAVA必須掌握的數(shù)據(jù)結(jié)構(gòu)和算法
URL鏈接：http://www.rwnh.cn/article6/ihjgog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供營(yíng)銷型網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、網(wǎng)站策劃、建站公司、品牌網(wǎng)站制作、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)