算法精解

前言

本書(shū)封面上的動(dòng)物是海馬，屬于海龍科。海馬這個(gè)詞來(lái)源于希臘語(yǔ)中的“彎曲的馬”。海馬那不同尋常的身體由大約50塊左右包圍著身體的骨板構(gòu)成，宛如一圈盔甲的形狀。海馬依靠它狹窄的鼻口作為進(jìn)食的管道，主要吸食浮游生物和小魚(yú)的幼蟲(chóng)。公海馬的肚子上有一個(gè)袋子，母海馬每次將100枚或更多的海馬蛋放在公海馬的袋子里。公海馬使袋子內(nèi)的海馬蛋受精，并一直照料這些蛋直到小海馬孵化出來(lái)。根據(jù)海馬的種類，這個(gè)過(guò)程大約需要10天到6個(gè)星期。盡管也有一些種類的海馬居住在海洋中，但是海馬通常都出現(xiàn)在熱帶和亞熱帶的淺海水域。所有海馬都使用骨盆和胸鰭來(lái)完成轉(zhuǎn)向的動(dòng)作。它們采用直立的姿勢(shì)游動(dòng)，但速度很慢且常常停下來(lái)休息。在休息的時(shí)候，它們用自己的尾巴纏繞住海藻或珊瑚使自己停住。除了能提供一個(gè)休息的地方外，海藻和珊瑚還能為海馬提供良好的偽裝效果。世界上體型最大的海馬是太平洋海馬，大約有12英寸長(zhǎng)。最小的海馬是矮海馬，大約只有1.5英寸長(zhǎng)。

內(nèi)容概要

本書(shū)是數(shù)據(jù)結(jié)構(gòu)和算法領(lǐng)域的經(jīng)典之作，十余年來(lái)，暢銷(xiāo)不衰！全書(shū)共分為三部分：第一部分首先介紹了數(shù)據(jù)結(jié)構(gòu)和算法的概念，以及使用它們的原因和意義，然后講解了數(shù)據(jù)結(jié)構(gòu)和算法中最常用的技術(shù)——指針和遞歸，最后還介紹了算法的分析方法，旨在為讀者學(xué)習(xí)這本書(shū)打下堅(jiān)實(shí)的基礎(chǔ)；第二部分對(duì)鏈表、棧、隊(duì)列、集合、哈希表、堆、圖等常用數(shù)據(jù)結(jié)構(gòu)進(jìn)行了深入闡述；第三部分對(duì)排序、搜索數(shù)值計(jì)算、數(shù)據(jù)壓縮、數(shù)據(jù)加密、圖算法、幾何算法等經(jīng)典算法進(jìn)行了精辟的分析和講解。
本書(shū)的眾多特色使得它在同類書(shū)中獨(dú)樹(shù)一幟：具體實(shí)現(xiàn)都采用正式的C語(yǔ)言代碼而不是偽代碼，在很多數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)過(guò)程中，有大量細(xì)節(jié)問(wèn)題是偽代碼不能解決的；每一章都有精心組織的主題和應(yīng)用；全部示例來(lái)自真實(shí)的應(yīng)用，不只是一般的練習(xí)；對(duì)每種數(shù)據(jù)結(jié)構(gòu)、算法和示例都進(jìn)行了詳細(xì)分析；每一章的末尾都會(huì)有一系列問(wèn)題和對(duì)應(yīng)的回答，旨在強(qiáng)調(diào)這一章的重要思想……
本書(shū)中的代碼尤為值得強(qiáng)調(diào)：所有實(shí)現(xiàn)都采用C語(yǔ)言編寫(xiě)，所有代碼都優(yōu)先用于教學(xué)目的，所有代碼都在4種平臺(tái)上經(jīng)過(guò)完整測(cè)試，頭文件記錄了所有公共的接口，命名規(guī)則適用于全書(shū)所有的代碼，所有的代碼都包含大量注釋……
　　本書(shū)內(nèi)容包括：
　　· 數(shù)據(jù)結(jié)構(gòu)和算法的概念，以及使用它們的原因和意義
　　· 指針和遞歸
　　· 算法分析
　　· 常用數(shù)據(jù)結(jié)構(gòu)：鏈表、棧、隊(duì)列、集合、哈希表、樹(shù)、堆、優(yōu)先級(jí)隊(duì)列以及圖
　　· 排序和搜索
　　· 數(shù)值計(jì)算
　　· 數(shù)據(jù)壓縮
　　· 數(shù)據(jù)加密
　　· 圖算法
　　· 幾何算法

作者簡(jiǎn)介

Kyle Loudon，是美國(guó)加州洛斯加托斯Jeppesen
Dataplan公司的一名軟件工程師，主管圖形接口開(kāi)發(fā)小組，主攻航跡規(guī)劃軟件的研發(fā)，這些軟件主要用于商業(yè)航空公司、私營(yíng)航空部門(mén)和其他一些航空制造業(yè)。在來(lái)到Jeppesen之前，Kyle在IBM公司是一名系統(tǒng)程序員。在技術(shù)上，Kyle主要對(duì)操作系統(tǒng)、網(wǎng)絡(luò)、人機(jī)交互等領(lǐng)域感興趣。1992年，Kyle在普渡大學(xué)拿到了計(jì)算機(jī)科學(xué)學(xué)士學(xué)位，并取得了法語(yǔ)的第二學(xué)位，同時(shí)他還被選入斐陶斐榮譽(yù)學(xué)會(huì)（美國(guó)大學(xué)優(yōu)等生之榮譽(yù)學(xué)會(huì)）。他在普渡大學(xué)計(jì)算機(jī)系教了三年的計(jì)算機(jī)課程。在這期間，他完成了他個(gè)人的第一本書(shū)《Understanding
Computers》，這本書(shū)用理論結(jié)合實(shí)踐的方式介紹計(jì)算機(jī)的方方面面。如今，盡管他繼續(xù)工作在硅谷的軟件業(yè)，但他仍然堅(jiān)韌不拔地在追求一個(gè)更高的學(xué)位。
除了計(jì)算機(jī)，Kyle多年來(lái)喜歡打網(wǎng)球、教網(wǎng)球。他還喜歡山地騎行、滑冰，偶爾也和朋友們一起參加高爾夫課程。另外，Kyle還喜歡各種形式的戲劇、美食，以及某些風(fēng)格的音樂(lè)和藝術(shù)；他期望成為鋼琴家和藝術(shù)家，但希望渺茫。他現(xiàn)在在Jeppesen的工作是從他1992年開(kāi)始駕駛飛機(jī)之后找到的?，F(xiàn)在，他是一個(gè)擁有美國(guó)聯(lián)邦航空局頒發(fā)的商業(yè)飛行員執(zhí)照的飛行員。

書(shū)籍目錄

1. 前言
2. 第1部分 預(yù)備知識(shí)
3. 第1章 概述
4. 數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介
5. 算法簡(jiǎn)介
6. 小酌軟件工程
7. 如何使用本書(shū)
8. 第2章 指針操作
9. 指針基礎(chǔ)
10. 存儲(chǔ)空間分配
11. 數(shù)據(jù)集合與指針的算術(shù)運(yùn)算
12. 作為函數(shù)參數(shù)的指針
13. 泛型指針與類型轉(zhuǎn)換
14. 函數(shù)指針
15. 問(wèn)與答
16. 相關(guān)主題
17. 第3章 遞歸
18. 基本遞歸
19. 尾遞歸
20. 問(wèn)與答
21. 相關(guān)主題
22. 第4章 算法分析
23. 最壞情況分析
24. O表示法
25. 計(jì)算的復(fù)雜度
26. 實(shí)例分析：插入排序
27. 問(wèn)與答
28. 相關(guān)主題
29. 第2部分 數(shù)據(jù)結(jié)構(gòu)
30. 第5章 鏈表
31. 單鏈表介紹
32. 單鏈表接口的定義
33. 單鏈表的實(shí)現(xiàn)與分析
34. 使用鏈表的例子：頁(yè)幀管理
35. 雙向鏈表介紹
36. 雙向鏈表接口的定義
37. 雙向鏈表的實(shí)現(xiàn)與分析
38. 循環(huán)鏈表介紹
39. 循環(huán)鏈表接口的定義
40. 循環(huán)鏈表的實(shí)現(xiàn)與分析
41. 使用循環(huán)鏈表的例子：第二次機(jī)會(huì)頁(yè)面置換法
42. 問(wèn)與答
43. 相關(guān)主題
44. 第6章 棧和隊(duì)列
45. 棧的描述
46. 棧的接口定義
47. 棧的實(shí)現(xiàn)與分析
48. 隊(duì)列的描述
49. 隊(duì)列的接口定義
50. 隊(duì)列的實(shí)現(xiàn)與分析
51. 隊(duì)列示例：事件處理
52. 問(wèn)與答
53. 相關(guān)主題
54. 第7章 集合
55. 集合介紹
56. 集合的性質(zhì)
57. 集合接口的定義
58. 集合抽象數(shù)據(jù)類型的實(shí)現(xiàn)和分析
59. Set示例：集合覆蓋
60. 問(wèn)與答
61. 相關(guān)主題
62. 第8章 哈希表
63. 鏈?zhǔn)焦１淼拿枋?br />64. 鏈?zhǔn)焦１淼慕涌诙x
65. 鏈?zhǔn)焦１淼膶?shí)現(xiàn)與分析
66. 鏈?zhǔn)焦１淼睦樱悍?hào)表
67. 開(kāi)地址哈希表的描述
68. 開(kāi)地址哈希函數(shù)的接口定義
69. 開(kāi)地址哈希表的實(shí)現(xiàn)與分析
70. 問(wèn)與答
71. 相關(guān)主題
72. 第9章 樹(shù)
73. 二叉樹(shù)介紹
74. 二叉樹(shù)的接口定義
75. 二叉樹(shù)的實(shí)現(xiàn)與分析
76. 二叉樹(shù)示例：表達(dá)式處理
77. 二叉搜索樹(shù)介紹
78. 二叉搜索樹(shù)的接口定義
79. 二叉搜索樹(shù)的實(shí)現(xiàn)與分析
80. 問(wèn)與答
81. 相關(guān)主題
82. 第10章 堆和優(yōu)先隊(duì)列
83. 堆的描述
84. 堆的接口定義
85. 堆的實(shí)現(xiàn)與分析
86. 優(yōu)先隊(duì)列的描述
87. 優(yōu)先隊(duì)列的接口定義
88. 優(yōu)先隊(duì)列的實(shí)現(xiàn)與分析
89. 優(yōu)先隊(duì)列的示例：包裹分揀
90. 問(wèn)與答
91. 相關(guān)主題
92. 第11章 圖
93. 圖的描述
94. 圖的接口定義
95. 圖的實(shí)現(xiàn)與分析
96. 關(guān)于圖的應(yīng)用舉例：計(jì)算網(wǎng)絡(luò)跳數(shù)
97. 關(guān)于圖的應(yīng)用舉例：拓?fù)渑判?br />98. 問(wèn)與答
99. 相關(guān)主題
100. 第3部分 算法
101. 第12章 排序和搜索
102. 插入排序的描述
103. 插入排序的接口定義
104. 插入排序的實(shí)現(xiàn)與分析
105. 快速排序的描述
106. 快速排序的接口定義
107. 快速排序的實(shí)現(xiàn)與分析
108. 快速排序的例子：目錄列表
109. 歸并排序的描述
110. 歸并排序的接口定義
111. 歸并排序的實(shí)現(xiàn)與分析
112. 計(jì)數(shù)排序的描述
113. 計(jì)數(shù)排序的接口定義
114. 計(jì)數(shù)排序的實(shí)現(xiàn)與分析
115. 基數(shù)排序的描述
116. 基數(shù)排序的接口定義
117. 基數(shù)排序的實(shí)現(xiàn)與分析
118. 二分查找的描述
119. 二分查找的接口定義
120. 二分查找的實(shí)現(xiàn)與分析
121. 二分查找的例子：拼寫(xiě)檢查器
122. 問(wèn)與答
123. 相關(guān)主題
124. 第13章 數(shù)值計(jì)算
125. 多項(xiàng)式插值法
126. 多項(xiàng)式插值的接口定義
127. 多項(xiàng)式插值的實(shí)現(xiàn)與分析
128. 最小二乘估計(jì)法
129. 最小二乘估計(jì)的接口定義
130. 最小二乘估計(jì)的實(shí)現(xiàn)和分析
131. 方程求解介紹
132. 方程求解的接口定義
133. 方程求解的實(shí)現(xiàn)與分析
134. 問(wèn)與答
135. 相關(guān)主題
136. 第14章 數(shù)據(jù)壓縮
137. 位操作的描述
138. 位操作的接口定義
139. 位操作的實(shí)現(xiàn)與分析
140. 霍夫曼編碼的描述
141. 霍夫曼編碼的接口定義
142. 霍夫曼編碼的分析與實(shí)現(xiàn)
143. 霍夫曼編碼的例子：網(wǎng)絡(luò)優(yōu)化
144. LZ77的描述
145. LZ77的接口定義
146. LZ77的實(shí)現(xiàn)與分析
147. 問(wèn)與答
148. 相關(guān)主題
149. 第15章 數(shù)據(jù)加密
150. DES算法介紹
151. DES的接口定義
152. DES算法的實(shí)現(xiàn)和分析
153. DES應(yīng)用舉例：分組加密模式
154. RSA算法介紹
155. RSA的接口定義
156. RSA算法的實(shí)現(xiàn)與分析
157. 問(wèn)與答
158. 相關(guān)主題
159. 第16章 圖算法
160. 最小生成樹(shù)的描述
161. 最小生成樹(shù)的接口定義
162. 最小生成樹(shù)的實(shí)現(xiàn)與分析
163. 最短路徑的描述
164. 最短路徑的接口定義
165. 最短路徑的實(shí)現(xiàn)與分析
166. 最短路徑的例子：路由表
167. 旅行商問(wèn)題的描述
168. 旅行商問(wèn)題的接口定義
169. 旅行商問(wèn)題的實(shí)現(xiàn)與分析
170. 問(wèn)與答
171. 相關(guān)主題
172. 第17章 幾何算法
173. 測(cè)試線段是否相交
174. 測(cè)試線段是否相交的標(biāo)準(zhǔn)方法
175. 檢測(cè)線段是否相交的接口定義
176. 檢測(cè)線段是否相交的實(shí)現(xiàn)與分析
177. 凸包簡(jiǎn)介
178. Jarvis’s March
179. 凸包的接口定義
180. 凸包的實(shí)現(xiàn)與分析
181. 球面弧長(zhǎng)
182. 求解球面弧長(zhǎng)的接口定義
183. 求解球面弧長(zhǎng)的實(shí)現(xiàn)和分析
184. 球面弧長(zhǎng)的應(yīng)用舉例：地球上兩點(diǎn)之間的近似距離
185. 問(wèn)與答
186. 相關(guān)主題

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   問(wèn)與答 問(wèn)：鏈表比數(shù)組優(yōu)越的地方前面已經(jīng)介紹過(guò)了。但是，數(shù)組同樣也有比鏈表優(yōu)越的地方，那么什么情況下適合使用數(shù)組呢？ 答：當(dāng)我們期望進(jìn)行頻繁的插入和刪除操作時(shí)，鏈表比數(shù)組更有優(yōu)勢(shì)。然而，當(dāng)我們期望進(jìn)行隨機(jī)訪問(wèn)的次數(shù)高于插入和刪除操作的次數(shù)時(shí)，數(shù)組就顯得更有優(yōu)勢(shì)了。隨機(jī)訪問(wèn)是數(shù)組的強(qiáng)項(xiàng)，因?yàn)樗鼈兊脑卦趦?nèi)存中是連續(xù)排列的。這種連續(xù)的排列方式使得數(shù)組中的任何元素能夠在O(1)的時(shí)間內(nèi)通過(guò)其索引訪問(wèn)?；仡櫼幌略L問(wèn)鏈表中元素的方法，我們必須得有一個(gè)指向元素的指針。如果我們對(duì)訪問(wèn)元素的方式不甚了解，那么要獲取某個(gè)指向特定元素的指針的代價(jià)將非常高。在實(shí)踐中，對(duì)于許多應(yīng)用來(lái)說(shuō)，我們至少需要遍歷鏈表的一部分。如果存儲(chǔ)數(shù)據(jù)的總量是恒定的，則數(shù)組也有更大的優(yōu)勢(shì)，因?yàn)樗鼈儾恍枰黾宇~外的指針來(lái)使得它們所有的元素“鏈接”起來(lái)。 問(wèn)：關(guān)于鏈表的插入、刪除以及訪問(wèn)元素的操作和數(shù)組相比有何差異？ 答：回顧一下本章中各種形式的鏈表，除了銷(xiāo)毀鏈表操作外，其他的操作都具有O(1)的運(yùn)行時(shí)復(fù)雜度。確實(shí)，這種表現(xiàn)似乎很難控制。然而，在分析過(guò)程中有一點(diǎn)并沒(méi)有說(shuō)明，那就是對(duì)于許多鏈表的操作來(lái)說(shuō)，想得到指向鏈表中某個(gè)特定元素的指針其代價(jià)是很高的。例如，在最壞的情況下，可能需要遍歷整個(gè)鏈表，此時(shí)的開(kāi)銷(xiāo)就是O(n)，這里n代表鏈表中的元素個(gè)數(shù)。另一方面，在一個(gè)設(shè)計(jì)得當(dāng)?shù)膽?yīng)用中，比如本章的頁(yè)幀管理，則對(duì)此就不會(huì)有任何性能上的額外開(kāi)銷(xiāo)。因此，觀察應(yīng)用的特點(diǎn)是非常重要的。對(duì)于數(shù)組，插入和刪除都是O(n)級(jí)別的操作，因?yàn)樵谧顗牡那闆r下，插入或刪除索引為0的元素需要將其他所有的元素都移動(dòng)一個(gè)位置來(lái)調(diào)整整個(gè)數(shù)組的布局。如果我們知道索引值，則訪問(wèn)數(shù)組中的元素就是o(1)的操作。 問(wèn)：假設(shè)我們想在本章給出的單鏈表基礎(chǔ)上寫(xiě)一個(gè)名為list_ins_pos的函數(shù)，它的作用是在給定的位置之后插入一個(gè)新元素。假設(shè)我們希望在第9個(gè)元素之后插入新元素，但并不直接提供指向第9個(gè)元素的指針。那么這個(gè)函數(shù)的運(yùn)行時(shí)復(fù)雜度是什么？

編輯推薦

《算法精解:C語(yǔ)言描述》編輯推薦：數(shù)據(jù)結(jié)構(gòu)和算法領(lǐng)域最具特色著作之一，公認(rèn)權(quán)威經(jīng)典，暢銷(xiāo)不衰！

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    算法精解 PDF格式下載

---