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

數(shù)據(jù)結(jié)構(gòu)與應(yīng)用算法教程目錄目錄 第1章緒論及C語(yǔ)言介紹(1) 1.1引言(1) 1.2數(shù)據(jù)結(jié)構(gòu)的基本概念(2) 1.2.1數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語(yǔ)(2) 1.2.2數(shù)據(jù)的邏輯結(jié)構(gòu)(4) 1.2.3數(shù)據(jù)的存儲(chǔ)結(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算法的時(shí)間復(fù)雜度與空間復(fù)雜度(12) 1.4C語(yǔ)言相關(guān)知識(shí)回顧(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線性表的順序存儲(chǔ)結(jié)構(gòu)(29) 2.2.1順序表的定義(29) 2.2.2順序表的實(shí)現(xiàn)與操作(30) 2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(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線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的對(duì)比(64) 2.6小結(jié)(65) 2.7習(xí)題2(65) 第3章棧和隊(duì)列的結(jié)構(gòu)分析與應(yīng)用(69) 3.1棧的定義(69) 3.1.1棧的順序存儲(chǔ)和實(shí)現(xiàn)(70) 3.1.2順序棧的操作(71) 3.1.3棧的鏈?zhǔn)酱鎯?chǔ)和實(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棧與背包問(wèn)題(77) 3.3隊(duì)列的定義(79) 3.3.1隊(duì)列的順序存儲(chǔ)和實(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ù)語(yǔ)(93) 4.1.2串的抽象數(shù)據(jù)類型(94) 4.2串的定長(zhǎng)順序存儲(chǔ)(94) 4.2.1串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)(94) 4.2.2定長(zhǎng)順序串的基本操作(95) 4.3串的堆存儲(chǔ)結(jié)構(gòu)(99) 4.3.1堆存儲(chǔ)結(jié)構(gòu)(99) 4.3.2堆結(jié)構(gòu)上的基本操作(99) 4.4串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(100) 4.4.1鏈?zhǔn)酱鎯?chǔ)結(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ù)組的行存儲(chǔ)和列存儲(chǔ)(112) 5.2矩陣的壓縮存儲(chǔ)(113) 5.2.1特殊矩陣的壓縮存儲(chǔ)(114) 5.2.2稀疏矩陣的壓縮存儲(chǔ)(116) 5.3廣義表的概念(122) 5.3.1廣義表常用表示(122) 5.3.2廣義表的深度(122) 5.3.3廣義表的基本運(yùn)算(123) 5.3.4廣義表的存儲(chǔ)結(jié)構(gòu)(123) 5.4矩陣的應(yīng)用算法(124) 5.5小結(jié)(125) 習(xí)題5(125) 第6章樹(shù)和二叉樹(shù)(128) 6.1樹(shù)的定義和術(shù)語(yǔ)(128) 6.1.1樹(shù)的定義(128) 6.1.2樹(shù)的邏輯表示方法(129) 6.1.3樹(shù)的基本術(shù)語(yǔ)(129) 6.2二叉樹(shù)(131) 6.2.1二叉樹(shù)的定義和性質(zhì)(131) 6.2.2二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(133) 6.3二叉樹(shù)的遍歷(136) 6.3.1二叉樹(shù)的遞歸遍歷算法(137) 6.3.2二叉樹(shù)的非遞歸遍歷算法(143) 6.3.3二叉樹(shù)的層次遍歷算法(150) 6.4二叉樹(shù)遍歷算法的應(yīng)用(152) 6.4.1查找數(shù)據(jù)元素(152) 6.4.2統(tǒng)計(jì)葉子節(jié)點(diǎn)的數(shù)目(154) 6.4.3求二叉樹(shù)深度(156) 6.5線索化二叉樹(shù)(157) 6.5.1線索二叉樹(shù)的定義及結(jié)構(gòu)(157) 6.5.2線索二叉樹(shù)的基本操作及算法實(shí)現(xiàn)(159) 6.6樹(shù)的存儲(chǔ)結(jié)構(gòu)(162) 6.6.1樹(shù)的雙親表示法(163) 6.6.2樹(shù)的孩子表示法(165) 6.6.3樹(shù)的孩子兄弟表示法(169) 6.7樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換(170) 6.7.1樹(shù)轉(zhuǎn)化為二叉樹(shù)(171) 6.7.2森林轉(zhuǎn)化為二叉樹(shù)(171) 6.8樹(shù)和森林的遍歷(172) 6.9哈夫曼樹(shù)及其應(yīng)用(173) 6.9.1哈夫曼樹(shù)的相關(guān)定義(173) 6.9.2哈夫曼樹(shù)的構(gòu)造(173) 6.9.3哈夫曼樹(shù)的實(shí)現(xiàn)(174) 6.9.4哈夫曼編碼(177) 6.9.5哈夫曼樹(shù)及編碼的完整算法(179) 6.10樹(shù)結(jié)構(gòu)的應(yīng)用算法(183) 6.10.1回溯法(183) 6.10.2《移動(dòng)迷宮》游戲算法(187) 6.11小結(jié)(192) 習(xí)題6(192) 第7章圖的結(jié)構(gòu)分析與應(yīng)用(197) 7.1圖的概念和術(shù)語(yǔ)(197) 7.2圖的存儲(chǔ)結(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無(wú)向圖的應(yīng)用(210) 7.4.1生成樹(shù)和生成森林(211) 7.4.2最小生成樹(shù)(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線性表查找的性能對(duì)比及分析(235) 8.3靜態(tài)查找法的應(yīng)用算法(236) 8.3.1使用折半查找法實(shí)現(xiàn)學(xué)生信息查詢模塊的設(shè)計(jì)(236) 8.3.2靜態(tài)樹(shù)表優(yōu)化查找算法(237) 8.4樹(shù)表的查找(240) 8.4.1二叉排序樹(shù)(240) 8.4.2二叉排序樹(shù)的查找(241) 8.4.3二叉排序樹(shù)的插入及構(gòu)建(241) 8.4.4二叉排序樹(shù)的刪除(242) 8.4.5二叉排序樹(shù)的查找性能分析(245)