? ? 1圖的表示
????????這節(jié)課學習了圖這種非線性表數(shù)據(jù)結(jié)構(gòu)约计，關(guān)于圖，我們需要理解這樣幾個概念：無向圖迁筛、有向圖煤蚌、帶權(quán)圖、定點细卧、邊尉桩、度、入度酒甸、出度魄健。除此之外，我們還學習了圖的兩個主要的存儲方式：鄰接矩陣和鄰接表插勤。
? ? ? ? 鄰接矩陣存儲方法的缺點是比較浪費空間沽瘦，但是優(yōu)點是查詢效率高，而且方便矩陣運算农尖。鄰接表存儲方法中每個頂點都對應一個鏈表析恋，存儲與其相連接的其他頂點。盡管鄰接表的存儲方式比較節(jié)省存儲空間盛卡，但鏈表不方便查找助隧，所以查詢效率沒有鄰接矩陣存儲方式高。針對這個問題，鄰接表還有改進升級版并村，即將鏈表換成更加高效的動態(tài)數(shù)據(jù)結(jié)構(gòu)巍实，比如平衡二叉查找樹、跳表哩牍、散列表等棚潦。
? ? 2深度和廣度優(yōu)先搜索
? ? ? ? 廣度優(yōu)先搜索和深度優(yōu)先搜索是圖上的兩種最常用、最基本的搜索算法膝昆，比起其他高級的搜索算法丸边，比如A*、IDA*等荚孵，要簡單粗暴妹窖，沒有什么優(yōu)化，所以收叶，也被叫做暴力搜索算法骄呼。所以，這兩種搜索算法僅適用于狀態(tài)空間不大判没，也就是說圖不大的搜索谒麦。
? ? ? ? 廣度優(yōu)先搜索，通俗的理解就是哆致，地毯式層層推進，從起始頂點開始患膛，依次往外遍歷摊阀。廣度優(yōu)先搜索需要借助隊列來實現(xiàn)，遍歷得到的路徑就是踪蹬，起始頂點到終止頂點的最短路徑胞此。????
? ? ? ? 深度優(yōu)先搜索用的是回溯思想，非常適合用遞歸實現(xiàn)跃捣。換種說法漱牵，深度優(yōu)先搜索是借助棧來實現(xiàn)的。
? ? ? ? 在執(zhí)行效率方面疚漆，深度優(yōu)先搜索和廣度優(yōu)先搜索的時間復雜度都是O(E)酣胀，空間復雜度是O(V)。
? ? 3字符串匹配基礎（上）
? ? ? ? 這節(jié)課學習了兩種字符串匹配算法娶聘，BF算法和RK算法闻镶。
? ? ? ? BF算法是最簡單、粗暴的字符串匹配算法丸升，它的實現(xiàn)思路是铆农，拿模式串與主串中所有子串匹配，看是否有能匹配的子串狡耻。所以墩剖，時間復雜度也比較高猴凹，是O(n*m)，n岭皂、m表示主串和模式串的長度郊霎。不過在實際的軟件開發(fā)中，這種算法實現(xiàn)簡單蒲障，對于處理小規(guī)模的字符串匹配很好用歹篓。
? ? ? ? RK算法是借助哈希算法對BF算法進行改造，即對每個子串分別求哈希值揉阎，然后拿子串的哈希值與模式串的哈希值比較庄撮，減少了比較的時間。所以毙籽，理想情況下洞斯，RK算法的時間復雜度是O(n)，跟BF算法相比坑赡，效率提高了很多烙如。不過這樣的效率取決于哈希算法的設計方法，如果存在沖突的情況下毅否，時間復雜度可能會退化亚铁。極端情況下，哈希算法大量沖突螟加，時間復雜度就退化為O(n*m)徘溢。
? ? 4字符串匹配基礎（中）
? ? ? ? 這節(jié)課學習了一種比較復雜的字符串匹配算法，BM算法捆探。盡管復雜然爆、難懂，但是匹配的效率卻很高黍图，在實際的軟件開發(fā)中曾雕，特別是一些文本編輯器中，應用很多助被。
? ? ? ? BM算法的核心思想是剖张，利用模式串本身的特點，在模式串中某個字符與主串不能匹配的時候揩环，將模式串往后多滑動幾位修械，以此來減少不必要的字符比較，提高匹配的效率检盼。BM算法構(gòu)建的規(guī)則有兩類肯污，壞字符規(guī)則和好后綴規(guī)則。好后綴規(guī)則可以獨立于壞字符規(guī)則使用，因為壞字符規(guī)則的實現(xiàn)比較消耗內(nèi)存蹦渣，為了節(jié)省內(nèi)存哄芜，我們可以只用好后綴規(guī)則來實現(xiàn)BM算法。
? ? 5字符串匹配基礎（下）
? ? ? ? KMP算法和上一節(jié)講的BM算法的本質(zhì)非常類似柬唯，都是根據(jù)規(guī)律在遇到壞字符的時候认臊，把模式串往后多滑動幾位。
? ? ? ? BM算法有兩個規(guī)則锄奢，壞字符和好后綴失晴。KMP算法借鑒BM算法的思想，可以總結(jié)成好前綴規(guī)則拘央。這里面最難懂的就是next數(shù)組的計算涂屁。如果用最笨的方法來計算，確實不難灰伟，但是效率會比較低拆又。所以我們學習了一種類似動態(tài)規(guī)劃的方法，按照下標i從小到大栏账，依次計算next[i]帖族，并且next[i]的計算通過前面已經(jīng)計算出來的next[0]，next[1]挡爵，......竖般，next[i-1]來推導。
? ? ? ? KMP算法的時間復雜度是O(n+m)茶鹃，不過它的分析過程稍微需要一點技巧捻激，不那么直觀，我們懂了即可前计，無需掌握，在平常的開發(fā)中垃杖，很少會有這么難分析的代碼男杈。
