程序員實用算法

前言

　　數(shù)據(jù)結(jié)構(gòu)與算法是計算機專業(yè)的核心課程，是計算機軟件開發(fā)和應用人員必備的專業(yè)基礎。今天的大多數(shù)關于算法的圖書都是大學教科書，或者是令人厭倦的相同算法集合改頭換面后的作品。本書是給出所有算法的完整代碼實現(xiàn)的第一本書，這些算法對于開發(fā)人員在其日常工作中是有用的?！　”緯榻B了關于算法的基礎知識、基本數(shù)據(jù)結(jié)構(gòu)、散列、查找、排序、樹、日期和時間、任意精度的算術運算、數(shù)據(jù)壓縮以及數(shù)據(jù)完整性和驗證等內(nèi)容。本書的目的是為在應用程序中使用的算法提供一個實用的綱要。與關于算法的大多數(shù)著作不同的是，本書不是一本教材：書中沒有提供實現(xiàn)細節(jié)，把它作為練習留給讀者完成；也沒有利用較小的代碼段對算法進行高度理論化的討論，以說明如何進行實現(xiàn)。相反，本書完全用c語言實現(xiàn)了各種算法，并且討論了如何在各種應用程序中最佳地使用它們?！　”緯灰笞x者具有c語言的初級知識以及不超出基本代數(shù)之外的數(shù)學知識。源代碼是符合ANSI標準的，并且對它們進行了測試，它們都可以運行在UNIX下以及Borland、Microsoft和Watcom的編譯器上?！　”緯浅＿m合于高等院校計算機專業(yè)的學生閱讀，對于從事計算機軟件開發(fā)的人員，也將從本書中受益匪淺?！　⒓颖緯g的人員有：陳宗斌、張景友、易小麗、陳婷、管學崗、王新彥、金惠敏、張海峰、徐曄、戴鋒?！　∮捎跁r間緊迫，加之譯者水平有限，錯誤在所難免，懇請廣大讀者批評指正。

內(nèi)容概要

　　《程序員實用算法》重點關注的是實用、立即可用的代碼，并且廣泛討論了可移植性和特定于實現(xiàn)的細節(jié)?！冻绦騿T實用算法》作者介紹了一些有用但很少被討論的算法，它們可用于語音查找、日期和時間例程（直到公元1年）、B樹和索引文件、數(shù)據(jù)壓縮、任意精度的算術、校驗和與數(shù)據(jù)驗證，并且還最全面地介紹了查找例程、排序算法和數(shù)據(jù)結(jié)構(gòu)。　　《程序員實用算法》結(jié)構(gòu)清晰，示例豐富，可作為廣大程序員的參考用書。

作者簡介

　　Andrew Binstock，是《UNIX Review》的主編和《C Gazette》的創(chuàng)刊編輯。他是《HP LaserJet Programming》（Addison-Wesley，1991）的第一作者?！　ohn Rex，是一位計算機顧問，專攻C和C++。他是《C Gazette》的前任技術編輯，并且為許多雜志撰寫文章。

書籍目錄

譯者序前言致謝第1章 緒論1.1 評估算法1.2 修改算法1.2.1 主要的優(yōu)化：I/O1.2.2 主要的優(yōu)化：函數(shù)調(diào)用1.3 資源和參考資料第2章 基本數(shù)據(jù)結(jié)構(gòu)2.1 鏈表2.1.1 雙向鏈表2.1.2 鏈表的其他特征2.2 棧和隊列2.2.1 棧的特征2.2.2 隊列的特征第3章 散列3.1 散列的概念3.2 散列函數(shù)3.3 沖突解決方法3.3.1 線性再散列法3.3.2 非線性再散列法3.3.3 外部拉鏈法3.4 性能問題3.5 資源和參考資料第4章 查找4.1 查找的特征4.1.1 準備時間4.1.2 運行時間4.1.3 回溯的需要4.2 蠻力查找4.3 Boyer?Moore查找4.3.1 啟發(fā)式方法#1：跳過字符4.3.2 啟發(fā)式方法#2：重復模式4.4 多字符串查找4.5 用于正則表達式的字符串查找：grep4.6 近似字符串匹配技術4.7 語音比較：Soundex算法4.8 Metaphone：現(xiàn)代的Soundex4.9 選擇技術4.10 資源和參考資料4.10.1 通用參考資料4.10.2 Boyer?Moore4.10.3 多字符串查找4.10.4 正則表達式查找4.10.5 近似字符串匹配4.10.6 Soundex算法和Metaphone算法第5章 排序5.1 排序的基本特征5.1.1 穩(wěn)定性5.1.2 對哨兵的需求5.1.3 對鏈表進行排序的能力5.1.4 輸入的階的相關性5.1.5 對額外存儲空間的需求5.1.6 內(nèi)部排序技術與外部排序技術5.2 排序模型5.2.1 冒泡排序5.2.2 插入排序5.2.3 希爾排序5.2.4 快速排序5.2.5 堆排序5.3 對鏈表進行插入排序5.4 對鏈表進行快速排序5.5 對多個鍵進行排序——不穩(wěn)定排序的修正方法5.6 網(wǎng)絡排序5.7 小結(jié)：選擇一種排序算法5.8 資源和參考資料第6章 樹6.1 二叉樹6.1.1 樹查找6.1.2 節(jié)點插入6.1.3 節(jié)點刪除6.1.4 二叉查找樹的性能6.1.5 AVL樹6.2 紅黑樹6.3 伸展樹6.4 B樹6.4.1 保持B樹平衡6.4.2 實現(xiàn)B樹算法6.4.3 B樹實現(xiàn)的代碼6.5 可以看見森林嗎6.6 資源和參考資料第7章 日期和時間7.1 日期例程的庫7.2 時間例程7.3 用于日期和時間數(shù)據(jù)的格式7.4 最后的提醒7.5 資源和參考資料第8章 任意精度的算術8.1 構(gòu)建計算器8.2表示數(shù)字8.3 計算8.4 加法8.5 減法8.6 乘法8.7 除法8.8 關于計算器要注意的最后幾點8.9 用于計算平方根的牛頓算法8.10 分期付款表8.11 資源和參考資料第9章 數(shù)據(jù)壓縮9.1 行程編碼9.2 霍夫曼壓縮9.2.1 代碼9.2.2 其他問題9.3 滑動窗口壓縮9.4 基于字典的壓縮（LZW）9.4.1 LZW算法的偽代碼9.4.2 LZW壓縮的實現(xiàn)9.4.3 填滿字典9.5 使用哪種壓縮方法9.6 資源和參考資料第10章 數(shù)據(jù)完整性和驗證10.1 簡單的校驗和10.2 加權校驗和10.3 循環(huán)冗余校驗10.3.1 CRC-CCITT10.3.2 CRC-1610.3.3 CRC-3210.4 資源和參考資料

章節(jié)摘錄

　　第1章　緒論　　1.1　評估算法　　除了最直觀的應用之外，算法是所有程序的核心和靈魂。算法一般被設計用于以最小的代價高效地解決特定的問題。算法的價值一般取決于兩方面因素：如何恰當?shù)亟鉀Q問題以及如何高效地實現(xiàn)解決方案。這些是算法分析的定性和定量方面。　　對于許多算法，質(zhì)量不是一個問題。例如，對于排序算法，必須保證每次都對所有元素正確地進行了排序。一旦出錯，就必須丟棄它并且嚴格說來不能將其視為一種算法。在其他領域，不能基于這種簡單的通過／失敗測試來度量質(zhì)量。例如，在第4章中介紹的Soundex算法允許檢索聽起來相同的單詞或名字。與排序算法不同，可以調(diào)整Soundex算法，以尋找接近的匹配或者相當寬泛的匹配；這取決于實現(xiàn)算法的方式和開發(fā)人員的需求。在這種情況下，質(zhì)量是可度量的并且是算法的重要方面，并且指導我們認真選擇不同的解決方案?！　∷惴ㄔO計的定量方面嘗試確定算法所需的資源。一般來說，最重要的度量標準是時間：即算法運行得有多快?偶爾，計算機資源（比如可用的內(nèi)存）也是一個重要因素。度量性能　　與基準的性能不同，算法的性能很少依據(jù)時間來加以說明。在論及排序例程時，你幾乎從未聽到它完成排序要花費8．62秒這樣的說明。這有一個很好的理由：這種計時難以復制，并且通常依賴于正在處理的數(shù)據(jù)的具體特征。算法不依賴于計時，而是依賴于一個直觀的方程，以顯示輸入的大小與性能之間的關系。用于顯示這種關系的傳統(tǒng)方法是使用符號D，稱為大O表示法（big.oh notation）。其工作方式是：假定你有一個算法，它簡單地通讀一個文本文件，從中查找單詞flea。一種合理的方法是尋找字母f的每個實例（參見第4章）。當找到一個f，該算法就測試4個字母的序列，看看它是不是單詞flea。在這個示例中，顯然執(zhí)行時間直接與文本文件的大小成正比。如果給定的文件包含Ⅳ個字符，那么我們就說該算法的執(zhí)行時間的界限是O（N）。你會注意到這種表述沒有考慮到可能影響性能的其他因素——例如，字母f在文本中出現(xiàn)的頻繁程度。在查找字符串時（比如fleas rarely wear collars），字符串的長度以及其中相似字符串（比如fleasrarely weal"colors）出現(xiàn)的頻率也會影響性能。不過，嚴格來講，這些因素是要處理的數(shù)據(jù)的函數(shù)，而不是算法的函數(shù)。因此，在大O表示法中，它們不會出現(xiàn)在公式中。該表示法只是簡單地說明數(shù)據(jù)規(guī)模（一般用Ⅳ表示，偶爾也用n表示）與算法的典型性能之間的關系?！　?hellip;…

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    程序員實用算法 PDF格式下載

---