數據結構與算法：C語言和Java語言描述（簡體書）

本書系統全面地講解了數據結構與算法的主要內容，包括線性表、棧和隊列、字符串、數組與矩陣、樹、圖、查找以及排序。對于每一種類型的數據結構，都詳細闡述了基本概念、各種不同的存儲結構和不同存儲結構上一些主要操作的算法，并給出完整的C語言代碼和Java代碼，有助于不同語言學習者的理解。C語言的指針概念雖較好地闡述了鏈表的結構，但目前軟件設計的主流方法是面向對象思想，所以本書在附錄中提供了各個算法對應的Java代碼。本書可作為應用型本科、高職高專、成人高校計算機相關專業課程的教材，也可作為各類培訓、計算機從業人員和愛好者的參考用書。本書封面貼有清華大學出版社防偽標簽，無標簽者不得銷售。

“數據結構與算法”是軟件開發技術的一門重要的專業基礎課程。課程主要討論現實世界中數據之間的各種邏輯結構、在計算機中的存儲結構以及各種算法的設計問題。本書討論的內容包括：線性表、堆棧、隊列、串、數組、樹、圖、查找、排序。其中，線性表、堆棧、隊列、串、數組屬于線性結構，樹和圖是非線性結構，查找和排序是兩個應用廣泛的算法設計問題。

章緒論11.1學習數據結構的意義11.1.1引言11.1.2數據結構研究什么21.2數據結構的基本概念31.3算法及其描述41.3.1算法的概念和特性41.3.2算法設計的要求51.3.3算法的分析51.4小結71.5習題7第2章線性表92.1線性表的定義及運算92.1.1線性表的定義92.1.2線性表的基本運算102.2順序線性表112.2.1順序存儲的定義112.2.2順序線性表的基本運算122.3線性表的鏈式存儲結構142.3.1線性表鏈式存儲結構的定義142.3.2單鏈表的定義152.3.3線性表鏈式存儲結構代碼描述152.3.4單鏈表的基本運算162.3.5單鏈表的創建202.4循環鏈表和雙向鏈表222.4.1循環鏈表222.4.2雙向鏈表232.5實訓24實訓1生成5個數放入順序表中,實現插入和刪除操作24實訓2創建5個節點的單鏈表,生成5個數并放入單鏈表中,實現插入和刪除操作272.6小結332.7習題33第3章棧和隊列343.1棧的定義和基本運算343.1.1棧的定義343.1.2棧的基本運算353.2順序棧353.2.1順序棧存儲的定義353.2.2順序棧的基本運算363.3鏈棧393.3.1鏈棧的定義393.3.2鏈棧的基本運算393.4隊列的定義和基本運算423.4.1隊列的定義423.4.2隊列的基本運算423.5順序隊列423.5.1順序隊列的存儲結構423.5.2順序隊列的基本運算453.6鏈式隊列493.6.1鏈式隊列的存儲結構493.6.2鏈式隊列的基本運算503.7實訓52實訓1順序共享棧的簡單實現52實訓2鏈式隊列分隊的簡單實現543.8小結573.9習題57第4章字符串594.1字符串的定義和基本運算594.1.1字符串的定義594.1.2字符串的基本運算604.2串的線性存儲結構和基本運算的實現604.2.1串的賦值運算614.2.2求串的長度614.2.3判斷兩個串是否相等614.2.4求子串614.2.5串值的連接624.2.6插入子串624.2.7刪除子串634.3串的模式匹配算法634.3.1BruteForce算法的設計思路634.3.2BruteForce算法的實現過程664.3.3BruteForce算法的時間復雜度664.4實訓練習和掌握BruteForce算法664.5小結694.6習題69第5章數組與矩陣715.1數組的基本概念715.1.1數組的定義715.1.2一維數組725.1.3二維數組725.1.4多維數組735.1.5數組的順序存儲結構735.2特殊矩陣的壓縮存儲745.2.1對稱矩陣745.2.2三角矩陣755.2.3對角矩陣765.3稀疏矩陣765.3.1三元組順序存儲表775.3.2稀疏矩陣的賦值運算775.3.3稀疏矩陣的轉置運算785.3.4稀疏矩陣的加法運算795.4實訓二維數組的相加815.5小結845.6習題85第6章樹876.1樹的相關知識876.1.1樹的基本概念876.1.2樹的表示方法886.1.3樹的常用術語896.2樹的基本操作906.3樹的存儲結構906.3.1雙親表示法906.3.2孩子表示法916.3.3孩子兄弟表示法936.4二叉樹的定義和基本操作946.4.1二叉樹的定義946.4.2二叉樹的基本操作946.4.3二叉樹的性質956.4.4二叉樹的順序存儲結構966.4.5二叉樹的鏈表存儲結構986.5二叉樹的遍歷986.5.1二叉樹的先根遍歷方法996.5.2二叉樹的中根遍歷方法1016.5.3二叉樹的后根遍歷方法1026.5.4遍歷序列與二叉樹的結構1036.6創建二叉樹1056.6.1用順序存儲方式創建二叉樹1056.6.2用鏈表方式創建二叉樹1066.7樹、森林與二叉樹的轉換1086.7.1一般樹轉換為二叉樹1086.7.2二叉樹還原為一般樹1096.7.3森林轉換為二叉樹1106.7.4二叉樹還原為森林1106.7.5樹與森林的遍歷1116.8二叉樹的應用——哈夫曼樹1116.8.1哈夫曼樹的定義1126.8.2哈夫曼樹的構造1136.8.3哈夫曼算法的實現1146.8.4哈夫曼樹的應用1166.9實訓創建二叉樹并遍歷1176.10小結1216.11習題121第7章圖1237.1圖的基本概念1237.1.1圖的定義1237.1.2圖的基本術語1247.2圖的存儲結構1267.2.1鄰接矩陣的概念1267.2.2建立圖的鄰接矩陣1277.2.3鄰接表1287.3圖的遍歷1317.3.1連通圖的深度優先搜索1327.3.2連通圖的廣度優先搜索1337.3.3非連通圖的遍歷1357.4小生成樹1357.4.1生成樹及小生成樹1357.4.2普里姆算法1367.4.3克魯斯卡爾算法1397.5短路徑1407.5.1迪杰斯特拉算法1417.5.2弗洛伊德(Floyd)算法1477.6拓撲排序1527.7實訓鄰接矩陣與遍歷算法1537.8小結1627.9習題162第8章查找1648.1查找的相關定義1648.2順序查找算法1648.2.1順序查找描述1658.2.2數據結構定義1658.2.3典型算法與分析1658.3折半查找算法1668.3.1折半查找描述1668.3.2折半查找分析1668.3.3數據結構定義1678.3.4典型算法與分析1678.4分塊查找1688.4.1分塊查找描述1688.4.2分塊查找分析1698.4.3數據結構定義1698.4.4典型算法與分析1698.5二叉排序樹查找1698.5.1二叉排序樹描述1698.5.2二叉排序樹分析1708.5.3數據結構定義1738.5.4典型算法與分析1738.6哈希表查找1738.6.1哈希表查找描述1738.6.2哈希表查找分析1748.6.3數據結構定義1778.6.4典型算法與分析1778.7實訓應用各種查找算法1788.8小結1818.9習題181第9章排序1849.1插入排序1849.1.1直接插入排序1849.1.2希爾排序1879.2交換排序1889.2.1冒泡排序1889.2.2快速排序1899.3選擇排序1919.3.1直接選擇排序1919.3.2堆排序1929.3.3歸并排序1989.4基數排序2009.4.1多關鍵字排序2009.4.2基數排序方法2009.5實訓實現不同的排序算法2029.6小結2109.7習題211附錄對應章節的Java代碼215習題答案258參考文獻271