數(shù)據結構

目錄 1緒論(1) 1.1概述(1) 1.1.1什么是數(shù)據結構(1) 1.1.2學習數(shù)據結構的意義(3) 1.2基本概念和術語(4) 1.2.1數(shù)據與數(shù)據元素(4) 1.2.2數(shù)據的邏輯結構(4) 1.2.3數(shù)據的存儲結構(5) 1.2.4數(shù)據運算(6) 1.2.5數(shù)據類型(6) 1.2.6抽象數(shù)據類型(7) 1.3算法和算法描述語言(8) 1.3.1算法的書寫格式(9) 1.3.2算法中的語句(9) 1.3.3常量、變量說明方式和數(shù)據類型標識符(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線性表存儲結構的討論(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ù)組的順序存儲結構(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二叉樹的性質(126) 6.2.3二叉樹的存儲結構(129) 6.3二叉樹的遍歷(130) 6.3.1遍歷算法的實現(xiàn)(131) 6.3.2遍歷算法的進一步討論與應用(136) 6.3.3遍歷算法思想的應用(137) 6.4線索二叉樹(139) 6.4.1線索二叉樹結構(140) 6.4.2線索二叉樹中前驅后繼的討論(141) 6.4.3線索二叉樹的插入(146) 6.4.4二叉樹的線索化(149) 6.5樹和森林(150) 6.5.1樹的存儲結構(150) 6.5.2樹(森林)與二叉樹的轉換(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存儲結構(212) 8.1.5內部排序的方法(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文件的邏輯結構(283) 10.1.3文件的物理結構(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)