數據結構與算法（簡體書）

數據結構與算法是計算機專業的重要基礎課，是該專業的核心課程之一，是一門集技術性、理論性和實踐性於一體的課程。《普通高等教育“十一五”國家級規劃教材．計算機系列教材：數據結構與算法》重點介紹抽象數據類型、基本數據結構、C語言數據結構描述、數據結構的應用、算法設汁與分析以及算法性能評價等內容，重點是讓讀者理解數據抽象與編程實現的關係，提高用計算機解決實際問題的能力。
《普通高等教育“十一五”國家級規劃教材．計算機系列教材：數據結構與算法》內容包括基本數據類型、抽象數據類型、順序表、鏈表、串、樹和二叉樹、圖、遞歸與分治算法、貪心算法、分支限界和動態規劃等內容。
《普通高等教育“十一五”國家級規劃教材．計算機系列教材：數據結構與算法》結構合理，內容豐富，算法描述清晰，用C語言編寫的算法代碼都已調試通過，便於自學，可作為高等院校計算機專業、軍事院校的基礎合訓專業和其他相關專業的教材和參考書，也可供從事計算機軟件開發的科技下作者參考。

熊嶽山，男，1963年4月出生，國防科技大學計算機學院教授，全軍優秀教師。計算機應用技術、計算數學博士生導師。主要研究興趣為虛擬手術、圖形圖像處理和數值計算方法。主持多項國家自然科學基金項目、“863”高技術項目、國防實驗技術研究項目的研究。曾主講“數據結構”、“數值分析及其應用”、“計算方法”、“偏微分方程數值解”、“矩陣迭代分析”、“計算幾何”等課程，多次獲教學優秀獎。編著的《數據結構》教材獲湖南省高等院校優秀教材，先後獲國防科技大學教學優秀二等獎2次，校教學成果一、二等獎各1次；所從事的研究工作受到國內外同行的關注，1995年、1997年、2002年曾三次應邀到香港理工大學從事訪問研究，先後在國內外有影響的刊物上發表研究論文80餘篇，其中16篇進入SCI檢索、20餘篇進入EI檢索。

祝恩，1976年出生于湖南益陽，2005年6月畢業于國防科技大學計算科學與技術專業，獲博士學位，現為國防科技大學副教授。2006年起從事數據結構與算法、計算機圖形學、人工智能、模式識別等課程的教學工作。主要研究領域為模式識別、圖像分析、生物認證等。在國際國內刊物和會議上發表學術論文90餘篇。博士學位論文評為全國百篇優秀博士學位論文。是中國計算機學會理論計算機科學專業委員會委員、模式識別與人工智能專業委員會委員。

《普通高等教育"十一五"國家級規劃教材?計算機系列教材:數據結構與算法》結構合理，內容豐富，算法描述清晰，用C語言編寫的算法代碼都已調試通過，便于自學，可作為高等院校計算機專業、軍事院校的基礎合訓專業和其他相關專業的教材和參考書，也可供從事計算機軟件開發的科技下作者參考。

第1章 數據結構概述
1.1 基本概念
1.1.1 數據、數據元素、數據對象
1.1.2 數據結構
1.2 數據結構的分類
1.3 數據類型
1.3.1 基本類型、組合類型
1.3.2 抽象數據類型
1.4 算法和算法分析
1.4.1 算法概念
1.4.2 算法分析
習題

第2章 向量、棧和隊列
2.1 線性表
2.1.1 線性表的抽象數據類型
2.1.2 線性表的結構表示
2.2 向量
2.2.1 向量的抽象數據類型
2.2.2 向量的插入和刪除
2.2.3 向量的應用
2.3 棧
2.3.1 棧的抽象數據類型及其實現
2.3.2 棧的應用
2.4 遞歸效率分析
2.4.1 遞歸方程求解
2.4.2 生成函數求解遞歸方程
2.4.3 特徵方程求解遞歸方程
2.4.4 遞歸樹方法
2.5 隊列
2.5.1 隊列的抽象數據類型及其實現
2.5.2 隊列的應用——模擬銀行活動
習題

第3章 鏈表
3.1 單鏈表
3.1.1 基本概念
3.1.2 單鏈表結點結構
3.1.3 單鏈表結構
3.1.4 棧的單鏈表實現
3.1.5 隊列的單鏈表實現
3.1.6 單鏈表的應用舉例
3.2 循環鏈表
3.3 雙鏈表
習題

第4章 串
4.1 基本概念
4.2 串的存儲
4.3 串結構和串的運算
4.4 模式匹配
4.4.1 樸素的模式匹配算法
4.4.2 KMP匹配算法
4.4.3 BM匹配算法
習題

第5章 排序
5.1 基本概念
5.2 插入排序
5.2.1 直接插入排序
5.2.2 折半插入排序
……
第6章 查找
第7章 樹和二叉樹
第8章 樹狀結構的應用
第9章 圖
第10章 算法設計與分析
圖
算法
關鍵字索引
參考文獻

第6章 查找
查找是數據處理領域最常用的一種重要運算，也稱為檢索。查找的對象可以是線性表，也可以是復雜的樹形結構和文件結構。本章主要討論基于線性表的查找。
6.1基本概念
所謂查找就是在給定的數據結構中搜索滿足某種條件的結點。最常見的查找是給出一個值，在數據結構中找出關鍵碼等于指定值的結點。例如，在學生成績表中，查找指定學號的學生成績，學號是學生成績表的關鍵碼，因為每個學生都有唯一的學號。查找的結果有兩種情況，第一種情況是學生成績表中有相應學號的學生成績，自然可以查找到該學生的成績，稱為“查找成功”；第二種情況是學生成績表中沒有相應學號的學生成績，也就不可能查找對應的成績，稱為“查找失敗”。
除了基于關鍵字的查找以外，還可能按其他屬性值進行查找。例如，可能需要查找學生成績表中英語成績為95分的學生。顯然，查找的結果有多種，可能沒有任何一個學生的成績為95分，可能有一個學生的成績為98分，也可能有多個學生的成績為95分。對于有多個滿足條件的結點，有些查找只要求給出一個結點即可，例如為了確定所有學生中是否有英語成績為98分的學生；有些查找要求給出所有滿足條件的結點，例如要找出所有學生中有哪些學生的英語成績為98分。一般來說，基于關鍵碼的查找和基于屬性值的查找沒有太多的區別。對不同的存儲結構，可以采用的查找方法也不盡相同。同時，為了提高查找的速度，也常常針對不同場合采用不同的存儲結構。衡量一個查找算法的好壞的依據主要是查找過程中需要執行的平均比較次數，或者稱為平均查找長度，通常用E（n）來表示，其中n為線性表中的結點個數。此外，還要考慮算法所需要的附加存儲空間，以及算法本身的復雜性等。
為方便起見，在本章以后的討論中，均假設結點是等長的，查找都是基于關鍵碼的查找，且關鍵碼都是整數。這些假設是合理的，因為，如果結點是不等長，則可以討論結點的目錄表；如果關鍵碼不是整數，則可以在關鍵碼和整數之間建立一一對應的關系。
6.2順序查找
順序查找是一種最簡單也是效率比較低下的查找算法。順序查找時，將每個結點的關鍵碼和給定的待查的關鍵碼值進行比較，直到找出相等的結點或者找遍了所有結點。執行順序查找算法時，被查找的線性表可以是順序存儲的，也可以是鏈接存儲的，對結點沒有排序要求，因而順序查找具有非常好的適應性。