數(shù)據(jù)結(jié)構(gòu)與算法 第4版
定 價(jià):59 元
叢書名:“十三五”普通高等教育規(guī)劃教材
- 作者:羅文劼
- 出版時(shí)間:2019/1/1
- ISBN:9787111614067
- 出 版 社:機(jī)械工業(yè)出版社
- 中圖法分類:TP311.12
- 頁碼:
- 紙張:膠版紙
- 版次:
- 開本:16開
《數(shù)據(jù)結(jié)構(gòu)與算法 第4版》共包括8章內(nèi)容,詳細(xì)講述了線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)中的數(shù)據(jù)表示及數(shù)據(jù)處理的方法,并對查找和排序兩種重要的數(shù)據(jù)處理技術(shù)做了細(xì)致的探討!稊(shù)據(jù)結(jié)構(gòu)與算法 第4版》對每一類數(shù)據(jù)結(jié)構(gòu)的分析均按照邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)基本運(yùn)算的實(shí)現(xiàn)時(shí)空性能分析典型應(yīng)用實(shí)例知識(shí)小結(jié)練習(xí)題實(shí)驗(yàn)題的順序進(jìn)行講解,算法全部采用C語言描述,很容易轉(zhuǎn)換成程序!稊(shù)據(jù)結(jié)構(gòu)與算法 第4版》語言敘述通俗易懂、由淺入深,算法可讀性好、應(yīng)用性強(qiáng)!稊(shù)據(jù)結(jié)構(gòu)與算法 第4版》不僅配有算法設(shè)計(jì)的應(yīng)用實(shí)例和大量的練習(xí)題,還針對重點(diǎn)、難點(diǎn)問題配有授課視頻講解,掃描二維碼即可觀看。
配套資源豐富:教學(xué)課件、習(xí)題解答、附錄、57個(gè)知識(shí)點(diǎn)視頻
新型態(tài)立體化教材,有重點(diǎn)難點(diǎn)的視頻講解;
經(jīng)過4次改版,教材結(jié)構(gòu)和內(nèi)容更加穩(wěn)定,更加適用于教育教學(xué)。
前 言數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)及相關(guān)專業(yè)的一門重要的專業(yè)基礎(chǔ)課,是介于數(shù)學(xué)計(jì)算機(jī)硬件和計(jì)算機(jī)軟件之間的一門計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域的核心課程,同時(shí)數(shù)據(jù)結(jié)構(gòu)技術(shù)也被廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。該課程主要介紹如何合理地組織和表示數(shù)據(jù)、如何有效地存儲(chǔ)和處理數(shù)據(jù)、如何正確地設(shè)計(jì)算法以及對算法的優(yōu)劣進(jìn)行分析和評價(jià)。
本書結(jié)合編者多年教學(xué)經(jīng)驗(yàn),在《數(shù)據(jù)結(jié)構(gòu)與算法》(第 3 版)的基礎(chǔ)上進(jìn)行了修訂,定位于應(yīng)用研究型本科層次,堅(jiān)持以面向應(yīng)用,易教易學(xué)為目標(biāo),數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)簡單明了,語言敘述通俗易懂,講解由淺入深,并在以下幾方面有所改進(jìn)。
1)增加部分章節(jié)的內(nèi)容。為加強(qiáng)應(yīng)用型本科教學(xué)的深入,注重培養(yǎng)學(xué)生靈活運(yùn)用數(shù)據(jù)結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)解決實(shí)際問題的能力,適應(yīng)學(xué)生參加程序能力相關(guān)考試和競賽以及考研的需要,在第5章加入Floyd算法的詳細(xì)描述與舉例。
2)對重點(diǎn)、難點(diǎn)內(nèi)容提供對應(yīng)的視頻講解,方便學(xué)習(xí)者在課下進(jìn)行有針對地學(xué)習(xí),也方便教學(xué)組織翻轉(zhuǎn)教學(xué),讓學(xué)生提前預(yù)習(xí)。
3)豐富了每章知識(shí)點(diǎn)小結(jié)的內(nèi)容。不僅描述了知識(shí)點(diǎn)的內(nèi)容和學(xué)習(xí)要求,還指出部分知識(shí)點(diǎn)在學(xué)習(xí)和運(yùn)用中容易誤解和使用錯(cuò)誤的地方。
4)豐富了配套練習(xí)。補(bǔ)充和修改了每章的課后練習(xí)題和實(shí)驗(yàn)題,尤其是增加了一些引導(dǎo)學(xué)生思考的簡答題和靈活運(yùn)用相關(guān)知識(shí)點(diǎn)解決實(shí)際問題的算法設(shè)計(jì)題。
5)補(bǔ)充了配套的教案資源,方便教學(xué)組織和翻轉(zhuǎn)課堂的使用。針對翻轉(zhuǎn)課堂對教學(xué)過程課前、課中和課后的要求,在提供的配套教案中,選擇了部分適合翻轉(zhuǎn)課堂的內(nèi)容,給出適合翻轉(zhuǎn)課堂教學(xué)使用的教案。
本書由羅文劼教授組織編定并負(fù)責(zé)統(tǒng)稿。其中第1、2、3、4、8章由羅文劼編寫,第5章由苗秀芬編寫,第6、7章由史青宣編寫。在本書的編寫過程中,張小莉、王苗、石強(qiáng)、和張瑜等多位從事數(shù)據(jù)結(jié)構(gòu)教學(xué)的老師對本書的編寫提出了寶貴的意見和建議,河北大學(xué)教務(wù)處也為本書的改版給予支持,在此一并表示感謝。
由于編者水平有限,書中難免存在疏漏之處,懇請各位讀者批評指正。
編 者
前言
第1章 緒論1
1.1 引言1
1.1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1
1.1.2 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容4
1.2 數(shù)據(jù)結(jié)構(gòu)的概念5
1.2.1 基本概念和術(shù)語5
1.2.2 抽象數(shù)據(jù)類型7
1.3 算法8
1.3.1 算法及其特征8
1.3.2 算法的描述9
1.3.3 算法的性能分析9
1.4 遞歸12
1.4.1 遞歸的概念12
1.4.2 遞歸調(diào)用的實(shí)現(xiàn)原理13
1.4.3 遞歸轉(zhuǎn)換為非遞歸15
1.4.4 遞歸應(yīng)用舉例16
1.5 本章知識(shí)點(diǎn)小結(jié)17
練習(xí)題18
實(shí)驗(yàn)題20
題目1 比較算法復(fù)雜性描述函數(shù)的
增長20
題目2 全排列的遞歸實(shí)現(xiàn)21
題目3 皇后問題21
第2章 基本線性結(jié)構(gòu)22
2.1 線性表22
2.1.1 問題提出22
2.1.2 線性表的定義23
2.1.3 線性表的基本運(yùn)算23
2.2 線性表的順序存儲(chǔ)24
2.2.1 順序表24
2.2.2 順序表上基本運(yùn)算的實(shí)現(xiàn)26
2.2.3 順序表應(yīng)用舉例29
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)31
2.3.1 單鏈表31
2.3.2 單鏈表上基本運(yùn)算的實(shí)現(xiàn)33
2.3.3 循環(huán)鏈表39
2.3.4 雙向鏈表39
2.3.5 鏈表應(yīng)用舉例41
2.4 順序表和鏈表的比較44
2.5 堆棧45
2.5.1 堆棧的定義45
2.5.2 堆棧的存儲(chǔ)及基本運(yùn)算的
實(shí)現(xiàn)46
2.5.3 堆棧應(yīng)用舉例49
2.6 隊(duì)列58
2.6.1 隊(duì)列的定義58
2.6.2 隊(duì)列的存儲(chǔ)及基本運(yùn)算的
實(shí)現(xiàn)59
2.6.3 隊(duì)列應(yīng)用舉例64
2.7 本章知識(shí)點(diǎn)小結(jié)67
練習(xí)題68
實(shí)驗(yàn)題72
題目1 Josephus環(huán)問題72
題目2 模擬停車場管理73
第3章 線性結(jié)構(gòu)的擴(kuò)展75
3.1 字符串75
3.1.1 字符串的基本概念75
3.1.2 順序串76
3.1.3 模式匹配79
3.2 多維數(shù)組與特殊矩陣84
3.2.1 多維數(shù)組84
3.2.2 特殊矩陣86
3.2.3 稀疏矩陣90
3.3 廣義表99
3.3.1 廣義表的基本概念99
3.3.2 廣義表的存儲(chǔ)101
3.4 本章知識(shí)點(diǎn)小結(jié)103
練習(xí)題104
實(shí)驗(yàn)題107
題目 格式化文本107
第4章 樹結(jié)構(gòu)110
4.1 引言110
4.1.1 問題提出110
4.1.2 相關(guān)概念111
4.2 二叉樹113
4.2.1 二叉樹的概念113
4.2.2 二叉樹的主要性質(zhì)114
4.2.3 二叉樹的存儲(chǔ)116
4.2.4 二叉樹基本運(yùn)算的實(shí)現(xiàn)119
4.3 二叉樹的遍歷121
4.3.1 遞歸方法實(shí)現(xiàn)二叉樹的遍歷121
4.3.2 非遞歸方法實(shí)現(xiàn)二叉樹的遍歷123
4.3.3 隊(duì)列方法實(shí)現(xiàn)二叉樹的層次遍歷126
4.4 二叉樹遍歷的應(yīng)用127
4.4.1 構(gòu)造二叉樹的二叉鏈表存儲(chǔ)127
4.4.2 在二叉樹中查找值為x的數(shù)據(jù)元素128
4.4.3 統(tǒng)計(jì)給定二叉樹中葉子結(jié)點(diǎn)的數(shù)目128
4.4.4 由遍歷序列恢復(fù)二叉樹129
4.5 線索二叉樹130
4.5.1 線索二叉樹的定義及結(jié)構(gòu)130
4.5.2 線索二叉樹的構(gòu)建132
4.5.3 線索二叉樹的遍歷133
4.6 最優(yōu)二叉樹136
4.6.1 最優(yōu)二叉樹的概念136
4.6.2 最優(yōu)二叉樹的構(gòu)造138
4.6.3 最優(yōu)二叉樹的應(yīng)用哈夫曼編碼141
4.7 樹和森林143
4.7.1 樹的基本操作與表示143
4.7.2 樹的存儲(chǔ)144
4.7.3 樹和森林與二叉樹之間的轉(zhuǎn)換148
4.7.4 樹或森林的遍歷150
4.7.5 樹的應(yīng)用151
4.8 本章知識(shí)點(diǎn)小結(jié)153
練習(xí)題155
實(shí)驗(yàn)題159
題目 哈夫曼編碼/譯碼器159
第5章 圖結(jié)構(gòu)161
5.1 引言161
5.1.1 問題提出161
5.1.2 相關(guān)概念162
5.1.3 圖的基本操作165
5.2 圖的存儲(chǔ)方法165
5.2.1 鄰接矩陣165
5.2.2 鄰接表167
*5.2.3 十字鏈表169
*5.2.4 鄰接多重表171
5.3 圖的遍歷173
5.3.1 深度優(yōu)先搜索173
5.3.2 廣度優(yōu)先搜索175
5.3.3 應(yīng)用圖的遍歷判定圖的連通性177
5.4 生成樹與最小生成樹178
5.4.1 生成樹和生成森林178
5.4.2 最小生成樹179
5.4.3 構(gòu)造最小生成樹的Prim
算法180
5.4.4 構(gòu)造最小生成樹的Kruskal
算法183
5.5 最短路徑186
5.5.1 從一個(gè)源點(diǎn)到其他各點(diǎn)的最短路徑186
*5.5.2 每一對頂點(diǎn)之間的最短路徑弗洛伊德算法189
5.6 拓?fù)渑判?93
5.6.1 有向無環(huán)圖的概念193
5.6.2 AOV網(wǎng)與拓?fù)渑判?94
5.7 關(guān)鍵路徑198
5.7.1 AOE網(wǎng)與關(guān)鍵路徑198
5.7.2 關(guān)鍵路徑的確定199
5.8 本章知識(shí)點(diǎn)小結(jié)203
練習(xí)題206
實(shí)驗(yàn)題208
題目 校園導(dǎo)游程序208
第6章 查找210
6.1 引言210
6.1.1 問題提出210
6.1.2 相關(guān)概念210
6.2 線性表查找212
6.2.1 順序查找212
6.2.2 在順序存儲(chǔ)的有序表上查找214
6.3 樹表查找218
6.3.1 二叉排序樹218
6.3.2 平衡二叉樹224
*6.3.3 B樹和B 樹230
6.4 散列表查找236
6.4.1 散列表236
6.4.2 常用的散列函數(shù)237
6.4.3 處理沖突的方法及散列表的構(gòu)造238
6.4.4 散列表上的查找242
6.4.5 散列表上的插入244
6.4.6 散列表上的刪除245
6.5 本章知識(shí)點(diǎn)小結(jié)245
練習(xí)題246
實(shí)驗(yàn)題249
題目1 職工信息檢索系統(tǒng)249
題目2 個(gè)人圖書管理系統(tǒng)250
第7章 排序252
7.1 引言252
7.1.1 問題提出252
7.1.2 相關(guān)概念252
7.2 插入排序254
7.2.1 直接插入排序254
7.2.2 折半插入排序256
7.2.3 希爾排序256
7.3 交換排序258
7.3.1 冒泡排序258
7.3.2 快速排序259
7.4 選擇排序261
7.4.1 簡單選擇排序261
7.4.2 樹型選擇排序262
7.4.3 堆排序263
7.5 歸并排序266
7.5.1 兩個(gè)有序表的合并266
7.5.2 二路歸并排序的迭代算法267
7.5.3 二路歸并排序的遞歸算法268
*7.6 基數(shù)排序268
7.6.1 多關(guān)鍵碼排序268
7.6.2 鏈?zhǔn)交鶖?shù)排序269
7.7 排序方法比較272
7.8 本章知識(shí)點(diǎn)小結(jié)274
練習(xí)題275
實(shí)驗(yàn)題278
題目 各種內(nèi)部排序的性能比較278
第8章 擴(kuò)展應(yīng)用舉例279
8.1 求最大子段和279
8.1.1 問題描述279
8.1.2 問題分析與解決279
8.2 表達(dá)式樹的構(gòu)造283
8.2.1 問題描述283
8.2.2 問題分析與解決283
8.3 由等價(jià)關(guān)系求劃分287
8.3.1 問題描述287
8.3.2 問題分析與解決287
8.4 本章知識(shí)點(diǎn)小結(jié)289
練習(xí)題290
實(shí)驗(yàn)題290
題目1 模擬銀行排隊(duì)辦理業(yè)務(wù)290
題目2 0-1背包問題291
附錄292
附錄A 實(shí)驗(yàn)要求292
實(shí)驗(yàn)題目294
附錄B 模擬試卷295
模擬試卷一295
模擬試卷二296
模擬試卷三299
模擬試卷四301
參考文獻(xiàn)304