09年自考《數據結構》各章要點二[5]

　　構造最小生成樹的算法

　　·Prim算法的時間復雜度為O(n^)與邊數無關適於稠密圖

　　·Kruskal算法的時間復雜度為O(lge)主要取決於邊數較適合於稀疏圖

　　最短路徑的算法

　　·Dijkstra算法時間復雜度為O(n^)

　　·類似於prim算法

　　拓撲排序是將有向無環圖G中所有頂點排成一個線性序列若∈E(G)則在線性序列u在v之前這種線性序列稱為拓撲序列

　　拓撲排序也有兩種方法

　　·無前趨的頂點優先每次輸出一個無前趨的結點並刪去此結點及其出邊最後得到的序列即拓撲序列

　　·無後繼的結點優先每次輸出一個無後繼的結點並刪去此結點及其入邊最後得到的序列是逆拓撲序列

　　第八章 排序

　　記錄中可用某一項來標識一個記錄則稱為關鍵字項該數據項的值稱為關鍵字

　　排序是使文件中的記錄按關鍵字遞增(或遞減)次序排列起來

　　·基本操作比較關鍵字大小改變指向記錄的指針或移動記錄

　　·存儲結構順序結構鏈表結構索引結構

[]  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22738.html