數(shù)據(jù)結構與應用算法教程

數(shù)據(jù)結構與應用算法教程目錄目錄 第1章緒論及C語言介紹(1) 1.1引言(1) 1.2數(shù)據(jù)結構的基本概念(2) 1.2.1數(shù)據(jù)結構的基本術語(2) 1.2.2數(shù)據(jù)的邏輯結構(4) 1.2.3數(shù)據(jù)的存儲結構(5) 1.2.4數(shù)據(jù)類型與抽象數(shù)據(jù)類型(6) 1.3算法描述與分析(8) 1.3.1算法與算法描述(8) 1.3.2算法分析(11) 1.3.3算法的時間復雜度與空間復雜度(12) 1.4C語言相關知識回顧(14) 1.4.1函數(shù)的基本概念(14) 1.4.2結構體概述(18) 1.4.3數(shù)據(jù)結構的綜合應用(22) 1.5小結(24) 習題1(25) 第2章線性表的結構分析與應用(27) 2.1線性表的定義和運算(27) 2.2線性表的順序存儲結構(29) 2.2.1順序表的定義(29) 2.2.2順序表的實現(xiàn)與操作(30) 2.3線性表的鏈式存儲結構(36) 2.3.1單鏈表的定義(37) 2.3.2單鏈表的實現(xiàn)與操作(37) 2.3.3雙鏈表的定義與實現(xiàn)(47) 2.3.4雙鏈表的操作(47) 2.3.5循環(huán)鏈表的定義與實現(xiàn)(56) 2.3.6循環(huán)鏈表的操作(57) 2.4鏈式結構的應用算法(60) 2.5線性表的順序存儲結構和鏈式存儲結構的對比(64) 2.6小結(65) 2.7習題2(65) 第3章棧和隊列的結構分析與應用(69) 3.1棧的定義(69) 3.1.1棧的順序存儲和實現(xiàn)(70) 3.1.2順序棧的操作(71) 3.1.3棧的鏈式存儲和實現(xiàn)(73) 3.1.4鏈式棧的操作(74) 3.1.5順序棧與鏈式棧的比較(75) 3.2棧的應用算法(76) 3.2.1棧與遞歸(76) 3.2.2棧與數(shù)制轉(zhuǎn)換(76) 3.2.3棧與背包問題(77) 3.3隊列的定義(79) 3.3.1隊列的順序存儲和實現(xiàn)(80) 3.3.2循環(huán)隊列的表達和實現(xiàn)(81) 3.3.3循環(huán)隊列的操作(82) 3.3.4鏈式隊列的表達和實現(xiàn)(84) 3.3.5鏈式隊列的操作(85) 3.4隊列的應用算法(87) 3.5小結(90) 習題3(90) 第4章字符串的結構分析與應用(93) 4.1字符串及其類型定義(93) 4.1.1串及其相關術語(93) 4.1.2串的抽象數(shù)據(jù)類型(94) 4.2串的定長順序存儲(94) 4.2.1串的定長順序存儲結構(94) 4.2.2定長順序串的基本操作(95) 4.3串的堆存儲結構(99) 4.3.1堆存儲結構(99) 4.3.2堆結構上的基本操作(99) 4.4串的鏈式存儲結構(100) 4.4.1鏈式存儲結構(100) 4.4.2鏈式結構上的基本操作(101) 4.5字符串的應用算法(103) 4.5.1KMP算法原理(103) 4.5.2KMP算法實現(xiàn)(107) 4.5小結(109) 習題4(109) 第5章二維數(shù)組及廣義表的結構分析(112) 5.1二維數(shù)組的行存儲和列存儲(112) 5.2矩陣的壓縮存儲(113) 5.2.1特殊矩陣的壓縮存儲(114) 5.2.2稀疏矩陣的壓縮存儲(116) 5.3廣義表的概念(122) 5.3.1廣義表常用表示(122) 5.3.2廣義表的深度(122) 5.3.3廣義表的基本運算(123) 5.3.4廣義表的存儲結構(123) 5.4矩陣的應用算法(124) 5.5小結(125) 習題5(125) 第6章樹和二叉樹(128) 6.1樹的定義和術語(128) 6.1.1樹的定義(128) 6.1.2樹的邏輯表示方法(129) 6.1.3樹的基本術語(129) 6.2二叉樹(131) 6.2.1二叉樹的定義和性質(zhì)(131) 6.2.2二叉樹的存儲結構(133) 6.3二叉樹的遍歷(136) 6.3.1二叉樹的遞歸遍歷算法(137) 6.3.2二叉樹的非遞歸遍歷算法(143) 6.3.3二叉樹的層次遍歷算法(150) 6.4二叉樹遍歷算法的應用(152) 6.4.1查找數(shù)據(jù)元素(152) 6.4.2統(tǒng)計葉子節(jié)點的數(shù)目(154) 6.4.3求二叉樹深度(156) 6.5線索化二叉樹(157) 6.5.1線索二叉樹的定義及結構(157) 6.5.2線索二叉樹的基本操作及算法實現(xiàn)(159) 6.6樹的存儲結構(162) 6.6.1樹的雙親表示法(163) 6.6.2樹的孩子表示法(165) 6.6.3樹的孩子兄弟表示法(169) 6.7樹、森林與二叉樹的轉(zhuǎn)換(170) 6.7.1樹轉(zhuǎn)化為二叉樹(171) 6.7.2森林轉(zhuǎn)化為二叉樹(171) 6.8樹和森林的遍歷(172) 6.9哈夫曼樹及其應用(173) 6.9.1哈夫曼樹的相關定義(173) 6.9.2哈夫曼樹的構造(173) 6.9.3哈夫曼樹的實現(xiàn)(174) 6.9.4哈夫曼編碼(177) 6.9.5哈夫曼樹及編碼的完整算法(179) 6.10樹結構的應用算法(183) 6.10.1回溯法(183) 6.10.2《移動迷宮》游戲算法(187) 6.11小結(192) 習題6(192) 第7章圖的結構分析與應用(197) 7.1圖的概念和術語(197) 7.2圖的存儲結構(200) 7.2.1鄰接矩陣表示法(200) 7.2.2鄰接表表示法(202) 7.3圖的遍歷(205) 7.3.1深度優(yōu)先搜索遍歷(205) 7.3.2廣度優(yōu)先搜索遍歷(207) 7.3.3圖遍歷的應用算法(208) 7.4無向圖的應用(210) 7.4.1生成樹和生成森林(211) 7.4.2最小生成樹(211) 7.5有向圖的應用(216) 7.5.1拓撲排序(216) 7.5.2最短路徑求解算法(219) 7.6小結(224) 習題7(224) 第8章查找的分析與應用(228) 8.1查找的基本概念(228) 8.2線性表的查找(230) 8.2.1順序查找法(230) 8.2.2折半查找法(231) 8.2.3分塊索引查找法(234) 8.2.4線性表查找的性能對比及分析(235) 8.3靜態(tài)查找法的應用算法(236) 8.3.1使用折半查找法實現(xiàn)學生信息查詢模塊的設計(236) 8.3.2靜態(tài)樹表優(yōu)化查找算法(237) 8.4樹表的查找(240) 8.4.1二叉排序樹(240) 8.4.2二叉排序樹的查找(241) 8.4.3二叉排序樹的插入及構建(241) 8.4.4二叉排序樹的刪除(242) 8.4.5二叉排序樹的查找性能分析(245)