數(shù)據(jù)結(jié)構(gòu)與應(yīng)用算法教程

數(shù)據(jù)結(jié)構(gòu)與應(yīng)用算法教程目錄目錄 第1章緒論及C語言介紹(1) 1.1引言(1) 1.2數(shù)據(jù)結(jié)構(gòu)的基本概念(2) 1.2.1數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語(2) 1.2.2數(shù)據(jù)的邏輯結(jié)構(gòu)(4) 1.2.3數(shù)據(jù)的存儲結(jié)構(gòu)(5) 1.2.4數(shù)據(jù)類型與抽象數(shù)據(jù)類型(6) 1.3算法描述與分析(8) 1.3.1算法與算法描述(8) 1.3.2算法分析(11) 1.3.3算法的時間復(fù)雜度與空間復(fù)雜度(12) 1.4C語言相關(guān)知識回顧(14) 1.4.1函數(shù)的基本概念(14) 1.4.2結(jié)構(gòu)體概述(18) 1.4.3數(shù)據(jù)結(jié)構(gòu)的綜合應(yīng)用(22) 1.5小結(jié)(24) 習(xí)題1(25) 第2章線性表的結(jié)構(gòu)分析與應(yīng)用(27) 2.1線性表的定義和運(yùn)算(27) 2.2線性表的順序存儲結(jié)構(gòu)(29) 2.2.1順序表的定義(29) 2.2.2順序表的實(shí)現(xiàn)與操作(30) 2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)(36) 2.3.1單鏈表的定義(37) 2.3.2單鏈表的實(shí)現(xiàn)與操作(37) 2.3.3雙鏈表的定義與實(shí)現(xiàn)(47) 2.3.4雙鏈表的操作(47) 2.3.5循環(huán)鏈表的定義與實(shí)現(xiàn)(56) 2.3.6循環(huán)鏈表的操作(57) 2.4鏈?zhǔn)浇Y(jié)構(gòu)的應(yīng)用算法(60) 2.5線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的對比(64) 2.6小結(jié)(65) 2.7習(xí)題2(65) 第3章棧和隊(duì)列的結(jié)構(gòu)分析與應(yīng)用(69) 3.1棧的定義(69) 3.1.1棧的順序存儲和實(shí)現(xiàn)(70) 3.1.2順序棧的操作(71) 3.1.3棧的鏈?zhǔn)酱鎯蛯?shí)現(xiàn)(73) 3.1.4鏈?zhǔn)綏５牟僮?74) 3.1.5順序棧與鏈?zhǔn)綏５谋容^(75) 3.2棧的應(yīng)用算法(76) 3.2.1棧與遞歸(76) 3.2.2棧與數(shù)制轉(zhuǎn)換(76) 3.2.3棧與背包問題(77) 3.3隊(duì)列的定義(79) 3.3.1隊(duì)列的順序存儲和實(shí)現(xiàn)(80) 3.3.2循環(huán)隊(duì)列的表達(dá)和實(shí)現(xiàn)(81) 3.3.3循環(huán)隊(duì)列的操作(82) 3.3.4鏈?zhǔn)疥?duì)列的表達(dá)和實(shí)現(xiàn)(84) 3.3.5鏈?zhǔn)疥?duì)列的操作(85) 3.4隊(duì)列的應(yīng)用算法(87) 3.5小結(jié)(90) 習(xí)題3(90) 第4章字符串的結(jié)構(gòu)分析與應(yīng)用(93) 4.1字符串及其類型定義(93) 4.1.1串及其相關(guān)術(shù)語(93) 4.1.2串的抽象數(shù)據(jù)類型(94) 4.2串的定長順序存儲(94) 4.2.1串的定長順序存儲結(jié)構(gòu)(94) 4.2.2定長順序串的基本操作(95) 4.3串的堆存儲結(jié)構(gòu)(99) 4.3.1堆存儲結(jié)構(gòu)(99) 4.3.2堆結(jié)構(gòu)上的基本操作(99) 4.4串的鏈?zhǔn)酱鎯Y(jié)構(gòu)(100) 4.4.1鏈?zhǔn)酱鎯Y(jié)構(gòu)(100) 4.4.2鏈?zhǔn)浇Y(jié)構(gòu)上的基本操作(101) 4.5字符串的應(yīng)用算法(103) 4.5.1KMP算法原理(103) 4.5.2KMP算法實(shí)現(xiàn)(107) 4.5小結(jié)(109) 習(xí)題4(109) 第5章二維數(shù)組及廣義表的結(jié)構(gòu)分析(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廣義表的基本運(yùn)算(123) 5.3.4廣義表的存儲結(jié)構(gòu)(123) 5.4矩陣的應(yīng)用算法(124) 5.5小結(jié)(125) 習(xí)題5(125) 第6章樹和二叉樹(128) 6.1樹的定義和術(shù)語(128) 6.1.1樹的定義(128) 6.1.2樹的邏輯表示方法(129) 6.1.3樹的基本術(shù)語(129) 6.2二叉樹(131) 6.2.1二叉樹的定義和性質(zhì)(131) 6.2.2二叉樹的存儲結(jié)構(gòu)(133) 6.3二叉樹的遍歷(136) 6.3.1二叉樹的遞歸遍歷算法(137) 6.3.2二叉樹的非遞歸遍歷算法(143) 6.3.3二叉樹的層次遍歷算法(150) 6.4二叉樹遍歷算法的應(yīng)用(152) 6.4.1查找數(shù)據(jù)元素(152) 6.4.2統(tǒng)計(jì)葉子節(jié)點(diǎn)的數(shù)目(154) 6.4.3求二叉樹深度(156) 6.5線索化二叉樹(157) 6.5.1線索二叉樹的定義及結(jié)構(gòu)(157) 6.5.2線索二叉樹的基本操作及算法實(shí)現(xiàn)(159) 6.6樹的存儲結(jié)構(gòu)(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哈夫曼樹及其應(yīng)用(173) 6.9.1哈夫曼樹的相關(guān)定義(173) 6.9.2哈夫曼樹的構(gòu)造(173) 6.9.3哈夫曼樹的實(shí)現(xiàn)(174) 6.9.4哈夫曼編碼(177) 6.9.5哈夫曼樹及編碼的完整算法(179) 6.10樹結(jié)構(gòu)的應(yīng)用算法(183) 6.10.1回溯法(183) 6.10.2《移動迷宮》游戲算法(187) 6.11小結(jié)(192) 習(xí)題6(192) 第7章圖的結(jié)構(gòu)分析與應(yīng)用(197) 7.1圖的概念和術(shù)語(197) 7.2圖的存儲結(jié)構(gòu)(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圖遍歷的應(yīng)用算法(208) 7.4無向圖的應(yīng)用(210) 7.4.1生成樹和生成森林(211) 7.4.2最小生成樹(211) 7.5有向圖的應(yīng)用(216) 7.5.1拓?fù)渑判?216) 7.5.2最短路徑求解算法(219) 7.6小結(jié)(224) 習(xí)題7(224) 第8章查找的分析與應(yīng)用(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)查找法的應(yīng)用算法(236) 8.3.1使用折半查找法實(shí)現(xiàn)學(xué)生信息查詢模塊的設(shè)計(jì)(236) 8.3.2靜態(tài)樹表優(yōu)化查找算法(237) 8.4樹表的查找(240) 8.4.1二叉排序樹(240) 8.4.2二叉排序樹的查找(241) 8.4.3二叉排序樹的插入及構(gòu)建(241) 8.4.4二叉排序樹的刪除(242) 8.4.5二叉排序樹的查找性能分析(245)