數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程 PDF格式下載

---