算法分析與設(shè)計

前言

算法分析與設(shè)計是一門重要課程。算法設(shè)計在各類科學(xué)計算中具有核心地位和作用，沒有好的算法，計算機(jī)完成一件工作可能需要很長時間，而有好算法，完成一件工作可能僅需要幾秒。同時，算法被公認(rèn)為是計算科學(xué)的基石，翻開重要的學(xué)術(shù)刊物，算法都占有一席之地，沒有算法，程序?qū)⒉粡?fù)存在。1.體系介紹算法是一門方法論方面的課程，方法論是人們認(rèn)識世界、改造世界的一般方法，是人們用什么樣的方式、方法來觀察事物和處理問題的一般依據(jù)。在哲學(xué)上，世界觀主要解決世界“是什么”的問題，方法論主要解決“怎么辦”的問題。在科學(xué)計算方面，算法也是解決“怎么辦”的問題。作為一門方法論的課程，主要講解一些普適的、抽象的解決問題的方法。從認(rèn)知角度來講，對于抽象內(nèi)容需要一些具體實際的例子來幫助消化吸收，否則知識將變得非?？辗骸Ｄ壳?，算法分析與設(shè)計方面的圖書從來源上可以分成兩類：國內(nèi)圖書和國外引進(jìn)。從內(nèi)容上也可以分成兩類：單純講解算法和同時講解數(shù)據(jù)結(jié)構(gòu)與算法，總體內(nèi)容上幾乎沒有太大的區(qū)別。從算法描述上，主要以采用C／C++和Java語言描述居多，以程序?qū)崿F(xiàn)算法框架為主，完整的算法實現(xiàn)的實例相對較少，這使得算法課程成為一門理論性較強(qiáng)的課程。編者對國內(nèi)眾多專業(yè)課程進(jìn)行了調(diào)研，考慮到讀者前期一般具有c或者C++語言基礎(chǔ)，Java語言大多是高年級以后以選修課程的形式開設(shè)，而算法課程開設(shè)的時間一般早于Java語言，因此選擇C／C++語言描述。編寫算法對語言要求相對較高，涉及面的也廣，因此安排一章對C++算法設(shè)計進(jìn)行介紹。并在此基礎(chǔ)上介紹了線性、非線性數(shù)據(jù)結(jié)構(gòu)和排序搜索算法設(shè)計，最后詳細(xì)介紹了目前算法中被稱為“五虎上將”的分治法、貪心法、動態(tài)規(guī)劃、回溯法和分支限界法，同時對于每一種算法都列舉了幾個完整的實例。

內(nèi)容概要

本書以程序設(shè)計作為基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)作為工具、五大核心算法作為目標(biāo)，系統(tǒng)地介紹了算法設(shè)計中典型問題的求解過程。    全書分成程序設(shè)計基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)和五大核心算法3個部分共10章。第1部分為算法分析與程序設(shè)計基礎(chǔ)，介紹了算法分析的時間和空間復(fù)雜度，以及C++算法相關(guān)的程序設(shè)計基礎(chǔ)；第2部分為算法設(shè)計數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，介紹了線性和非線性數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，同時對常用的排序和搜索算法作了詳細(xì)介紹；第3部分為典型算法分析與問題求解，介紹了經(jīng)典算法設(shè)計中的“五虎上將”：分治法、貪心法、動態(tài)規(guī)劃、回溯法和分支限界法。    本書可以作為高校及各類培訓(xùn)機(jī)構(gòu)相關(guān)課程的教材或參考書，提供全書源代碼、軟件和授課幻燈片等資料，可以從圖書支持網(wǎng)站http://www.gettop.net下載，也可以從出版社網(wǎng)站http://press.bjtu.edu.cn的下載欄目中下載。

書籍目錄

第1部分  算法分析與程序設(shè)計基礎(chǔ)　第1章  算法的基本概念　  1.1  算法的基本概念　    1.1.1  算法的特征　    1.1.2  算法的4個標(biāo)準(zhǔn)　    1.1.3  算法的描述形式　  1.2  算法復(fù)雜性分析框架　    1.2.1  增長次數(shù)　    1.2.2  漸進(jìn)符號　    1.2.3  時間復(fù)雜度　    1.2.4  空間復(fù)雜度　  本章小結(jié)　  課后習(xí)題　第2章  C++算法程序設(shè)計基礎(chǔ)　  2.1  C++語言概述　    2.1.1  C++語言的優(yōu)勢　    2.1.2  C++語言的內(nèi)容　    2.1.3  編程工具　  2.2  C++程序結(jié)構(gòu)初步　    2.2.1  預(yù)處理指示符初步　    2.2.2  注釋　    2.2.3  基本輸入／輸出　  2.3  使用C++語言編寫簡單代碼　    2.3.1  面向過程的C語言　    2.3.2  面向過程的C++語言　    2.3.3  面向?qū)ο蟮腃++語言　  2.4  C++面向?qū)ο蠡A(chǔ)　    2.4.1  數(shù)據(jù)成員　    2.4.2  成員函數(shù)　    2.4.3  類對象成員的訪問　    2.4.4  類的訪問限制　    2.4.5  動態(tài)內(nèi)存分配　    2.4.6  C++程序內(nèi)存分配　  2.5  構(gòu)造函數(shù)和析構(gòu)函數(shù)　    2.5.1  構(gòu)造函數(shù)的概念　    2.5.2  析構(gòu)函數(shù)的概念　    2.5.3  帶參數(shù)的構(gòu)造函數(shù)　    2.5.4  重載構(gòu)造函數(shù)　  2.6  類中的this指針　  2.7  類中的const修飾符　    2.7.1  常對象　    2.7.2  常成員函數(shù)　    2.7.3  常數(shù)據(jù)成員　  2.8  模板的基本概念　    2.8.1  使用模板的必要性　    2.8.2  模板的分類　  2.9  函數(shù)模板　    2.9.1  函數(shù)模板的定義　    2.9.2  使用函數(shù)模板　    2.9.3  函數(shù)模板的重載　  2.10  類模板　    2.10.1  類模板的定義　    2.10.2  使用類模板　  2.11  繼承的基本概念　    2.11.1  繼承的必要性　    2.11.2  繼承的實現(xiàn)方式　    2.11.3  繼承中的靜態(tài)數(shù)據(jù)成員　  2.12  基類和派生類的關(guān)系　    2.12.1  基類指針　    2.12.2  繼承下的構(gòu)造函數(shù)和析構(gòu)函數(shù)　    2.12.3  重寫基類成員　    2.12.4  調(diào)用基類成員函數(shù)　  2.13  詳解protected關(guān)鍵字　  2.14  保護(hù)繼承與私有繼承　    2.14.1  公有繼承　    2.14.2  私有繼承　    2.14.3  保護(hù)繼承　  本章小結(jié)　  課后習(xí)題第2部分  算法設(shè)計數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)　第3章  線性數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)　  3.1  抽象數(shù)據(jù)類型　  3.2  線性表基礎(chǔ)　    3.2.1  線性表定義及特點　    3.2.2  順序表　    3.2.3  鏈表　    3.2.4  數(shù)組與鏈表性能比較　  3.3  棧與隊列基礎(chǔ)　    3.3.1  棧　    3.3.2  隊列　  本章小結(jié)　  課后習(xí)題　第4章  非線性數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)　  4.1  樹與二叉樹　    4.1.1  樹的基本概念　    4.1.2  二叉樹　  4.2  樹與二叉樹的存儲結(jié)構(gòu)　    4.2.1  二叉樹的存儲結(jié)構(gòu)　    4.2.2  樹的存儲結(jié)構(gòu)　    4.2.3  二叉樹的遍歷　  4.3  圖　    4.3.1  圖的基本概念　    4.3.2  圖的存儲結(jié)構(gòu)　  本章小結(jié)　  課后習(xí)題　第5章  排序與搜索算法基礎(chǔ)　  5.1  排序算法的基本概念　    5.1.1  排序的分類　    5.1.2  排序算法的評價標(biāo)準(zhǔn)　  5.2  簡單排序算法　    5.2.1  插入排序　    5.2.2  選擇排序　    5.2.3  冒泡排序　  5.3  快速排序　  5.4  堆排序　  5.5  歸并排序　  5.6  希爾排序　  5.7  線性表查找　    5.7.1  順序查找　    5.7.2  二分查找　  5.8  樹與圖的搜索　    5.8.1  二叉排序樹搜索　    5.8.2  B-樹　    5.8.3  廣度優(yōu)先搜索　    5.8.4  圖的深度優(yōu)先搜索　  本章小結(jié)　  課后習(xí)題第3部分  典型算法分析與問題求解　第6章  遞歸與分治法算法設(shè)計　  6.1  遞歸法　    6.1.1  遞歸算法的特性　    6.1.2  遞歸的執(zhí)行過程　  6.2  遞歸法應(yīng)用舉例　    6.2.1  漢諾塔問題求解　    6.2.2  斐波那契數(shù)列問題求解　    6.2.3  八皇后問題　  6.3  分治法　    6.3.1  問題提出　    6.3.2  分治法概述　  6.4  分治法應(yīng)用舉例　  本章小結(jié)　  課后習(xí)題　第7章  貪心算法設(shè)計　  7.1  貪心法　    7.1.1  問題提出　    7.1.2  貪心法的基本思路　  7.2  貪心法應(yīng)用舉例　    7.2.1  背包問題　    7.2.2  哈夫曼編碼　    7.2.3  單源最短路徑　    7.2.4  最小生成樹　  本章小結(jié)　  課后習(xí)題　第8章  動態(tài)規(guī)劃算法設(shè)計　  8.1  動態(tài)規(guī)劃法　    8.1.1  動態(tài)規(guī)劃法的基本概念　    8.1.2  多階段決策　    8.1.3  動態(tài)規(guī)劃法適用條件　    8.1.4  動態(tài)規(guī)劃法解決問題的步驟　  8.2  動態(tài)規(guī)劃法應(yīng)用舉例　    8.2.1  多源最短路徑　    8.2.2  最大公共子序列問題　    8.2.3  導(dǎo)彈攔截問題　  本章小結(jié)　  課后習(xí)題　第9章  回溯法算法設(shè)計　  9.1  回溯法　    9.1.1  回溯法的基本概念　    9.1.2  回溯法的基本思想　    9.1.3  回溯法求解問題的步驟　  9.2  回溯法應(yīng)用舉例　    9.2.1  小老鼠走迷宮問題　    9.2.2  子集合問題　    9.2.3  全排列問題　    9.2.4  八皇后問題　    9.2.5  0-1背包問題　  本章小結(jié)　  課后習(xí)題　第10章  分支限界算法設(shè)計　  10.1  分支限界　    10.1.1  分支限界法的基本思想　    10.1.2  求解問題的適用條件和步驟　    10.1.3  分支限界的優(yōu)缺點　  10.2  分支限界應(yīng)用舉例　    10.2.1  0-1背包問題　    10.2.2  旅行售貨員問題　  本章小結(jié)　  課后習(xí)題附錄A  部分習(xí)題參考答案參考文獻(xiàn)

章節(jié)摘錄

插圖：1.1.1算法的特征計算機(jī)的問世是20世紀(jì)人類最偉大的發(fā)明之一，它把人類社會帶進(jìn)了信息技術(shù)時代，而算法是計算機(jī)科學(xué)的重要基礎(chǔ)，就像算盤一樣，人們需要為計算機(jī)編制各種各樣的“口訣”即算法，才能使其工作。雖然每天都在和算法打交道，但是能嚴(yán)格地指出什么是算法卻不是一件容易的事。著名的Webster詞典在“algorithm”詞條下指出：“算法即在有限步驟內(nèi)解一個數(shù)學(xué)問題的過程，步驟中常常包括某一操作的重復(fù)”。更廣義地說，一個算法就是解一個問題或?qū)崿F(xiàn)某一目標(biāo)的逐步過程。這個定義并未與計算機(jī)相關(guān)，事實上，我國的數(shù)學(xué)著作《九章算術(shù)》就是采用問題集的形式編的，該書共有246個問題的求解算法，遠(yuǎn)在計算機(jī)出現(xiàn)之前就已提出。D.E.Knuth給出了另一個說明：一個算法，就是一個有窮規(guī)則的集合，規(guī)定了一個解決某一特定類型問題的運算序列，此外還應(yīng)具有如下5個重要特性。1.輸入性一個算法要具有0個或多個外部量作為算法的輸入，這些外部量通常體現(xiàn)為算法中的一組變量，有些輸入量需要在算法執(zhí)行過程中輸入。從表面上看，有些算法好像沒有輸入量，實際上是輸入量已被嵌入算法之中。2.輸出性  一個算法必須具有一個或多個輸出，以反映算法對輸入數(shù)據(jù)加工后的結(jié)果，沒有輸出的算法是毫無意義的。

編輯推薦

《算法分析與設(shè)計(C++描述)》：原理與技術(shù)的完美結(jié)合教學(xué)與科研的最新成果語言精練、實例豐富可操作性強(qiáng)，實用性突出

圖書封面

評論、評分、閱讀與下載

---

    算法分析與設(shè)計 PDF格式下載

---