順序存儲計算公式 Li=L0+(i-1)×K 順序結構可以進行隨機存取;插人、刪除運算會引起相應節點的大量移動

　　鏈式存儲結構：a、指針域可以有多個，可以指向空，比比順序存儲結構的存儲密度小

　　b、邏輯上相鄰的節點物理上不一定相鄰。 c、插人、刪除等不需要大量移動節點

　　4、順序表：一般情況下，若長度為n的順序表，在任何位置插入或刪除的概率相等，元素移動的平均次數為n/2(插入)和(n-1)/2(刪除)。

　　5、鏈表：線性鏈表(單鏈表和雙向鏈表等等)和非線性鏈表

　　線性鏈表也稱為單鏈表，其每個一節點中只包含一個指針域，雙鏈表中，每個節點中設置有兩個指針域。(注意結點的插入和刪除操作)

　　6、棧：“后進先出”(LIFO)表。棧的應用：表達式求解、二叉樹對稱序周游、快速排序算法、遞歸過程的實現等

　　7、隊列：“先進先出”線性表。應用：樹的層次遍歷

　　8、串：由零個或多個字符組成的有限序列。

　　9、多維數組的順序存儲：

　　10、稀疏矩陣的存儲：下三角矩陣順序存儲

　　其他常見的存儲方法還有三元組法和十字鏈表法

　　11、廣義表：由零個或多個單元素或子表所組成的有限序列。廣義表的元素可以是子表，而子表的元素還可以是子表

　　12、樹型結構：非線性結構。常用的樹型結構有樹和二叉樹。

　　二叉樹與樹的區別：二叉樹不是樹的特殊情況，樹和二叉樹之間最主要的區別是：二叉樹的節點的子樹要區分左子樹和右子樹，即使在節點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。

　　13、樹(森林)與二叉樹之間的轉換(要會轉換)

　　14、二叉樹和樹的周游(遍歷)

　　二叉樹的周游主要有以下3種方式：前序法(NLR)、對稱序法(LNR)、后序法(LRN)

　　周游樹和樹林：深度優先和按廣度優先兩種方式進行。深度優先方式又可分為按先根次序和按后根次序周游

　　樹與二叉樹周游之間的對應關系：按先根次序周游樹正好與按前序法周游樹對應的二叉樹等同，后根次序周游樹正好與按對稱序法周游對應的二叉樹等同

　　按廣度優先方式就是層次次序周游

　　15、二叉樹的存儲和線索

　　二叉樹的存儲結構：二叉樹的llink一rlink法存儲表示

　　線索二叉樹：在有n個節點的二叉樹的且llink - rlink法存儲表示中，必定有n+1個空指針域

　　16、哈夫曼樹：一類帶權路徑長度最短的樹。樹的帶權路徑長度為樹中所有葉子節點的帶權路徑長度之和WPL。

　　17、查找：

　　(1)順序查找：平均查找長度為(n +1 )/2次，時間復雜度為O(n)

　　(2)二分法查找：線性表節點必須按關鍵碼值排序，且線性表是以順序存儲方式存儲的。查找成功比較次數log2n，查找失敗比較次數log2n+1

　　(3)分塊查找：先是塊間查找，然后塊內查找。

　　(4)散列表(哈希表Hash)的存儲和查找：處理沖突的方法：開地址法(線性探測法)、拉鏈法等

　　負載因子(裝填因子)=表實際存儲的結點個數/表的最大能存儲結點個數(即表長)

　　二叉排序樹：每個結點左子樹的所有關鍵碼值都小于該結點關鍵碼值，右子樹所有結點關鍵碼值都大于該結點關鍵碼值。對稱周游二叉排序樹，得到一個有序序列，時間復雜度O(log2n)

　　B樹和B+樹：M階樹，每個結點至多有M-1個關鍵碼，至少有M/2(取上界)-1個關鍵碼。B樹適合隨機查找，不適合順序查找。B+樹適合順序查找。

　　18、排序

　　直接插人排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序算法要了解。

　　直接選擇排序、希爾排序、快速排序和堆排序是不穩定排序，其他排序為穩定排序