基本信息
圖書詳細信息：定價：39.5元
印次：1-1
裝幀：平裝
印刷日期：2012-8-14
圖書簡介
本書介紹了數據結構的基本概念、基本知識以及數據結構的套用。全書按照三部分編寫。第一部分是線性結構，包括線性表、棧與佇列、數組和特殊矩陣；第二部分是非線性結構，包括樹和二叉樹、圖；第三部分是數據處理技術，包括查找和排序，內容涵蓋了全國碩士研究生計算機綜合考試課程的數據結構知識。本書適合作為各類高等院校、高等職業技術學校與計算機相關的各類專業的數據結構與算法的教學用書，也是從事軟體設計人員一本難得的參考書。
前言
“數據結構”是計算機及相關專業的一門核心專業基礎課，在計算機課程的教學計畫中，它起著核心主導、承上啟下的作用，是培養學生程式設計能力的一門重要課程，也是計算機及相關專業的大學生應聘、考研的一門必需課程。長期以來，數據結構課程由於其抽象與動態性，使得在教學過程中始終存在“能聽懂，編不了程，不會套用”的現象。目前大部分學生在學數據結構之前，只學了一門程式設計語言。受學時的限制，數據結構需要的鍊表基礎，學生知之甚少，幾乎沒有編寫過有關鍊表的程式，因此造成了學生學習“數據結構”的困難。另外，目前國內外的很多數據結構教科書都是在抽象層次上闡述，它們在介紹典型數據結構之前，雖然也使用了一些實際問題作為切入點，但最後並沒有針對這些問題給出具體的解決方案，學生還是沒有弄清楚為什麼要學習這種結構，怎樣用這種結構來解決實際問題。
由於以上問題，我們認為數據結構的教學改革勢在必行。為此，我們對傳統的教學方法進行改革嘗試，以套用為主線，用案例驅動的教學方式，對每一種典型的數據結構教學採用以下方法：
(1) 引入實際問題。
(2) 分析實際問題中的數據和數據之間的關係，以及對數據需要做的常用操作。
(3) 抽象出實際問題涉及數據的邏輯結構、存儲結構和基本操作的設計與實現。
(4) 用所學的數據結構設計和實現解決這些實際問題的算法。
(5) 編碼、調試並分析運行結果。
上述案例驅動的教學模式，我們已經實踐了4年，取得了可喜的成績。我們邊教學邊總結，編寫了這本以案例驅動為主導，以解決實際問題為主線，以激發學生學習熱情為目標的教材，目的是使得原本難教難學的課程變得生動形象，更貼近實際，從而切實提高學生的程式設計能力。
此外，本教材還具有以下特點：
(1) 加強對基本操作實現的函式形參的分析。每個基本操作都配以示意圖，顯示存放在記憶體中的數據對象在操作完成前後的變化，分析操作的對象，需要的輸入和輸出，以及操作是否引起數據對象的變化，幫助讀者熟練掌握基本操作的設計與實現。新編數據結構及算法教程前言 (2) 數據結構中的很多算法涉及遞歸操作，初學者很難理解遞歸算法的執行過程，為此我們對較難理解的遞歸算法，配以圖表，揭示每一步的變化，將抽象的想像變為可以看到的具體過程，提升讀者對遞歸算法的設計能力。
(3) 對複雜的算法，我們用實際數據，採用圖表結合的方式，將存儲結構的變化和邏輯結構的變化同步展現，加強讀者對算法的理解，使讀者進一步掌握複雜算法的設計與實現。
(4) 各章內容均與授課對象進行過多次交流，廣泛聽取學生的意見，及時進行內容的更新和修改。
全書共8章，由林碧英老師統一編排、審核。第1章、第7章和第8章由石敏老師編寫；第2章和第3章由焦潤海老師編寫；第4章、第5章和第6章由林碧英老師編寫。各章的習題由蘇辰雋、莫瑞芳整理。
我們只是在案例教學做了一些嘗試，在教材的編寫中可能還有很多不盡人意的地方，懇請廣大讀者多提寶貴意見。
編寫組
2012年8月於北京
目錄
第1章 緒論 /?11.1 數據結構的起源與發展1
1.2 基本概念和術語2
1.3 理解數據結構3
1.4 數據的邏輯結構和存儲結構4
1.4.1 邏輯結構5
1.4.2 存儲結構6
1.5 抽象數據類型8
1.5.1 數據類型8
1.5.2 抽象數據類型8
1.6 算法分析與評價11
1.6.1 數據結構與算法的關係11
1.6.2 算法的定義11
1.6.3 算法的5大特性11
1.6.4 算法設計的要求12
1.6.5 算法效率分析13
1.6.6 算法的時間複雜度14
1.6.7 算法存儲空間需求16
1.7 本章小結17
1.8 習題17
第2章 線性表 /?20
2.1 問題的提出20
2.1.1 問題中的數據分析20
2.1.2 問題中的功能分析21
2.1.3 問題中的數據結構22
2.2 線性表22
2.2.1 線性表的定義22
2.2.2 線性表的存儲結構和基本操作的實現24
2.2.3 線性表的兩種存儲結構的區別47新編數據結構及算法教程目錄 2.3 案例實現48
2.3.1 基於順序表的新生成績管理系統48
2.3.2 基於單向鍊表的新生成績管理系統52
2.4 其他形式的鍊表54
2.4.1 單向循環鍊表54
2.4.2 雙向循環鍊表57
2.5 線性表的套用60
2.5.1 兩個線性表的合併60
2.5.2 一元多項式的套用63
2.6 本章小結69
2.7 習題與實驗70
第3章 棧與佇列 /?74
3.1 問題的提出74
3.1.1 問題中的數據分析74
3.1.2 問題中的功能分析74
3.1.3 問題中的數據結構75
3.2 棧76
3.2.1 棧的定義76
3.2.2 棧的存儲結構和基本操作的實現77
3.2.3 棧的兩種存儲結構的區別87
3.2.4 案例實現: 基於棧的括弧匹配87
3.3 棧的套用89
3.3.1 表達式求值89
3.3.2 棧與遞歸94
3.4 佇列103
3.4.1 佇列的定義103
3.4.2 佇列的存儲結構和基本操作的實現105
3.4.3 佇列的兩種存儲結構的區別116
3.4.4 案例實現: 基於佇列的醫院掛號模擬系統116
3.5 佇列的套用120
3.6 共用棧和雙佇列124
3.6.1 共用棧124
3.6.2 雙端佇列126
3.7 本章小結127
3.8 習題與實驗127
第4章 數組和特殊矩陣 /?133
4.1 多維數組133
4.1.1 數組的邏輯結構133
4.1.2 數組的記憶體映像133
4.2 特殊矩陣的壓縮存儲136
4.2.1 對稱矩陣136
4.2.2 三角矩陣138
4.2.3 帶狀矩陣139
4.3 稀疏矩陣140
4.3.1 稀疏矩陣的三元組表存儲140
4.3.2 稀疏矩陣的十字鍊表存儲146
4.4 本章小結152
4.5 習題152
第5章 樹和二叉樹 /?155
5.1 問題的提出155
5.1.1 問題中的數據分析155
5.1.2 問題中的功能分析156
5.1.3 問題中的數據結構156
5.2 樹的定義和基本術語156
5.2.1 樹的遞歸定義156
5.2.2 樹的基本術語156
5.2.3 樹的表示158
5.2.4 樹的抽象數據類型描述159
5.3 二叉樹159
5.3.1 二叉樹的定義159
5.3.2 二叉樹的性質161
5.3.3 二叉樹的抽象數據類型162
5.3.4 二叉樹的存儲結構163
5.3.5 二叉樹的遍歷及其套用166
5.3.6 案例實現： 基於表達式二叉樹的動態表達式計算192
5.4 線索二叉樹192
5.4.1 線索二叉樹的定義193
5.4.2 線索二叉樹的基本操作實現194
5.4.3 基於中序線索二叉樹的遍歷算法200
5.5 樹、森林與二叉樹的轉換及其套用203
5.5.1 樹、森林與二叉樹的轉換203
5.5.2 樹的存儲結構204
5.5.3 樹和森林的遍歷209
5.5.4 樹的簡單套用210
5.5.5 案例實現： 基於樹結構的行政機構管理217
5.6 哈夫曼樹及其套用220
5.6.1 最優二叉樹--哈夫曼樹220
5.6.2 哈夫曼樹及哈夫曼編碼的構建算法224
5.7 本章小結229
5.8 習題與實驗229
第6章 圖 /?234
6.1 問題的提出234
6.1.1 問題中的數據分析235
6.1.2 問題中的功能分析235
6.1.3 問題中的數據結構235
6.2 圖的定義和基本術語235
6.2.1 圖的定義235
6.2.2 圖的基本術語235
6.2.3 圖的分類與連通性237
6.2.4 圖的抽象數據類型定義238
6.3 圖的存儲結構239
6.3.1 圖的鄰接矩陣表示240
6.3.2 圖的鄰接表表示243
6.3.3 有向圖的十字鍊表表示246
6.3.4 無向圖的鄰接多重表表示247
6.4 圖的遍歷249
6.4.1 連通圖的深度優先搜尋(Depth-First Search)249
6.4.2 連通圖的廣度優先搜尋(Breadth-First Search)253
6.4.3 非連通圖的深度(廣度）優先遍歷255
6.4.4 圖的遍歷算法套用255
6.5 圖的連通性261
6.5.1 無向圖的連通分量和生成樹261
6.5.2 最小生成樹及套用261
6.6 最短路徑272
6.6.1 求從某個源點到其餘各點的最短路徑272
6.6.2 每一對頂點之間的最短路徑278
6.7 有向無環圖及其套用283
6.7.1 拓撲排序284
6.7.2 關鍵路徑287
6.7.3 案例實現： 教學計畫編排系統290
6.7.4 案例實現： 基於有向無環圖的表達式計算295
6.8 本章小結300
6.9 習題與實驗301
第7章 查找 /?305
7.1 問題的提出305
7.2 基本概念與描述306
7.2.1 查找的基本概念306
7.2.2 性能分析307
7.2.3 內部查找和外部查找308
7.2.4 C語言描述308
7.3 線性表查找308
7.3.1 順序查找309
7.3.2 二分查找310
7.3.3 分塊查找314
7.3.4 案例實現： 基於順序查找的學生信息表查詢316
7.4 樹表查找320
7.4.1 二叉排序樹320
7.4.2 平衡二叉樹328
7.4.3 B-樹和B+樹344
7.4.4 案例實現： 基於二叉排序樹的學生信息管理352
7.5 哈希表357
7.5.1 哈希表概念357
7.5.2 常用的哈希函式358
7.5.3 解決衝突的方法359
7.5.4 哈希表的查找及其性能分析362
7.6 本章小結364
7.7 習題與實驗365
第8章 排序 /?369
8.1 問題的提出369
8.2 基本概念369
8.3 插入排序371
8.3.1 直接插入排序371
8.3.2 折半插入排序373
8.3.3 希爾排序374
8.4 交換排序375
8.4.1 冒泡排序375
8.4.2 快速排序377
8.5 選擇排序379
8.5.1 簡單選擇排序380
8.5.2 堆排序381
8.6 歸併排序384
8.7 基數排序386
8.7.1 多關鍵字排序386
8.7.2 鏈式基數排序387
8.8 案例實現： 學生基本信息表的排序390
8.9 各種內部排序方法的比較397
8.10 本章小結398
8.11 習題399
參考文獻 /?402
