《數據結構》必須掌握的知識點與算法第一章緒論1、算法的五個重要特性〔有窮性、確定性、可行性、輸入、輸出〕2、算法設計的要求〔正確性、可讀性、健壯性、效率與低存儲量需求〕3、算法與程序的關系：〔1〕一個程序不一定滿足有窮性。例操作系統，只要整個系統不遭破壞，它將永遠不會停止，即使沒有作業需要處理，它仍處于動態等待中。因此，操作系統不是一個算法?！?〕程序中的指令必須是機器可執行的，而算法中的指令則無此限制。算法代表了對問題的解，而程序則是算法在電腦上的特定的實現?！?〕一個算法假設用程序設計語言來描述，則它就是一個程序。4、算法的時間復雜度的表示與計算〔這個比較復雜，具體看算法本身，一般關心其循環的次數與N的關系、函數遞歸的計算〕第二章線性表1、線性表的特點：〔1〕存在唯一的第一個元素；〔這一點決定了圖不是線性表〕〔2〕存在唯一的最后一個元素；〔3〕除第一個元素外，其它均只有一個前驅〔這一點決定了樹不是線性表〕〔4〕除最后一個元素外，其它均只有一個后繼。2、線性表有兩種表示：順序表示〔數組〕、鏈式表示〔鏈表〕，棧、隊列都是線性表，他們都可以用數組、鏈表來實現。3、順序表示的線性表〔數組）地址計算方法：〔1〕一維數組，設DataTypea[N]的首地址為A0，每一個數據〔DataType類型〕占m個字節，則a[k]的地址為：Aa[k]=A°+m*k〔其直接意義就是求在數據a[k]的前面有多少個元素，每個元素占m個字節〕〔2〕多維數組，以三維數組為例，設DataTypea[M][N][P]的首地址為A000,每一個數據（DataType類型〕占m個字節，則在元素a[i][j][k]的前面共有元素個數為：M*N*i+N*j+k，其其地址為：4、線性表的歸并排序:Aa[i]U][k]=A000+m*(M*N*i+N*j+k)；4、線性表的歸并排序:5、掌握線性表的順序表示法定義代碼，各元素的含義;7、順序線性表的元素的查找。8、順序線性表的元素的插入算法，注意其對于91011、鏈表的定義代碼，各元素的含義，并能用圖形象地表示出來，以利分析;12、鏈表中元素的查找13、鏈表的元素插入，算法與圖解，14、鏈表的元素的刪除，算法與圖解，15、鏈表18、循環鏈表的定義，意義19、循環鏈表的構造算法〔其與單鏈表的區別是在創建時確定的〕、圖解20、循環鏈表的插入、刪除算法、圖解21、雙向鏈表的定義，意義22、雙向鏈表的構造算法〔其與單鏈表的區別是在創建時確定的〕、圖解24、補充：在循環鏈表中，只設立一個表尾指針比只設立一個表頭指針更方便些，為什么？第三章棧和隊列1、棧的順序表示與實現2、棧的鏈表表示與實現3、棧的入棧、出棧操作算法4、棧的幾個經典應用〔迷宮、表達式求值〕5、棧與遞歸的實現，如Hanoi塔問題6、隊列鏈式表示與實現7、鏈式隊列的入隊、出隊操作算法8、循環隊列的表示〔順序表示〕和實現，特別注意其判滿、判空方法、入隊操作、出隊操作的實現〔特別重要，考得頻率很大〕9、補充：共享棧的方法與實現〔即兩個棧共享一個空間，他們采用棧頂相向，迎面增長的存儲方式〕10、補充：用兩個棧來模擬一個隊列的思路、算法11、補充：表達式〔前綴、后綴、中綴〕的表達互換，這個操作要求對棧在表達式求值中的應用相當熟練，并要求對后面的二叉樹相當熟練12、補充：了解雙端隊列〔只需了解〕13、補充：鏈棧比順序棧的優點與缺點14、補充：一系列元素依次入棧再出棧的順序，經典題目為：有5個元素，其入棧次序為A、B、C、D、E，以下哪種出棧的順序是不可能的？15、補充：了解用循環鏈表實現隊列，注意在該循環鏈表中只有一個頭指針或一個表尾指針〔只需了解〕16、補充：根據給出的數學公式，寫出對應的遞歸算法，最經典的就是用遞歸求階乘。第六章樹和二叉樹1、幾個重要的概念：樹、森林、子樹、根、終端結點〔葉子〕、非終端結點、雙親、孩子、兄弟、堂兄弟、度、深度、有序樹、無序樹、二叉樹、k叉樹、完全二叉樹、滿二叉樹、線索二叉樹；2、二叉樹的5種基本形態；3、二叉樹的5個重要性質：〔1〕在二叉樹的第i層上至多有2/-1個結點〔iN1〕；〔2〕深度為k的二叉樹至多有2k—1個結點，般N1〕〔3〕對任何一棵二叉樹T，如果其終端結點〔葉子〕數為n0，度為2的結點數為n2,則n0=n2+1；〔4〕具有n個結點的完全二叉樹的深度為Llog2nJ+1；〔5〕如果對一棵有n個結點的完全二叉樹〔其深度為Llogn」+1〕的結點按性層序編號〔從第12層到第LlognJ+1層，每層從左到右〕，則對任一結點i〔IWiWn〕，有：.....一一…■〔i〕如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親Parent〔i〕是結點項」〔ii〕如果2i>n，則結點i無左孩子〔結點i為葉子結點〕；否則其左孩子LChild(i〕是結點2i；(iii〕如果2i+1>n，則結點i無右孩子；否則其右孩子RChild(i〕是結點2i+1利用完全二叉樹的上述性質，能處理大多數完全二叉樹的計算題；4、二叉樹的存儲結構：〔1〕了解順序存儲結構，只做了解；〔2〕鏈式存儲結構，重要，需要掌握，后面的算法都是基于此結構；5、二叉樹的遍歷：〔1〕能對任意一棵二叉樹進行手動前序、中序、后序遍歷；〔2〕能將由前序+中序、后序+中序給出的序列復原成一棵二叉樹；〔3〕能將一個數學表達式用中序方法將其用二叉樹畫出來，并能寫出其前綴〔波蘭式〕、中綴、后綴〔逆波蘭式〕表達出來；6、二叉樹的遍歷遞歸算法〔注意前、中、后序三個算法只有細微的差異〕，可見算法6.1，而他們的非遞歸算法不作要求；7、建立二叉樹鏈表的遞歸算法，可見算法6.4；8、線索二叉樹的存儲結構圖；9、能用手畫出任意二叉樹對應的線索二叉樹〔中序、后序線索〕；10、線索二叉樹的非遞歸遍歷算法，可見算法6.5；11、理解線索二叉樹的中序線索化過程算法，可見算法6.6；12、手動寫出任意森林、樹的深度優先、廣度優先遍歷順序；13、森林、二叉樹的轉換過程，能用手畫出即可；14、哈夫曼樹的相關概念：路徑長度、帶權路徑長度WPL、權值；15、二叉哈夫曼樹的構造過程，能用手動構造，并能將構造好的樹用編碼表示出來；16、了解哈夫曼樹的構造算法，可見算法6.12,只需要了解，無需掌握；17、記住樹的記數公式：對一棵有n個結點的有七Cn棵不同的二叉樹18、補充：二叉排序樹、插入、刪除結點的操作〔在查找一章中有詳述〕；19、補充：滿二叉樹、完全二叉樹用數組存儲方式，其元素、結點對應關系；20、補充：求二叉樹的高度〔深度〕算法；21、補充：將二叉樹中左、右孩子交換的算法；22、補充：將用數組存儲的完全二叉樹轉換成鏈式結構的算法；23、補充：對用數組存儲的完全二叉樹進行非遞歸的前序、中序、后序遍歷算法；24、補充：求二叉樹中葉子數、度為1的、度為2的結點數算法；25、補充：對于K叉樹，其結點總數為N，求出該樹的最大高度、高小高度；26、補充：構造結點數為n的k叉哈夫曼樹〔其所有的結點要么度為0，要么度為k〕，注意一般都需要增加m個權為0的結點〔稱為虛結點〕，其中如果葉子結點數目不足以構成正則的k叉樹〔樹中只有度為k或0的結點〕，即不滿足(n-1)M0D(k-1)=0〔其中MOD是取余運算〕，需要添加權為0的結點，添加的個數為m=k-(n-1)MOD(k-1)-1。添加的位置應該是距離根結點的最遠處。假設n=10，k=3，則需要添加1個權為0的虛結點〔其字母可以為空〕。第七章圖1、圖的幾個重要概念：頂點、孤、孤尾、孤頭、邊、有向圖、無向圖、完全圖、鄰接點、入度、出度、度、路徑、回路〔環〕、連通圖、連通分量、強連通圖、強連通分量、生成森林、關節點、重連通圖、AOV-網、AOE-網；2、圖的幾種存儲、表示方法：數組表示法〔重要〕、鄰接表〔最重要，應用最廣〕、逆鄰接表〔掌握〕、十字鏈表〔理解〕、鄰接多重表〔了解〕，并能大致掌握他們各種方法表示的優缺點；3、圖的兩種遍歷順序：深度、廣度優先，建議同時掌握其算法；4、圖的生成樹和生成森林〔只需掌握手畫方法〕；5、圖的最小生成樹的兩種算法：普里姆〔Prim〕算法〔實質是頂點優先〕、克魯斯卡爾〔Kruskal〕算法〔實質是邊優先〕，掌握他們的手動構造過程，了解算法；6、理解求關節點算法，可見算法7.10、7.11；7、了解拓撲排序；8、掌握由AOE-網得到關鍵路徑的方法〔手動〕，了解算法〔7.13、7.14〕；9、掌握最短路徑的手動求解過程、方法〔兩種：迪杰斯特拉Dijkstra、弗洛伊德Floyd〕，了解算法;10、補充：Prim算法、Kruskal算法、Dijkstra算法、Floyd算法的時間復雜度；11、補充：了解拓撲排序算法；12、補充：能將圖的抽象定義，如有向圖G=〔V,{A}〕，V={v1,v2,v3,v4},A={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}畫成圖，也能將圖用抽象定義寫出；13、補充：能根據圖的鄰接表、逆鄰接表、數組表示法表示出來的圖畫出，亦能根據圖寫出其鄰接表、逆鄰接表、數組表示法；14、補充：了解四色定理(Fourcolortheorem):最先是由一位叫古德里〔FrancisGuthrie〕的英國大學生提出來的。德?摩爾根〔AugustusDeMorgan,1806?1871〕1852年10月23日致哈密頓的一封信提供了有關四色定理來源的最原始的記載。他在信中簡述了自己證明四色定理的設想與感受。四色問題的內容是“任何一張地圖只用四種顏色就能使具有共同邊界的國家染上不同的顏色。”用數學語言表示，即“將平面任意地細分為不相重疊的區域，每一個區域總可以用1,2,3,4這四個數字之一來標記，而不會使相鄰的兩個區域得到相同的數字?！?5、補充：了解離散數學中的歐拉圖、哥尼斯堡七橋問題；16、補充：了解漢密爾頓圖；第九章查找1、掌握幾個重要的概念：靜態查找表、動態查找表、平均查找長度、二叉排序樹、平衡二叉樹、平衡因子、B-樹、B+樹、哈希表；2、順序表的查找算法〔9.1〕及其時間復雜度的性能分析；3、折半查找〔二分查找〕算法〔9.2〕及其性能分析；4、能畫出任意個數元素的二分查找過程形成的判定樹；5、掌握次優二叉查找樹的構造過程，能用手畫出，其算法只做了解要求；6、掌握索引順序表的查找〔又稱分塊查找〕基本原理，并能分析其性能；7、能手動根據元素的順序，構造出一棵二叉排序樹；8、掌握二叉排序樹的幾種算法：查找算法〔、9.5b〕、二叉排序樹的插入算法〔9.6〕，而插入過程就是構造二叉排序樹的過程；9、掌握二叉排序樹的刪除結點的手動過程及算法〔9.7、9.8〕；10、掌握二叉排序樹的查找性能分析過程；11、平衡二叉樹的構造過程，重點在于平衡被破壞后的調整，LL型、LR型、RR型、RL型的平衡旋轉處理；12、平衡樹查找的性能分析；13、B-樹的查找操作，了解其算法；14、B-樹的查找性能分析；15、B+樹的查找操作；16、引入哈希表的目的、優點、基本原理；17、了解幾種常用的哈希函數：直接定址法、數字分析法、平方取中法、折疊法、除留余數法、隨機數法；18、掌握幾種常用的處理沖突的方法：開放定址法〔線性探測法、偽隨機數序列法〕、再哈希法、鏈地址法、公共溢出區法；19、哈希表的查找性能分析；第十章內部排序1、掌握幾個重要的概念：排序、排序方法的穩定性〔即關鍵字相同的經排序后原順序會不會變化〕、排序算法效率的穩定性〔即排序算法效率會不會受待排序數據序列的影響而出現較大的變化〕、內部排序、外部排序、堆2、直接插入排序的過程〔手動分析一趟排序的過程、結果〕、算法〔10.1〕；3、掌握折半插入排序算法〔10.2〕、理解2一路插入排序、了解表插入排序；4、希爾排序過程〔手動分析一趟排序的過程、結果〕、算法〔10.4、10.5〕；5、冒泡排序過程〔手動分析一趟排序的過程、結果〕、算法；6、快速排序過程〔手動分析一趟排序的過程、結果〕、原理、算法〔10.6-8〕7、快速排序性能分析；8、簡單項選擇擇排序過程〔手動分析一趟排序的過程、結果〕、算法〔10.9〕；9、堆排序過程〔手動分析建初始堆過程、一