數(shù)據(jù)結(jié)構(gòu)

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