學習之路，長路漫漫，寫學習筆記的過程就是把知識講給自己聽的過程。成都創(chuàng)新互聯公司是專業(yè)的海珠網站建設公司，海珠接單;提供成都做網站、網站設計,網頁設計,網站設計,建網站,PHP網站建設等專業(yè)做網站服務;采用PHP框架,可快速的進行海珠網站開發(fā)網頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網站,專業(yè)的做網站團隊,希望更多企業(yè)前來合作!
目錄
數據結構初定義
常用數據結構
這 8 種數據結構有什么區(qū)別呢？
①、數組
②、鏈表
③、棧
④、隊列
⑤、樹
⑥、堆
⑦、圖
⑧、哈希表
數據結構
集合結構(非線性結構)
線性結構
數組
線性表
存儲結構
模式匹配
二叉樹
存儲結構
順序存儲結構
二叉鏈表
哈夫曼編碼
哈夫曼編碼實現壓縮，解壓縮
數據元素是多對多的關系
存儲結構
鄰接矩陣
鄰接表
十字鏈表
鄰接多重表
邊集數組
遍歷
最小生成樹
物理結構(存儲結構)
順序查找(線性查找)
折半查找(二分查找)
插值查找
斐波那契查找
線性索引查找
稠密索引
分塊索引
二叉搜索樹(又稱二叉查找樹/排序數)
平衡二叉搜索樹(AVL樹)
多路查找樹(B樹)
紅黑樹
散列表查找(哈希表)
內排序與外排序
冒泡排序
冒泡排序優(yōu)化
簡單選擇排序
直接插入排序
希爾排序
堆排序
歸并排序
快速排序
算法
數據結構初定義數據結構(data structure)是帶有結構特性的數據元素的集合，它研究的是數據的邏輯結構和數據的物理結構以及它們之間的相互關系，并對這種結構定義相適應的運算，設計出相應的算法，并確保經過這些運算以后所得到的新結構仍保持原來的結構類型。簡而言之，數據結構是相互之間存在一種或多種特定關系的數據元素的集合，即帶“結構”的數據元素的集合?！敖Y構”就是指數據元素之間存在的關系，分為邏輯結構和存儲結構。
常用數據結構數組(Array)
是一種聚合數據類型，它是將具有相同類型的若干變量有序地組織在一起的集合。數組可以說是最基本的數據結構，在各種編程語言中都有對應。一個數組可以分解為多個數組元素，按照數據元素的類型，數組可以分為整型數組、字符型數組、浮點型數組、指針數組和結構數組等。數組還可以有一維、二維以及多維等表現形式。?
棧( Stack)
棧是一種特殊的線性表，它只能在一個表的一個固定端進行數據結點的插入和刪除操作。棧按照先進后出或后進先出的原則來存儲數據，也就是說，先插入的數據將被壓入棧底，最后插入的數據在棧頂，讀出數據時，從棧頂開始逐個讀出。棧在匯編語言程序中，經常用于重要數據的現場保護。棧中沒有數據時，稱為空棧。?
隊列(Queue)
隊列和棧類似，也是一種特殊的線性表。和棧不同的是，隊列只允許在表的一端進行插入操作，而在另一端進行刪除操作。一般來說，進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊頭。隊列中沒有元素時，稱為空隊列。?
鏈表( Linked List)
鏈表是一種數據元素按照鏈式存儲結構進行存儲的數據結構，這種存儲結構具有在物理上存在非連續(xù)的特點。鏈表由一系列數據結點構成，每個數據結點包括數據域和指針域兩部分。其中，指針域保存了數據結構中下一個元素存放的地址。鏈表結構中數據元素的邏輯順序是通過鏈表中的指針鏈接次序來實現的。?
樹( Tree)
樹是典型的非線性結構，它是包括，2個結點的有窮集合K。在樹結構中，有且僅有一個根結點，該結點沒有前驅結點。在樹結構中的其他結點都有且僅有一個前驅結點，而且可以有兩個后繼結點，m≥0。?
圖(Graph)
圖是另一種非線性數據結構。在圖結構中，數據結點一般稱為頂點，而邊是頂點的有序偶對。如果兩個頂點之間存在一條邊，那么就表示這兩個頂點具有相鄰關系。??
堆(Heap)
堆是一種特殊的樹形數據結構，一般討論的堆都是二叉堆。堆的特點是根結點的值是所有結點中最小的或者大的，并且根結點的兩個子樹也是一個堆結構。?
散列表(Hash)
散列表源自于散列函數(Hash function)，其思想是如果在結構中存在關鍵字和T相等的記錄，那么必定在F(T)的存儲位置可以找到該記錄，這樣就可以不用進行比較操作而直接取得所查記錄。?[5]?
這 8 種數據結構有什么區(qū)別呢？優(yōu)點：
按照索引查詢元素的速度很快；按照索引遍歷數組也很方便。
缺點：
數組的大小在創(chuàng)建后就確定了，無法擴容；數組只能存儲一種類型的數據；添加、刪除元素的操作很耗時間，因為要移動其他元素。
②、鏈表《算法（第 4 版）》一書中是這樣定義鏈表的：
鏈表是一種遞歸的數據結構，它或者為空（null），或者是指向一個結點（node）的引用，該節(jié)點還有一個元素和一個指向另一條鏈表的引用。
Java 的 LinkedList 類可以很形象地通過代碼的形式來表示一個鏈表的結構：
這是一種雙向鏈表，當前元素 item 既有 prior 又有 next，不過 first 的 prior 為 null，last 的 next 為 null。如果是單向鏈表的話，就只有 next，沒有 prior。
單向鏈表的缺點是只能從頭到尾依次遍歷，而雙向鏈表可進可退，既能找到下一個，也能找到上一個——每個節(jié)點上都需要多分配一個存儲空間。
鏈表中的數據按照“鏈式”的結構存儲，因此可以達到內存上非連續(xù)的效果，數組必須是一塊連續(xù)的內存。
由于不必按照順序的方式存儲，鏈表在插入、刪除的時候可以達到 O(1) 的時間復雜度（只需要重新指向引用即可，不需要像數組那樣移動其他元素）。除此之外，鏈表還克服了數組必須預先知道數據大小的缺點，從而可以實現靈活的內存動態(tài)管理。
優(yōu)點：
不需要初始化容量；可以添加任意元素；插入和刪除的時候只需要更新引用。
缺點：
含有大量的引用，占用的內存空間大；查找元素需要遍歷整個鏈表，耗時。
③、棧棧就好像水桶一樣，底部是密封的，頂部是開口，水可以進可以出。用過水桶的小伙伴應該明白這樣一個道理：先進去的水在桶的底部，后進去的水在桶的頂部；后進去的水先被倒出來，先進去的水后被倒出來。
同理，棧按照“后進先出”、“先進后出”的原則來存儲數據，先插入的數據被壓入棧底，后插入的數據在棧頂，讀出數據的時候，從棧頂開始依次讀出。
隊列就好像一段水管一樣，兩端都是開口的，水從一端進去，然后從另外一端出來。先進去的水先出來，后進去的水后出來。
和水管有些不同的是，隊列會對兩端進行定義，一端叫隊頭，另外一端就叫隊尾。隊頭只允許刪除操作（出隊），隊尾只允許插入操作（入隊）。
注意，棧是先進后出，隊列是先進先出——兩者雖然都是線性表，但原則是不同的，結構不一樣嘛。
⑤、樹樹是一種典型的非線性結構，它是由 n（n>0）個有限節(jié)點組成的一個具有層次關系的集合。
之所以叫“樹”，是因為這種數據結構看起來就像是一個倒掛的樹，只不過根在上，葉在下。樹形數據結構有以下這些特點：
每個節(jié)點都只有有限個子節(jié)點或無子節(jié)點；沒有父節(jié)點的節(jié)點稱為根節(jié)點；每一個非根節(jié)點有且只有一個父節(jié)點；除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹。下圖展示了樹的一些術語：
根節(jié)點是第 0 層，它的子節(jié)點是第 1 層，子節(jié)點的子節(jié)點為第 2 層，以此類推。
深度：對于任意節(jié)點 n，n 的深度為從根到 n 的唯一路徑長，根的深度為 0。高度：對于任意節(jié)點 n，n 的高度為從 n 到一片樹葉的最長路徑長，所有樹葉的高度為 0。樹的種類有很多種，常見的有：
無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關系。那怎么來理解無序樹呢，到底長什么樣子？假如有三個節(jié)點，一個是父節(jié)點，兩個是同級的子節(jié)點，那么就有三種情況：
假如有三個節(jié)點，一個是父節(jié)點，兩個是不同級的子節(jié)點，那么就有六種情況：
三個節(jié)點組成的無序樹，合起來就是九種情況。
二叉樹：每個節(jié)點最多含有兩個子樹。二叉樹按照不同的表現形式又可以分為多種。完全二叉樹：對于一顆二叉樹，假設其深度為 d（d >1）。除了第 d 層，其它各層的節(jié)點數目均已達大值，且第 d 層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹。
拿上圖來說，d 為 3，除了第 3 層，第 1 層、第 2 層 都達到了大值（2 個子節(jié)點），并且第 3 層的所有節(jié)點從左向右聯系地緊密排列（H、I、J、K、L），符合完全二叉樹的要求。
滿二叉樹：一顆每一層的節(jié)點數都達到了大值的二叉樹。有兩種表現形式，第一種，像下圖這樣（每一層都是滿的），滿足每一層的節(jié)點數都達到了大值 2。
第二種，像下圖這樣（每一層雖然不滿），但每一層的節(jié)點數仍然達到了大值 2。
二叉查找樹：英文名叫 Binary Search Tree，即 BST，需要滿足以下條件：
任意節(jié)點的左子樹不空，左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；任意節(jié)點的右子樹不空，右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；任意節(jié)點的左、右子樹也分別為二叉查找樹。
基于二叉查找樹的特點，它相比較于其他數據結構的優(yōu)勢就在于查找、插入的時間復雜度較低，為 O(logn)。假如我們要從上圖中查找 5 個元素，先從根節(jié)點 7 開始找，5 必定在 7 的左側，找到 4，那 5 必定在 4 的右側，找到 6，那 5 必定在 6 的左側，找到了。
理想情況下，通過 BST 查找節(jié)點，所需要檢查的節(jié)點數可以減半。
平衡二叉樹：當且僅當任何節(jié)點的兩棵子樹的高度差不大于 1 的二叉樹。由前蘇聯的數學家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉樹，根據科學家的英文名也稱為 AVL 樹。
平衡二叉樹本質上也是一顆二叉查找樹，不過為了限制左右子樹的高度差，避免出現傾斜樹等偏向于線性結構演化的情況，所以對二叉搜索樹中每個節(jié)點的左右子樹作了限制，左右子樹的高度差稱之為平衡因子，樹中每個節(jié)點的平衡因子絕對值不大于 1。
平衡二叉樹的難點在于，當刪除或者增加節(jié)點的情況下，如何通過左旋或者右旋的方式來保持左右平衡。
Java 中最常見的平衡二叉樹就是紅黑樹，節(jié)點是紅色或者黑色，通過顏色的約束來維持著二叉樹的平衡：
1）每個節(jié)點都只能是紅色或者黑色
2）根節(jié)點是黑色
3）每個葉節(jié)點（NIL 節(jié)點，空節(jié)點）是黑色的。
4）如果一個節(jié)點是紅色的，則它兩個子節(jié)點都是黑色的。也就是說在一條路徑上不能出現相鄰的兩個紅色節(jié)點。
5）從任一節(jié)點到其每個葉子的所有路徑都包含相同數目的黑色節(jié)點。
B 樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持數據有序，擁有多于兩個的子樹。數據庫的索引技術里就用到了 B 樹。
堆可以被看做是一棵樹的數組對象，具有以下特點：
堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；堆總是一棵完全二叉樹。將根節(jié)點大的堆叫做大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。
圖是一種復雜的非線性結構，由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V，E），其中，G 表示一個圖，V 是圖 G 中頂點的集合，E 是圖 G 中邊的集合。
上圖共有 V0，V1，V2，V3 這 4 個頂點，4 個頂點之間共有 5 條邊。
在線性結構中，數據元素之間滿足唯一的線性關系，每個數據元素（除第一個和最后一個外）均有唯一的“前驅”和“后繼”；
在樹形結構中，數據元素之間有著明顯的層次關系，并且每個數據元素只與上一層中的一個元素（父節(jié)點）及下一層的多個元素（子節(jié)點）相關；
而在圖形結構中，節(jié)點之間的關系是任意的，圖中任意兩個數據元素之間都有可能相關。
⑧、哈希表哈希表（Hash Table），也叫散列表，是一種可以通過關鍵碼值（key-value）直接訪問的數據結構，它大的特點就是可以快速實現查找、插入和刪除。
數組的大特點就是查找容易，插入和刪除困難；而鏈表正好相反，查找困難，而插入和刪除容易。哈希表很完美地結合了兩者的優(yōu)點， Java 的 HashMap 在此基礎上還加入了樹的優(yōu)點。
哈希函數在哈希表中起著常關鍵的作，它可以把任意長度的輸入變換成固定長度的輸出，該輸出就是哈希值。哈希函數使得一個數據序列的訪問過程變得更加迅速有效，通過哈希函數，數據元素能夠被很快的進行定位。
若關鍵字為 k，則其值存放在hash(k)的存儲位置上。由此，不需要遍歷就可以直接取得 k 對應的值。
對于任意兩個不同的數據塊，其哈希值相同的可能性極小，也就是說，對于一個給定的數據塊，找到和它哈希值相同的數據塊極為困難。再者，對于一個數據塊，哪怕只改動它的一個比特位，其哈希值的改動也會非常的大——這正是 Hash 存在的價值！
盡管可能性極小，但仍然會發(fā)生，如果哈希沖突了，Java 的 HashMap 會在數組的同一個位置上增加鏈表，如果鏈表的長度大于 8，將會轉化成紅黑樹進行處理——這就是所謂的拉鏈法（數組+鏈表）。
數據結構數據結構是相互之間存在一種或多種特定關系的數據元素的集合
邏輯結構(分為線性結構和非線性結構)
反映數據元素之間的邏輯關系的數據結構，是針對具體問題的，可以表示成一種或多種存儲結構
集合結構(非線性結構)集合通常是由一組無序的, 不能重復的元素構成 數據結構中的元素之間除了“同屬一個集合” 的相互關系外，別無其他關系
線性結構線性結構是一個有序數據元素的集合，常用的線性結構有：線性表，棧，隊列，雙隊列，數組，串。 非線性結構，其邏輯特征是一個結點元素可能有多個直接前趨和多個直接后繼。常見的非線性結構有：二維數組，多維數組，廣義表，樹(二叉樹等)。
線性結構是一個有序數據元素的集合
數組0個或多個具有相同類型的數據元素的有限序列
存儲結構順序存儲結構
順序存儲結構，用一段地址連續(xù)的存儲單元 一次存儲線性表的數據元素。比如數組
每個數據元素存數據元素信息外(數據域)，還要存儲它的后繼元素的存儲地址(指針域)
優(yōu)點：
無需為表示表中元素之間的邏輯關系而增加額外的存儲空間
可以快速的存取表中任意位置的元素，時間復雜度為O(1)
缺點：
插入和刪除操作需要移動大量元素
當線性表變化較大時，難以確定存儲空間的容量
造成存儲空間的"碎片"
鏈式存儲結構
用一組任意的存儲單元存儲線性表的數據元素， 這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的
單鏈表
鏈表中每個結點可以包含若干個數據域和若干個指針域。 如果每個結點中只包含一個指針域，則稱其為單鏈表。
優(yōu)點：
單鏈表不需要分配存儲空間，只要有就可以分配，元素個數也不受限制
插入和刪除更快，時間復雜度為O(n)，在給出某位置的指針后，復雜度僅為O(1)
缺點：
查找效率比順序存儲結構差，時間復雜度為O(n)
靜態(tài)鏈表
用數組描述的鏈表叫靜態(tài)鏈表(用數組代替指針)
為了給沒有指針的高級語言設計的視線單鏈表的方法，很少用(雖然java,c#也沒有指針，但是引用類型相當于變樣實現了指針)
優(yōu)點： 插入和刪除只需要修改游標，無需移動元素 從而改進了在順序存儲結構中的插入，刪除移動大量元素的缺點
缺點： 沒有解決連續(xù)存儲分配帶來的表長難以確認的問題 失去了順序存儲結構隨機存取的特性
循環(huán)鏈表
將單鏈表中終端結點的指針段由空指針改為指向頭結點，就使整個單鏈表形成一個環(huán)，這種頭尾相接的單鏈表就
稱為單循環(huán)鏈表，簡稱循環(huán)鏈表
雙向鏈表
在單鏈表的每個結點中，再設置一個指向其前驅結點的指針域 (就意味著雙向鏈表的結點都有倆個指針域，一個指向直接后繼， 一個指向直接前驅)
棧(特殊的線性表)
限定僅在表尾進行插入和刪除操作的線性表，又稱后進先出(LIFO)的線性表 (允許插入和刪除的一端稱為棧頂，另一端稱為棧底)
隊列(特殊的線性表)
只允許在一端進行插入操作，而另一端進行刪除操作的線性表 先進先出(FIFO)
順序存儲結構(順序隊列)
循環(huán)隊列
鏈式存儲結構(鏈隊列)
串(字符串)
有0個或多個字符組成的有限序列
針對的是字符集，就是說把字符串中多個字符連在一起
存儲結構
順序存儲結構
鏈式存儲結構
模式匹配樸素的描述匹配 (從頭開始一個個字符匹配)
效率很低，復雜度為O((n-m+1)*m) n是總的字符串，m是需要匹配的字符串
KMP模式匹配算法
算法證明和更詳細的說明，請參閱《算法導論》第2版第32章字符串匹配
KMP模式匹配算法改進
樹形結構(非線性結構)
數據元素之間存在一對多的層次關系
數是n(n>=0)個節(jié)點的有限集。若n=0,稱為空樹。樹的節(jié)點是互不交互的。 + 度：節(jié)點擁有的子數(節(jié)點)數量稱為"度"，度為0的稱為葉節(jié)點。 + 樹的度：樹的度是樹內各節(jié)點的度的大值 + 節(jié)點的層次：跟為第一層，一次類推。 + 數的深度：數中節(jié)點的大層次稱為"深度"或"高度"
二叉樹特點
每個結點最多有倆棵子樹
左右子樹是順序的，次序不能顛倒
即使樹中只有一棵子樹，也要區(qū)分左右
五種形態(tài)
空二叉樹
只有一個根結點
根結點只有左子樹
根結點只有右子樹
根結點既有左子樹，又有右子樹
性質
在二叉樹的第i層上之多有2i-1(i-1是上標)個結點
深度為K的二叉樹至多有2k-1(k>=1,k是上表)個結點
特殊二叉樹
斜樹
所有結點都只有左子樹的二叉樹叫左斜樹
所有結點都只有右子樹的二叉樹叫右斜樹
滿二叉樹
一個二叉樹中，所有分支結點都存在左子樹和右子樹， 并且所有葉子都在同一層上，稱為滿二叉樹
完全二叉樹
若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到大個數，第 h 層所有的結點都連續(xù)集中 在最左邊，這就是完全二叉樹。
線索二叉樹
每個二叉樹左右倆個指針域，如果為空，放著也浪費空間。 所以第一次遍歷二叉樹時，如果左指針域為空就存前驅地址， 右指針域為空就存后繼地址。但是左側需要一個tag來標識左指 針域存的是左孩子結點還是前驅，右側也同樣需要。
存儲結構只用于完全二叉樹(因為完全二叉樹定義的嚴格， 可以用順序結構表示出二叉樹的結構，很有優(yōu)越性。詳情參考P172) 該結構不太通用，通用的見二叉鏈表
二叉鏈表二叉樹每個結點最多有倆個孩子，所以可以用 一個數據域+倆個指針域這樣的結構存儲二叉樹
遍歷
概念
從根結點出發(fā)，按照某種次序依次訪問二叉樹中 所有結點，使得每個結點被訪問一次且僅被訪問一次
遍歷方法(限定了從左到右的習慣)
前序遍歷
根結點=>左子樹=>右子樹 (切記：是先把所有左子樹遍歷完了，再遍歷右子樹)
中序遍歷
從根結點開始(并不是先訪問根結點)，遍歷根結點的 左子樹=>根結點=>右子樹
后序遍歷
從根結點開始(并不是先訪問根結點)，遍歷根結點的 左子樹=>右子樹=>根結點
層序遍歷(BFS常用)
根結點一層層從上而下遍歷
哈夫曼樹(也叫最優(yōu)二叉樹)
帶權路徑長度WPL最小的二叉樹稱作哈夫曼樹
哈夫曼編碼原理：先構造哈夫曼樹，然后對字符串再次編碼，二進制的長度會明顯縮小， 所以達到了壓縮的效果。解壓縮也要用哈夫曼樹，才能知道哪幾個二進制對應哪個字符
圖形結構(非線性結構)
數據元素是多對多的關系概念：有頂點的有窮非空集合和頂點之間邊的集合組成 表示為G(V,E),其中G表示一個圖，V是圖G中頂點的集合，E是邊的集合
特點：圖中數據元素稱為頂點，圖中不允許沒有頂點
術語
頂點
圖中數據元素稱為頂點，圖中不允許沒有頂點
無向邊
頂點Vi到Vj(i和j是下標)之間的邊沒有方向， 則稱這條邊為無向邊，用無序偶對(ViVj)來表示
有向邊
頂點Vi到Vj之間的邊有方向， 則稱這條邊為有向邊，也稱為弧
無向圖
圖中任意倆個頂點之間的邊都是無向邊
連通圖
概念：從頂點V導頂點V'有路徑，稱V和V'是連通的。 如果對于圖中任意倆個頂點都是連通的則稱為連通圖 (能連通就行，不一定要相鄰)
連通分量
要是子圖
子圖要是連通的
連通子圖還有極大頂點數
具有極大頂點數的連通子圖包含依附于這些頂點的所有邊
生成樹
一個連通圖的生成樹是一個極小的連通子圖， 它含有圖中全部的n個頂點，但只有足以構成一棵樹的n-1條邊(p221)
有向圖
圖中任意倆個頂點之間的邊都是有向邊
強連通圖
概念：如果對于圖中任意倆個頂點都是連通的則稱為連通圖 (能連通就行，不一定要相鄰)
強連通分量
參考連通分量定義
有向樹
概念：一個有向圖恰有一個頂點的入口為0(根節(jié)點)， 其余頂點的入度均為1，則是一顆有向樹
簡單圖
不存在頂點到其自身的邊(自己到自己)，且同一條邊不重復出現
無向完全圖
在無向圖中，任意倆個頂點之間都存在邊
有向完全圖
在有向圖中，任意倆個頂點之間都存在方向互為相反的倆條弧網
有的圖的邊或弧具有與它相關的數字，這叫做權。權可以表示一個頂點到另 一個頂點的距離或者耗費，這種帶權的圖稱為網
存儲結構用倆個數組來表示圖，一個一維數組存儲圖中頂點信息， 一個二維數組(鄰接矩陣)存儲圖中的邊或弧的信息
缺點
對于邊數相對于頂點較少(頂點多，邊數少)的圖， 這種結構存在存儲空間的浪費
鄰接表數組和鏈表相結合的存儲方法稱為鄰接表
特點
圖中頂點用一個一維數組存儲
每個頂點的所有鄰接點構成一個新線性表，
如果是有向圖，還可以建立有向圖的逆鄰接表，
即對每個頂點vi都建立一個鏈接為vi為弧頭的表。 (可以很容易得到頂點的入度或以頂點為弧頭的弧)
優(yōu)缺點
想了解入度就必須遍歷整個圖才知道，反之，逆鄰接鏈表解決了入度卻不了解出度的情況。倆者不可兼得
十字鏈表把鄰接表和逆鄰接表結合起來
鄰接多重表主要優(yōu)化無向圖
邊集數組倆個一維數組構成，一個存儲頂點的信息，一個存儲邊的信息。 這個邊數組每個數據元素由一條邊的起點下標，終點下標和權重組成
遍歷深度優(yōu)先(DFS)
約定原則：在沒有碰到重復頂點的情況下，始終向右手邊走。 走回到頂點之后，還要按原路一步步返回，在一步步驗證是否都都走過了
廣度優(yōu)先(BFS)
圖需要變形下，改造成類似樹那樣有明顯的層級關系的樣式
最小生成樹概念：我們把構造連通網的最小代價生成樹稱為最小生成樹
所謂最小代價，就是n個頂點,用n-1條邊 把一個連通圖連接起來，并且使得權值的和最小
算法
普里姆(Prim)算法
以某頂點為起點，逐步找各頂點上最小權值的邊來構建最小生成樹
克魯斯卡爾(Kruskal)算法
以最小權值邊開始構建
最短路徑
迪杰斯特拉(Dijkstra)算法
一步步求出與頂點的最短路徑，過程中都是基于已經求出的大路徑的基礎上
佛洛伊德(Floyd)算法
拓撲排序算法
物理結構(存儲結構)數據的邏輯結構在計算機中的存儲形式
順序存儲結構
數據元素存放在地址連續(xù)的存儲單元里， 數據間的邏輯關系和物理關系是一致的 (不方便插入，刪除)
不方便插入，刪除
鏈式存儲結構
數據元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的， 也可以是不連續(xù)的 (很靈活，給個指針就能找到。需要一個指針存放數據元素的地址)
很靈活，給個指針就能找到。需要一個指針存放數據元素的地址
索引存儲結構
為了方便查找，整體無序，但索引塊之間有序，需要額外空間，存儲索引表。 優(yōu)點：對順序查找的一種改進，查找效率高 缺點：需額外空間存儲索引
散列存儲結構
選取某個函數，數據元素根據函數計算存儲位置可能存在多個數據元素存儲在同一位置，引起地址沖 優(yōu)點：查找基于數據本身即可找到，查找效率高，存取效率高。 缺點：存取隨機，不便于順序查找。
數據運算
查找運算
順序表查找
順序查找(線性查找)從表中第一個(或最后一個)記錄開始，逐個進行記錄的的關鍵字和給定值比較。
有序表查找
折半查找(二分查找)切記：表必須是有序的。mid=(low+high)/2。復雜度是0(logn)
可以優(yōu)化的地方：每次都從1/2處查找，對于有些場景還是不太適合的， 比如查找am單詞，很顯然從字典的前面查找效率更高，所以優(yōu)化點是從哪里開始折半
插值查找公式：mid=low+(key-a[low])*(high-low)/a[high]-a[low] ；low和high是數組的下標
適合場景：
表長較大，而關鍵字分配又比較均勻的查找表，性能比折半查找要好得多。復雜度也是0(logn)
斐波那契查找構造另外一個斐波那契數列用于輔助
公式：mid=low+F[K-1]-1 ；F是斐波那契數列
比較：平均效率優(yōu)于折半查找，最壞情況下，效率低于折半
線性索引查找數據集增長非常快的情況下，保證關鍵字有序，代價很高昂。所以這種數據都是按先后順序存儲。
稠密索引索引項一定要按照關鍵碼有序的排列
分塊索引把數據集的記錄分成了若干塊，滿足倆個條件
塊內無序
塊間有序
倒排索引(P312)
概念：記錄號表存儲具有相同次關鍵字的所有記錄的記錄號 (可以指向記錄的指針或者該記錄的主關鍵字)
搜索引擎最基礎的搜索技術
二叉搜索樹(又稱二叉查找樹/排序數)特點：
若左子樹不為空，則左子樹上所有結點值均小于根結點的值
若右子樹不為空，則右子樹上所有結點的值均大于它的根結點的值
它的左右子樹也分別為二叉排序樹
優(yōu)點：
是一個既使得插入和刪除效率不錯，又可以比較高效率的實現查找的算法
缺點：
極端情況下，會退化成鏈表。時間復雜度為O(n)
平衡二叉搜索樹(AVL樹)概念：是一種二叉排序樹，其中每一個節(jié)點 的左子樹和右子樹的高度差絕對值不超過1
優(yōu)缺點：
維護這種高度平衡所付出的代價比從中獲得的效率收益還大，故而實際的應用不多， 更多的地方是用追求局部而不是非常嚴格整體平衡的紅黑樹。 當然，如果應用場景中對插入刪除不頻繁，只是對查找要求較高，那么AVL還是較優(yōu)于紅黑樹。
多路查找樹(B樹)概念：每一個結點的孩子樹可以多余倆個，且每一個結點處可以存儲多個元素
4種形式
2-3樹
每一個結點都具有倆個孩子(稱為2結點)，或三個孩子(稱為3結點)
2-3-4樹
2-3樹的擴展，最多四個孩子
B樹
一種平衡的多路查找樹
所有葉子結點都位于同一層
B+樹
應文件系統(tǒng)那個所需而出的一種B樹的變形樹
出現在分支節(jié)點中的元素會在葉子結點中再次列出，每一個葉子結點都會保存一個指向后一葉子結點的指針
紅黑樹概念：一種自平衡二叉查找樹，和AVL樹類似(并不是真正的平衡二叉樹)， 都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能。
適合：適合搜索，插入，刪除較多的情況
性質：
每個結點要么是紅色，要么是黑色
根結點永遠是黑色
所有的葉節(jié)點都是空結點(即null)，并且是黑色的
每個紅色結點的倆個子結點都是黑色(從每個葉子到跟的路徑上不會有倆個連續(xù)的紅色結點)
從任一結點到其子樹中每個葉子結點的路徑都包含相同數量的黑色結點
關鍵性質：
這些性質強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。主要原因在于，性質4導致了路徑不能有兩個毗連的紅色節(jié)點，最短的可能路徑都是黑色節(jié)點，最長的可能路徑有交替的紅色和黑色節(jié)點，根據性質5所有最長的路徑都有相同數目的黑色節(jié)點，這就表明了沒有路徑能多于任何其他路徑的兩倍長
散列表查找(哈希表)概念：散列技術是在記錄的存儲位置和它的關鍵字之間建立一個穩(wěn)定的對于關系f， 使得每個關鍵字key對于一個存儲位置f(key)，f稱為散列函數，又稱為哈希(Hash)函數
特點
在存儲時，通過散列函數計算記錄的散列地址，并按此散列地址存儲該記錄
查找記錄時，我們通過同樣的散列函數計算記錄的散列地址，按此散列地址訪問該記錄
缺點
有時候倆個關鍵字不同，但是算出來的地址相同，稱為沖突
散列函數構造方法
直接定址法
數字分析法
平方取中法
折疊法
除留余數法
隨機數法
散列沖突的解決方法
開放定址法
一個沖突，就去尋找下一空的散列函數
再散列函數法
準備多個散列函數，有沖突就換一個
鏈地址法
公共溢出區(qū)法
沖突的都單獨存儲到溢出表中
排序運算
概念
內排序與外排序內排序是在排序整個過程中，待排序的所有記錄都放置在內存中。外排序是由于排序的記錄太多， 不能同時放置在內存，整個排序過程需要在內外存之間多次交換數據才能進行
排序種類
冒泡排序復雜度O(n2) 2是上標
正宗的冒泡排序是相鄰元素倆倆比較
冒泡排序優(yōu)化加個flag，如果后面后面已經是有序的了，就不需要再繼續(xù)后面的循環(huán)判斷了
簡單選擇排序每個元素依次和后面所有的元素比較大小
直接插入排序將一個記錄插入到已經排好序的有序表中，從而得到一個新的記錄數+1的有序表
希爾排序把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；雖則增量逐漸減少， 每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組
堆排序利用堆這種數據結構所設計的一種排序算法
歸并排序將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序
快速排序通過一次排序將待排序記錄分割稱獨立的倆部分，其中一部分記錄的關鍵字均比另一部分小， 則可分別堆這倆部分記錄繼續(xù)進行排序，以達到整個序列有序的目的
算法算法是解決特定問題求解步驟的描述。
時間復雜度(大O表示法)
推導方法
\1. 用常數1取代運行時間匯總的所有加法常數
\2. 在修改后的運行次數函數中，只保留最高階
\3. 如果最高階項存在且不是1，則去除與這個項相乘的常數， 得到的結果就是大O階
常見的復雜度
常數階 =>O(1)
線性階 =>O(n)
對數階 =>O(log2n，縮寫為logn)
平方階 =>O(n2)
內容結束，感謝瀏覽，如果需要pdf等類型文檔，記得私信！💪你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧
重慶分公司
重慶分公司
