前言

本書為普通高等教育“十一五”國家級規劃教材。

算法設計與分析不僅是計算機科學與技術專業學生的必備知識，也是計算機應用工作者必不可少的基礎知識。掌握扎實的算法設計與分析理論和方法有助于理工科學生進一步學習計算機技術，適應更廣泛的職業挑戰。

計算機學科教學計劃2001（Computing Curricula 2001，簡稱CC2001）將計算機學科分成14個領域，每個領域分成若干個知識單元，每個知識單元又包括若干個主題。CC2001強調算法，重視算法設計與分析能力和程序設計能力。計算機算法的基本內容主要包含在算法與復雜性（Algorithm And Complexity，簡稱AL）和程序設計基礎（Programming Fundamental，簡稱PL）等知識領域中。在CC2001建議的計算機科學與技術專業的280個核心學時中，程序設計與算法方面分配90個核心學時，約占總核心學時的32.1%。

算法領域涉及的內容廣泛，通常包括迄今為止，算法學家們所設計的許多基本和經典算法，如排序、搜索、圖算法、組合問題算法、字符串算法和大量的數值算法，算法問題求解、算法分析技術和常用的算法設計策略，可計算性理論和問題復雜性的研究，如計算模型、NP完全問題和問題復雜度下界理論。近年來，算法研究在隨機算法、近似算法、密碼算法、分布式算法和并行算法，以及其他算法方面也都有很多新成果。

作為“算法設計與分析”課程教材，根據我國在算法與數據結構方面課程開設的實際情況，本書不再重復屬于我國傳統“數據結構”課程中的基本數據結構和算法的內容，但選用快速排序等在“數據結構”課程中已學過的若干排序、搜索和圖算法，它們被作為算法設計策略和算法分析的實例使用。這種做法不是內容的簡單重復，而是必要的和有益的深化。以學生熟知的知識為基礎，介紹新知識，可使學生更容易理解和接受新的算法知識。

算法知識理論性較強，涉及的范圍又很廣，給學習和理解造成困難。為了將本書寫成條理清晰、內容翔實、邏輯嚴謹、深入淺出的“算法設計與分析”教材，作者做了以下努力。

首先，本書分3部分組織內容，力求做到結構清晰、內容取舍恰當。

其次，書中算法都有完整的C++程序，程序結構清楚，構思精巧，對程序代碼都做了詳細注釋，所有程序都已在VC++環境下編譯通過并能正確運行，它們既是學習算法設計的示例，也是很好的C++程序設計示例。

此外，本書通過大量實例和圖示介紹算法，并有豐富的習題，便于自學。

這樣做的目的是在保持算法科學性的同時，加強其技術性和實用性，也降低算法學習的難度，使復雜抽象的算法設計更容易為學習者理解和掌握。這也體現了計算機學科的科學性和工程性、理論性和實踐性并重的學科特點。

全書包括3部分：算法和算法分析、算法設計策略及求解困難問題。

第1部分介紹算法概念、算法問題分類和問題求解方法，算法復雜度、遞歸技術，還介紹了兩種新的數據結構：跳表和伸展樹，以及它們特定的算法分析方法。

第2部分討論常用的算法設計策略：基本搜索和遍歷方法、分治法、貪心法、動態規劃法、回溯法和分枝限界法。對于每種算法設計策略，通常先介紹一般方法，然后使用該策略解決若干經典的算法問題。

第3部分介紹NP完全問題、隨機算法、近似算法，并對現代密碼學和數論算法也做了簡要論述。

本書作者在南京郵電大學講授“算法設計與分析”和“數據結構”課程多年。本書是在作者編寫出版的多本關于算法與數據結構領域教材的基礎上，參考了近年來國內外多種算法設計與分析的優秀教材編寫而成的。本書的編寫得到了電子工業出版社的大力支持，并得到了南京郵電大學和計算機學院領導的推薦和關心，在此表示衷心感謝。

書中若有不妥之處，敬請讀者批評指正。

作者