程式設計算法基礎

成書過程

編寫情況

《程式設計算法基礎》是由梁冰、馮林組織大連理工大學ACM集訓隊員在教學案例和訓練題庫的基礎上編寫完成的。參加編寫的ACM歷屆集訓隊員有高品、張璨、孫木鑫、劉卓、胡駿、戴宇心、楊文冕、趙漢光、陳梁堅、劉博等同學。

此外，該書在撰寫過程中還參考了中國國內外的相關研究成果和網站資源。擔任該書主審的是清華大學吳文虎教授、北京郵電大學計算機學院房鳴教授。

出版工作

2018年4月30日，《程式設計算法基礎》由高等教育出版社出版。

出版社工作人員

策劃編輯	責任編輯	封面設計	版式設計	插圖繪製	責任校對	責任印製
孫琳	孫琳	李小璐	童丹	杜曉丹	李大鵬	劉思涵

內容簡介

《程式設計算法基礎》共分11章，第1章介紹Linux作業系統與C++編程環境；第2章簡單介紹初級算法；第3章介紹基礎數據結構；第4章介紹枚舉、遞推、遞歸、貪心、分治、哈希和二分等基礎算法設計；第5章介紹簡單排序算法；第6章介紹圖論的相關知識，包括最短路徑問題和最小生成樹問題的一些經典算法；第7章介紹並查集和線段樹兩種高級數據結構；第8章介紹KMP、字典樹、Z算法和馬拉車算法等處理字元串的數據結構；第9章介紹搜尋的相關算法，包括深度優先搜尋、寬度優先搜尋、雙向寬度優先搜尋、A*搜尋和一些剪枝常用的策略；第10章介紹初等數論；第11章介紹動態規劃，重點介紹背包問題。

教材目錄

前輔文

第1章 Linux作業系統與編程環境

1.1 Linux基礎

1.2 編譯器

1.2.1 Code::Blocks安裝

1.2.2 Code::Blocks編程環境配置

1.2.3 Code::Blocks編寫程式

1.3 編譯C++檔案

1.4 ACM國際大學生程式設計競賽

1.5 自動評測系統

1.5.1 評測系統反饋

1.5.2 國內知名評測系統

第2章算法入門

2.1 快速冪取模算法

2.1.1 模運算

2.1.2 冪取模的計算

2.1.3 例題講解

2.2 算法

2.2.1 算法的定義

2.2.2 學習算法的意義

2.2.3 算法複雜度分析

第3章基本數據結構

3.1 基本線性數據結構

3.1.1 線性表

3.1.2 棧

3.1.3 佇列

3.1.4 例題講解

3.2 二叉搜尋樹

3.2.1 二叉搜尋樹的定義

3.2.2 二叉搜尋樹的實現

3.3 C++標準模板庫

3.3.1 vector

3.3.2 set

3.3.3 map

3.3.4 priority_queue

3.3.5 例題講解

3.4 練習題

第4章基本算法設計

4.1 枚舉

4.1.1 枚舉算法的定義

4.1.2 枚舉算法的解題過程

4.1.3 枚舉算法的特點

4.1.4 例題講解

4.2 遞推

4.2.1 遞推的概念

4.2.2 遞推與數列

4.2.3 斐波那契數列

4.2.4 遞推的兩種順序

4.2.5 例題講解

4.3 遞歸

4.3.1 遞歸的定義

4.3.2 遞歸的要求

4.3.3 遞歸與遞推

4.3.4 例題講解

4.4 貪心算法

4.4.1 貪心算法的概念

4.4.2 貪心算法的原理

4.4.3 例題講解

4.5 分治算法

4.5.1 分治的基本思想

4.5.2 分治的一般解題步驟

4.5.3 分治的特點

4.5.4 歸併排序

4.5.5 例題講解

4.6 模擬

4.6.1 高精度計算

4.6.2 矩陣運算

4.6.3 例題講解

4.7 哈希

4.7.1 直接定址表

4.7.2 哈希表

4.7.3 例題講解

4.8 二分法

4.8.1 二分查找

4.8.2 二分逼近

4.8.3 求解性問題的二分策略

4.8.4 例題講解

4.9 練習題

第5章排序算法

5.1 基於比較的排序算法

5.1.1 簡單排序

5.1.2 快速排序

5.1.3 限制和優勢

5.2 基於統計的排序算法

5.2.1 計數排序

5.2.2 基數排序

5.3 例題講解

5.4 練習題

第6章圖的基本算法

6.1 圖的定義及存儲方法

6.1.1 圖的定義

6.1.2 有向圖和無向圖

6.1.3 路徑與連通

6.1.4 圖的存儲結構

6.2 圖的遍歷及拓撲排序

6.2.1 圖的深度優先遍歷

6.2.2 圖的寬度優先遍歷

6.2.3 圖的拓撲排序

6.2.4 例題講解

6.3 最小生成樹

6.3.1 Kruskal算法

6.3.2 Prim算法

6.4 單源最短路徑

6.4.1 Dijkstra算法

6.4.2 Bellman-Ford算法

6.4.3 SPFA算法

6.4.4 差分約束系統

6.4.5 例題講解

6.5 每對頂點的最短路徑

6.5.1 最短路徑和矩陣乘法

6.5.2 Floyd算法

6.5.3 例題講解

6.6 練習題

第7章並查集和線段樹

7.1 並查集

7.1.1 並查集的基本概念

7.1.2 並查集的操作

7.1.3 例題講解

7.2 線段樹

7.2.1 線段樹的概念與性質

7.2.2 線段樹的基本操作

7.2.3 例題講解

7.3 練習題

第8章字元串問題

8.1 Trie樹

8.1.1 Trie樹的基本概念

8.1.2 Trie樹的操作

8.1.3 例題講解

8.2 KMP算法

8.2.1 BF算法簡介

8.2.2 KMP算法原理和實現

8.2.3 例題講解

8.3 Z算法與Manacher算法

8.3.1 Z算法

8.3.2 Manacher算法

8.3.3 例題講解

8.4 練習題

第9章搜尋

9.1 狀態空間和狀態空間搜尋

9.2 寬度優先搜尋

9.2.1 基本概念

9.2.2 算法分析與實現

9.2.3 例題講解

9.3 深度優先搜尋

9.3.1 基本概念

9.3.2 算法分析與實現

9.3.3 例題講解

9.4 雙向寬度優先搜尋

9.5 A*搜尋

9.5.1 基本概念

9.5.2 算法分析與實現

9.5.3 例題講解

9.6 剪枝

9.6.1 基本概念

9.6.2 可行性剪枝

9.6.3 最優性剪枝

9.6.4 例題講解

9.7 練習題

第10章初等數論

10.1 初等數論簡介

10.2 最大公約數和擴展歐幾里得算法

10.2.1 歐幾里得算法

10.2.2 擴展歐幾里得算法

10.2.3 例題講解

10.3 線性方程與同餘方程

10.3.1 線性方程

10.3.2 例題講解

10.4 乘法逆元

10.4.1 整數集合下逆元的求解方法

10.4.2 例題講解

10.5 中國剩餘定理

10.5.1 中國剩餘定理

10.5.2 中國剩餘定理的擴展

10.6 質數篩法與質因數分解

10.6.1 埃拉托斯特尼（Eratosthenes）篩法

10.6.2 歐拉（Euler）篩法

10.6.3 質因數分解

10.7 歐拉函式

10.7.1 歐拉函式與歐拉定理

10.7.2 例題講解

10.8 原根與剩餘系

10.9 指數方程與高次同餘方程

10.9.1 指數方程

10.9.2 高次同餘方程

10.9.3 例題講解

10.10 高斯消元

10.11 練習題

第11章動態規劃入門

11.1 動態規劃概述

11.1.1 數字三角形

11.1.2 組合數

11.1.3 動態規劃方法求解的問題類型

11.1.4 例題講解

11.2 背包問題

11.2.1 0-1背包

11.2.2 完全背包

11.2.3 多重背包

11.3 經典動態規劃問題

11.3.1 最長上升子序列

11.3.2 最長公共子序列

11.3.3 矩陣鏈相乘問題

11.4 練習題

參考文獻

（註：目錄排版順序為從左列至右列）

教學資源

課程資源

《程式設計算法基礎》有配套的Abook數字課程，該數字課程包含程式運行過程抓屏錄製的58個視頻和9個課外拓展閱讀pdf檔案等內容。

課程名稱	出版社	內容編輯
“程式設計算法基礎”數字課程	高等教育出版社、高等教育電子音像出版社	孫琳

教材特色

該教材以ACM程式設計競賽的題目為基礎，依次介紹了一些包括排序算法在內的、基礎的數據結構和算法設計，可以當作算法入門的讀物。

該教材對每個算法都有圖文講解；每章節的後面都有針對該節知識點的例題講解，每道例題都是中國國內外程式線上判題系統中的原題，而對每道例題都從理解題意開始，詳細講解解題的思路，並附有完整的可以正確通過測試樣例的代碼。

該教材每一章的最後帶有一些練習題，並且每道練習題後附帶有思路分析。

作者簡介

梁冰，女，博士，大連理工大學創新實驗學院工程師。