數(shù)據(jù)結構及應用算法教程

內(nèi)容概要

　　本書從數(shù)據(jù)類型的角度，分別討論了四大類型的數(shù)據(jù)結構的邏輯特性、存儲表示及其應用。此外，還專辟一章，以若干實例闡述以抽象數(shù)據(jù)類型為中心的程序設計方法。書中每一章后都配有適量的習題，以供讀者復習提高之用。第1～9章還專門設有“解題指導與示例”一節(jié)內(nèi)容，不僅給出答案，對大部分題目提供了詳盡的解答注釋；其中的一些算法題還給出了多種解法。書中主要算法和最后一章的實例中的全部程序代碼均收錄在與本書配套的光盤之中。
　　本書內(nèi)容豐富，概念闡述細致清楚，可作為高等院校計算機類專業(yè)和信息類相關專業(yè)“數(shù)據(jù)結構”或“軟件基礎”課程的本科教材。另外，對于準備參加計算機類研究生專業(yè)課統(tǒng)考的考生，本書也可作為應試的解題指導。

書籍目錄

第1章 緒論
1.1 數(shù)據(jù)結構討論的范疇
1.2 與數(shù)據(jù)結構相關的概念
1.2.1 基本概念和術語
1.2.2 數(shù)據(jù)結構(data structures)
1.2.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型
1.3 算法及其描述和分析
1.3.1 算法
1.3.2 算法的描述
1.3.3 算法效率的衡量方法和準則
1.3.4 算法的存儲空間需求
解題指導與示例
習題
第2章 線性表
2.1 線性表的類型定義
2.1.1 線性表的定義
2.1.2 線性表的基本操作
2.2 線性表的順序表示和實現(xiàn)
2.2.1 順序表--線性表的順序存儲表示
2.2.2 順序表中基本操作的實現(xiàn)
2.2.3 順序表其他算法舉例
2.3 線性表的鏈式表示和實現(xiàn)
2.3.1 單鏈表和指針
2.3.2 單鏈表的基本操作
2.3.3 單鏈表的其他操作舉例
2.3.4 循環(huán)鏈表
2.3.5 雙向鏈表
2.4 有序表
2.5 順序表和鏈表的綜合比較
解題指導與示例
習題
第3章 排序
3.1 排序的基本概念
3.2 簡單排序方法
3.2.1 插入排序
3.2.2 起泡排序
3.3 先進排序方法
3.3.1 快速排序
3.3.2 歸并排序
3.3.3 堆排序
3.4 基數(shù)排序
3.5 各種排序方法的綜合比較
解題指導與示例
習題
第4章 棧和隊列
4.1 棧
4.1.1 棧的結構特點和操作
4.1.2 棧的表示和操作的實現(xiàn)
4.2 棧的應用舉例
4.3 隊列
4.3.1 隊列的結構特點和操作
4.3.2 隊列的表示和操作的實現(xiàn)
4.4 隊列應用舉例
解題指導與示例
習題
第5章 串和數(shù)組
5.1 串的定義和操作
5.2 串的表示和實現(xiàn)
5.2.1 定長順序存儲表示
5.2.2 堆分配存儲表示
5.2.3 塊鏈存儲表示
5.3 正文模式匹配
5.4 正文編輯--串操作應用舉例
5.5 數(shù)組
5.5.1 數(shù)組的定義和操作
5.5.2 數(shù)組的順序表示和實現(xiàn)
5.5.3 數(shù)組的應用
5.6 矩陣的壓縮存儲
5.6.1 特殊形狀矩陣的存儲表示
5.6.2 隨機稀疏矩陣的存儲壓縮
解題指導與示例
習題
第6章 二叉樹和樹
6.1 二叉樹
6.1.1 二叉樹的定義和基本術語
6.1.2 二叉樹的幾個基本性質
6.1.3 二叉樹的存儲結構
6.2 二叉樹遍歷
6.2.1 問題的提出
6.2.2 遍歷算法描述
6.2.3 二叉樹遍歷應用舉例
6.2.4 線索二叉樹
6.3 樹和森林
6.3.1 樹和森林的定義
6.3.2 樹和森林的存儲結構
6.3.3 樹和森林的遍歷
6.4 樹的應用
6.4.1 堆排序的實現(xiàn)
6.4.2 二叉排序樹
6.4.3 赫夫曼樹及其應用
解題指導與示例
習題
第7章 圖和廣義表
7.1 圖的定義和術語
7.2 圖的存儲結構
7.2.1 圖的數(shù)組（鄰接矩陣）存儲表示
7.2.2 圖的鄰接表存儲表示
7.3 圖的遍歷
7.3.1 深度優(yōu)先搜索遍歷圖
7.3.2 廣度優(yōu)先搜索遍歷圖
7.4 連通網(wǎng)的最小生成樹
7.5 單源最短路徑
7.6 拓撲排序
7.7 關鍵路徑
7.8 廣義表
7.8.1 廣義表的定義
7.8.2 廣義表的存儲結構
7.8.3 廣義表的遍歷
解題指導與示例
習題
第8章 查找表
8.1 靜態(tài)查找表
8.1.1 順序查找
8.1.2 折半查找
8.1.3 分塊查找
8.2 動態(tài)查找表
8.2.1 二叉查找樹
8.2.2 鍵樹
8.3 哈希表及其查找
8.3.1 什么是哈希表
8.3.2 構造哈希函數(shù)的幾種方法
8.3.3 處理沖突的方法和建表示例
8.3.4 哈希表的查找及其性能分析
8.3.5 哈希表的應用舉例
解題指導與示例
習題
第9章 文件
9.1 基本概念
9.1.1 外存儲器簡介
9.1.2 有關文件的基本概念
9.2 順序文件
9.2.1 存儲在順序存儲器上的文件
9.2.2 存儲在直接存儲器上的文件
9.3 索引文件
9.3.1 B樹
9.3.2 B?+ 樹和索引順序文件
9.4 哈希文件
9.4.1 文件組織方式
9.4.2 文件的操作
9.5 多關鍵碼文件
9.5.1 倒排文件
9.5.2 索引鏈接文件
解題指導與示例
習題
第10章 數(shù)據(jù)結構程序設計示例
10.1 抽象數(shù)據(jù)類型
10.2 從問題到程序的求解過程
10.2.1 建立數(shù)據(jù)結構模型設計抽象數(shù)據(jù)類型
10.2.2 算法設計
10.2.3 實現(xiàn)抽象數(shù)據(jù)類型
10.2.4 編制程序代碼并進行靜態(tài)測試和動態(tài)調試
10.3 程序的規(guī)范說明
10.4 應用示例分析
10.4.1 含并、交和差運算的集合類型
10.4.2 最佳任務分配方案求解
10.4.3 排隊問題的系統(tǒng)仿真
10.4.4 十進制四則運算計算器
10.4.5 自行車零部件庫的庫存模型
10.4.6 教務課程計劃的輔助制定
10.4.7 一個小型全文檢索模型
10.4.8 汽車牌照的快速查找
實習題
實習一 鏈表的維護與文件形式的保存
實習二 用回溯法求解“穩(wěn)定婚配”問題
實習三 以隊列實現(xiàn)的仿真技術預測理發(fā)館的經(jīng)營狀況
實習四 利用樹形結構的搜索算法模擬因特網(wǎng)域名的查詢
實習五 管道鋪設施工的最佳方案選擇
實習六 使用哈希表技術判別兩個源程序的相似性
附錄 算法一覽表
參考文獻

章節(jié)摘錄

版權頁：插圖：1.2.3數(shù)據(jù)類型和抽象數(shù)據(jù)類型與數(shù)據(jù)結構密切相關的是定義在數(shù)據(jù)結構之上的一組操作，操作的種類和數(shù)目不同，即使邏輯結構相同，這個數(shù)據(jù)結構能起的作用也不同。一個數(shù)據(jù)結構加上定義在這個數(shù)據(jù)結構上的一組操作，即構成一個抽象數(shù)據(jù)類型的定義。抽象數(shù)據(jù)類型的概念其實質和程序設計語言中的數(shù)據(jù)類型概念相同。在用程序設計語言編寫的程序中，必須對程序中出現(xiàn)的每個變量、常量或表達式明確說明它們所屬的數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了在程序執(zhí)行期間，變量或表達式所有可能取值的范圍，以及在這些值上允許進行的操作。即數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱。例如，C語言中的整型變量，其值集為某個區(qū)間上的整數(shù)（區(qū)間大小依賴于不同的機器和軟件系統(tǒng)），定義在其上的操作為加、減、乘、除和取模等算術運算。各種高級程序設計語言中都擁有的“整數(shù)”類型即為一個抽象數(shù)據(jù)類型，盡管它們在不同處理器上實現(xiàn)的方法可以不同，但由于它們的數(shù)學特性相同，在用戶看來都是相同的。因此“抽象”的意義在于強調數(shù)據(jù)類型的數(shù)學特性。另一方面，抽象數(shù)據(jù)類型的范疇更廣，它不再局限于現(xiàn)有程序設計語言中已實現(xiàn)的數(shù)據(jù)類型（通常稱為固有數(shù)據(jù)類型），還包括用戶在設計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。為了提高軟件的復用率，在近代程序設計方法學中指出，一個軟件系統(tǒng)的框架應建立在數(shù)據(jù)之上，而不是建立在操作之上（后者是傳統(tǒng)的軟件設計方法所為）。

編輯推薦

《數(shù)據(jù)結構及應用算法教程(修訂版)》：概念講述兼顧精準和通俗，滿足學習和應試備考的廣大讀者群需求。強調基本內(nèi)容與知識運用的銜接，通過豐富的解題實例鞏固學習效果。以靜態(tài)跟蹤的詳盡圖示剖析算法執(zhí)行的過程，透視數(shù)據(jù)結構的運作機理。提供常見題型的解題步驟和思考的脈絡，利于培育舉一反三的能力。披露數(shù)據(jù)結構算法的寫作秘密，評述并比較各種解法的優(yōu)勢及特色。匯集了最常用數(shù)據(jù)結構應用算法實例的源代碼，可作為開發(fā)的借鑒資源。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    數(shù)據(jù)結構及應用算法教程 PDF格式下載

---