數據結構實用教程（簡體書）

《高職高專工作過程．立體化創新規劃教材．計算機系列：數據結構實用教程》依據高職高專計算機基礎教育的特點，結合作者多年從事計算機教育的經驗編寫而成。全書共10章，主要內容包括緒論、線性表、棧和隊列、串、數組及廣義表、樹、圖、查找、排序以及綜合實訓。 《高職高專工作過程．立體化創新規劃教材．計算機系列：數據結構實用教程》以“工作場景導入”一“知識講解”一“回到工作場景”一“工作實訓營”為主線編寫，以例題配合深入學習，知識講解細緻。同時，每章都有配套的實訓練習，突出了實用性和操作性，另外還提供了實踐中常見問題解析，能夠進一步拓展學生的知識，靈活應對實際操作時會遇到的困難，使學生提高操作能力。本書結構清晰、易教易學、實例豐富、可操作性強、學以致用、注重能力的培養。 《高職高專工作過程．立體化創新規劃教材．計算機系列：數據結構實用教程》注重實際應用，既可作為高職高專院校計算機及相關專業的教材，也可作為各類培訓班的培訓教程。此外，本書也適合於有關工程技術人員、技師參考閱讀。．

《高職高專工作過程?立體化創新規劃教材?計算機系列:數據結構實用教程》注重實際應用，既可作為高職高專院校計算機及相關專業的教材，也可作為各類培訓班的培訓教程。此外，《高職高專工作過程?立體化創新規劃教材?計算機系列:數據結構實用教程》也適合于有關工程技術人員、技師參考閱讀。

第1章 緒論1.1 什麼是數據結構1.1.1 數據結構的產生與發展1.1.2 數據和數據結構1.1.3 數據的邏輯結構和存儲結構1.1.4 數據類型1.2 算法與算法分析1.2.1 算法1.2.2 算法設計的目標1.2.3 算法設計的時間複雜度1.2.4 算法設計的空間複雜度本章小結習題第2章 線性表2.1 工作場景導入2.2 線性表的定義和基本操作2.2.1 線性表的定義2.2.2 線性表的基本操作2.3 線性表的順序存儲結構2.3.1 順序表的特點2.3.2 順序表的基本操作2.4 線性表的鏈式存儲結構2.4.1 單鏈表2.4.2 雙向鏈表2.4.3 循環鏈表2.5 回到工作場景2.6 工作實訓營2.6.1 訓練實例2.6.2 常見問題解析本章小結習題第3章 棧和隊列3.1 工作場景導入3.2 棧3.2.1 棧的概念及操作3.2.2 棧的實現與基本操作3.2.3 棧的應用3.3 隊列3.3.1 隊列的概念及操作3.3.2 循環隊列3.3.3 隊列的基本操作實現3.3.4 隊列的應用3.4 回到工作場景3.5 工作實訓營3.5.1 訓練實例一：模擬排隊看病3.5.2 訓練實例二：模擬計算器3.5.3 常見問題解析本章小結習題第4章 串4.1 工作場景導入4.2 串的基本概念4.3 串的順序存儲結構與基本操作4.4 串的鏈式存儲結構4.5 串的模式匹配4.5.1 Brute.Force算法4.5.2 KMP算法4.6 回到工作場景4.7 工作實訓營4.7.1 訓練實例4.7.2 常見問題解析本章小結習題第5章 數組及廣義表5.1 工作場景導入5.2 數組的定義5.3 數組的順序存儲結構與實現5.3.1 數組的順序存儲結構5.3.2 基本操作的實現5.3.3 數組的應用舉例5.4 矩陣的壓縮存儲5.4.1 特殊矩陣5.4.2 稀疏矩陣5.5 廣義表5.5.1 廣義表的定義5.5.2 廣義表的存儲結構5.5.3 廣義表的應用5.6 回到工作場景5.7 工作實訓營5.7.1 訓練實例5.7.2 常見問題解析本章小結習題第6章 樹6.1 工作場景導入6.2 樹的基本概念6.2.1 樹的定義6.2.2 樹的基本術語6.3 二叉樹6.3.1 二叉樹的基本概念6.3.2 二叉樹的存儲結構6.4 二叉樹的遍歷6.4.1 二叉樹的前序遍歷6.4.2 二叉樹的中序遍歷6.4.3 二叉樹的後序遍歷6.5 線索二叉樹6.5.1 線索二叉樹的定義6.5.2 中序線索二叉樹6.6 樹和森林6.6.1 樹的存儲結構6.6.2 森林、樹、二叉樹的相互轉化6.6.3 樹和森林的遍歷6.7 哈夫曼樹及其應用6.7.1 哈夫曼樹的概念6.7.2 哈夫曼編碼6.8 回到工作場景6.9 工作實訓營6.9.1 訓練實例6.9.2 常見問題解析本章小結習題第7章 圖7.1 工作場景導入7.2 圖的基本概念與存儲方式7.2.1 鄰接矩陣表示法7.2.2 鄰接表表示法7.3 圖的遍歷7.3.1 深度優先搜索遍歷7.3.2 廣度優先搜索遍歷7.3.3 遍歷算法的實現7.4 生成樹和最小生成樹7.4.1 生成樹7.4.2 最小生成樹7.4.3 普裡姆算法7.4.4 克魯斯卡爾算法7.5 最短路徑7.5.1 單源點最短路徑7.5.2 所有頂點對最短路徑問題7.6 回到工作場景7.7 工作實訓營7.7.1 訓練實例7.7.2 常見問題解析本章小結習題第8章 查找8.1 工作場景導入8.2 查找的基本概念8.3 順序查找8.4 二分查找8.5 分塊查找^第9章 排序第10章 綜合實訓附錄 習題參考答案參考文獻．

【問題3】已知某帶權連通無向圖邊的個數遠遠小于頂點的個數，若求其最小生成樹用哪種算法最好？
【答】用克魯斯卡爾（Kruskal）算法較好。該算法的時間復雜度是O。
該算法的基本思想：假設G=（V，E）是一個具有n個頂點e條邊的連通圖，T=（U，TE）是G的最小生成樹，U的初值等于K即包含有G中的全部頂點，TE的初值為空集。該算法的基本思想是：將G中的邊按權值從小到大的川頁序依次選取，若選取的邊使生成樹T形成回路，則將其舍棄，如此進行下去，直到TE中包含n一1條邊為止，此時的T即為最小生成樹。
【問題4】在求每兩個頂點間的最短路徑的（Floyd）算法中有什么要求？
【答】Floyd算法在使用中的限制：圖中允許負邊，但圖中不能含有帶負權值的邊組成的回路。
【問題5】求有向無環圖的拓撲序列時，其結果為何不唯一？
【答】因為可能存在n個結點的入度都為0，選擇從哪一個開始排序將決定排序的順序。
【問題6】怎樣判斷一個有向圖是否有回路？
【答】拓樸排序可以判斷圖中是否有回路，當拓撲排序進行到圖中沒有入度（或出度）為0的結點，但還有結點沒有被排序的情況，則說明有回路。
每次將一個沒有入度的結點從圖中刪除，并刪除從此結點出發的邊。如果最后沒有結點剩余，則說明該有向圖不存在回路。
對于一個n個結點的無向連通圖，該圖無環當且僅當它只有n—1條邊。由圖的邊數和度數的關系可知，如果一個無向圖所有頂點的度≥2，則它邊數至少為n。所以該無向連通圖必存在回路。
【問題7】如何用圖的框架及其遍歷方法解決背包問題？
【答】背包問題是指：設有n個物品，其重量分別為W1，W2，…，Wn，所有物品的重量之和大于等于背包所能放置的重量S，要求從中找出若干物品放入背包中，使得其重量之和正好為S的所情況。
假設有5個物品的有向圖如圖7—22所示。
對圖7—22所示的有向圖，采用圖的深度優先遍歷算法分別從頂點W1、W2、W3、W4、W5開始進行深度優先遍歷，且判斷訪問的頂點序列的權值之和是否為S，若是，則輸出，否則繼續。若設S=50，n=5，（W1，W2，W3，W4，W5）=（29，19，18，3，2），則滿足要求的所有輸出序列為：
（1） 29， 19， 2
（2） 29， 18， 3
通常圖的深度優先遍歷是基于鄰接表存儲結構，而n個物品的重量是存放在數組W[1..n]中的，若按照圖7—4格式建立鄰接表，將增加算法的存儲空間。為此，將教組W[1..n]看成為虛擬的鄰接表，其中W[i]的鄰接點為W[i+1]，W[i+2]，…，W[n]，則得到“背包”問題的遞歸和非遞歸算法。我們只介紹解決“背包”問題的遞歸算法。