數(shù)據(jù)結(jié)構

目錄 1緒論(1) 1.1概述(1) 1.1.1什么是數(shù)據(jù)結(jié)構(1) 1.1.2學習數(shù)據(jù)結(jié)構的意義(3) 1.2基本概念和術語(4) 1.2.1數(shù)據(jù)與數(shù)據(jù)元素(4) 1.2.2數(shù)據(jù)的邏輯結(jié)構(4) 1.2.3數(shù)據(jù)的存儲結(jié)構(5) 1.2.4數(shù)據(jù)運算(6) 1.2.5數(shù)據(jù)類型(6) 1.2.6抽象數(shù)據(jù)類型(7) 1.3算法和算法描述語言(8) 1.3.1算法的書寫格式(9) 1.3.2算法中的語句(9) 1.3.3常量、變量說明方式和數(shù)據(jù)類型標識符(12) 1.3.4運算符號約定(13) 1.4算法分析(13) 思考題與習題(17) 2線性表(19) 2.1線性表的定義和運算(19) 2.1.1線性表的定義(19) 2.1.2線性表的運算(20) 2.2線性表的順序存儲(21) 2.2.1順序表(21) 2.2.2基本運算在順序表上的實現(xiàn)(22) 2.2.3順序表的應用實例(26) 2.3線性表的鏈式存儲(27) 2.3.1單鏈表(27) 2.3.2循環(huán)鏈表(38) 2.3.3雙鏈表(40) 2.4線性表存儲結(jié)構的討論(42) 2.4.1線性表順序存儲與鏈接存儲的比較(42) 2.4.2線性表存儲空間的靜態(tài)分配與動態(tài)分配(43) 2.5線性表的應用舉例(45) 思考題與習題(48) 3棧和隊列(50) 3.1棧(50) 3.1.1棧的定義和運算(50) 3.1.2棧的順序存儲(51) 3.1.3棧的鏈表存儲(55) 3.1.4棧的應用(57) 3.2隊列(63) 3.2.1隊列的定義和運算(63) 3.2.2隊列的鏈表存儲(64) 3.2.3順序隊列(67) 3.2.4隊列應用舉例(71) 3.3棧的應用——棧和遞歸(72) 3.3.1遞歸程序的實現(xiàn)(73) 3.3.2遞歸程序設計(80) 思考題與習題(84) 4串(86) 4.1串的定義和運算(86) 4.1.1串的定義(86) 4.1.2串的運算(87) 4.2串的存儲(89) 4.2.1串值的存儲(89) 4.2.2符號表(92) 4.3模式匹配(95) 4.3.1強行搜索算法(95) 4.3.2kmp算法(97) 思考題與習題(102) 5數(shù)組和廣義表(103) 5.1數(shù)組(103) 5.1.1數(shù)組的定義和運算(103) 5.1.2數(shù)組的順序存儲結(jié)構(104) 5.1.3特殊矩陣的壓縮存儲(110) 5.1.4稀疏矩陣的壓縮存儲(111) 5.2廣義表(117) 5.2.1廣義表的定義和運算(117) 5.2.2廣義表的存儲(119) *5.2.3廣義表運算的實現(xiàn)(120) 思考題與習題(121) 6樹(123) 6.1概述(123) 6.2二叉樹(125) 6.2.1二叉樹的有關概念(126) 6.2.2二叉樹的性質(zhì)(126) 6.2.3二叉樹的存儲結(jié)構(129) 6.3二叉樹的遍歷(130) 6.3.1遍歷算法的實現(xiàn)(131) 6.3.2遍歷算法的進一步討論與應用(136) 6.3.3遍歷算法思想的應用(137) 6.4線索二叉樹(139) 6.4.1線索二叉樹結(jié)構(140) 6.4.2線索二叉樹中前驅(qū)后繼的討論(141) 6.4.3線索二叉樹的插入(146) 6.4.4二叉樹的線索化(149) 6.5樹和森林(150) 6.5.1樹的存儲結(jié)構(150) 6.5.2樹(森林)與二叉樹的轉(zhuǎn)換(154) 6.5.3樹(森林)的遍歷(155) 6.6哈夫曼樹(158) 6.6.1問題描述及求解方法(159) 6.6.2應用實例(162) 思考題與習題(164) 7圖(167) 7.1圖的定義與術語(168) 7.1.1圖的定義(168) 7.1.2圖的基本術語(169) 7.1.3圖的基本操作(170) 7.2圖的存儲表示(172) 7.2.1鄰接矩陣表示法(172) 7.2.2鄰接表表示法(173) 7.2.3鄰接多重表表示法(176) 7.2.4十字鏈表表示法(177) 7.3圖的遍歷(179) 7.3.1深度優(yōu)先遍歷(180) 7.3.2廣度優(yōu)先遍歷(182) 7.4最小生成樹(184) 7.4.1最小生成樹的概念(184) 7.4.2普里姆算法(185) 7.4.3克魯斯卡爾算法(188) 7.5拓撲排序與關鍵路徑(189) 7.5.1拓撲排序(190) 7.5.2關鍵路徑(193) 7.6最短路徑(199) 7.6.1從某個源點到其余各頂點的最短路徑(199) 7.6.2所有頂點對之間的最短路徑(203) 思考題與習題(207) 8排序(210) 8.1基本概念(210) 8.1.1什么是排序(210) 8.1.2排序的分類(211) 8.1.3基本操作(211) 8.1.4存儲結(jié)構(212) 8.1.5內(nèi)部排序的方法(212) 8.1.6穩(wěn)定性(213) 8.2插入排序(213) 8.2.1直接插入排序(214) 8.2.2折半插入排序(217) 8.2.3希爾排序(218) 8.3交換排序(220) 8.3.1冒泡排序(220) 8.3.2快速排序(222) 8.4選擇排序(229) 8.4.1直接選擇排序(229) 8.4.2堆排序(230) 8.5歸并排序(235) 8.5.1方法描述(235) 8.5.2排序算法(236) 8.5.3算法分析(238) 8.6基數(shù)排序(238) 8.6.1概述(238) 8.6.2從高到低的排序(239) 8.6.3從低到高的排序(240) 8.7幾種排序方法的比較(242) 8.7.1時間復雜度(243) 8.7.2空間復雜度(243) 8.7.3穩(wěn)定性(244) 8.7.4關于“排序方法的時間復雜度的下限”(244) 8.7.5實例(245) 8.8外部排序簡介(247) 思考題與習題(249) 9查找(250) 9.1基本概念(250) 9.2順序表的查找(252) 9.2.1簡單順序表的查找(253) 9.2.2折半查找(254) 9.2.3索引順序表的查找(257) 9.3樹表的查找(258) 9.3.1二叉排序樹(259) 9.3.2平衡二叉樹(261) 9.3.3b樹和b+樹(265) 9.4散列表(271) 9.4.1散列表(272) 9.4.2散列函數(shù)的構造方法(273) 9.4.3沖突及其解決方法(276) 9.4.4散列表的查找及其分析(278) 思考題與習題(281) 10文件簡介(282) 10.1文件的基本概念(282) 10.1.1文件的分類(282) 10.1.2文件的邏輯結(jié)構(283) 10.1.3文件的物理結(jié)構(283) 10.1.4文件的操作(283) 10.2順序文件(284) 10.3索引文件(285) 10.4isam文件和vsam文件(286) 10.4.1isam文件(286) 10.4.2vsam文件(286) 10.5散列文件(287) 10.6多關鍵字文件(288) 10.6.1多重表文件(288) 10.6.2倒排文件(290) 思考題與習題(291) 參考文獻(293)