Frank 直面数据结构
出處:https://space.bilibili.com/19658621/dynamic
該視頻知識產(chǎn)權(quán)為B站Micro_Frank所有。
Frank語錄：
本門課的目的是將數(shù)據(jù)結(jié)構(gòu)與代碼脫離開來，這是傳統(tǒng)教育很難做到的。
了解思想比一個題做個十遍頂用多了。
可以結(jié)合每個視頻中的問題看看自己能否回答出來
一、Academic
0-0.剖析數(shù)據(jù)結(jié)構(gòu)的含義，數(shù)據(jù)結(jié)構(gòu)的用途，區(qū)分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法
數(shù)據(jù)結(jié)構(gòu)（英語：data structure）是計算機中存儲，組織數(shù)據(jù)的方式。
總的來說就是（1）數(shù)據(jù)的（2）存儲與（3）組織。
1）數(shù)據(jù)：比如我們的QQ號，微信ID，支付密碼了；這些都叫數(shù)據(jù)；
2）存儲：以何種方式存放數(shù)據(jù)，鏈表，數(shù)組，樹，圖。。。
3）組織：CRUD增刪改查；
線性表就是數(shù)組，國際上沒有線性表這個詞，是我們直譯過來的；
他們并不是與關(guān)系，不是學(xué)數(shù)據(jù)結(jié)構(gòu)我就要一定會算法，這是我國的教育方式罷了；算法只是研究組織數(shù)據(jù)結(jié)構(gòu)最優(yōu)的CRUD解。它是更好的，更有效地對數(shù)據(jù)存儲。
1-0.內(nèi)存，內(nèi)存是如何保存不同數(shù)據(jù)類型的
1)數(shù)據(jù)在內(nèi)存中存儲應(yīng)該是什么樣的？
內(nèi)存條中像圖中的每一個單元格都是有自己的地址，一個格子可以是一個字節(jié)，那么如果要存取一個大型數(shù)據(jù)(比如一個4字節(jié)的數(shù)據(jù))，就必須存儲在連續(xù)的單元格。
拿int（占用4個字節(jié)）舉例，有數(shù)組 int arr[1,2];
假如1號單元格已被占用，那么，如果我們存儲數(shù)組中的1，就必須重新分配一個連續(xù)的空間，比如2，3，4，5；
生活中的例子：
住院部，幾個病人要求住在連續(xù)序號的房間中；
1-1.int類型的范圍是如何計算的？為什么會占用四個字節(jié)？四個字節(jié)為什么可以表示該范圍？內(nèi)存中是怎樣的
語言不重要。
1)在c/c++中：
不同的編程語言中取值范圍是不同的。在c/c++語言中int范圍取決于字長。 字長是計算機處理的最大位數(shù)，與cpu有關(guān)。所以了，在32位機器上，字長就是32位，此時表示范圍：2^32。
考慮正負(fù)號(有符號位):表示范圍為-(231)~(231)-1
不考慮正負(fù)號( 無符號位):表示范圍為 0~(2^32)-1
2）python：
python中int范圍表示是無限的。
2-0.Computational Analysis of algorithms計算機算法復(fù)雜度分析的基本含義
引出時間復(fù)雜度與空間復(fù)雜度。
以從不同的目的地去往市中心為例子,如下圖：
去往市中心（downtown）有三個地點（a,b,c），從圖中看出三地路程不盡相同。
而去往downtown的快慢取決于路的遠(yuǎn)近和所使用的交通工具。現(xiàn)在呢，從a,b,c地都有人出發(fā)去往市中心，a地乘客使用飛機，b地乘客使用拖拉機，c地乘客使用汽車。最終，a先到達(dá)，b最后到達(dá)。從這個例子中我們發(fā)現(xiàn)，不是路程近就能先到達(dá)，它與兩個因素都有關(guān)。計算機同理。
在計算機中我們可以把路程比作空間復(fù)雜度，所使用的交通工具比作時間復(fù)雜度。我們通常所說的時間復(fù)雜度是使用相同計算能力的機器，考慮如何在更短的時間能夠完成任務(wù)。
在計算機中，空間復(fù)雜度難以度量。
3-0.Big O notation復(fù)雜度標(biāo)記符以及舉例
1）該如何理解這些復(fù)雜度的數(shù)值？
以數(shù)組為例
O(1) 查找某個病房的住的是誰
O(n)醫(yī)生早上查病房，每個病人都要去看一遍
O(n^2) n個女的和n個男的每個XJ一次；
3-1.復(fù)雜度對比函數(shù)圖
3-2.最基礎(chǔ)的對數(shù)復(fù)習(xí)，照顧職業(yè)院校學(xué)生。
1）什么是對數(shù)?
對于指數(shù)：2^3=8 ,對數(shù)就是問 2的幾次方=8 。答案是3。
2)介紹log2n的含義，為什么它的值越來越平滑？
? 從上節(jié)圖中可以發(fā)現(xiàn)問題，為什么logn越的值來越平滑？
舉個數(shù)組擴(kuò)容例子。
如下數(shù)組：
int arr[1];
int arr[1，2];
int arr[1，2，3，4];
int arr[1，2，3，4，5，6，7，8];
int arr[1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16];
我們現(xiàn)在需要做的事情是：如果我該數(shù)組已經(jīng)使用完，而我還需要在該數(shù)組存放元素，那么我就需要先把該數(shù)組擴(kuò)容為原來的1倍。然后接著在數(shù)組中存放元素，如果我又用完了，我就接著擴(kuò)容。一直如此。
對于上述數(shù)組：
要變做int arr[1，2];則是在int arr[1]基礎(chǔ)上擴(kuò)容一倍；
要變做int arr[1，2，3，4];則是在int arr[1，2]基礎(chǔ)上擴(kuò)容一倍；
…
上述數(shù)組長度變化：1->2->4->8->16->32->64…->2^N。
長度為1的數(shù)組，經(jīng)過n次不斷的擴(kuò)容，數(shù)組會變得會變得非常大。而隨后的每次擴(kuò)容出來的值會更大，你一下子也很難用完，想再去擴(kuò)容也會變得很慢，所以這個值會很平緩。
4-0.Array
提及國內(nèi)翻譯錯誤？
國際上沒有線性表( Linear list )這個概念；
Linear list 就是Array 和Linked list，而不是線性表，直接說成數(shù)組和鏈表
如何理解數(shù)組在內(nèi)存中的存儲以及如何找到想要的指定元素位置？
我們要存儲數(shù)組 int arr[1,2,3,4]；
前提：首先呢 ，在內(nèi)存中1號位置已經(jīng)被占用，那么現(xiàn)在我們要存儲該數(shù)組中的四個元素，需要怎么存儲呢。
首先我們每一個格子是一個字節(jié)，而數(shù)組中的每一個整形數(shù)據(jù)都為4個字節(jié)，那么數(shù)組中4個元素 則需要 4*4=16個字節(jié)，而一號位置已經(jīng)被占用，則從2號位置開始放 這些元素，存放完這些元素要到17號停止。
那么我們要訪問指定元素（下標(biāo)為n所在位置的元素值），只需要套用如下公式，首地址+sizeof（數(shù)據(jù)長度）*n。
比如3號元素 ： 2+4*3 = 14，那么3號位置的元素就是從14號開始的。
4-1.Static Array 復(fù)雜度分析
1）查早與修改時間復(fù)雜度？
通過四則運算就能夠找到對應(yīng)下標(biāo)，然后修改對應(yīng)的值即可。
時間復(fù)雜度：O (1) T
2）插入考慮 RAM的隨機性？在首中尾位插入？時間復(fù)雜度？
? 你想在首部，中部，和尾部直接插入元素有沒有考慮到該數(shù)組周圍已經(jīng)被占用了。所以你只能重新找一片新的空間，復(fù)制原來的元素再加上新元素。copy的復(fù)雜度為O(n),而插入新元素時間復(fù)雜度為O（1），總的時間復(fù)雜度為O(n+1)，化簡得O(n);
為什么1可以忽略掉？ 那假如O(n^2+2n)，2n可以忽略掉嗎？
當(dāng)數(shù)據(jù)量特別大得時候，比如100萬，它的平方和乘2倍，哪個大？
相對于n^2而言，2n小的可憐，所以我們可以把它化簡掉。就像你都已經(jīng)欠債100萬元，還在乎再欠上100塊？
3）刪除得時間復(fù)雜度？在數(shù)組首，尾，中 ，刪除有區(qū)別嗎？
首先先給出結(jié)論。刪除數(shù)組首，中間的元素時間復(fù)雜度是O(n)T，刪除末尾是O(1)T。
為什么？
首地址不能變，且數(shù)組的元素必須連續(xù)。所以要刪除第一個元素，或者中間的某個元素只能把后面的元素在復(fù)蓋到前一位來。
在末尾直接刪除，首地址沒有變，且刪除后剩余數(shù)組元素是連續(xù)的。
假如要多次刪除首元素，時間復(fù)雜度有多高？我們使用它是不是有點蠢？
假如n個元素，要刪除n次，第一個元素，則時間復(fù)雜度為O(n*n)。
解決辦法：
面試題：jvm中的mark and —sweep（標(biāo)記and清除） 。 就是先把要刪除的都先標(biāo)記，再后統(tǒng)一把后面的往前移。時間復(fù)雜度為O(n)
4-2.Dynamic Array擴(kuò)容復(fù)雜度分析，剖析高級語言中的ArrayList原理，提及復(fù)雜度震蕩的情況
1)動態(tài)數(shù)組就是搶先分配，提前分配出1倍的空間。
2)擴(kuò)容復(fù)雜度為什么是O(n),談?wù)劯邤?shù)中的級數(shù)收斂？
比如數(shù)組int arr[1];
現(xiàn)在數(shù)組要變成 ：
int arr[1，2];
int arr[1，2，3，4];
int arr[1，2，3，4，5，6，7，8];
int arr[1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16];
要變做int arr[1，2];則是在int arr[1]基礎(chǔ)上擴(kuò)容一倍；
要變做int arr[1，2，3，4];則是在int arr[1，2]基礎(chǔ)上擴(kuò)容一倍；
? 對于元素3，插入1，2元素的時間復(fù)雜度都為O(1),而3，是在原來元素基礎(chǔ)上擴(kuò)容出來一倍，然后再插入3這個元素，在這時它的時間復(fù)雜度為O(n+1)為O(n),而4這個元素再插入時時間復(fù)雜度為O(1)，因為4這個元素的空間已經(jīng)是擴(kuò)容出來的。
所以上述不斷地擴(kuò)容時間復(fù)雜度為
O(1)+O(2)+O(4)+ O(8)+O(16)+O(32)+…+O(n)=O(2n)化簡為O(n)
計算用到高數(shù)中的級數(shù)收斂：N+N/2+N/4+N/8+N/16+N/32+…1 約等于2N
上述方法有個裝逼的詞語？
平攤分析。維基百科搜索平攤分析，里面有對數(shù)組平攤分析的介紹。
縮容分析？
5-0.Linked list與Singly linked list含義以及復(fù)雜度分析舉例
用解密游戲理解單鏈表。拿到每個地方的道具，同時哪里還存儲著下個存儲寶藏所在地的信息。
什么是頭節(jié)點，節(jié)點？
單鏈表的時間復(fù)雜度
查：從第一個開始遍歷，直到找到你要的值O(n)
插入：從頭開始遍歷，找到要插入的元素位置；
先查找，再插入 O(n)+O(1) =O(n)
修改：從頭開始遍歷，找到要修改的元素位置
先查找，再插入 O(n)+O(1) =O(n)
刪除：從頭開始遍歷，找到要刪除的元素位置
先查找，再插入 O(n)+O(1) =O(n)
再尾節(jié)點留空，備胎。有的節(jié)點也是指向最后一個元素的，這樣插入時時間復(fù)雜度為O(1)。
數(shù)據(jù)結(jié)構(gòu)離不開內(nèi)存的
5-1.Doubly linked list與Circular linked list含義以及復(fù)雜度分析舉例
1 雙鏈表
雙鏈表，雜交 ，每個節(jié)點有3個塊：pre val next；
雙鏈表時間復(fù)雜度，頭尾O(1),中間O(n)
2循環(huán)列表
循環(huán)列表 ，對于單鏈表，尾部指針指向頭節(jié)點。
? 對于雙鏈表，頭pre指向尾，尾next指向頭節(jié)點。
其時間復(fù)雜度和雙鏈表一樣。
5-2.舉例以及題外話
單鏈表：學(xué)生報名，派對人來的順序。
雙向鏈表：細(xì)小問題沒人注意—》》瀏覽器上面標(biāo)簽欄快進(jìn)，后退。
數(shù)據(jù)結(jié)構(gòu)：從設(shè)計方面去思考；
算法：CRUD效率；
思想很重要。。
這節(jié)可以說就是本門課程的DLC。
6-0.Hash
1）散列算法，哈希函數(shù)？
這兩個詞語是一個意思。這是把一樣?xùn)|西通過函數(shù)計算得到另一樣?xùn)|西過程。把明文加密的過程叫做hash function哈希函數(shù)，比如八路軍過城門檢查。
2）什么哈希碰撞？有什么例子？
通過某種驗證方式是得到你的哈希值和已有的哈希值一樣。
例子：就像人在囧途 兩人票一樣，身份證一樣，特工偽裝完一樣的這種感覺。
3）單向散列函數(shù)？應(yīng)用？
明文加密得到密文，但是把你不能通過計算用密文得到我的明文。
應(yīng)用1：網(wǎng)盤秒上傳功能。你的文件要上傳，網(wǎng)盤會拿你的該文件的哈希值，通過某種函數(shù)與服務(wù)器上存儲的哈希值匹配，如果碰撞上，證明你的文件我的服務(wù)器上也存在，這時候我只需要復(fù)制一份文件的地址給你就歐克了。
應(yīng)用2：蘋果驗證sha驗證下載的文件是不是正版；
6-1.Hash Table或Hash Map的原理與復(fù)雜度分析
1）什么是哈希表？<key,value>？發(fā)生哈希碰撞咋辦？
hash table and hash map是一個東西。把key通過哈希函數(shù)計算得到一個內(nèi)存地址，再把value放到該地址中。這種設(shè)計就是哈希表。如果兩個key計算得到的內(nèi)存地址一樣，那么可以用拉鏈法，再哪個地址中存一個鏈表的首地址。而鏈表的每一個節(jié)點有兩部分。一個放value，一個放key的地址。
2）哈希表時間復(fù)雜度？
平均O(1)
最差O(n) ，因為發(fā)生哈希碰撞，可能要以鏈表的形式存儲。
3）擴(kuò)展？
理解編程語言中hash table的實現(xiàn)，java，python，js。。。。
7-0.Stack堆棧原理的實際用途與時間復(fù)雜度分析
1）棧？堆棧？
一個東西，push與pop不就是堆疊的過程。
什么是棧？打工刷盤子就能理解？
你去打工，你是洗盤子的，服務(wù)員是取盤子用的。
用途？
剪貼板，撤銷，瀏覽器的歷史記錄；
棧的時間復(fù)雜度？
push O(1)
pop O(1)
查看（peek）某個元素 棧頂O( 1) ,剩余的元素O(n)
8-0.Queue原理實際應(yīng)用與時間復(fù)雜度分析（超簡單）
1）隊列？取票？（FIFO）
隊列，就是元素先來先操作，后來后操作。
比如你去排隊取你的火車票，你排在最前面，工作人員肯定先給你辦理，你來的最晚，那你就排在最后面慢慢等著。
2）用什么實現(xiàn)？空間復(fù)雜度？時間復(fù)雜度？
空間復(fù)雜度為O(n);
鏈表：刪除，插入時間復(fù)雜度為 o(1)
查找：O(n)
數(shù)組：查找O(1)，增加O(1),刪除O(n)
3)應(yīng)用
在系統(tǒng)中應(yīng)用廣泛。
比如計算機網(wǎng)絡(luò)中的緩存網(wǎng)絡(luò)數(shù)據(jù)包，我們電腦中后臺進(jìn)程管理。
4)思考最差和平均的出現(xiàn)？！！！！！
我覺得是所操作元素的位置決定，而不是Frank說的和所用的是鏈表還是數(shù)組的原因。
9-0.Tree樹的含義以及術(shù)語
1)什么是樹？
樹就是我們的家譜。
2)理解什么是節(jié)點，根節(jié)點，子節(jié)點，葉子節(jié)點，兄弟節(jié)點，子樹，邊，高度，深度？等級？
節(jié)點：家譜中的所展現(xiàn)的每個人；
根節(jié)點：最上面的人，你的太上老爺這種感覺；
子節(jié)點：根下面的都是子節(jié)點，或者是相對于你爸爸，你就是字節(jié)點；
兄弟節(jié)點：一個爹生下來的孩子，是兄弟；
子樹：族譜中你爸爸和及它的孩子們就相當(dāng)于一個子樹；
高度：假如你是你們家族最新的一代人，相對于你（葉子節(jié)點）而言，上面還有幾代人；
深度：上帝視角，別人看你家族譜，嗯~你家有n代人（包括你這代）；
等級：家譜中的每代人；
9-1.Tree的應(yīng)用
樹就是用來表示層級關(guān)系的；
例子：
公司職位表；
windows的文件管理器中的層級結(jié)構(gòu)；
linux中的命令；
html語言的代碼；
搜索引擎存儲網(wǎng)頁結(jié)構(gòu)；
制作IDE 的語法分析 表述語法樹；
決策樹；
軟件的導(dǎo)航欄（菜單欄）
9-2.常見樹種類
0）二叉樹：每個節(jié)點最多有2個節(jié)點；
1） prefect binary tree
完美二叉樹：同深度的葉子節(jié)點都為2
2）amost prefect binary tree
完全二叉樹：所有的葉子節(jié)點不在同一深度上，且最深的一層所在的葉子節(jié)點必須連接在最左邊的分支上。
3）balance binary tree（AVL）
平衡二叉樹：每個節(jié)點所在子樹中的左右分支中最大高度差為1。
計算方法： 比如
節(jié)點1： 左右子樹差為 3-3 =0；
節(jié)點2： 左右子樹差為 2-1 =1；
節(jié)點4： 左右子樹差為1-0=1；
4）full binary tree
滿二叉樹：每層的葉子節(jié)點不是滿的(2的倍數(shù))。
9-3.樹的進(jìn)一步研究
1）平衡二叉樹，滿二叉樹的時間復(fù)雜度？怎么理解？
空間：O(N)
搜索：O(log n)
插入：O(log n)
刪除：O(log n)
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-eYcaxvft-1673580279223)(.\數(shù)據(jù)結(jié)構(gòu)\image-20230108105522176.png)]
2）為什么插入是O(log n)?其他的也是同理。
首先最重要的是樹的結(jié)構(gòu)，要滿足是平衡二叉樹或者呢滿二叉樹(因為目前Frank視頻中只是講了這幾種樹，所以我說要是平衡二叉樹或者滿二叉樹，其余的自己可以擴(kuò)展了解)。 比如在4的左子樹插入8。那么先經(jīng)過1，然后砍一半，只看節(jié)點2，把3所在的子樹刪除了。然后再2處再砍一半，只看節(jié)點4,然后再4的左邊插入8。這樣的，每次砍一半，看了左半邊，就不看右半邊。**這里注重的是每次只砍一半的感覺，不要在意為什么要在4處插入，為什么只看左子樹。
3）提及其它樹？自己分析。
普通二叉樹 。時間復(fù)雜度O(n)
堆：O(log n)
線段樹，區(qū)間查詢 ，修改 O(log n)
字典樹：O(m)m是鍵的長度。
圖：鄰接表，鄰接矩陣。
9-4.Graph圖的含義以及舉例
1）圖？頂點？邊？
表示關(guān)系
頂點：就是圖中的節(jié)點
邊：有方向的線。邊必須有方向。
2）有向圖，無向圖，循環(huán)圖，無環(huán)圖？例子？
有向圖：有箭頭指向的圖
例如： 飛機從某地到某地有沒有航班。B站用戶相互關(guān)注情況。鐵路某地到某地有沒有鐵路段。無向圖：無箭頭指向的圖，但也是表示這是連接關(guān)系。雖然沒有箭頭。
循環(huán)圖：有至少三個節(jié)點連接成環(huán)，形成了一個循環(huán)的周期
無環(huán)圖：沒有形成環(huán)的圖
注意：樹就是特殊的圖
3）鄰接表，鄰接矩陣？
鄰接表：鏈表。
鄰接矩陣：數(shù)組。
9-5.其他的圖以及時間復(fù)雜度
連通圖：節(jié)點（V）邊（E）遍歷時間復(fù)雜度：O(v+e)
其他的樹時間復(fù)雜度可能與之不同。因為樹的種類太多了。難以一一分析。
擴(kuò)展知識： 最小生成樹，最短路徑算法。。。領(lǐng)域不同，所需要了解的深度不同。
圖最壞的時間復(fù)雜度為O(v+e)。
人工智能，計算機圖形學(xué) 研究圖的。
9-6.總結(jié)
維基百科看看，數(shù)據(jù)結(jié)構(gòu)有多么的多，講不完的。
動漫 境界（死神）；程序員不是全知全能的。
要學(xué)會谷歌，這個東西的含義，在那個領(lǐng)域，特性。如何分析？實際應(yīng)用，有什么例子。
什么是堆？
一種特殊的完全二叉樹。
想要成功，必須合作。
數(shù)據(jù)結(jié)構(gòu)是長期發(fā)現(xiàn)的過程，算法是長期訓(xùn)練的過程。
算法可以在leecode中練習(xí)，并且要學(xué)會定時。
總結(jié)
以上是生活随笔為你收集整理的Frank 直面数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： PPT计算机基础知识,计算机基础知识(精
- 下一篇： 小程序：手持弹幕