數據結構與算法

　　◆算法的基本概念

　　1. 算法：是對問題處理方案的正確而完整的描述，是求解問題的方法，是指令的有效序列。

　　2. 具有5個特性：

　　(1) 有窮性(在有窮步后完成)算法程序的運行時間是有限的

　　(2) 確定性(每一步都有確定的含義)

　　(3) 可行性

　　(4) 輸入(一個算法有零個或多個輸入)

　　(5) 輸出(一個算法有一個或多個輸出)

　　3. 算法的復雜度

　　包括：時間復雜度和空間復雜度。 二者沒有必然的聯系。

　　時間復雜度：執行算法所需要的計算工作量或基本運算次數。

　　空間復雜度：算法所需要的空間的度量。

　　◆數據結構的定義

　　1. 數據結構包括數據的邏輯結構、數據的存儲結構、數據的操作

　　數據的邏輯結構：數據的外部結構，指各數據元素之間的邏輯關系，反映人們對數據含義的解釋。 包括：線性結構(線性表、棧、隊列)和非線性結構(樹和圖)

　　數據的存儲結構：數據的物理結構，指數據的邏輯結構在計算機中的表示。

　　一個邏輯結構可以有多種存儲結構。

　　◆ 線性表：線性表中元素的個數n(n>=0)定義為線性表的長度。

　　順序存儲是線性表的一種最常用的存儲方式。

　　線性表的順序存儲結構和線性表的鏈式存儲結構分別是隨機存取的存儲結構和順序存取的存儲結構。

　　1.棧：是限定在表尾進行插入和刪除操作的線性表。 具有記憶功能 只能順序存儲(錯)

　　允許插入和刪除的一端叫棧頂。另一端叫棧底。

　　后進先出的線性表

　　2隊列：是限定在一端插入而在另一端刪除，插入端叫隊尾，刪除端叫對頭。

　　先進先出的線性表

　　3棧和隊列的順序存儲結構

　　循環隊列屬于線性表存儲結構中順序存儲結構和鏈式存儲結構的前者。

　　◆ 樹

　　1.定義:樹的結點、度(結點的度)、葉子(終端結點)、數的度、深度、有序樹和無序數

　　2.二叉樹：結點至多有兩棵子樹，并且二叉樹的子樹有之分，次序不能顛倒。

　　性質：★在二叉樹的第i層上至多有2i-1個結點

　　★ 深度為k的二叉樹至多有2k-1個結點。

　　★ 對任一個二叉樹T，如果其葉子(終端結點數)為n，度為二的結點數為m,則n=m+1.

　　★ 具有n個結點的完全二叉樹的深度為k+1，其中k是㏒2n的整數部分。

　　2. 二叉樹的遍歷

　　▼先序遍歷(根—左—右)

　　▼中序遍歷(左—根—右)

　　▼后序遍歷(左—右—根)

　　◆查找算法

　　(1)順序查找

　　順序查找的平均查找長度為(n+1)/2，最壞的情況下比較的次數為n

　　(2) 二分查找

　　限定于順序存儲的有序線性表

　　◆排序算法

　　(1)插入類排序

　　▲直接插入排序

　　▲折半插入排序

　　▲希爾排序

　　(2)交換類排序

　　▲冒泡排序 最壞情況下的比較次數n(n-1)/2

　　▲快速排序 最壞情況下的比較次數n(n-1)/2

　　(3)選擇類排序

　　例題精選:

　　1. 設一棵完全二叉樹共有699個結點,則在該二叉樹中的葉子結點數為:350

　　2. 已知二叉樹后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列為：cedba

　　3. 要求內存量最大的是：歸并排序

　　4. 在數據結構中，與所使用的計算機無關的是數據的是：邏輯結構

　　5. 棧底至棧頂依次存放元素A.B.C.D,在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是：DCBEA

　　6. 已知數據表A 中每個元素距其最終位置不遠，為節省時間，應采取的算法是：直接插入排序

　　7. 用鏈式表示線性表的優點是：便于插入和刪除操作。