目錄 第 1 章 大數(shù)據(jù)概論...........................................1 1.1 數(shù)據(jù) .........................................................2 1.2 數(shù)據(jù)結(jié)構(gòu) .................................................3 1.2.1 數(shù)據(jù)邏輯結(jié)構(gòu)..............................4 1.2.2 數(shù)據(jù)物理結(jié)構(gòu)..............................6 1.3 大數(shù)據(jù)計(jì)算 .............................................7 本章小結(jié).............................................................9 本章習(xí)題.............................................................9 第 2 章 Python 語言基礎(chǔ)......................10 2.1 Python 安裝 ........................................11 2.2 Python 數(shù)據(jù)類型 ................................12 2.2.1 int 類型 ......................................13 2.2.2 float 類型 ...................................14 2.2.3 字符串 .......................................14 2.2.4 序列數(shù)據(jù)....................................15 2.3 Python 程序控制 ................................16 2.3.1 條件判斷................................... 16 2.3.2 循環(huán)控制................................... 17 2.3.3 異常處理................................... 18 2.4 Python 函數(shù)........................................ 19 本章小結(jié).......................................................... 20 本章習(xí)題.......................................................... 20 課程實(shí)驗(yàn).......................................................... 20 第 3 章 線性表...................................................... 22 3.1 線性表................................................... 23 3.2 順序表................................................... 23 3.2.1 順序表動態(tài)存儲....................... 24 3.2.2 順序表靜態(tài)存儲....................... 24 3.2.3 順序表的實(shí)現(xiàn)........................... 24 3.3 鏈表....................................................... 27 3.3.1 單鏈表....................................... 27 3.3.2 雙鏈表....................................... 30 3.3.3 單向循環(huán)鏈表........................... 31 3.3.4 雙向循環(huán)鏈表........................... 32 3.4 鏈表應(yīng)用............................................... 33 本章小結(jié) ..........................................................34 本章習(xí)題 ..........................................................34 課程實(shí)驗(yàn) ..........................................................34 第 4 章 棧與隊(duì)列...............................................35 4.1 棧 ...........................................................36 4.1.1 順序棧 .......................................36 4.1.2 鏈?zhǔn)綏?.......................................37 4.1.3 棧的應(yīng)用 ...................................38 4.2 隊(duì)列 .......................................................39 4.2.1 順序隊(duì)列 ...................................39 4.2.2 鏈?zhǔn)疥?duì)列 ...................................41 4.2.3 循環(huán)隊(duì)列 ...................................42 本章小結(jié) ..........................................................43 本章習(xí)題 ..........................................................43 課程實(shí)驗(yàn) ..........................................................44 第 5 章 數(shù)組與字符串..................................45 5.1 數(shù)組 .......................................................46 5.1.1 數(shù)組的定義 ...............................46 5.1.2 數(shù)組的表示和實(shí)現(xiàn)....................47 5.2 矩陣的壓縮存儲 ...................................48 5.2.1 特殊矩陣 ...................................48 5.2.2 稀疏矩陣 ...................................50 5.2.3 稀疏矩陣的轉(zhuǎn)置........................50 5.3 字符串 ...................................................51 5.3.1 字符串存儲結(jié)構(gòu)....................... 51 5.3.2 字符串的順序存儲................... 51 5.3.3 字符串的鏈?zhǔn)酱鎯?.................. 52 5.3.4 字符串匹配算法....................... 52 本章小結(jié).......................................................... 55 本章習(xí)題.......................................................... 55 課程實(shí)驗(yàn).......................................................... 55 第 6 章 樹與二叉樹........................................ 57 6.1 樹基本概念........................................... 58 6.2 二叉樹................................................... 59 6.2.1 二叉樹定義............................... 59 6.2.2 二叉樹分類............................... 59 6.2.3 二叉樹性質(zhì)............................... 61 6.3 二叉樹存儲結(jié)構(gòu)................................... 62 6.3.1 二叉樹的順序存儲................... 62 6.3.2 二叉樹的鏈?zhǔn)酱鎯?.................. 63 6.4 二叉樹操作........................................... 63 6.4.1 二叉樹的遍歷........................... 63 6.4.2 二叉樹遍歷的遞歸實(shí)現(xiàn)........... 63 6.4.3 二叉樹遍歷的非遞歸實(shí)現(xiàn) ....... 64 6.4.4 二叉樹的創(chuàng)建........................... 65 6.5 樹的存儲結(jié)構(gòu)....................................... 65 6.5.1 雙親表示法............................... 65 6.5.2 孩子表示法............................... 67 6.5.3 雙親孩子表示法....................... 68 6.5.3 孩子兄弟表示法....................... 68 6.6 樹與森林............................................... 69 6.6.1 二叉樹與樹的轉(zhuǎn)換....................69 6.6.2 二叉樹與森林的轉(zhuǎn)換................70 6.7 二叉查找樹 ...........................................71 6.7.1 二叉查找樹的創(chuàng)建....................71 6.7.2 二叉查找樹的插入....................71 6.7.3 二叉查找樹的刪除....................71 6.8 平衡二叉樹 ...........................................72 6.8.1 平衡二叉樹的概念....................72 6.8.2 平衡二叉樹的插入....................72 6.8.3 平衡二叉樹的刪除....................73 6.9 赫夫曼樹 ...............................................74 6.9.1 赫夫曼樹性質(zhì)............................74 6.9.2 赫夫曼樹構(gòu)造............................75 6.9.3 赫夫曼編碼................................75 本章小結(jié)...........................................................76 本章習(xí)題...........................................................76 課程實(shí)驗(yàn)...........................................................77 第 7章圖........................................................78 7.1 圖基本概念 ...........................................79 7.2 圖數(shù)據(jù)結(jié)構(gòu) ...........................................80 7.2.1 圖鄰接矩陣................................80 7.2.2 圖鄰接表....................................81 7.2.3 圖十字鏈表................................82 7.2.4 圖多重鄰接表............................83 7.3 圖遍歷算法 ...........................................85 7.3.1 深度優(yōu)先遍歷............................85 7.3.2 廣度優(yōu)先遍歷............................88 7.4 最小生成樹........................................... 89 7.4.1 最小生成樹性質(zhì)....................... 89 7.4.2 Prim 算法 .................................. 92 7.4.3 Kruskal 算法 ............................. 92 7.5 最短路徑............................................... 94 7.5.1 單源點(diǎn)最短路徑的 Dijkstra 算法........................... 94 7.5.2 任意頂點(diǎn)間最短路徑的 Floyd 算法......................... 95 7.6 有向圖................................................... 95 本章小結(jié).......................................................... 96 本章習(xí)題.......................................................... 96 課程實(shí)驗(yàn).......................................................... 98 第 8 章 鍵值對...................................................... 99 8.1 鍵值對概念......................................... 100 8.2 鍵值對存儲結(jié)構(gòu)................................. 100 8.2.1 概念......................................... 100 8.2.2 一般想法................................. 100 8.2.3 散列函數(shù)................................. 101 8.2.4 散列沖突................................. 103 8.2.5 散列沖突的解決方法 ............. 103 8.3 鍵值對操作......................................... 105 8.3.1 鍵值對的插入操作 ................. 105 8.3.2 鍵值對的查找操作 ................. 106 8.3.3 鍵值對的刪除操作 ................. 106 8.3.4 散列查找算法......................... 106 8.4 典型的基于鍵值對的數(shù)據(jù)庫 ............. 107 8.4.1 Redis........................................107 8.4.2 Memcached..............................108 8.4.3 適用場景 .................................108 本章小結(jié) ........................................................109 本章習(xí)題 ........................................................110 課程實(shí)驗(yàn) ........................................................110 第 9 章 嵌套數(shù)據(jù)結(jié)構(gòu)................................ 111 9.1 嵌套數(shù)據(jù)結(jié)構(gòu)概念 .............................112 9.2 數(shù)據(jù)模型 .............................................112 9.3 物理存儲結(jié)構(gòu) .....................................113 9.4 數(shù)據(jù)重構(gòu)方法 .....................................117 9.5 查詢引擎 .............................................118 9.5.1 多層服務(wù)樹架構(gòu)......................119 9.5.2 類 SQL.....................................120 9.6 適用場景 .............................................121 本章小結(jié) ........................................................122 本章習(xí)題 ........................................................123 課程實(shí)驗(yàn) ........................................................123 第 10 章 列存儲結(jié)構(gòu).......................................125 10.1 列存儲結(jié)構(gòu)概念...............................126 10.2 列存儲數(shù)據(jù)模型...............................126 10.2.1 重要概念 ...............................126 10.2.2 邏輯模型 ...............................127 10.2.3 物理模型 ...............................129 10.2.4 存儲機(jī)制............................... 129 10.3 列存儲的數(shù)據(jù)操作 .......................... 131 10.3.1 讀操作................................... 131 10.3.2 寫操作................................... 131 10.3.3 掃描操作............................... 132 10.3.4 刪除操作............................... 132 10.4 列存儲的索引 .................................. 133 10.4.1 二級索引............................... 133 10.4.2 索引方案............................... 134 10.5 列存儲的適用場景 .......................... 136 本章小結(jié)........................................................ 138 本章習(xí)題........................................................ 138 課程實(shí)驗(yàn)........................................................ 139 第 11 章 排序算法............................................. 141 11.1 內(nèi)部排序 .......................................... 142 11.1.1 插入排序............................... 142 11.1.2 希爾排序............................... 143 11.1.3 冒泡排序............................... 144 11.1.4 快速排序............................... 145 11.2 內(nèi)部排序算法比較 .......................... 146 11.3 外部排序 .......................................... 147 11.3.1 二路歸并排序 ....................... 147 11.3.2 多路歸并排序 ....................... 148 本章小結(jié)........................................................ 150 本章習(xí)題........................................................ 150 課程實(shí)驗(yàn)........................................................ 150 第 12 章 查找算法.............................................152 12.1 查找概述...........................................153 12.2 順序表查找.......................................153 12.3 折半查找...........................................153 12.4 索引順序查找...................................155 12.5 散列表...............................................156 12.5.1 散列表簡介............................156 12.5.2 散列函數(shù)的構(gòu)造....................157 12.5.3 解決沖突的方法....................158 12.5.4 散列表查找............................161 本章小結(jié).........................................................163 本章習(xí)題.........................................................164 課程實(shí)驗(yàn).........................................................164 第 13 章 基礎(chǔ)算法設(shè)計(jì)................................165 13.1 分治法...............................................166 13.1.1 基本思想................................166 13.1.2 整數(shù)乘法................................167 13.1.3 求兩個矩陣的乘積................169 13.2 動態(tài)規(guī)劃法.......................................172 13.2.1 基本思想................................172 13.2.2 矩陣連乘問題........................173 13.3 貪心算法...........................................175 13.3.1 基本思想................................176 13.3.2 背包問題................................176 13.4 回溯法 .............................................. 177 13.4.1 基本思想............................... 177 13.4.2 單詞匹配問題....................... 178 本章小結(jié)........................................................ 179 本章習(xí)題........................................................ 179 課程實(shí)驗(yàn)........................................................ 180 第 14 章 機(jī)器學(xué)習(xí)算法基礎(chǔ).................. 181 14.1 監(jiān)督學(xué)習(xí)算法................................... 182 14.1.1 樸素貝葉斯算法 ................... 183 14.1.2 決策樹算法........................... 185 14.2 無監(jiān)督學(xué)習(xí)算法............................... 186 14.2.1 聚類分析............................... 186 14.2.2 層次聚類............................... 186 14.2.3 k-means.................................. 187 14.3 PageRank 算法.............................. 187 14.3.1 背景概述............................... 187 14.3.2 算法概述............................... 188 本章小結(jié)........................................................ 189 本章習(xí)題........................................................ 189 課程實(shí)驗(yàn)........................................................ 189 第 15 章 大數(shù)據(jù)框架下的算法設(shè)計(jì)................................. 190 15.1 樸素貝葉斯算法實(shí)現(xiàn)....................... 191 15.1.1 MapReduce 框架下的樸素貝葉斯算法....................194 15.1.2 Spark 框架下的樸素貝葉斯算法 .........................196 15.1.3 性能分析與比較....................197 15.2 k-means 算法實(shí)現(xiàn) ........................198 15.2.1 MapReduce 框架下的 k-means 算法 ......................201 15.2.2 Spark 框架下的 k-means 算法..........................202 15.2.3 性能分析與比較....................204 15.3 PageRank 算法實(shí)現(xiàn)......................204 15.3.1 MapReduce 框架下的PageRank 算法............. 208 15.3.2 Spark 框架下的 PageRank 算法............................ 210 15.3.3 性能分析與比較................... 212 本章小結(jié)........................................................ 212 本章習(xí)題........................................................ 212 課程實(shí)驗(yàn)........................................................ 213 參考文獻(xiàn)............................................. 214