《高等學校應用型“十二五”規劃教材（計算機類）：數據結構與算法分析》以程序設計能力的培養為目標，系統地介紹了數據結構和算法設計的相關知識，其主要內容包括：線性表、棧、隊列、串、數組、樹、圖、索引和散列等基本數據結構及其應用；分治法、動態規劃、貪心算法、回溯法、分支界限法等常用的算法設計方法。書中還通過具體實例的分析和設計，介紹了軟件設計規范及程序設計的關鍵技術，具有較高的使用價值。
第1章 緒論
1.1 軟件的基本概念
1.2 數據結構概述
1.3 算法與算法分析
1.4 程序設計的關鍵技術
1.5 程序設計的步驟及實例
習題
第2章 線性表
2.1 線性表的基本概念及運算
2.2 順序表
2.3 鏈表
習題
第3章 棧和隊列
3.1 棧
3.2 隊列
習題
第4章 串和數組
4.1 串及其運算
4.2 串的存儲結構
4.3 串運算的實現
4.4 數組的定義和運算
4.5 數組的順序存儲結構
4.6 矩陣的壓縮存儲
習題
第5章 樹
5.1 樹的基本概念
5.2 二叉樹
5.3 二叉樹的存儲結構
5.4 二叉樹的遍歷
5.5 樹和森林
5.6 線索二叉樹
5.7 二叉樹的應用
習題
第6章 圖
6.1 圖的基本概念
6.2 圖的存儲方法
6.3 圖的遍歷
6.4 生成樹和最小生成樹
6.5 最短路徑
6.6 拓撲排序
6.7 關鍵路徑
習題
第7章 索引結構與散列技術
7.1 索引結構
7.2 散列技術
習題
第8章 縮小規模算法
8.1 分治與遞歸算法
8.2 動態規劃
8.3 貪心算法
習題
第9章 搜索算法
9.1 回溯法
9.2 分支界限法
習題
第10章 “難”問題求解算法
10.1 概率算法
10.2 近似算法
習題
參考文獻
第1章 緒 論
隨著計算機科學技術的發展和日趨成熟，軟件已經成為社會發展的重要驅動力之一：軟件是商業決策的基本引擎，是解決現代科學研究和工程問題的基礎，也是提升現代產品和服務品質的關鍵因素。軟件在現代社會中是不可缺少的，它可以應用于各種類型的應用系統中，如辦公、娛樂、交通、教育、醫藥、通信……數不勝數，并成為從基礎教育到基因工程的所有領域的推進器。
所有這一切改變了軟件原有的概念，軟件無所不在，已經成為人們現實生活中必不可少的實用技術。
1.1 軟件的基本概念
從一般意義上講，能夠在計算機上運行的程序都可以稱為軟件。軟件更準確的定義是利用計算機本身提供的邏輯功能，合理地組織計算機的工作流程，簡化或替代人們使用計算機過程中的各個環節，提供給使用者一個便于操作的工作環境的“程序集”。它包括計算機程序和與之相關的文檔資料的總和（文檔是指編制程序所使用的技術資料和使用該程序的說明性資料，如使用說明書等，即開發、使用和維護程序所需的一切資料）。
軟件是邏輯的而不是物理的產品，與硬件相比具有以下完全不同的特征：
（1）軟件是由開發或工程化而形成的，而不是由傳統意義上的制造產生的。硬件的再制造過程中可能引入質量問題，軟件則幾乎不可能發生類似問題。軟件的成本集中于開發，而硬件的成本除了開發成本外還有生產成本。
（2）軟件不會磨損。軟件的故障率隨時間的推移而降低，而硬件的故障率隨時間的推移而增加。硬件模塊磨損后可以用新的備用模塊替換，而軟件故障則是其中的錯誤，沒有可替換的備件。
（3）大多數軟件是自定義的，而不是通過已有的組件組裝而來的。當然，目前基于組件的軟件開發已經成為軟件未來的主要發展趨勢。
1.1.1 軟件應用
從某種程度上講，對軟件應用給出一個確切的分類是比較困難的。下面給出的一些軟件的應用領域，可以看做是一種潛在的應用分類：
（1）系統軟件。系統軟件是指一組為其他程序服務的程序，如操作系統、編譯器等。
（2）實時軟件。管理、分析和控制現實世界中發生的事件的程序稱為實時軟件。實時軟件包括：①數據接收部件：負責從外部環境獲取和格式化信息；②分析部件：負責將信息轉換為具體應用所需要的形式；③控制/輸出部件：負責對外部事件做出響應；④管理部件：負責協調其他各部件，使得系統能夠保持一個可接受的實時響應時間。
（3）商業軟件。商業信息處理是目前最大的軟件應用領域。具體的“信息系統”均可歸入管理信息系統（MIS）軟件。使用這類軟件可以訪問一個或多個包含商業信息的大型數據庫。該領域的應用使已有的數據重新構造，變換成一種能夠輔助商業操作或管理決策的形式。除了傳統的數據處理應用外，商業軟件還包括交互式計算和客戶/服務器模式計算（如POS事務處理）。
（4）工程和科學計算軟件。工程和科學計算軟件的特征是“數值分析”算法。此類軟件應用的涵蓋面很廣，從天文學到火山學，從汽車壓力分析到航天飛機的軌道動力學，從分子生物學到自動化制造等。
（5）嵌入式軟件。智能產品在工業和消費電子市場上都是必不可少的，而嵌入式軟件正是駐留在這些智能產品的只讀內存中，實現產品的智能應用。嵌入式軟件能夠執行有限但專職的功能。
（6）個人軟件。僅供個人使用的程序稱為個人軟件，如文字處理、電子表格、多媒體娛樂、數據庫管理、個人金融應用、訪問外部網絡應用等。
（7）人工智能軟件。利用非數值算法解決復雜的問題，這些問題不能通過計算或直接分析得到答案，這就要使用人工智能軟件，如專家系統（基于知識的軟件）、模式識別、定理證明、游戲等。
1.1.2 軟件生存期
軟件生存期是指從軟件項目的需求定義到完成使命后而廢棄的全過程。把整個過程中的活動進一步展開，可以得到軟件生存期的六個工作階段，即制定計劃、需求分析和定義、軟件設計、程序編制、軟件測試及運行/維護。
1．制定計劃
首先要確定開發軟件系統的總目標，給出對其在功能、性能、可靠性以及接口等方面的要求；然后由系統分析員和用戶合作，論證該項軟件任務的可行性，探討解決問題的方案，并對可利用的資源（計算機硬件、軟件、人力等）、研發的成本、可取得的效益、開發的進度做出評估，制定出完成開發任務的實施計劃，連同可行性研究報告，提交管理部門審查。
2．需求分析和定義
對開發軟件提出的需求進行分析并給出詳細的定義。首先由軟件人員和用戶共同討論決定哪些需求是可以滿足的，并對其加以確切的描述；然后編寫出軟件需求說明書或系統功能說明書，以及初步的系統用戶手冊，提交管理機構評審。
3．軟件設計
在軟件設計階段中，設計人員把已確定的各項需求轉換成一個相應的體系結構。結構中的每一個組成部分都是意義明確的模塊，每個模塊都和某些需求相對應，即概要設計。然后對每個模塊要完成的工作進行具體的描述，為源程序的編寫打下基礎，即詳細設計。
……
新書資訊